J Shanghai Jiaotong Univ Sci

Journal of Shanghai Jiaotong University(Science) >

2024 , Vol. 29 >Issue 6: 1037 - 1049

DOI: https://doi.org/10.1007/s12204-022-2503-9

Medicine-Engineering Interdisciplinary

Symmetric Nonnegative Matrix Factorization for Vertex Centrality in Complex Networks

  • 卢鹏丽1，陈玮1，郭育红2，陈娅红3
Expand
  • （1. School of Computer and Communication, Lanzhou University of Technology, Lanzhou 730050, China; 2. School of Mathematics and Statistics, Hexi University, Zhangye 734000, Gansu, China; 3. Department of Mathematics, Lishui University, Lishui 323000, Zhejiang, China)

Accepted date: 2021-07-01

  Online published: 2024-11-28

Fold

Abstract

One of the most important problems in complex networks is to identify the influential vertices for understanding and controlling of information diffusion and disease spreading. Most of the current centrality algorithms focus on single feature or manually extract the attributes, which occasionally results in the failure to fully capture the vertex’s importance. A new vertex centrality approach based on symmetric nonnegative matrix factorization (SNMF), called VCSNMF, is proposed in this paper. For highlight the characteristics of a network,the adjacency matrix and the degree matrix are fused to represent original data of the network via a weighted linear combination. First, SNMF automatically extracts the latent characteristics of vertices by factorizing the established original data matrix. Then we prove that each vertex’s composite feature which is constructed with one-dimensional factor matrix can be approximated as the term of eigenvector associated with the spectral radius of the network, otherwise obtained by the factor matrix on the hyperspace. Finally, VCSNMF integrates the composite feature and the topological structure to evaluate the performance of vertices. To verify the effectiveness of the VCSNMF criterion, eight existing centrality approaches are used as comparison measures to rank influential vertices in ten real-world networks. The experimental results assert the superiority of the method.

Cite this article

卢鹏丽1，陈玮1，郭育红2，陈娅红3 . Symmetric Nonnegative Matrix Factorization for Vertex Centrality in Complex Networks[J]. Journal of Shanghai Jiaotong University(Science), 2024 , 29(6) : 1037 -1049 . DOI: 10.1007/s12204-022-2503-9

References

