Complementarity and Similarity in Complex Networks

Abstract

Networks are becoming ever more important in today's highly interconnected society, from telecommunication networks and social networks to power grids and the Internet. The field of Network Science seeks to uncover structure within the complex topologies of networks and the processes that govern their link formation. Many methods and models in the field are founded on link-formation principles that are driven by similarity, drawing inspiration from social network theory. In this dissertation, we discuss various network representations based on similarity, and we introduce and illustrate an alternative link formation principle that is based on complementarity.
The first part of this dissertation focuses on clustering the nodes of a network or community detection. Here, the nodes of a network are partitioned into several clusters and the objective is to precisely determine the cluster memberships based on only the network topology. Many clustering methods assume that the true number of clusters is known a priori. In Chapter 2, we investigate how exactly to find this number of clusters for a given graph. We discuss several modularity maximization and spectral clustering methods, and we outline how they can be used to find the number of clusters. We compare the performance of several different algorithms by evaluating these methods on benchmark graph models where the ground truth clusters are known.
In the second part, we explore network representations in the hyperbolic space. In Chapter 3, we extend the 2-dimensional random hyperbolic graph model to a hyperbolic space of arbitrary dimensionality. Our rescaling of the model parameters and variables casts the random hyperbolic graph model of any dimension to a unified mathematical framework, such that the degree distribution is invariant to the dimensionality of the space. We analyze the different connectivity regimes of the model and their limiting cases. In Chapter 4, we describe how hyperbolic graphs are built on a connection principle based on similarity, and we identify a class of real-world networks in which the links are driven by principles of complementarity rather than similarity. We propose a framework for embedding complementarity-driven networks into hyperbolic space and we describe the ensuing complementarity random hyperbolic graph model. In Chapter 5, we further investigate the topological properties of the complementarity random hyperbolic graph.
The third and final part of the dissertation centers on semantic networks, which describe semantic relations between words or concepts. In Chapter 6, we systematically analyze the topological properties of a large, multilingual dataset of semantic networks. Our investigation covers both universal and language-specific structural properties of these networks. We examine the roles that the connection principles of similarity and complementarity play in their link formation, and we discuss how a deeper understanding of these organizing principles benefits applications in natural language processing.