Two-stage algorithm using influence coefficient for detecting the hierarchical, non-overlapping and overlapping community structure

• We proposed an evaluation function MdMd with a tunable parameter λλ.
• We can get the community structures with different overlapping levels by adjusting λλ.
• As λ=0.5λ=0.5, MdMd can detect the wrongly classified nodes and revise them.
• Analysis of the algorithm shows that the time complexity is low.
• The method can detect the hierarchical, non-overlapping and overlapping structures.

Community detection is one of the most important problems in complex networks. Many algorithms have been proposed in the last decade, and most of them focus on the non-overlapping community structures in the early days. Overlapping and hierarchical structures are another two important properties in complex networks, which have attracted researchers’ extensive concern in recent years. In this paper, we proposed a two-stage method which can detect the hierarchical, non-overlapping and overlapping community structures in complex networks. In this method, the CNM algorithm, a fast hierarchical agglomerative algorithm proposed by Clauset, Newman and Moore, is used in the first stage. In the second stage, a new evaluation function named as influence coefficient based on the local community structure is proposed, which can get the overlapping community structures at different overlapping levels by adjusting a tunable parameter. Besides, the proposed evaluation function can detect the wrongly classified nodes in the partition of the first stage and correct them. Finally, the computational complexity of the algorithm is low. The experimental results on both synthetic and real-world network datasets show the efficiency of our method.