基于环路紧密度的复杂网络社区挖掘方法

吉林大学学报(工学版) ›› 2013, Vol. 43 ›› Issue (01): 98-105.

基于环路紧密度的复杂网络社区挖掘方法

刘大有^1,2, 杨建宁^1,2, 杨博^1,2, 赵学华^1,2, 金弟³

1. 吉林大学计算机科学与技术学院, 长春 130012;
2. 吉林大学符号与知识工程教育部重点实验室长春130012;
3. 天津大学计算机科学与技术学院, 天津 300072

收稿日期:2012-05-06 出版日期:2013-01-01 发布日期:2013-01-01
通讯作者: 杨博(1974-),男,教授,博士生导师.研究方向:Agent系统,数据挖掘,复杂网络分析.E-mail:ybo@jlu.edu.cn E-mail:ybo@jlu.edu.cn
作者简介:刘大有(1942-),男,教授,博士生导师.研究方向:多Agent系统,移动Agent,知识工程与专家系统,数据挖掘以及空间推理.E-mail:liudy@jlu.edu.cn
基金资助:
国家自然科学基金项目(60873149,60973088,61133011,61170092);模式识别国家重点实验室开放课题;中央高校基本科研业务费专项资金(20093177);教育部新世纪优秀人才支持计划项目(NCET-11-0204);2011年教育部博士学术新人奖项目(450060454018).

Community mining from complex networks based on loop tightness

LIU Da-you^1,2, YANG Jian-ning^1,2, YANG Bo^1,2, ZHAO Xue-hua^1,2, Jin Di³

1. College of Computer Science and Technology, Jilin University, Changchun 130012, China;
2. Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun, 130012, China;
3. School of Computer Science and Engineering, Tianjin University, Tianjin 300072, China

Received:2012-05-06 Online:2013-01-01 Published:2013-01-01

摘要/Abstract

摘要： 提出了一种基于环路紧密度的复杂网络社区挖掘算法(LTA):首先提出一种快速发现网络环路和计算其紧密值的算法,然后根据环路紧密值将网络聚类,再次揭示网络环路与社区结构的联系。并使用人工合成网络和真实网络数据集对LTA进行了验证,实验结果证明了LTA对复杂网络社区挖掘问题的有效性和高效性。

关键词: 人工智能, 数据挖掘, 复杂网络, 社区挖掘, 环路紧密度算法

Abstract: In this paper, a Loop Tightness Algorithm (LTA) is proposed. First, it finds the network loops and calculates it tightness value quickly. Then, it obtains the communities of the networks based on the tightness values. Finally, it reveals the relationship between the network loops and the community structure. The LTA is tested and validated by means of synthetic networks and real networks.

Key words: artificial infelligence, data mining, complex networks, community mining, loop tightness algorithm(LTA)

中图分类号:

TP18

刘大有, 杨建宁, 杨博, 赵学华, 金弟. 基于环路紧密度的复杂网络社区挖掘方法[J]. 吉林大学学报(工学版), 2013, 43(01): 98-105.

LIU Da-you, YANG Jian-ning, YANG Bo, ZHAO Xue-hua, Jin Di. Community mining from complex networks based on loop tightness[J]. 吉林大学学报(工学版), 2013, 43(01): 98-105.

参考文献

[1] 杨博,刘大有,Liu Ji-ming,等.复杂网络聚类方法[J].软件学报, 2009,20(1):54-66. Yang Bo, Liu Da-you, Liu Ji-ming, et al. Complex network clustering algorithms[J]. Journal of Software,2009,20(1):54-66.

[2] Kleinberg J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM (JACM),1999,46:604-632.

[3] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences,2002,99:7821.

[4] Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences of the United States of America,2004,101:2658.

[5] Tyler J R, Wilkinson D M, Huberman B A. Email as spectroscopy:Automated discovery of community structure within organizations[J]. The Information Society,2005,21(2):143-153.

[6] Wu F, Huberman B A. Finding communities in linear time: a physics approach[J]. The European Physical Journal B-Condensed Matter and Complex Systems,2004,38:331-338.

[7] Yang B, Cheung W K, Liu J. Community mining from signed social networks[J].IEEE Transactions on. Knowledge and Data Engineering, 2007,19:1333-1348.

[8] Pothen A, Simon H D, Liou K P. Partitioning sparse matrices with eigenvectors of graphs[J]. Siam J Matrix Anal Applic,1990,11:430-452.

[9] Fiedler M. Algebraic connectivity of graphs[J]. Czechoslovak Mathematical Journal,1973,23:298-305.

[10] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal,1970,49:291-307.

