一种基于最大度节点扩展的社区发现算法  

A Novel Community Detection Algorithm Based on Maximal-degree Nodes Expansion

作　　者：赵卫绩[1] 刘井莲[1] 佟良[1] 

机构地区：[1]绥化学院信息工程学院,黑龙江绥化152061

出　　处：《通化师范学院学报》2016年第8期72-75,共4页Journal of Tonghua Normal University

基　　金：绥化市2015年科技计划项目"基于社区发现的社交网络分析与研究";绥化学院青年基金资助项目(KQ1301002);黑龙江省大学生创新创业训练计划项目(201610236014)

摘　　要：针对星状社会网络,提出一种基于最大度节点扩展的社区发现算法.首先,计算网络中所有节点的度,选取节点的度大于等于阈值p的k个节点,以这k个节点为中心,与其各自的邻居节点形成k个分散的初始社区,删除重叠度高于给定阈值q的小社区.然后,对出现在这些初始社区中的重叠节点,提出一种近邻方法,通过计算这些节点到所在社区的距离,将其划分到距离最近的社区.对于k个初始社区外的节点,采用同样方法,将其划入到相应距离最近的社区.在真实网络数据集上进行了实验,实验结果表明,该方法能有效地处理初始社区内外边缘部分的不确定节点的划分问题,揭示出网络中存在的社区结构.相比经典的GN算法,该算法能得到更准确的划分结果,也具有更高的性能.For detecting community structure in star networks, a novel algorithm based on maximal -degree nodes expansion is proposed. Firstly, the degrees of all nodes in a ne^ork is computed. The top - k nodes as the center nodes whose degrees are bigger than or equal to threshold p, the top - k nodes and their neigh- bor nodes form k initial communities are found out. The small communities whose overlapping with other communities are larger than a predefined threshold q is deleted. Then, a close neighbor method, which adds the node to a community with which it has a minimum distance is proposed for dealing with the over- lapping nodes among initial communities. Using the same method, add the nodes outside the k initial communities to the corresponding community with which they have minimum distances. Finally, our algo- rithm on a famous real -word network is evaluated. The result demonstrates that our algorithm can deal with overlapping nodes and nodes outside the initial communities effectively, and can uncover the com- munity structure in networks. Compared with GN algorithm, our algorithm has a higher accuracy and bet- ter performance.

关 键 词：星状网络 社区发现 最大度节点 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]