[1] BORGE-HOLTHOEFER J, MORENO Y. Absence of influential spreaders in rumor dynamics [J]. Physical Review E, 2012, 85(2 Pt 2): 026116.
[2] ZHANG Y M, LIU F, KOURA Y H, et al. Dynamics of a delayed interactive model applied to information dissemination in social networks [J]. Mathematical Problems in Engineering, 2021, 2021: 6611168.
[3] ZHANG X H, ZHU J, WANG Q, et al. Identifying influential nodes in complex networks with community structure [J]. Knowledge-Based Systems, 2013, 42: 74-84.
[4] OMAR K M, HERZALLAH F A, AYYASH M M. The impact of viral marketing strategy via social network sites on student’s image: A case study at Palestine Technical University-Kadoorie [J]. Journal of Theoretical and Applied Information Technology, 2021, 99(2):420-435.
[5] SUNG E C. The effects of augmented reality mobile app advertising: Viral marketing via shared social experience [J]. Journal of Business Research, 2021, 122:75-87.
[6] MORONE F, MAKSE H A. Influence maximization in complex networks through optimal percolation [J].Nature, 2015, 524(7563): 65-68.
[7] WANG R J. Local information based model for epidemic controlling on multiplex networks [C]//2020 IEEE 5th Information Technology and Mechatronics Engineering Conference. Chongqing: IEEE, 2020: 20-24.
[8] MA X K, SUN P G, GONG M G. An integrative framework of heterogeneous genomic data for cancer dynamic modules based on matrix decomposition [J].IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2022, 19(1): 305-316.
[9] FREEMAN L C. Centrality in social networks conceptual clarification [J]. Social Networks, 1978, 1(3):215-239.
[10] FREEMAN L C. A set of measures of centrality based on betweenness [J]. Sociometry, 1977, 40(1): 35.
[11] SABIDUSSI G. The centrality index of a graph [J].Psychometrika, 1966, 31(4): 581-603.
[12] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks [J].Nature Physics, 2010, 6(11): 888-893.
[13] BONACICH P. Factoring and weighting approaches to status scores and clique identification [J]. The Journal of Mathematical Sociology, 1972, 2(1): 113-120.
[14] LIU Z H, JIANG C, WANG J Y, et al. The node importance in actual complex networks based on a multiattribute ranking method [J]. Knowledge-Based Systems, 2015, 84: 56-66.
[15] ZAREIE A, SHEIKHAHMADI A. A hierarchical approach for influential node ranking in complex social networks [J]. Expert Systems with Applications, 2018,93: 200-211.
[16] LI C, WANG L, SUN S W, et al. Identification of influential spreaders based on classified neighbors in realworld complex networks [J]. Applied Mathematics and Computation, 2018, 320: 512-523.
[17] SALAVATI C, ABDOLLAHPOURI A, MANBARI Z.BridgeRank: A novel fast centrality measure based on local structure of the network [J]. Physica A: Statistical Mechanics and its Applications, 2018, 496: 635-653.
[18] ZHAO Z J, GUO Q, YU K, et al. Identifying influential nodes for the networks with community structure [J].Physica A: Statistical Mechanics and Its Applications,2020, 551: 123893.
[19] BERTUCCI F, NG C K Y, PATSOURIS A, et al. Genomic characterization of metastatic breast cancers [J].Nature, 2019, 569(7757): 560-564.
[20] SHEREKAR S, VISWANATHAN G A. Boolean dynamic modeling of cancer signaling networks: Prognosis, progression, and therapeutics [J]. Computational and Systems Oncology, 2021, 1(2): e1017.
[21] ZHANG Z Y, WANG Y, AHN Y Y. Overlapping community detection in complex networks using symmetric binary matrix factorization [J]. Physical Review E,2013, 87(6): 062803.
[22] WASSERMAN S, FAUST K. Social network analysis:Methods and applications [M]. Cambridge: Cambridge University Press, 1994.
[23] LI M T, ZHANG R S, HU R J, et al. Identifying and ranking influential spreaders in complex networks by combining a local-degree sum and the clustering coefficient [J]. International Journal of Modern Physics B,2018, 32(6): 1850118.
[24] FEI L G, ZHANG Q, DENG Y. Identifying influential nodes in complex networks based on the inverse-square law [J]. Physica A: Statistical Mechanics and its Applications, 2018, 512: 1044-1059.
[25] SHENG J F, DAI J Y, WANG B, et al. Identifying influential nodes in complex networks based on global and local structure [J]. Physica A: Statistical Mechanics and its Applications, 2020, 541: 123262.
[26] ZHAO J, WANG Y C, DENG Y. Identifying influential nodes in complex networks from global perspective [J].Chaos, Solitons & Fractals, 2020, 133: 109637.
[27] GU M, EISENSTAT S C. Efficient algorithms for computing a strong rank-revealing QR factorization [J].SIAM Journal on Scientific Computing, 1996, 17(4):848-869.
[28] ACAR E, DUNLAVY D M, KOLDA T G. Link prediction on evolving data using matrix and tensor factorizations [C]//2009 IEEE International Conference on Data Mining Workshops. Miami: IEEE, 2009: 262-269.
[29] LEE D D, SEUNG H S. Algorithms for non-negative matrix factorization [M]// Advances in neural information processing systems 13. Red Hook: Curran Associates Inc., 2000.
[30] BROUWER A E, HAEMERS W H. Spectra of graphs[M]. New York: Springer, 2012: 25-26.
[31] BAPAT R B, RAGHAVAN T E S. Nonnegative matrices and applications [M]. Cambridge: Cambridge University Press, 1997: 17.
[32] BIGGS N. Algebraic graph theory [M]. Cambridge:Cambridge University Press, 1974: 13.
[33] HORN R A. The Hadamard product [C]// Symposia in Applied Mathematics. Providence: AMS, 1990: 87-169.
[34] ZACHARY W W. An information flow model for conflict and fission in small groups [J]. Journal of Anthropological Research, 1977, 33(4): 452-473.
[35] LUSSEAU D, SCHNEIDER K, BOISSEAU O J, et al.The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations [J]. Behavioral Ecology and Sociobiology, 2003, 54(4): 396-405.
[36] GLEISER P M, DANON L. Community structure in jazz [J]. Advances in Complex Systems, 2003, 6(4):565-573.
[37] LV Z W, ZHAO N, XIONG F, et al. A novel measure of identifying influential nodes in complex networks [J].Physica A: Statistical Mechanics and Its Applications, 2019, 523: 488-497.
[38] GUIMERA R, DANON L, DIAZ-GUILERA A, et al.Self-similar community structure in a network of human interactions [J]. Physical Review E, 2003, 68(6):065103.
[39] ADAMIC L A, GLANCE N. The political blogosphere and the 2004 US election: Divided they blog [C]// 3rd International Workshop on Link Discovery. Chicago: ACM, 2005: 36-43.
[40] JEONG H, MASON S P, BARABASI A L, et al.Lethality and centrality in protein networks [J]. Nature, 2001, 411(6833): 41-42.
[41] ZAREIE A, SHEIKHAHMADI A, JALILI M. Influential node ranking in social networks based on neighborhood diversity [J]. Future Generation Computer Systems, 2019, 94: 120-129.
[42] MCAULEY J, LESKOVEC J. Learning to discover social circles in ego networks [M]// Advances in neural information processing systems 25. Red Hook: Curran Associates Inc., 2012: 539-547.
[43] WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks [J]. Nature, 1998, 393(6684):440-442.
[44] HUANG C Y, LEE C L, WEN T H, et al. A computer virus spreading model based on resource limitations and interaction costs [J]. Journal of Systems and Software, 2013, 86(3): 801-808.
[45] KENDALL M G. The treatment of ties in ranking problems [J]. Biometrika, 1945, 33(3): 239-251.
[46] BAE J, KIM S. Identifying and ranking influential spreaders in complex networks by neighborhood coreness [J]. Physica A: Statistical Mechanics and Its Applications, 2014, 395: 549-559.
[47] WEBBER W, MOFFAT A, ZOBEL J. A similarity measure for indefinite rankings [J]. ACM Transactions on Information Systems, 2010, 28(4): 20.
Options
Outlines

/

〈 〉