[11] Newman MEJ. Fast algorithm for detecting community structure in networks[J]. Physical Review E,2004,69:066133.

[12] Guimera R, Amaral L A N. Functional cartography of complex metabolic networks[J]. Nature 2005,433:895-900.

[13] Xing E P, Jordan M I, Russell S. A Generalized Mean Field Algorithm for Variational Inference in Exponential Families. Uncertinty in AI 2003.

[14] Fu W, Song L, Xing E P. Dynamic mixed membership blockmodel for evolving networks//In Proceedings of the 26th Annual International Conference on Machine learning,2009:329-336.

[15] Airoldi E M, Blei D M, Fienberg S E, et al. Mixed membership stochastic blockmodels[J]. The Journal of Machine Learning Research,2008,9:1981-2014.

[16] Wang Y J, Wong G Y. Stochastic blockmodels for directed graphs[J]. Journal of the American Statistical Association,1987:8-19.

[17] Flake G W, Lawrence S, Giles C L, et al. Self-organization and identification of web communities[J]. Computer,2002;35:66-70.

[18] Hofman J M, Wiggins C H. Bayesian approach to network modularity[J]. Physical Review Letters,2008,100:258701.

[19] Holland P W, Leinhardt S. Local structure in social networks[J]. Sociological methodology 1976,7:1-45.

[20] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E,2004,69(2):026113.

[21] Guimera R, Sales-Pardo M, Amaral L A N. Modularity from fluctuations in random graphs and complex networks[J]. Physical Review E,2004,70:025101.

[22] Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J]. Physical Review E,2009,80:016118.

[23] Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology,2003,54:396-405.

[24] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research,1977:452-473.

相关文章 15

[1]	董飒, 刘大有, 欧阳若川, 朱允刚, 李丽娜. 引入二阶马尔可夫假设的逻辑回归异质性网络分类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1571-1577.
[2]	顾海军, 田雅倩, 崔莹. 基于行为语言的智能交互代理[J]. 吉林大学学报(工学版), 2018, 48(5): 1578-1585.
[3]	王旭, 欧阳继红, 陈桂芬. 基于垂直维序列动态时间规整方法的图相似度度量[J]. 吉林大学学报(工学版), 2018, 48(4): 1199-1205.
[4]	张浩, 占萌苹, 郭刘香, 李誌, 刘元宁, 张春鹤, 常浩武, 王志强. 基于高通量数据的人体外源性植物miRNA跨界调控建模[J]. 吉林大学学报(工学版), 2018, 48(4): 1206-1213.
[5]	黄岚, 纪林影, 姚刚, 翟睿峰, 白天. 面向误诊提示的疾病-症状语义网构建[J]. 吉林大学学报(工学版), 2018, 48(3): 859-865.
[6]	李雄飞, 冯婷婷, 骆实, 张小利. 基于递归神经网络的自动作曲算法[J]. 吉林大学学报(工学版), 2018, 48(3): 866-873.
[7]	刘杰, 张平, 高万夫. 基于条件相关的特征选择方法[J]. 吉林大学学报(工学版), 2018, 48(3): 874-881.
[8]	邓剑勋, 熊忠阳, 邓欣. 基于谱聚类矩阵的改进DNALA算法[J]. 吉林大学学报(工学版), 2018, 48(3): 903-908.
[9]	王旭, 欧阳继红, 陈桂芬. 基于多重序列所有公共子序列的启发式算法度量多图的相似度[J]. 吉林大学学报(工学版), 2018, 48(2): 526-532.
[10]	杨欣, 夏斯军, 刘冬雪, 费树岷, 胡银记. 跟踪-学习-检测框架下改进加速梯度的目标跟踪[J]. 吉林大学学报(工学版), 2018, 48(2): 533-538.
[11]	刘雪娟, 袁家斌, 许娟, 段博佳. 量子k-means算法[J]. 吉林大学学报(工学版), 2018, 48(2): 539-544.
[12]	马健, 樊建平, 刘峰, 李红辉. 面向对象软件系统演化模型[J]. 吉林大学学报(工学版), 2018, 48(2): 545-550.
[13]	曲慧雁, 赵伟, 秦爱红. 基于优化算子的快速碰撞检测算法[J]. 吉林大学学报(工学版), 2017, 47(5): 1598-1603.
[14]	李嘉菲, 孙小玉. 基于谱分解的不确定数据聚类方法[J]. 吉林大学学报(工学版), 2017, 47(5): 1604-1611.
[15]	邵克勇, 陈丰, 王婷婷, 王季驰, 周立朋. 无平衡点分数阶混沌系统全状态自适应控制[J]. 吉林大学学报(工学版), 2017, 47(4): 1225-1230.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed