Abstract
Community detection and clustering are two closely related issues that have drawn much of the attention in network analysis. Due to the rapid growth of the scale of networked data, the efficiency and the scalability of community detection algorithms and clustering algorithms are taken more seriously. In this thesis, we provide several efficient methods to perform community detection and clustering that can deal with diverse and large-scale data. The thesis is organized into three parts. In the first part of this thesis, we address two major points: (i) a formal and precise definition of the graph clustering and community detection problem in directed networks, and (ii) algorithm design and evaluation of community detection algorithms in directed networks. Motivated by these, we develop a probabilistic framework for structural analysis and community detection in directed networks based on our previous work in undirected networks. By relaxing the assumption from symmetric bivariate distributions in our previous work to bivariate distributions that have the same marginal distributions in this thesis, we can still formally define various notions for structural analysis in directed networks, including centrality, relative centrality, community, and modularity. We also extend three commonly used community detection algorithms in undirected networks to directed networks: the hierarchical agglomerative algorithm, the partitional algorithm, and the fast unfolding algorithm. These are made possible by two modularity preserving and sparsity preserving transformations. In conjunction with the probabilistic framework, we show these three algorithms converge in a finite number of steps. In particular, we show that the partitional algorithm is a nearly-linear time algorithm for large sparse graphs. Moreover, the outputs of the hierarchical agglomerative algorithm and the fast unfolding algorithm are guaranteed to be communities. These three algorithms can also be extended to general bivariate distributions with some minor modifications. We also conduct various experiments by using two sampling methods in directed networks: (i) PageRank and (ii) random walks with self-loops and backward jumps. In the second part of this thesis, we first propose a new iterative algorithm, called the K-sets+ algorithm for clustering data points in a semi-metric space, where the distance measure does not necessarily satisfy the triangular inequality. We show that the K-sets+ algorithm converges in a finite number of iterations and it retains the same performance guarantee as the K-sets algorithm for clustering data points in a metric space. We then extend the applicability of the K-sets+ algorithm from data points in a semi-metric space to data points that only have a symmetric similarity measure. Such an extension leads to great reduction of computational complexity. In particular, for an n × n similarity matrix with m nonzero elements in the matrix, the computational complexity of the K-sets+ algorithm is O((Kn+m)I), where I is the number of iterations. The memory complexity to achieve that computational complexity is O(Kn+m). As such, both the computational complexity and the memory complexity are linear in n when the n × n similarity matrix is sparse, i.e., m=O(n). We also conduct various experiments to show the effectiveness of the K-sets+ algorithm by using a synthetic dataset from the stochastic block model and a real network from the WonderNetwork website. In the third part of this thesis, we detail the implementation of the fast unfolding algorithm that has a nearly-linear time complexity and a linear memory complexity. Since the time and the memory complexity depend heavily on the data structures, we introduce three essential data structures for the implementation of the nearly-linear time fast unfolding algorithm: (i) adjacency list, (ii) disjoin sets, and (iii) array set. The adjacency list is a commonly used memory-efficient data structure for storing sparse networks. The disjoint sets and array set are our newly invented data structure that can allow us to avoid using superlinear operations such as sorting and insertings in a hash (or binary) tree. We also do an experiment to test the efficiency and scalability of our implementation of the fast unfolding algorithm. With the data structures and techniques designed by us, our implementation is 3.6 times faster than the competitor, and can cope with networks with one billion edges.