Community Detection Algorithm Based On Local Similarity

With the development and wide promotion of Internet technology and application, online social network applications such as forum, post bar, microblog have been rapidly developed. Social network have two significant characteristics: community structure and node attribute. Community structure reflects the property of network structure and node attribute corresponds to the description of network nodes. The research of social network has practical significance, such as user interest topics detect and hot event analysis and tracking. As one of the important issues of social network, community detection has been widely concerned by scholars from domestic and foreign.In view of two characteristics of social network, most existing community detection algorithms consider network topological structure or node attribute solely, which is based on single clustering factor and the detected communities either have high heterogeneity or loose structure. In recent years, researchers introduce node attribute when analyzing community structure, and combine both of them to detect communities. However, most of these algorithms only consider discrete attribute. Textual attribute is converted to discrete attribute and is not fully used. This paper proposes a local similarity based algorithm combining topological structure and attribute, which names LSTA. The main work of this paper is summarized as follows:(1) We combines network structure and node attribute to avoid clustering factor singly. To analyze network topological structure, we calculate the importance of nodes and measure structure similarity between nodes. There are two types of attribute: discrete attribute and textual attribute. To analyze textual attribute, topic model is used to analyze textual topic distribution. Then the attribute similarity is obtained by the weighted sum of each attribute similarity. Lastly, a weighting factor is used to balance structure similarity and attribute similarity.(2) We proposes a local similarity based method, which considers local information of node and avoids to underestimate the similarity of pairwise nodes that calculating by common neighbor. The similarity between two nodes’ local neighbors is treated as the local similarity of two nodes. To reduce time complexity, this paper proposes an improved algorithm.(3) The paper is based on improved k-medoids clustering algorithm. Nodes with high importance are initialed as clusters centroids. In the process of node cluster assignment, the local similarity between node and cluster centroid is calculated.This paper performs experiments on two public Citeseer dataset and DBLP dataset and compares to related classic algorithm. Extensive experimental results demonstrate the effectiveness of the proposed algorithm LSTA.