nach oben

Neural Processing Letters

Erschienen in:

07.01.2020

Community Detection in Complex Networks Using Nonnegative Matrix Factorization and Density-Based Clustering Algorithm

verfasst von: Hong Lu, Qinghua Zhao, Xiaoshuang Sang, Jianfeng Lu

Erschienen in: Neural Processing Letters | Ausgabe 2/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Community detection is a critical issue in the field of complex networks. Capable of extracting inherent patterns and structures in high dimensional data, the non-negative matrix factorization (NMF) method has become one of the hottest research topics in community detection recently. However, this method has a significant drawback; most community detection methods using NMF require the number of communities to be preassigned or determined by searching for the best community structure among all candidates. To address the problem, in this paper, we use an improved density peak clustering to obtain the number of cores as the pre-defined parameter of nonnegative matrix factorization. Then we adopt nonnegative double singular value decomposition initialization which can rapidly reduce the approximation error of nonnegative matrix factorization. Finally, we compare and analyze the performance of different algorithms on artificial networks and real-world networks. Experimental results indicate that the proposed method is superior to the state-of-the-art methods.

Vorheriger Artikel General and Improved Five-Step Discrete-Time Zeroing Neural Dynamics Solving Linear Time-Varying Matrix Equation with Unknown Transpose

Nächster Artikel -Almost Periodic Solutions of Clifford-Valued Fuzzy Cellular Neural Networks with Time-Varying Delays

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Girvan M, Newman ME (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821–7826MathSciNetMATH

Lu H, Zhu X, Liu H, Skogerbøphi G, Zhang J, Zhang Y, Bu D (2004) The interactome as a tree—an attempt to visualize the protein–protein interaction network in yeast. Nucleic Acids Res 32(16):4804–4811

Leskovec J, Lang KJ, Dasgupta A et al (2009) Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math 6(1):29–123MathSciNetMATH

Newman M (2018) Networks. Oxford University Press, OxfordMATH

Newman ME (2004) Fast algorithm for detecting community structure in networks. Phys Rev E 69(6):066133

Newman ME (2006) Modularity and community structure in networks. Proc Natl Acad Sci 103(23):8577–8582

Duch J, Arenas A (2005) Community detection in complex networks using extremal optimization. Phys Rev E 72(2):027104

Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008(10):P10008MATH

Li HJ, Wang Y, Wu LY, Liu ZP, Chen L, Zhang XS (2012) Community structure detection based on Potts model and network’s spectral characterization. EPL (Europhys Lett) 97(4):48005

10.

Jin H, Wang S, Li C (2013) Community detection in complex networks by density-based clustering. Phys A Stat Mech Appl 392(19):4606–4618

11.

Jiang Y, Jia C, Yu J (2013) An efficient community detection method based on rank centrality. Phys A Stat Mech Appl 392(9):2182–2194MathSciNet

12.

Lai D, Lu H (2008) Identification of community structure in complex networks using affinity propagation clustering method. Mod Phys Lett B 22(16):1547–1566MATH

13.

Zhang XS, Li Z, Wang RS, Wang Y (2012) A combinatorial model and algorithm for globally searching community structure in complex networks. J Comb Optim 23(4):425–442MathSciNetMATH

14.

Huang J, Sun H, Song Q, Deng H, Han J (2013) Revealing density-based clustering structure from the core-connected tree of a network. IEEE Trans Knowl Data Eng 25(8):1876–1889

15.

Rosvall M, Bergstrom CT (2008) Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci 105(4):1118–1123

16.

Wang W, Liu D, Liu X, Pan L (2013) Fuzzy overlapping community detection based on local random walk and multidimensional scaling. Phys A Stat Mech Appl 392(24):6578–6586

17.

Zhang ZY, Wang Y, Ahn YY (2013) Overlapping community detection in complex networks using symmetric binary matrix factorization. Phys Rev E 87(6):062803

18.

Zhang ZY, Ahn YY (2015) Community detection in bipartite networks using weighted symmetric binary matrix factorization. Int J Mod Phys C 26(09):1550096MathSciNet

19.

Yang L, Jin D, Wang X, Cao X (2015) Active link selection for efficient semi-supervised community detection. Sci Rep 5:9039

20.

He YC, Lu HT, Huang L, Sh XH (2015) Non-negative matrix factorization with pairwise constraints and graph laplacian. Neural Process Lett 42(1):167–185

21.

Fortunato S (2010) Community detection in graphs. Phys Rep 486(3–5):75–174MathSciNet

22.

Xie J, Kelley S, Szymanski BK (2013) Overlapping community detection in networks: the state-of-the-art and comparative study. ACM Comput Surv (CSUR) 45(4):43MATH

23.

Wu W, Kwong S, Zhou Y, Jia Y, Gao W (2018) Nonnegative matrix factorization with mixed hypergraph regularization for community detection. Inf Sci 435:263–281MathSciNet

24.

Li W, Xie J, Xin M, Mo J (2018) An overlapping network community partition algorithm based on semi-supervised matrix factorization and random walk. Expert Syst Appl 91:277–285

25.

Chen N, Liu Y, Chao HC (2017) Overlapping community detection using non-negative matrix factorization with orthogonal and sparseness constraints. IEEE Access 6:21266–21274

26.

Ma X, Gao L, Yong X, Fu L (2010) Semi-supervised clustering algorithm for community structure detection in complex networks. Phys A Stat Mech Appl 389(1):187–197

27.

Shi X, Lu H, He Y, He S (2015) Community detection in social network with pairwisely constrained symmetric non-negative matrix factorization. In: 2015 IEEE/acm international conference on advances in social networks analysis and mining (ASONAM), pp 541–546

28.

Rodriguez A, Laio A (2014) Clustering by fast search and find of density peaks. Science 344(6191):1492–1496CrossRef

29.

Lin YR, Sun J, Castro P, Konuru R, Sundaram H, Kelliher A (2009) Metafac: community discovery via relational hypergraph factorization. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 527–536

30.

Psorakis I, Roberts S, Ebden M, Sheldon B (2011) Overlapping community detection using bayesian non-negative matrix factorization. Phys Rev E 83(6):066114

31.

Wang F, Li T, Wang X, Zhu S, Ding C (2011) Community discovery using nonnegative matrix factorization. Data Min Knowl Discov 22(3):493–521MathSciNetMATH

32.

Zhang Y, Yeung DY (2012) Overlapping community detection via bounded nonnegative matrix tri-factorization. In: Proceedings of the 18th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 606–614

33.

He D, Jin D, Baquero C, Liu D (2014) Link community detection using generative model and nonnegative matrix factorization. PloS One 9(1):e86899

34.

Du M, Ding S, Jia H (2016) Study on density peaks clustering based on k-nearest neighbors and principal component analysis. Knowl Based Syst 99:135–145

35.

Xu M, Li Y, Li R, Zou F, Gu X (2019) EADP: an extended adaptive density peaks clustering for overlapping community detection in social networks. Neurocomputing 337:287–302

36.

Li Z, Tang Y (2018) Comparative density peaks clustering. Expert Syst Appl 95:236–247

37.

Mehmood R, Zhang G, Bie R, Dawood H, Ahmad H (2016) Clustering by fast search and find of density peaks via heat diffusion. Neurocomputing 208:210–217

38.

Liang Z, Chen P (2016) Delta-density based clustering with a divide-and-conquer strategy: 3DC clustering. Pattern Recognit Lett 73:52–59

39.

Yaohui L, Zhengming M, Fang Y (2017) Adaptive density peak clustering based on K-nearest neighbors with aggregating strategy. Knowl Based Syst 133:208–220

40.

Hou J, Xu E, Liu W (2018) Density based cluster growing via dominant sets. Neural Process Lett 48(2):933–954

41.

Xie J, Gao H, Xie W, Liu X, Grant PW (2016) Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors. Inf Sci 354:19–40

42.

Chen M, Li L, Wang B, Cheng J, Pan L, Chen X (2016) Effectively clustering by finding density backbone based-on kNN. Pattern Recognit 60:486–498

43.

Bai X, Yang P, Shi X (2017) An overlapping community detection algorithm based on density peaks. Neurocomputing 226:7–15

44.

Boutsidis C, Gallopoulos E (2008) SVD based initialization: a head start for nonnegative matrix factorization. Pattern Recognit 41(4):1350–1362MATH

45.

Yang L, Cao X, He D, Wang C, Wang X, Zhang W (2016) Modularity based community detection with deep learning. In: IJCAI, vol 16, pp 2252–2258

46.

Danon L, Diaz-Guilera A, Duch J, Arenas A (2005) Comparing community structure identification. J Stat Mech Theory Exp 2005(09):P09008MATH

47.

Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78(4):046110

48.

Kuang Da, Yun S, Park H (2015) SymNMF: nonnegative low-rank approximation of a similarity matrix for graph clustering. J Glob Optim 62(3):1–30MathSciNetMATH

Titel: Community Detection in Complex Networks Using Nonnegative Matrix Factorization and Density-Based Clustering Algorithm
verfasst von: Hong Lu
Qinghua Zhao
Xiaoshuang Sang
Jianfeng Lu
Publikationsdatum: 07.01.2020
Verlag: Springer US
Erschienen in: Neural Processing Letters / Ausgabe 2/2020
Print ISSN: 1370-4621
Elektronische ISSN: 1573-773X
DOI: https://doi.org/10.1007/s11063-019-10170-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2020

Class-specific discriminant regularization in real-time deep CNN models for binary classification problems

Fast Synchronization of Complex Networks via Aperiodically Intermittent Sliding Mode Control

Maintenance Personnel Detection and Analysis Using Mask-RCNN Optimization on Power Grid Monitoring Video

DNN-Based Cross-Lingual Voice Conversion Using Bottleneck Features

An Image Clustering Auto-Encoder Based on Predefined Evenly-Distributed Class Centroids and MMD Distance

Bi-directional LSTM Model with Symptoms-Frequency Position Attention for Question Answering System in Medical Domain