Community Detection In Complex Networks

Complex network has gradually become an attractive research field in recent years include information science, sociology, physics and even life science. The so-called com-plex networks, refer to each natural entity in the abstract for one node in its network, enti-ties and relationships between entities abstracted as the network edges. Many systems in nature could be expressed as the form of complex networks, such as social network, sci-entists cooperation network, communication network, Internet, human diseases genetic network, and so on. The latest research indicates that complex networks have complicated internal structures and diverse structural features. Among these characteristics, modular-ity (namely, community structure) is an important feature in complex networks. There are some nodes clustering as communities in complex networks. These communities are sub-groups of vertices in which the edges between the vertices in the same groups are much denser than those in different groups. Besides, in real-world networks, communities are always overlapping in most cases. The discovery of (overlapping) community structure in complex networks is of great significance in the analysis of its topology structure, the understanding of its function, the finding of its hidden rules, and even the prediction of its behavior.At present, researchers have proposed many (overlapping) community detection methods, which have been successfully applied to the analysis of real systems. However, a lot of them have many problems, for example, the relationship between community detection in complex network and cluster analysis remains to be studied; The accuracy and efficiency of community detection algorithms especially overlapping community de-tection algorithms need to be improved; The traditional partition evaluation function-Q function has a resolution limit, and so on. Because community detection in complex network and cluster analysis in traditional machine learning both partition a data set, and cluster analysis in machine learning has increasingly become mature, so in this the-sis, based on some related technologies and methods in machine learning, we proposed and improved some (overlapping) community detection algorithms. The main research achievements are as follows:(1) First, we revealed the differences and relationships between cluster analysis and community detection, then we improved GN (Girvan and Newman) algorithm by taking the concept of vertex similarity which was defined in cluster analysis, and proposed an improved algorithm called SGN (GN based on Similarity). According to the comparison and the analysis of them, we have found that, if we compute vertex similarity of a network, community detection will transform to clustering, and we can take advantage of any reliable clustering method for network parti-tion. Then, we analyzed and compared the different clustering algorithms’per-formance of finding communities based on the different vertex similarity methods. Besides, we introduced a method of computing vertex similarity into traditional GN algorithm, replacing the time-consuming betweenness calculation in GN algo-rithm. The new improved method called SGN reduced the time complexity of GN algorithm.(2) Second, we proposed a general framework for overlapping community detection in complex network based on cluster prototypes, and applied it to some actual cluster-ing algorithms. According to our research, we have found that overlapping nodes in complex network are often located in the border area of different communities, namely the intersectant parts of them. Given those characteristics, we took the ad-vantages of those clustering algorithms based on cluster prototypes, and defined one concept of vertex central membership measure in the networks. We proposed an efficient framework of algorithms based on cluster prototypes for overlapping community detection in complex network. Then this framework was applied to some classic clustering algorithms, e.g., K-means algorithm, AP (Affinity Propa-gation) algorithm, hierarchical clustering algorithm AL (Average Linkage) and NJW (Ng, Jordan and Weiss) spectral clustering algorithm. Algorithms based on our proposed framework could effectively identify not only non-overlapping com-munities, but also overlapping communities in the networks.(3) Third, we proposed K-rank algorithm which was based on rank centrality. Similar with K-means algorithm, K-rank algorithm updated all the seeds of different com-munities by constant iteration until the algorithm converged. At the same time, the proposed algorithm (K-rank) found the community central node by calculating a kind of criterion (called rank centrality) which described the nodes’centrality in the network. Thus K-rank avoided producing empty clusters easily like K-means algorithm in the iteration process. Then K-rank algorithm was improved and ex-tended to handle directed, weighted and overlapping community networks.(4) Fourth, we proposed an efficient community detection algorithm based on greedy surprise optimization. The previous references pointed out that the new commu-nity detection objective function, surprise function did not suffer from the resolu-tion limit, comparing with traditional evaluation function-Q function. Therefore, the advantages of surprise function is obvious when evaluating those networks with communities of unequal sizes. But at present, there is none related method based on optimizing surprise function directly for community detection. There-fore, in this thesis, adopting the idea of greed and considering the characteristics of surprise function, we proposed an efficient community detection algorithm called AGSO (Algorithm based on Greedy Surprise Optimization) and its improved ver-sion FAGSO (Fast-AGSO), which were based on greedy surprise optimization and did not suffer from the resolution limit. Tests on experimental networks showed that (F) AGSO had high efficiency.