基于局部稠密度的社团划分算法  

Community Partition Algorithm Based on Local Consistency

作　　者：马杰良[1] 潘贞贞[1] 韩路[1] 宋艳[1] 

机构地区：[1]南京信息工程大学电子与信息工程学院和信息与控制学院,南京210044

出　　处：《科学技术与工程》2014年第27期135-139,共5页Science Technology and Engineering

基　　金：国家自然科学基金(61372128)资助

摘　　要：社团划分是研究复杂网络结构与功能之间关系的基础,提出了一种基于局部稠密度的社团划分算法。算法首先计算网络中节点的局域密度,从局域密度最大的节点v开始,找出以节点v及其邻居如果αlocal(vi)≥γin则将其设为初始社团S。首次定义了节点的入团率β,并且使用整体和单个入团的方式将节点加入到初始社团中,直到αlocal<γout时算法停止。然后再使用内部连接P来检测社团划分的效果,并将错误划分的节点重新归类。把这个算法用在三个社会网络中,都得到了正确的划分。并用MATLAB仿真结果表明:划分出的社团内部连接相当紧密,从而达到了内部连接紧外部连接稀疏的划分社团的要求。此算法不需要计算模块度,在找到初始社团后,并不需要对整个网络的所有节点进行计算,只需计算其一阶邻居节点。这样算法所占用时间少,结果精确率高。Divided community is the basic to study the relationship between structure and function of the complex network,a community partitioning algorithm based on local dense degree was presented. The algorithm firstly calculates the local network density of nodes in the network. From the beginning of the highest density network,then set it to an initial community S if αlocal（ vi） ≥ γin. For the first time joining rate β of node was defined,and nodes are made to join the initial community using overall and individual joining ways,the algorithm stops untilαlocal γout. Then the effect of divided societies are detected using the internal connection P,and the error-divided node are reclassifieol. The algorithm have got the correct results when used in three social networks. The MATLAB simulation indicates that： divided community has very closely internal connection,so reached,requirements of divided community with the tight internal connection and the sparse external connection. This algorithm does not need compute module degrees. After finding the group,it does not need calculate all the nodes of the entire network,just need calculate the one-order neighbors. This algorithm takes less time and has results with accurate rate.

关 键 词：社团划分 初始社团 局部密度 入团率 

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