[1]张华健,王有权,伍之昂,等.基于局部紧耦合结构的模块性优化社区检测方法[J].东南大学学报(自然科学版),2014,44(3):504-509.[doi:10.3969/j.issn.1001-0505.2014.03.010]
 Zhang Huajian,Wang Youquan,Wu Zhiang,et al.Modularity optimization method for community detection based on local close-knit structures[J].Journal of Southeast University (Natural Science Edition),2014,44(3):504-509.[doi:10.3969/j.issn.1001-0505.2014.03.010]
点击复制

基于局部紧耦合结构的模块性优化社区检测方法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
44
期数:
2014年第3期
页码:
504-509
栏目:
计算机科学与工程
出版日期:
2014-05-16

文章信息/Info

Title:
Modularity optimization method for community detection based on local close-knit structures
作者:
张华健1王有权2伍之昂3孙知信1
1南京邮电大学物联网学院, 南京 210003; 2南京理工大学计算机科学与工程学院, 南京 210094; 3南京财经大学江苏省电子商务重点实验室, 南京 210003
Author(s):
Zhang Huajian1 Wang Youquan2 Wu Zhiang3 Sun Zhixin1
1College of Internet of Things, Nanjing University of Post and Telecoms, Nanjing 210003, China
2College of Computer Science and Technology, Nanjing University of Science and Technology, Nanjing 210094, China
3Jiang
关键词:
社区检测 模块性 FN算法 社会网络 紧耦合结构
Keywords:
community detection modularity Fast Newman(FN)algorithm social network close-knit structure
分类号:
TP393
DOI:
10.3969/j.issn.1001-0505.2014.03.010
摘要:
利用局部紧耦合结构提升社区检测的模块性优化质量.首先,定义了4类边缘紧耦合结构,并提出了一种具有线性复杂度的边缘紧耦合结构挖掘算法.其次,分别选择k-clique,k-clan,k-plex结构作为核心紧耦合结构,并以长结构优先和短结构优先2种策略将边缘与核心紧耦合结构合并.然后,将合并后的局部紧耦合结构融入模块性优化过程,提出了一种NFN算法.该算法将每个局部紧耦合结构初始化为独立社区,不断凝聚模块性增量最大的2个社区,直至找到预定义数量的社区. 6个真实数据集上针对外部指标和内部指标的实验结果均表明,相比于传统的FN算法,NFN算法能发现更高质量的社区.在参数设置方面,长结构优先策略优于短结构优先策略,且采用k-clique结构作为核心紧耦合结构优于采用其他结构.因此,长结构优先策略结合k-clique成为NFN算法的最佳参数组合.
Abstract:
Local close-knit structures are used to improve the quality of modularity optimization in community detection. First, four kinds of periphery close-knit structures are defined, and an algorithm for mining periphery close-knit structures with linear complexity is presented. By selecting k-clique, k-clan, and k-plex as core close-knit structures, two strategies including long-structure-first and short-structure-first are employed for merging periphery with core structures. Thus, a novel algorithm named new Fast Newman(NFN)is proposed by incorporating merged local structures into the modularity optimization process. In particular, each local close-knit structure is initialized as an isolated community, and then two communities are merged to maximize the increase of modularity. This process is repeated until the pre-defined number of communities is discovered. The experimental results in terms of both internal and external validities on six real-world social networks demonstrate that compared with the traditional Fast Newman(FN)algorithm, the NFN algorithm can find communities in better quality. Moreover, the long-structure-first strategy outperforms the short-structure-first strategy, and employing k-clique as core close-knit structures is better than other structures. Therefore, the long-structure-first strategy with k-clique is the best parameter setting for the NFN algorithm.

参考文献/References:

[1] 张忠元. 基于字典学习的网络社团结构探测算法[J]. 中国科学: 信息科学, 2011, 41(11): 1343-1355.
  Zhang Zongyuan. Community structure detection in social networks based on dictionary learning [J]. SCIENTIA SINICA Informationis, 2011, 41(11):1343-1355.
[2] 杨博,刘大有,Liu Jinming,等. 复杂网络聚类方法[J]. 软件学报,2009, 20(1): 54-66.
  Yang Bo, Liu Dayou, Liu Jinming, et al. Complex network clustering algorithms [J]. Journal of Software, 2009, 20(1):54-66.(in Chinese)
[3] Newman M E J. Fast algorithm for detecting community structure in networks [J]. Physical Review E, 2004, 69(6): 066133.
[4] Wasserman S, Faust K. Social network analysis: methods and applications [M]. Cambridge: Cambridge University Press, 1994:36-47.
[5] Lewis T G. Network science: theory and applications [M]. Weinheim: Wiley, 2011: 40-47.
[6] Papadopoulos S, Kompatsiaris Y, Vakali A, et al. Community detection in social media [J]. Data Mining and Knowledge Discovery, 2012, 24(3): 515-554.
[7] Tang L, Liu H. Community detection and mining in social media [M]. San Rafael, CA, USA: Morgan & Claypool Publishers, 2010:1-127.
[8] Fortunato S. Community detection in graphs [J]. Physics Reports, 2010, 486(3): 75-174.
[9] Wu Z, Cao J, Wu J, et al. Detecting genuine communities from large-scale social networks: a pattern-based method [EB/OL].(2013-11-14)[2013-12-12]. http://comjnl.oxfordjournals.org/content/early/2013/11/14/comjnl.bxt113.short.
[10] Cao J, Wu Z, Wu J, et al. SAIL: summation-based incremental learning for information theoretic text clustering [J]. IEEE Transactions on Cybernetics, 2013, 43(2): 570-584.

备注/Memo

备注/Memo:
收稿日期: 2013-10-21.
作者简介: 张华健(1977—),男,博士生,讲师;伍之昂(联系人),男,博士,副教授,zawuster@gmail.com.
基金项目: 国家自然科学基金资助项目(60973140,61103229,71372188)、国家级电子商务信息处理国际联合研究中心资助项目(2013B01035)、国家科技支撑计划资助项目(2013BAH16F03).
引用本文: 张华健,王有权,伍之昂,等.基于局部紧耦合结构的模块性优化社区检测方法[J].东南大学学报:自然科学版,2014,44(3):504-509. [doi:10.3969/j.issn.1001-0505.2014.03.010]
更新日期/Last Update: 2014-05-20