Journal of Shandong University(Engineering Science) ›› 2021, Vol. 51 ›› Issue (2): 57-64.doi: 10.6040/j.issn.1672-3961.0.2020.231

Previous Articles    

Community detection using nonnegative matrix factorization with structure extension

LIN Xiaowei1,2, CHEN Lifei1,2*   

  1. 1. College of Mathematics and Informatics, Fujian Normal University, Fuzhou 350117, Fujian, China;
    2. Digital Fujian Internet-of-Things Laboratory of Environmental Monitoring, Fujian Normal University, Fuzhou 350117, Fujian, China
  • Published:2021-04-16

PDF (PC)

351

Abstract: Nonnegative matrix factorization with structure extension(NMF-SE)was proposed to enhance the structural similarity of adjacent nodes and increase the density of connections between nodes, which improved the performance of nonnegative matrix factorization in community detection. In the process of structure extension, nodes transmitted their own structure to the surrounding nodes in a certain proportion, so that adjacent nodes could get the topology information from each other. This process constructed a new feature matrix, which made nonnegative matrix factorization(NMF)more suitable for community detection. Meanwhile, in the semi-supervised task with graph regularization, the prior information could be better incorporated. The experimental results on synthetic network and real network showed that NMF-SE algorithm effectively improved the accuracy of community detection in complex network.

Key words: complex network, community detection, nonnegative matrix factorization, feature matrix, structure extension, graph regularization

CLC Number: 

  • TP391
[1] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826.
[2] NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2):167-256.
[3] GLIGORIJEVIC V, PANAGAKIS Y, ZAFEIRIOU S P. Non-negative matrix factorizations for multiplex network analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2019, 41(4): 928-940.
[4] NEWMAN M E J, GIRVAN M. Finding and evaluatingcommunity structure in networks[J]. Phys Rev E, 2004, 69(2): 026113.
[5] BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large networks[J]. J Stat Mech-Theory E, 2008, 2008(10): 10008.
[6] SHI Jianbo, JITENDRA Malik. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8):888-905.
[7] RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E: Statistical Nonlinear and Soft Matter Physics, 2007, 76(3): 036106.
[8] LEE D D, SEUNG H S. Learning the parts of objects by non-negative matrix factorization[J]. Nature, 1999, 401(6755): 788-791.
[9] LI Yafan, JIA Caiyan, YU Jian. Survey on community detection algorithms using nonnegative matrix factorization model[J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(1): 1-13.
[10] ZHANG Shihua, WANG Ruisheng, ZHANG Xiangsun. Uncovering fuzzy community structure in complex networks[J]. Physical Review E: Statistical Nonlinear and Soft Matter Physics, 2007, 76(4): 046103.
[11] WANG Fei, LI Tao, WANG Xin, et al. Community discovery using nonnegative matrix factorization[J]. Data Mining and Knowledge Discovery, 2011, 22(3): 493-521.
[12] MA Xiaoke, GAO Lin, YONG Xuerong, et al. Semi-supervised clustering algorithm for community structure detection in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2010, 389(1): 187-197.
[13] YANG Liang, CAO Xiaochun, JIN Di, et al. A unified semi-supervised community detection framework using latent space graph regularization[J]. IEEE Transactions on Cybernetics, 2015, 45(11): 2585-2598.
[14] CAI Deng, HE Xiaofei, HAN Jiawei, et al. Graph regularized nonnegative matrix factorization for data representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 33(8): 1548-1560.
[15] MA Xiaoke, SUN Penggang, WANG Yu. Graph regularized nonnegative matrix factorization for temporal link prediction in dynamic networks[J]. Physica A: Statis-tical Mechanics and Its Applications, 2018, 496: 121-136.
[16] PEI Yulong, CHAKRABORTY N, SYCARA K P. Nonnegative matrix tri-factorization with graph regulari-zation for community detection in social networks[C] //Proceedings of the International Conference on Artificial Intell-igence. California, USA: AAAI Press, 2015:2083-2089.
[17] LAFFERTY J, RISI I K. Kernels on graphs and other discrete input spaces[C] //Proceedings of the International Conference on Machine Learning. San Francisco, USA: Margan Kaufmann Press, 2002:315-322.
[18] CAI Deng, HE Xiaofei, WU Xiaoyun, et al. Non-negative matrix factorization on manifold[C] //Proceedings of the International Conference on Data Mining.New York, USA: IEEE Press, 2008:63-72.
[19] LIU Xiao, WANG Wenjun, HE Dongxiao, et al. Semi-supervised community detection based on non-negative matrix factorization with node popularity[J]. Information Sciences, 2017, 381:304-321.
[20] LEE D D, SEUNG H S. Algorithms for non-negative matrix factorization[C] //Proceedings of the Neural Information Processing Systems. Massachusetts, USA: MIT Press, 2001, 13:556-562.
[21] WANG Dingding, LI Tao, ZHU Shenghuo, et al. Multi-document summarization via sentence-level semantic analysis and symmetric matrix factorization[C] //Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, USA: ACM Press, 2008:307-314.
[22] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E Statistical Nonlinear and Soft Matter Physics, 2008, 78(4): 046110.
[23] NEWMAN M E J. Modularity andcommunity structure in networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(23): 8577-8582.
[24] FORTUNATO S, BARTHELEMY M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1): 36-41.
[25] DANON L, DIAZ-GUILERA A, DUCH J, et al. Comparing community structure identification[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005(9): P09008.
[1] HUANG Chengkai, YANG Hao, JIANG Bin, CHENG Shuyao. Fault tolerant cooperative control for a class of complex networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 203-209.
[2] ZHANG Yuting, LI Wang, WANG Chenguang, LIU Youquan, SHI Hongjun. Synchronization of time-delayed complex dynamical networks with discontinuous coupling [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(4): 43-49.
[3] LI Wang, MA Zhicai, SHI Hongjun. Finite-time stochastic generalized outer synchronization of time-delayed complex dynamical networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(3): 1-8.
[4] HAO Chongqing, WANG Zhihong. Classification and analysis of epileptic EEG based on complex networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(3): 8-15.
[5] LYU Zhen, LI Suxue, ZHANG Chuanting, YUAN Dongfeng. An improved CNM algorithm based on network structure information [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(1): 37-41.
[6] CHU Xiaodong, ZHANG Rongxiang, HUANG Haoyi, TANG Maosen. Synergetic physical-cyber simulation platform for global energy interconnection [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(4): 103-110.
[7] LI Xinyu, XU Guiyun, REN Shijin, YANG Maoyun. Discriminative manifold-based uncorrelated sparse projective nonnegative matrix factorization [J]. Journal of Shandong University(Engineering Science), 2015, 45(5): 1-12.
[8] LI Wang1,2, SHI Yong2, MA Ji-wei2. Finite-time outer synchronization of complex dynamical networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2013, 43(2): 48-53.
[9] ZHAO Yong-qing, JIANG Ming-hui. Adaptive synchronous feedback control of mixed time-varying delayed and double-linked complex networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 61-68.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd