基于加权树的层次社团划分算法

Hierarchical community detection algorithm based on weighted tree

社团发现常用于挖掘复杂网络中的隐藏信息,如功能模块和拓扑结构.为提高复杂网络中社团结构挖掘的质量,提出一种基于加权树的层次社团划分算法HCD_WTree(Hierarchical Community Detection Algorithm Based on Weighted Tree).首先,结合邻域重叠比和节点的度中心性来度量节点间关系强度,基于该度量将原无权网络转换成加权网络;接着,对网络进行简化,得到加权树;最后,基于层次社团挖掘方法,根据边权依序裁剪加权树,得到层次的社团结构,并结合模块度函数获得最优的社团划分结果.在公用数据集上的实验结果表明,与现有的社团挖掘技术相比,HCD_WTree算法能够更准确地划分复杂网络中的社团结构.

Complex network is widely used to describe a complex system.The nodes and edges in a network represent entities and relationships between the entities respectively.Community structure is the most basic and important topological characteristic of complex network.Community detection is significant to its character statistics.In order to improve the quality of the community structure in complex networks,an algorithm named Hierarchical Community Detection Algorithm Based on Weighted Tree(HCD_WTree algorithm)is proposed in this paper.Firstly,based on the definition of Neighborhood Overlap,a new measurement is given to measure the relationship strength of neighbor nodes by introducing the degree centrality of nodes.Secondly,the strength of the relations(edges)in the network is calculated according to the new measurement so that the original unweighted network is transformed into a weighted network.Kruskal algorithm is used to build a weighted tree for the weighted network.This not only improves the efficiency of the algorithm,but also makes it more intuitive to observe the evolution of the community structure.Thirdly,based on hierarchical community detection method,using split operation,according to the weight of the edges,from small to large to cut the weighted tree step by step,the community structure of levels is obtained and in conjunction with the modularity function,the best result of division is obtained.The experimental results on public datasets show that the proposed algorithm HCD_WTree can find the community structure more accurately and effectively.