进化谱分算法检测动态网络社团结构

doi:10.3969/j.issn.1001-2400.2018.02.008

西安电子科技大学学报

进化谱分算法检测动态网络社团结构

付立冬1,2;马小科2;聂靖靖1

(1. 西安科技大学计算机学院，陕西西安 710054;
2. 西安电子科技大学计算机学院，陕西西安 710071)

收稿日期:2017-04-18 出版日期:2018-04-20 发布日期:2018-06-06
通讯作者: 马小科(1982-)，男，副教授，E-mail: xkma@xidian.edu.cn
作者简介:付立冬(1973-)，男，西安电子科技大学博士研究生，E-mail: fulidong2005@163.com
基金资助:
国家自然科学基金资助项目(61502363, 61672406)；陕西省自然科学基金资助项目(2016JQ6044)；中央高校基本科研业务费专项资金资助项目(JB160306, BDY181417)；陕西省教育厅科学研究计划重点资助项目(16JZ040)

Evolutionary spectral approach to finding communities in dynamic networks

FU Lidong1,2;MA Xiaoke2;NIE Jingjing1

(1. The School of Computer, Xi'an Univ. of Science and Technology, Xi'an 710054, China;
2. School of Computer Science and Technology, Xidian Univ., Xi'an 710071, China)

Received:2017-04-18 Online:2018-04-20 Published:2018-06-06

摘要/Abstract

摘要：

为有效地检测动态复杂网络中的社团结构，在进化时间平滑框架下对模块函数及模块密度函数进行了优化．通过两种函数的优化进程，论证了模块函数及模块密度函数可在进化框架下作为进化谱分聚类方法检测动态网络中社团结构的理论基础，在此理论基础上提出了检测动态网络社团结构的进化谱分算法．在计算机合成的动态网络及真实世界动态网络中，检验了该算法的合理性及准确性并与其他方法进行了比较．实验结果显示，这种新的算法仍有很高的准确性．

关键词: 动态网络, 社团结构, 模块函数, 模块密度, 进化谱分

Abstract:

To effectively detect community structure in dynamic complex networks, modularity and modularity density functions are optimized under the evolutionary framework. By optimizing these two functions, we prove that optimizing these two functions can be reformulated as an evolutionary spectral optimization problem, and novel evolutionary spectral clustering algorithms are proposed. Compared to state-of-the-art approaches, the proposed algorithms are more accurate for both the simulated networks and real world dynamic networks.

Key words: dynamic networks, community structure, modularity, modularity density, evolutionary spectral clustering

付立冬;马小科;聂靖靖. 进化谱分算法检测动态网络社团结构[J]. 西安电子科技大学学报, 2018, 45(2): 43-47+53.

FU Lidong;MA Xiaoke;NIE Jingjing. Evolutionary spectral approach to finding communities in dynamic networks[J]. Journal of Xidian University, 2018, 45(2): 43-47+53.

参考文献

［1］ PALLA G, BARABSI A L, VICSEK T. Quantifying Social Group of Evolution［J］. Nature, 2007, 466(5): 664-667.
［2］ NEWMAN M E J. Finding Community Structure in Networks Using the Eigenvectors of Matrices［J］. Physical Review E, 2006, 74(3): 036104.
［3］ YU L, WANG B B, MA X K, et al. The Extraction of Drug-disease Correlations Based on Module Distance in Incomplete Human Interactome［J］. BMC Systems Biology, 2016, 10(111): 532-548.
［4］ GUO X L, GAO L, LIAO Q, et al. Long Non-coding RNAs Function Annotation: a Global Prediction Method Based on Bi-colored Networks［J］. Nucleic Acids Research, 2013, 41(2): e35.
［5］ NEWMAN M E J. Modularity and Community Structure in Networks［J］. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(23): 8577-8582.
［6］ WANG P Z, GAO L, MA X K. Dynamic Community Detection Based on Network Structural Perturbation and Topological Similarity［J］. Journal of Statistical Mechanics: Theory and Experiment, 2017, 2017(1): 013401.
［7］ YANG Y J, YU J X, GAO H, et al. Mining Most Frequently Changing Component in Evolving Graphs［J］. World Wide Web, 2014, 17(3): 351-376.
［8］ YANG C, ZHANG X, ZHONG C, et al. A Spatiotemporal Compression Based Approach for Efficient Big Data Processing on Cloud［J］. Journal of Computer and System Sciences, 2014, 80(8): 1563-1583.
［9］ CRAENEL B D, BERXL G. Regulatory Networks Defining EMT During Cancer Initiation and Progression［J］. Nature Review Cancer, 2013, 13: 97-110.
［10］ FOLINO F, PIZZUTI C. An Evolutionary Multiobjective Approach for Community Discovery in Dynamic Networks［J］. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(8): 1838-1852.
［11］黄伟华, 马中, 戴新发, 等. 一种特征加权模糊聚类的负载均衡算法［J］. 西安电子科技大学学报, 2017, 44(2): 127-132.
HUANG Weihua, MA Zhong, DAI Xinfa, et al. Fuzzy Clustering Based Load Balancing Algorithm with Feature Weighted［J］. Journal of Xidian University, 2017, 44(2): 127-132.
［12］李翠芸, 王精毅, 姬红兵, 等. 模型参数未知时的CPHD多目标跟踪方法［J］. 西安电子科技大学学报, 2017, 44(2): 37-41.
LI Cuiyun, WANG Jingyi, JI Hongbing, et al. CPHD Multi-target Tracking Algorithm with Unknown Model Parameters［J］. Journal of Xidian University, 2017, 44(2): 37-41.
［13］ MA X K, DONG D. Evolutionary Nonnegative Matrix Factorization Algorithms for Community Detection in Dynamic Networks［J］. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(5): 1045-1058.
［14］ FOLINO F, PIZZUTI C. An Evolutionary Behavior of Interaction Graph［J］. IEEE Transactions on Knowledge and Data Engineering, 2014, 26: 1838-1852.

[1]	郝修清;李俊民. 拓扑结构时变的复杂动态网络的自适应同步 [J]. J4, 2015, 42(2): 102-107.
[2]	郝修清;李俊民. 非一致节点的未知复杂动态网络的自适应同步[J]. J4, 2014, 41(4): 71-76.
[3]	王玙;高琳. 动态网络桥系数增量聚类算法[J]. J4, 2013, 40(1): 30-35.
[4]	李俊民;曹梦涛;沈思. 时变复杂动态网络非脆弱同步算法[J]. J4, 2012, 39(5): 119-125+185.
[5]	付立东;高琳. 特征向量的核方法检测网络社团结构[J]. J4, 2012, 39(2): 175-180.
[6]	付立东;高琳. 模块密度谱分的网络社团发现方法[J]. J4, 2010, 37(5): 916-920+965.

进化谱分算法检测动态网络社团结构

Evolutionary spectral approach to finding communities in dynamic networks

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

Metrics

本文评价

推荐阅读 10