Research On Community Detection Algorithm Based On Node Similarity

Many complex systems can be modeled as complex networks,such as social network,protein interaction network,transportation network,etc.Complex network analysis is widely used in sociology,biology and other fields.Nodes in a complex network often can be grouped into different clusters,called communities.Nodes in the same group form specific functional modules through tight intra-connection,and nodes from different group have relatively loose inter-connection to ensure cooperation among the functional modules of the system.Detecting community structures is crucial to understand the topological structure and dynamic characteristics of networks.Based on analyzing connecting patterns within and between communities,researchers can discover the functional modules and their evolution processes in various complex systems.In view of community detection problems in complex networks,this paper mainly includes the following two aspects:(1)Node similarity metrics play important roles in community detection algorithms.We propose a community detection algorithm,called PGC.We define a novel node similarity index SLP based on vertex non-repetitive paths between nodes.The proposed SLP Index weakens the influence of large-degree nodes on the calculation of nodes' similarity.Compared with other classical community detection algorithms on 11 real networks and 22 artificial networks,the proposed algorithm PGC shows a preferable performance.(2)Due to the random process in node selection and label propagation,the stability of the results of traditional LPA is poor.A two-stage community detection algorithm is proposed based on label propagation,abbreviated as LPA-TS.In first step of LPA-TS,the labels of nodes are updated according to their participation coefficients in non-decreasing order,and the node label is determined according to the similarity of nodes in the process of node label updating.Some clusters found by Step 1 might not satisfy the weak community condition.If a cluster is not a weak community,then in the beginning of Step 2,we will merge it with the cluster that has most connections with it.Next,we treat each community as a node,and the number of edges between two communities as their edge weights between corresponding nodes.We compute the participation coefficients of each node of the resulted network,and use similar process to get the final results of the communities.The proposed algorithm LPA-TS reduces the randomness in the process of node selection and label propagation.Compared with other classical community detection algorithms on some real networks and artificial networks,the proposed algorithm shows a preferable performance on stability,NMI,ARI and modularity.