计算机科学与探索 ›› 2009, Vol. 3 ›› Issue (3): 309-320.DOI: 10.3778/j.issn.1673-9418.2009.03.009

• 学术研究 • 上一篇    下一篇

CCDCD:基于图密度的动态约束社团核心挖掘方法

魏绪仲,唐常杰+,徐开阔,段 磊,巩 杰,姜页希,李太勇   

  1. 四川大学 计算机学院,成都 610065
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2009-05-15 发布日期:2009-05-15
  • 通讯作者: 唐常杰

CCDCD: Community Core Mining with Dynamic Constrains Based on Graph Density

WEI Xuzhong, TANG Changjie+, XU Kaikuo, DUAN Lei, GONG Jie, JIANG Yexi, LI Taiyong   

  1. Computer Science and Technology School, Sichuan University, Chengdu 610065, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2009-05-15 Published:2009-05-15
  • Contact: TANG Changjie

摘要: 社会网络中社团核心的发现是目前研究界和产业界关注的热点问题。现有算法把社团处理为特定约束下的图后,将社团核心发现规约为紧凑子图的提取,但对于动态约束下的多图效率很低。为此,提出基于图密度的动态约束社团核心挖掘方法——CCDCD (community core mining with dynamic constrains based on graph density)。主要工作包括:(1)分析约束条件变化下,关于社团的图密度变化规律;(2)提出约束变化下,社团图密度的近似求解算法DCUE (dynamic calculation based on updated edges);(3)通过实验表明,与现有方法相比,对较大规模的社团图,新方法能获得更好解,降低时间消耗80%以上;验证了动态约束能发现更多有兴趣度的知识。

关键词: 社团核心, 图密度, 动态约束, 紧凑子图,

Abstract: Community core mining (CCM) is a current hot topic in the field of data mining. Existing methods reduce the community to the graphs with specific constraints and treat CCM as dense sub-graphs mining. The existing methods are inefficient on complex problem with multi-graph and dynamic constraints. To improve the efficiency, a novel method for community core mining with dynamic constrains based on graph density (CCDCD). The main contributions include: (1) Reveal the inner disciplines in the graph density with dynamic constraints; (2) Present algorithm dynamic calculation based on updated edges (DCUE) to fast evaluate graph density with variant constraints; (3) Give extensive experiments to show that newly proposed DCUE gets more satisfied results while saving more than 80% time over complex problem, and discover more interesting knowledge about community core with dynamic constraints.

Key words: community core, graph density, dynamic constraints, dense sub-graph, clique