|本期目录/Table of Contents|

[1]李圆媛,余汪建,何敏华.集合扩充的社团分解算法[J].武汉工程大学学报,2013,(09):79-81,86.[doi:103969/jissn16742869201309016]
　LI Yuan\|yuan,YU Wang\|jian,HE Min\|hua.Community decomposition algorithm based on set expansion[J].Journal of Wuhan Institute of Technology,2013,(09):79-81,86.[doi:103969/jissn16742869201309016]
点击复制

集合扩充的社团分解算法(/HTML)
分享到：

《武汉工程大学学报》[ISSN:1674-2869/CN:42-1779/TQ]

卷:
期数:
2013年09期
页码:
79-81,86
栏目:
机电与信息工程
出版日期:
2013-10-10

文章信息/Info

Title:
Community decomposition algorithm based on set expansion
文章编号:
16742869(2013)09007904
作者:
李圆媛1; 2; 余汪建1; 何敏华1; 2
1. 武汉工程大学理学院，湖北 武汉 430074；2. 智能机器人湖北省重点实验室，湖北 武汉 430074
Author(s):
LI Yuan\|yuan1; 2;  YU Wang\|jian1;  HE Min\|hua1; 2
1.School of Science, Wuhan Institute of Technology, Wuhan 430074, China; 2.Hubei Province Key Laboratory of Intelligent Robot, Wuhan 430074, China
关键词:
复杂网络; 社团结构; 集合扩展
Keywords:
complex network;  community structure;  set expansion
分类号:
TP393
DOI:
103969/jissn16742869201309016
文献标志码:
A
摘要:
社团结构是复杂网络的重要特征之一，寻找网络中的社团对于分析整个网络的结构和功能都有非常重要的意义.综述了一些经典的复杂网络社团结构划分的算法，提出了一种基于集合扩充的社团结构划分的新算法.该算法以网络中相邻的两个节点构成的集合为起点，用社团同外部联系的边的数目与社团内部边的数目的比值作为度量指标，通过计算将某一个邻居节点加入该集合后度量指标值的变化情况来判断某个邻居节点是否加入该集合，若度量指标值变小则将该邻居节点加入该集合，若度量指标值变大则不将该邻居节点加入该集合，直到不再有新的邻居节点加入时，一个社团就被划分出来.在剩下的网络中重复这个过程直到网络中的节点完全被划分.用社团结构分解中的两个经典例子测试了该算法，从测试结果来看，用该方法能够合理地划分网络中的社团结构，且运算量小，运行效率高，达到了预期目标.该社团结构的划分方法对于规模较大的复杂网络也具有普遍意义.
Abstract:
Community structure is one of important characteristics in complex network, seeking communities has very important meaning in the analysis of structure and function of the whole network. On the basis of some classical complex network structure partition algorithms, a new community structure partition algorithm based on set expansion was proposed. In this work, we defined an indicator, which is the ratio of the number of edges internal and external community. In the proposed algorithm, the set was originally composed of two adjacent nodes, indicator was recalculated if a neighbor node joined the set. Set was expanded when the indicator decreased. A community was detected until there was no new neighbor node to join. Other communities in the network were detected by repeating this process. This algorithm was implemented to detect communities in two classical networks. Experimental results show that this algorithm can reasonably detect communities with little computation and high efficiency. Moreover, the proposed algorithm can be generalized to other large\|scale complex networks.

参考文献/References:

［1］汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用［M］. 北京: 清华大学出版社, 2006.［2］Barabasi A L, Frangos J. Linked: The New Science of Networks ［M］. Massachusetts: Perseus Books Group, 2002.［3］Girvan M, Newman M E J. Community structure in social and biological networks［J］. Proceedings of the National Academy of Sciences of the United States of America, 2001, 99(12): 7821\|7826.［4］李晓佳, 张鹏, 狄增如, 等. 复杂网络中的社团结构［J］. 复杂系统与复杂性科学, 2008, 5(3): 20\|42.LI Xiao\|jia,ZHANG Peng,DI Zeng\|ru, et al. Community Structure in Complex Networks［J］.Complex Systems and Complexity Science,2008, 5(3): 19\|42. （in Chinese）［5］Pothen A, Simon H D, Liou K P. Partitioning sparse matrices with eigenvectors of graphs［J］. SIAM Journal on Matrix Analysis and Applications, 1990, 11(3): 430\|452.［6］Newman M E J. Fast algorithm for detecting community structure in networks［J］. Physical Review E, 2004, 69(6): 066133\|066137.［7］解㑇, 汪小帆. 复杂网络中的社团结构分析算法研究综述［J］. 复杂系统与复杂性科学, 2005, 2(3): 1\|12.Xie Zhou,Wang Xiao\|fan. An Overview of a Lgorithms for Analyzingf Community Structure in Complex Networks ［J］.Complex Systems and Complexity Science,2005, 2(3): 1\|12.（in Chinese）［8］Zachary W W. An information flow model for conflict and fission in small groups［J］. Journal of Anthropological Research, 1977, 33(4): 452\|473.

相似文献/References:

备注/Memo

备注/Memo:
收稿日期：20130723基金项目：湖北省教育厅科学技术研究项目（Q20121512）；武汉工程大学青年科学基金（Q201208）作者简介：李圆媛（1980\|），女，湖北宜都人，讲师，硕士. 研究方向：计算系统生物学.
更新日期/Last Update: 2013-10-11