结构扩展的非负矩阵分解社区发现算法

doi:10.6040/j.issn.1672-3961.0.2020.231

摘要/Abstract

摘要： 提出结构扩展的非负矩阵分解社区发现算法(nonnegative matrix factorization with structure extension, NMF-SE),通过结构扩展,加强相邻节点结构相似性,提高节点间连接的稠密度,从而提高非负矩阵分解在社区发现中的表现。结构扩展过程使节点将自身结构以一定的比例传递给周围的节点,从而使相邻节点间能够得到对方的拓扑结构信息。该过程构造了新的特征矩阵,使非负矩阵分解(nonnegative matrix factorization, NMF)更好地适用于社区发现,在图正则化的半监督任务中能更好地融合先验信息。在人工网络和真实网络上进行试验验证的结果表明,NMF-SE算法有效提高了复杂网络社区发现的准确性。

关键词: 复杂网络, 社区发现, 非负矩阵分解, 特征矩阵, 结构扩展, 图正则化

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

中图分类号:

TP391

林晓炜,陈黎飞. 结构扩展的非负矩阵分解社区发现算法[J]. 山东大学学报 (工学版), 2021, 51(2): 57-64.

LIN Xiaowei, CHEN Lifei. Community detection using nonnegative matrix factorization with structure extension[J]. Journal of Shandong University(Engineering Science), 2021, 51(2): 57-64.

参考文献

[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.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed