Community Detection Algorithm Based on Neighbor Similarity

Abstract

Many complex networks have displayed the community structures, and the detection of community structure can give insights into the structural and functional information of these complex networks. In this paper, we proposed a neighbor similarity based new algorithm for community structure detection, in which we only consider the similarities between a node and its unclassified neighbors in the breadth-first traversal order, without considering other nodes’ influences; we take this node as a father node and its neighbors as the children nodes, to find out those children nodes which should belong in the same community with their father node. Then these children nodes are processed in the same way as their father node recursively, until the termination condition is reached. The most prominent property of our algorithm is that it has near liner time complexity, and furthermore it is a deterministic algorithm. We have tested our algorithm on several real networks, compared with some other algorithms, and the results have manifested that our algorithm outperforms the previous algorithms significantly.

DOI: http://dx.doi.org/10.11591/telkomnika.v11i8.3064