从属度树算法检测复杂网络重叠社团

Following-degree Tree Algorithm to Detect Overlapping Communities in Complex Networks

重叠社团检测一直是复杂网络研究领域的重点和难点。由于真实网络普遍存在层次结构,结合层次性的重叠社团检测方法将更适用于现实世界复杂网络的研究分析,但目前这类方法的研究还比较少。因此,在定义复杂网络节点领导度、从属度概念的基础上,结合网络层次性建立数学模型,提出了新颖的从属度树检测重叠社团算法。该算法根据从属度值建立从属度树,通过划分树发现重叠节点和重叠社团。在人工网络实验中证明了从属度树算法可以结合层次性发现重叠节点,在Dolphin网络和Karate网络上的实验验证了其检测重叠社团结果的可靠性。与已有一些算法比较的结果表明,从属度树算法能找到其他算法不能找到的重叠节点,以扩展模块度和实际社团结构作为从属度树算法划分重叠社团结果的评价指标。新算法的扩展模块度值大于对比算法,社团划分结果更接近实际社团结构。

Overlapping community detection is a key and difficult issue in complex network research field.Due to the widespread hierarchical structures in real networks,the hierarchical overlapping community detection methods are more suitable for studying and analyzing complex networks in the real world.However,these researches of this kind of method are not many now.This paper proposed a new overlapping community detection algorithm named following-degree tree based on the definition of complex network node leadership and subordination concept.Combined with the hierarchical characteristic,this algorithm constructs the following-degree tree by calculating the following degree of eve-ry nodes and finally finds the overlapping nodes and overlapping communities by dividing the tree.The feasibility of the algorithm was proved by an artificial network experiment,and its effectiveness was verified by the experiments on Dolphin network and Karate network.The proposed algorithm has high extended modularity and more reasonable division,which can find overlapping nodes that other algorithms cannot find.