Algorithms For Community Structure Detection In Complex Networks And Their Applications

Many complex systems in nature can be modeled as networks. Communitystructure is one of the crucial structural characteristics of complex networks. The wholefunction of a network is displayed by the interaction of communities. Therefore,community structure detection is an signifcant topic in the study of complex networks.This paper focuses on community detection algorithms and their applications. Themain contributions are as follows:1. In many real networks, a node may participate in different functions and belongto several communities, which cause the overlap among communities. To solve thisproblem, we propose a computationally efficient algorithm, named by OAP(Overlapped Affinity Propagation), which is based on AP (Affinity Propagation)algorithm to detect the overlapping communities. When using AP to detect communities,we first identify all of the exemplars, and then assign each node to an exemplar. Finally,the nodes with the same exemplar constitute a community. In some special cases, a nodecannot make its choice for there are several exemplars which satisfy the chosencondition. AP avoids this situation by adding a tiny amount of noise to the inputsimilarities. But we treat this situation as an important clue for overlapping nodesidentification. First, AP algorithm is adopted to obtain a hard partition of the network.Then the candidate overlapping nodes for each community are identified. Finally, astrategy is constructed with an immediate purpose to filter noise in these candidateoverlapping nodes. The OAP is applied to the karate club network of Zachary to verifythe rationality of the candidate selection strategy. The OAP is also applied to theSaccharomyces cerevisiae PPI network, and the experimental results demonstrate thatour algorithm can discover more functional modules with high precision. OAP isvalidated as an effective algorithm in identifying overlapping communities.2. When detecting communities, there are two possible sources of information onecan use: the network structure, and the features and attributes of nodes. In this paper, analgorithm is developed to detect communities in networks with node attributes. Firstly,the feature similarity is defined between nodes based on the subspace of the nodeattributes. Since communities form aroud nodes that have common edges and commonattributes, the feature similarity is combined with topological similarity of node pairs tocalculate the similarity of edge pairs. And then single-linkage hierarchical clusteringalgorithm is employed to partition edges. The induced nodes of similar edges constitute a community. Finally, each community is labeled by abstracting the common propertiesin edges to explain why this community forms. The experimental results on Facebookdata demonstrate that our algorithm can not only detect communities efficiency andaccuracy, but also can convincingly explain the meaning of a community. Theexperimental results on PPI data show that our algorithm can identify significantbiology communities. The proposed method is validated as a universal and effectivealgorithm in identifying communities in networks with node attributes.3. Analyzing the evolution of communities in different snapshots is a relevant topicin dynamic networks. Since in dynamic networks there is little change in adjacentnetwork snapshots, a bridgeness-based local clustering algorithm and an incrementalclustering algorithm based on it are proposed to avoid clustering similar snapshots. Weutilize bridgeness-based local clustering algorithm to obtain communities in t-1snapshot by abstracting the minimum bridgeness spanning tree for each community.The community structures detected in t-1snapshot are used as the initial clusteringresults in t snapshot. Then the edge bridgeness is adopted to judge the influence onclustering results arising from the snapshot change. Finally, the community structuresfitting current snapshot are obtained by locally modifying the initial clustering results.The experimental results on football data demonstrate the accuracy of thebridgeness-based local clustering algorithm. The experimental results on synthetic dataverify the accuracy of the incremental clustering algorithm. The experimental results onDBLP data display the efficiency of the incremental clustering algorithm.4. Characterization and identification of protein complexes in PPI networks isimportant in understanding cellular processes. With the core-attachment concept, anovel core-attachment algorithm is proposed by characterizing the protein complex corefrom the perspective of edges. A protein complex core is reinvited to be a set of closelyinterrelated edges rather than a set of interrelated proteins. We first identify the edgesmust belong to a core, and then partition these edges to extract cores. After that, theredundancy cores are filtered. Finally, the attachments for each complex core areselected to form a protein complex. We evaluate the performance of our algorithm byapplying it on two different yeast PPI networks. The experimental results show that ouralgorithm outperforms the MCL, CPM, CoAch in terms of number of preciselypredicted protein complexes, localization as well as GO semantic similarity. Ourproposed method is validated as an effective algorithm in identifying protein complexesand can provide more insights for future biological study. It proves that edge communityis a better topological characterization of protein complex. 5. Recommending friends to registered users is a crucial personal service of OnlineSocial Networks (OSN). OSN will recommend a friend to a user if they share somecommon attributes or neighbors. But the recommendation accuracy is usually not sogood since users’ profile information may be incomplete and the relationships betweenneighbors are ignored. In fact, users can group their friends into several social circlesand two users are more likely to become friends if they share similar social circles.Therefore, a social circle detection algorithm is utilized firstly to detect social circles,and then the social circle similarity is defined. Based on this similarity, we canrecommend friends to a user. Our hypothesis is verified by statistically analyzing theYouTube dataset. We utilize social circle similarity, common neighbor similarity andJaccard similarity to predict friend relationships in Facebook New Orleans network. Theexperimental results provide strong evidence that our algorithm is more precision infriend recommendation.