Community Detection Based on Node Similarity without thresholds

Abstract

To identify communities in social networks represented by a graph, we simply need to detect the edges that connect vertices of different communities and remove them, but the problem is what measure has to be used to identify these edges? and, how we use it? To tackle this problem, this paper proposes an efficient algorithm based on node similarity. This algorithm neither needs a predefined number of communities nor threshold to determine which edges to be deleted. The algorithm tries to add new edges for the most similar nodes to strengthen intra-community links and remove edges between the least similar nodes to weaken links between communities. In order to prove its efficiency, the algorithm was evaluated with synthetic and real-world networks.

Keywords

• social network
• community detection
• node similarity
• modularity
• gn algorithm