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

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.

相关文章 15

[1]	王英楠,郑文萍,杨贵. 基于双视角网络嵌入聚类集成社区发现算法[J]. 山东大学学报 (工学版), 2025, 55(1): 41-50.
[2]	武凯丽,陈京荣. 基于节点重要性排序的局部社区检测算法[J]. 山东大学学报 (工学版), 2025, 55(1): 77-85.
[3]	林振宇,邵蓥侠. 基于盖根堡多项式最佳平方近似的谱图网络[J]. 山东大学学报 (工学版), 2024, 54(5): 93-100.
[4]	胡钢, 王乐萌, 卢志宇, 王琴, 徐翔. 基于节点多阶邻居递阶关联贡献度的重要性辨识[J]. 山东大学学报 (工学版), 2024, 54(1): 1-10.
[5]	李颖,王建坤. 基于监督图正则化和信息融合的轻度认知障碍分类方法[J]. 山东大学学报 (工学版), 2023, 53(4): 65-73.
[6]	来逢波,许冰,续颖,张蕾,孙义荣. 高铁复杂网络拓扑特征及节点中心性研究[J]. 山东大学学报 (工学版), 2022, 52(6): 14-22.
[7]	赵康,田浩,马欢,杨冬. 基于复杂网络理论的多直流馈入受端电网优化分区方法[J]. 山东大学学报 (工学版), 2022, 52(1): 128-134.
[8]	黄成凯,杨浩,姜斌,程舒瑶. 一类复杂网络的协同容错控制[J]. 山东大学学报(工学版), 2017, 47(5): 203-209.
[9]	张玉婷,李望,王晨光,刘友权,侍红军. 不连续耦合的时滞复杂动态网络的同步[J]. 山东大学学报(工学版), 2017, 47(4): 43-49.
[10]	郝崇清,王志宏. 基于复杂网络的癫痫脑电分类与分析[J]. 山东大学学报(工学版), 2017, 47(3): 8-15.
[11]	李望,马志才,侍红军. 时滞复杂动态网络的有限时间随机广义外部同步[J]. 山东大学学报(工学版), 2017, 47(3): 1-8.
[12]	王鑫,陆静雅,王英. 面向推荐的用户兴趣扩展方法[J]. 山东大学学报(工学版), 2017, 47(2): 71-79.
[13]	吕振,李苏雪,张传亭,袁东风. 一种基于结构信息的改进CNM算法[J]. 山东大学学报(工学版), 2017, 47(1): 37-41.
[14]	褚晓东,张荣祥,黄昊怡,唐茂森. 全球能源互联网物理-信息系统协同仿真平台[J]. 山东大学学报(工学版), 2016, 46(4): 103-110.
[15]	李新玉, 徐桂云,任世锦,杨茂云. 基于鉴别流形的不相关稀疏投影非负矩阵分解[J]. 山东大学学报 (工学版), 2015, 45(5): 1-12.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed