作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (17): 56-58,62. doi: 10.3969/j.issn.1000-3428.2012.17.016

• 软件技术与数据库 • 上一篇    下一篇

基于组合模型的局部搜索弱社团结构发现算法

叶 慧,李 旻   

  1. (华南师范大学计算机科学系,广州 510631)
  • 收稿日期:2011-10-24 修回日期:2011-12-12 出版日期:2012-09-05 发布日期:2012-09-03
  • 作者简介:叶 慧(1983-),女,硕士研究生,主研方向:复杂网络,数据挖掘;李 旻,工程师、硕士研究生

Local Searching Weak Community Structure Discovery Algorithm Based on Combinatorial Model

YE Hui, LI Min   

  1. (Dept. of Computer Science, South China Normal University, Guangzhou 510631, China)
  • Received:2011-10-24 Revised:2011-12-12 Online:2012-09-05 Published:2012-09-03

摘要: 针对复杂网络社团结构发现算法中全局模块度存在的分辨率缺陷问题,即不能发现很多实际存在的小社团,甚至发现的社团不满足普通意义上的社团定义,给出一种新型的多目标整数规划模型。结合弱社团定义、局部适应度和全局模块度标准,提出一种高效的启发式算法,发现网络的层次重叠社团。实验结果表明,该算法克服全局模块度的缺陷,能充分挖掘出小社团,具有较高的效率。

关键词: 复杂网络, 弱社团结构, 全局模块度, 局部适应度, 多目标整数规划

Abstract: Existing complex network community algorithms mostly take the global modularity as a criterion of searching the best community structure. However, it is revealed to suffer a resolution limit that may fail to discover small known qualified communities and discover some unqualified communities. Aiming at this problem, combining weak community definition, local fitness and global modularity, this paper presents a new multi-objective integer programming model and an efficient heuristic algorithm. It successfully discovers networks’ hierarchical and overlapping community structure. Experimental results show that the algorithm overcomes the disadvantages and fully discovers small communities with high efficiency.

Key words: complex network, weak community structure, global modularity, local fitness, multi-objective integer programming

中图分类号: