复杂网络中社团结构划分的快速分裂算法  

Fast splitting algorithm for partitioning community structure in complex networks

作　　者：张聪[1] 沈惠璋[1] 李峰[1] 

机构地区：[1]上海交通大学安泰经济管理学院,上海200052

出　　处：《计算机应用研究》2011年第4期1242-1244,1250,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(71071096);高等学校博士学科点专项科研基金资助项目(20070248054)

摘　　要：针对已有分裂算法时间复杂度较高,不适用于社团数目未知的大型网络等问题,借鉴电压谱分割算法和GN算法的思想,提出以扩散距离为分割依据,以模块度函数为社团结构划分满意度的快速分裂算法。实验结果表明,与已有的社团结构划分算法相比,基于扩散距离的快速分裂算法能够得到高质量的社团结构,其时间复杂度较低,不仅对稀疏网络能够快速运算,对非稀疏网络更能高效求解,这进一步体现出算法具有较高的稳定性。Most of the proposed splitting algorithms are not suitable for very large networks because of their high time complexity and unknown quantity of community number.Referencing the voltage spectrum segmentation algorithm and GN algorithm,this paper proposed a fast splitting algorithm based on diffusion distance and the modularity function.Its segmentation basis was the diffusion distance,and the ability of modularity function could find the best community number in large networks.Experimental results show that the algorithm has better partitioning ability and lower time complexity than the proposed partitioning community structure algorithms.Not only it is capable of fast operation for the sparse network,but also for the non-sparse network,which reflects the algorithm has high stability.

关 键 词：复杂网络 社团结构 分裂算法 模块度 扩散距离 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]