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 linkformation 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 2dimensional 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 realworld networks in which the links are driven by principles of complementarity rather than similarity. We propose a framework for embedding complementaritydriven 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 languagespecific 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.
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 2dimensional 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 realworld networks in which the links are driven by principles of complementarity rather than similarity. We propose a framework for embedding complementaritydriven 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 languagespecific 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.
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Thesis sponsors  
Award date  16 Apr 2024 
Print ISBNs  9789463668453 
DOIs  
Publication status  Published  2024 
Funding
This work is part of NExTWORKx, a collaboration between TU Delft and KPN on future telecommunication networks.Keywords
 Complex networks
 Complementarity
 Similarity
 Hyperbolic geometry
 Network clustering