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     Next 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)

888

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] Gang HU, Lemeng WANG, Zhiyu LU, Qin WANG, Xiang XU. Importance identification method based on multi-order neighborhood hierarchical association contribution of nodes [J]. Journal of Shandong University(Engineering Science), 2024, 54(1): 1-10.
[2] Ying LI,Jiankun WANG. The classification of mild cognitive impairment based on supervised graph regularization and information fusion [J]. Journal of Shandong University(Engineering Science), 2023, 53(4): 65-73.
[3] Fengbo LAI,Bing XU,Ying XU,Lei ZHANG,Yirong SUN. Study on topological characteristics and node centrality of high-speed railway complex network [J]. Journal of Shandong University(Engineering Science), 2022, 52(6): 14-22.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] 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.
[11] 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.
[12] 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   
[1] LI Kan . Empolder and implement of the embedded weld control system[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 37 -41 .
[2] SHI Lai-shun,WAN Zhong-yi . Synthesis and performance evaluation of a novel betaine-type asphalt emulsifier[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 112 -115 .
[3] LAI Xiang . The global domain of attraction for a kind of MKdV equations[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 87 -92 .
[4] YU Jia yuan1, TIAN Jin ting1, ZHU Qiang zhong2. Computational intelligence and its application in psychology[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 1 -5 .
[5] LI Liang, LUO Qiming, CHEN Enhong. Graph-based ranking model for object-level search
[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 15 -21 .
[6] CHEN Rui, LI Hongwei, TIAN Jing. The relationship between the number of magnetic poles and the bearing capacity of radial magnetic bearing[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(2): 81 -85 .
[7] WANG Bo,WANG Ning-sheng . Automatic generation and combinatory optimization of disassembly sequence for mechanical-electric assembly[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 52 -57 .
[8] ZHANG Ying,LANG Yongmei,ZHAO Yuxiao,ZHANG Jianda,QIAO Peng,LI Shanping . Research on technique of aerobic granular sludge cultivationby seeding EGSB anaerobic granular sludge[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(4): 56 -59 .
[9] Yue Khing Toh1， XIAO Wendong2， XIE Lihua1. Wireless sensor network for distributed target tracking: practices via real test bed development[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 50 -56 .
[10] SUN Weiwei， WANG Yuzhen. Finite gain stabilization of singlemachine infinite bus system subject to saturation[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 69 -76 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd