Community detection in complex networks

Abstract

Complex networks such as social networks and biological networks represent complex systems in the real world. These networks usually consist of communities which are groups of nodes with dense connections among nodes in the same group and sparse connections between nodes in different groups. Identifying communities in complex networks is useful for many real-world applications. Numerous community detection approaches have been investigated over the past decades. Modularity is a well-known function to measure the quality of a network division into communities. The most popular detection approach is modularity optimization that identifes communities by finding the community division with highest modularity over all possible community divisions of the network. Current state-of-the-art algorithms for maximizing modularity perform well on networks of strong communities, which have more intra-community connections than inter-community connections. However, these algorithms tend to get trapped in a poor local maximum on networks with weak communities, which have more inter-community connections than intra-community connections. In the first part of this thesis, we develop a new algorithm for maximizing modularity in networks with weak communities. Our proposed algorithm extends the state-of-the-art algorithm LPAm+ by introducing a method to escape local maximum. Our algorithm follows a guided search strategy inspired by the record-to- record travel algorithm for a trade-off between performance and complexity. Experimental results show that our proposed algorithm, named meta-LPAm+, outperforms state-of-the-art algorithms, in terms of modularity, on networks with weak communities while retaining a comparable performance on networks of strong communities. In the second part of this thesis, we study the problem of evaluating community detection algorithms. Evaluating the detection algorithms on networks with known communities is important to estimate the accuracy of the algorithms and to compare different algorithms. Since there are currently only a small number of real networks with known communities available, the detection algorithms are most dominantly tested on synthetic networks with built-in community structure. Current benchmarks, that generate networks with built-in community structure, assign the same fraction of inter-community connections, referred to as the mixing fraction, for every community in the same network and ignore the presence of noise, or outliers. These existing benchmarks, therefore, cannot capture properties of nodes and communities in real networks. We address this issue by proposing a new benchmark that accounts for the heterogeneity in community mixing fractions and the presence of outliers. Our proposed benchmark extends the state-of-the-art benchmark LFR by incorporating heterogeneous community mixing fractions and outliers. We use our new benchmark to evaluate the performances of existing community detection algorithms. The results show that the variation in community mixing fractions and outliers change the performances of the detection algorithms in ways that lead to different evaluation results. Therefore, community detection algorithms need to be evaluated with heterogeneous community mixing fractions and outliers for a comprehensive view of the performances of the algorithms on real networks. The new benchmark is appropriate for implementing this evaluation as it provides parameters to control the heterogeneity among community mixing fractions and the number of outliers. Furthermore, we show that the evaluation of the detection algorithms with heterogeneous community mixing fractions and outliers gives more accurate estimates of the performances of the algorithms on several commonly studied real networks than the evaluation of the algorithms with homogeneous community mixing fractions and without outliers.