基于节点相异性指标的网络社团检测算法  

Network Community Detection Algorithm Based on Node Dissimilarity Index

作　　者：刘亚东 覃森[1] LIU Yadong;QIN Sen(School of Sciences,Hangzhou Dianzi University,Hangzhou Zhejiang 310018,China)

机构地区：[1]杭州电子科技大学理学院,浙江杭州310018

出　　处：《杭州电子科技大学学报（自然科学版）》2020年第3期92-97,共6页Journal of Hangzhou Dianzi University：Natural Sciences

基　　金：浙江省自然科学基金资助项目(LY19F030018)。

摘　　要：受三元闭包原理的启发,基于节点邻居的差异性定义了3种相异性指标即单层邻居相异性、2-邻居相异性和全局2-邻居相异性。由于节点相异性越大越可能出现在不同的社团中,故通过逐步移除网络中相异性最高的两节点之间边的方式,设计一种高效的社团检测算法——基于节点相异性指标的网络社团检测算法。算法中,模块度最大时对应于网络的最佳社团结构,并采用标准化互信息衡量检测结果的准确度。选用LFR基准网络、Zachary网络和Football网络作为测试数据,与GN算法和Fast Newman算法的检测结果进行对比发现:基于节点相异性指标的网络社团检测算法能更准确地检测出网络社团结构。Inspired by the principle of ternary closure,three dissimilarity indicators,i.e.,single-layer neighbor dissimilarity,2-neighbor dissimilarity and global 2-neighbor dissimilarity,are defined based on the difference of node neighbors.The greater dissimilarity of nodes,the less likely it is to be in the same community.We design an efficient community detection algorithm by gradually removing the edges between the two nodes with the highest dissimilarity in the network.In this algorithm,the maximum modularity corresponds to the optimal community structure of the network,and the standardized mutual information is used to measure the accuracy of the detection results.LFR benchmark network,Zachary network and football network are used as test data.Comparing the accuracy with GN algorithm and Fast Newman algorithm,the network community detection algorithm based on the node dissimilarity index can detect the network community structure much more accurately.

关 键 词：相异性 社团检测算法 模块度 标准化互信息 

分 类 号：O157.5[理学—数学]