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.@en

We consider random hyperbolic graphs in hyperbolic spaces of any dimension d+1≥2. We present a rescaling of model parameters that casts the random hyperbolic graph model of any dimension to a unified mathematical framework, leaving the degree distribution invariant with respect to the dimension. Unlike the degree distribution, clustering does depend on the dimension, decreasing to 0 at d→∞. We analyze all of the other limiting regimes of the model, and we release a software package that generates random hyperbolic graphs and their limits in hyperbolic spaces of any dimension.

@en

Sequence data mining has become an increasingly popular research topic as the availability of data has grown rapidly over the past decades. Sequence clustering is a type of method within this field that is in high demand in the industry, but the sequence clustering problem is non-trivial and, as opposed to static cluster analysis, interpreting clusters of sequences is often difficult. Using Hidden Markov Models (HMMs), we propose the Discrete Bayesian HMM Clustering (DBHC) algorithm, an approach to clustering discrete sequences by extending a proven method for continuous sequences. The proposed algorithm is completely self-contained as it incorporates both the search for the number of clusters and the search for the number of hidden states in each cluster model in the parameter inference. We provide a working example and a simulation study to explain and showcase the capabilities of the DBHC algorithm. A case study illustrates how the hidden states in a mixture of HMMs can aid the interpretation task of a sequence cluster analysis. We conclude that the algorithm works well as it provides well-interpretable clusters for the considered application.

@en

Interpreting natural language is an increasingly important task in computer algorithms due to the growing availability of unstructured textual data. Natural Language Processing (NLP) applications rely on semantic networks for structured knowledge representation. The fundamental properties of semantic networks must be taken into account when designing NLP algorithms, yet they remain to be structurally investigated. We study the properties of semantic networks from ConceptNet, defined by 7 semantic relations from 11 different languages. We find that semantic networks have universal basic properties: they are sparse, highly clustered, and many exhibit power-law degree distributions. Our findings show that the majority of the considered networks are scale-free. Some networks exhibit language-specific properties determined by grammatical rules, for example networks from highly inflected languages, such as e.g. Latin, German, French and Spanish, show peaks in the degree distribution that deviate from a power law. We find that depending on the semantic relation type and the language, the link formation in semantic networks is guided by different principles. In some networks the connections are similarity-based, while in others the connections are more complementarity-based. Finally, we demonstrate how knowledge of similarity and complementarity in semantic networks can improve NLP algorithms in missing link inference.@en

Many clustering algorithms for complex networks depend on the choice for the number of clusters and it is often unclear how to make this choice. The number of eigenvalues located outside a circle in the spectrum of the non-backtracking matrix was conjectured to be an estimator of the number of clusters in a graph. We compare the estimate of the number of clusters obtained from the spectrum of the non-backtracking matrix with three estimators based on the concept of modularity and evaluate the methods on several benchmark graphs. We find that the non-backtracking method detects the number of clusters better than the modularity-based methods for the graphs in our simulation study, especially when the clusters have slightly different sizes. The estimates of the non-backtracking method are narrowly distributed around the true number of clusters for all benchmark graphs considered. Additionally, for graphs without a clustering structure, the non-backtracking method detects exactly one cluster, which is a convenient property of an estimator of the number of clusters. However, the lack of a well-defined concept of a cluster prevents sharp conclusions.

@en