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

doi:10.3969/j.issn.1001-2400.2018.02.008

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

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.

References

［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]	FU Lidong;GAO Lin. Kernel k-means clustering algorithm for detecting communities in complex networks based on eigenvector [J]. J4, 2012, 39(2): 175-180.
[2]	FU Li-dong;GAO Lin. Spectral approach to finding communities in networks based on the modularity density [J]. J4, 2010, 37(5): 916-920+965.
[3]	CHEN Ying-hui;DU Hai-feng;LI Shu-zhuo. Modified modularity and the corresponding community structure detecting algorithm [J]. J4, 2010, 37(2): 374-379.

Evolutionary spectral approach to finding communities in dynamic networks

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Metrics

Comments

Recommended 10