基于随机网络集成模型的广义网络社区挖掘算法

杨博; 刘杰; 刘大有

doi:10.3724/SP.J.1004.2012.00812

基于随机网络集成模型的广义网络社区挖掘算法

doi: 10.3724/SP.J.1004.2012.00812

杨博^1,2,
刘杰^1,2,
刘大有^1,2,

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

详细信息

通讯作者:
刘大有, 吉林大学计算机科学与技术学院教授. 主要研究方向为知识工程, 专家系统与不确定性推理, 时空推理, 分布式人工智能, 多Agent 和移动Agent 系统, 数据挖掘与多关系数据挖掘, 数据结构与计算机算法.

计量
- 文章访问数: 2224
- HTML全文浏览量: 101
- PDF下载量: 1151
- 被引次数: 0
出版历程
- 收稿日期: 2010-12-21
- 修回日期: 2011-12-19
- 刊出日期: 2012-05-20

A Random Network Ensemble Model Based Generalized Network Community Mining Algorithm

YANG Bo^1,2,
LIU Jie^1,2,
LIU Da-You^{1,2
,}

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

摘要

摘要: 根据结点的属性和链接关系,现实世界中的复杂网络大多可分为同配网络和异配网络,社区结构在这两类网络中均普遍存在. 准确地挖掘出两种不同类型网络的社区结构具有重要的理论意义和广泛的应用领域.由于待处理的网络类型通常未知, 因而难以事先确定应当选择何种类型的网络社区挖掘算法才能获得有意义的社区结构. 针对该问题, 本文提出了广义网络社区概念,力图将同配和异配网络社区结构统一起来. 本文提出了随机网络集成模型, 进而提出了广义网络社区挖掘算法G-NCMA. 实验结果表明: 该算法能够在网络类型未知的前提下准确地挖掘出有意义的社区结构, 并能分析出所得社区的类型特征.
- 复杂网络 /
- 社区挖掘 /
- 随机网络 /
- 极大似然估计
Abstract: According to the attributes of nodes and the linkages between them, most real-world complex networks could be assortative and disassortative. Community structures are ubiquitous in both types of networks. The ability to discovery meaningful community structures from both types of networks is fundamental for theoretical research and practical applications. Since the types of exploratory networks to be processed are usually unknown beforehand, it is difficult to determine what specific algorithms should be applied to them to obtain meaningful community structures. To address this issue, a novel concept of generalized network community is proposed in order to unify two concepts of assortative and disassortative communities. Based on a random network ensemble model, a generalized community mining algorithm, called G-NCMA, is proposed. Experimental results demonstrate that the G-NCMA algorithm is able to properly mine potential communities from explorative networks, as well as to determine their respective types.
- Complex network /
- community mining /
- random network /
- maximum likelihood estimation

HTML全文

参考文献(1)

[1]

Girvan M, Newman M E J. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826[2] Guimerá R, Amaral L A N. Functional cartography of complex metabolic networks. Nature, 2005, 433(7028): 895-900[3] Mucha P J, Richardson T, Macon K, Porter M A, Onnela J P. Community structure in time-dependent, multiscale, and multiplex networks. Science, 2010, 328(5980): 876-878[4] Newman M E J. Fast algorithm for detecting community structure in networks. Physical Review E, 2004, 69(6): 066133[5] Jin Di, Liu Jie, Yang Bo, He Dong-Xiao, Liu Da-You. Genetic algorithm with local search for community detection in large-scale complex networks. Acta Automatica Sinica, 2011, 37(7): 873-882 (金弟, 刘杰, 杨博, 何东晓, 刘大有. 局部搜索与遗传算法结合的大规模复杂网络社区探测. 自动化学报, 2011, 37(7): 873-882)[6] Yang B, Liu J M, Feng J F. On the spectral characterization and scalable mining of network communities. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(2): 326-337[7] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multiscale complexity in networks. Nature, 2010, 466(7307): 761-764[8] Yang T B, Chi Y, Zhu S H, Gong Y H, Jin R. Detecting communities and their evolutions in dynamic social networks — a Bayesian approach. Machine Learning, 2011, 82(2): 157-189[9] Newman M E J. Mixing patterns in networks. Physical Review E, 2003, 67(2): 026126[10] Newman M E J. Finding community structure in networks using the eigenvectors of matrices. Physical Review E, 2006, 74(3): 036104[11] Rosvall M, Bergstrom C T. An information-theoretic framework for resolving community structure in complex networks. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(18): 7327-7331[12] Newman M E J, Leicht E A. Mixture models and exploratory analysis in networks. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(23): 9564-9569

施引文献

资源附件(0)

访问统计

点击查看大图

计量

文章访问数: 2224
HTML全文浏览量: 101
PDF下载量: 1151
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

基于随机网络集成模型的广义网络社区挖掘算法

doi: 10.3724/SP.J.1004.2012.00812

通讯作者:
刘大有, 吉林大学计算机科学与技术学院教授. 主要研究方向为知识工程, 专家系统与不确定性推理, 时空推理, 分布式人工智能, 多Agent 和移动Agent 系统, 数据挖掘与多关系数据挖掘, 数据结构与计算机算法.

计量

A Random Network Ensemble Model Based Generalized Network Community Mining Algorithm

计量

目录

留言板

基于随机网络集成模型的广义网络社区挖掘算法

doi: 10.3724/SP.J.1004.2012.00812

通讯作者: 刘大有, 吉林大学计算机科学与技术学院教授. 主要研究方向为知识工程, 专家系统与不确定性推理, 时空推理, 分布式人工智能, 多Agent 和移动Agent 系统, 数据挖掘与多关系数据挖掘, 数据结构与计算机算法.

计量

出版历程

A Random Network Ensemble Model Based Generalized Network Community Mining Algorithm

计量

出版历程

目录

通讯作者:
刘大有, 吉林大学计算机科学与技术学院教授. 主要研究方向为知识工程, 专家系统与不确定性推理, 时空推理, 分布式人工智能, 多Agent 和移动Agent 系统, 数据挖掘与多关系数据挖掘, 数据结构与计算机算法.