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

doi:10.3778/j.issn.1673-9418.2009.03.009

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

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

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

四川大学计算机学院，成都 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

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

摘要/Abstract

摘要： 社会网络中社团核心的发现是目前研究界和产业界关注的热点问题。现有算法把社团处理为特定约束下的图后，将社团核心发现规约为紧凑子图的提取，但对于动态约束下的多图效率很低。为此，提出基于图密度的动态约束社团核心挖掘方法——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

魏绪仲,唐常杰+,徐开阔,段磊,巩杰,姜页希,李太勇. CCDCD：基于图密度的动态约束社团核心挖掘方法[J]. 计算机科学与探索, 2009, 3(3): 309-320.

WEI Xuzhong, TANG Changjie+, XU Kaikuo, DUAN Lei, GONG Jie, JIANG Yexi, LI Taiyong. CCDCD： Community Core Mining with Dynamic Constrains Based on Graph Density[J]. Journal of Frontiers of Computer Science and Technology, 2009, 3(3): 309-320.

[1]	彭家寅. 9-量子团簇态信道的非对称双向量子信息传输[J]. 计算机科学与探索, 2020, 14(2): 353-360.
[2]	王永贵，徐山珊，肖成龙. 无线城市社团发现的研究——在Spark上利用改进关联规则实现社团发现的算法[J]. 计算机科学与探索, 2019, 13(9): 1582-1592.
[3]	江淼淼，孙更新，宾晟. 多关系社交网络中社团结构发现算法[J]. 计算机科学与探索, 2019, 13(7): 1134-1144.
[4]	李春英，汤志康，汤庸，赵剑冬，黄泳航. 局部优先的社会网络社区结构检测算法[J]. 计算机科学与探索, 2018, 12(8): 1263-1277.
[5]	周旸，陈晓云，程建军，刘伟，苗海飞. 基于最优特征向量的谱二分社团检测方法[J]. 计算机科学与探索, 2017, 11(12): 1897-1906.
[6]	郝赫，司雨蒙，韦建文，文敏华，林新华. 天体物理成团研究中的非规则访存优化[J]. 计算机科学与探索, 2017, 11(1): 80-90.
[7]	孙焕良，富珊珊，刘俊岭，于戈，许鸿斐. 社会网络中弱关系团队形成问题研究[J]. 计算机科学与探索, 2016, 10(6): 773-785.
[8]	袁成哲，曾碧卿，汤庸，王大豪，曾惠敏. 面向学术社交网络的多维度团队推荐模型[J]. 计算机科学与探索, 2016, 10(2): 201-209.
[9]	张永辉，李川，唐常杰，李艳梅. 基于结构分析的信息网络社团趋势预测[J]. 计算机科学与探索, 2015, 9(4): 403-409.
[10]	胡新，王丽珍，周丽华，温佛生. 空间极大co-location模式挖掘研究[J]. 计算机科学与探索, 2014, 8(2): 150-160.
[11]	姚宏亮，罗明伟，李俊照，王浩，李国欢. 复合加权股票网络的活跃性层次聚类[J]. 计算机科学与探索, 2014, 8(2): 207-217.
[12]	胡新，王丽珍，何瓦特，姚华传. 度数法求解最大团问题[J]. 计算机科学与探索, 2013, 7(3): 262-271.
[13]	周伟，王峰，王崇骏，谢俊元. 利用效用度挖掘核心药物及配伍规律[J]. 计算机科学与探索, 2013, 7(11): 994-1001.
[14]	朱小虎1,2 , 宋文军1,2 , 王崇骏1,2+ , 谢俊元1,2 . 用于社团发现的Girvan-Newman改进算法[J]. 计算机科学与探索, 2010, 4(12): 1101-1108.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics