Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
International Journal of Machine Learning and Cybernetics
Published in: International Journal of Machine Learning and Cybernetics 2/2020

24-07-2019 | Original Article

An augmented Lagrangian alternating direction method for overlapping community detection based on symmetric nonnegative matrix factorization

Authors: Liying Hu, Gongde Guo

Published in: International Journal of Machine Learning and Cybernetics | Issue 2/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, we present an augmented Lagrangian alternating direction algorithm for symmetric nonnegative matrix factorization. The convergence of the algorithm is also proved in detail and strictly. Then we present a modified overlapping community detection method which is based on the presented symmetric nonnegative matrix factorization algorithm. We apply the modified community detection method to several real world networks. The obtained results show the capability of our method in detecting overlapping communities, hubs and outliers. We find that our experimental results have better quality than several competing methods for identifying communities.
previous article A hybrid optimization approach based on clustering and chaotic sequences
next article A two-stage hybrid probabilistic topic model for refining image annotation

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Show more products
Literature
1.
Lee DD, Seung HS (1999) Learning the parts of objects by non-negative matrix factorization. Nature 401(6755):788–791CrossRef
2.
Lin L (2010) Alternative gradient algorithms with applications to nonnegative matrix factorizations. Appl Math Comput 216:1763–1770MathSciNetMATH
3.
Lin L, Liu ZY (2011) An alternationg projected gradient algorithm for nonnegative matrix factorization. Appl Math Comput 217:9997–10002MathSciNetMATH
4.
Hoyer PO (2004) Non-negative matrix factorization with sparseness constraints. J Mach Learn Res 5(1):1457–1469MathSciNetMATH
5.
Berry M, Browne M, Langville A, Pauca P, Plemmons R (2007) Algorithms and applications for approximate nonnegative matrix factorization. Comput Stat Data Anal 52:155–173MathSciNetCrossRef
6.
Pauca P, Shahnaz F, Berry M, Plemmons R (2004) Text mining using non-negative matrix factorizations. In: Proceedings of the 2004 SIAM international conference on data mining, pp 452–456
7.
Saul LK, Sha F, Lee DD (2003) Statistical signal processing with nonnegativity constraints. Proc EuroSpeech 2:1001–1004
8.
Shahnaz F, Berry MW, Pauca VP, Plemmons R (2006) Document clusting using nonnegative matrix factorization. Inform Process Manag 42:373–386CrossRef
9.
Pauca VP, Piper J, Plemmons RJ (2006) Nonnegative matrix factorization for spectral data analysis. Linear Algebra Appl 416:29–47MathSciNetCrossRef
10.
Smaragdis P, Brown JC (2003) Non-negative matrix factorization for polyphonic music transcription. In: 2003 IEEE workshop on applications of signal processing to audio and acoustics, New Paltz, NY, 19–22 October 2003, pp 177–180
11.
Zarei M, Izadi D, Samani KA (2009) Detecting overlapping community structure of networks based on vertex-vertex correlations. J Stat Mech Theory Exp 2009(11):209–222CrossRef
12.
Psorakis I, Roberts S, Ebden M, Sheldon B (2011) Overlapping community detection using bayesian non-negative matrix factorization. Phys Rev E 83(6):066114CrossRef
13.
Wang F, Li T, Wang X, Zhu SH, Ding C (2011) Community discovery using nonnegative matrix factorization. Data Mining Knowl Discov 22(3):493–521MathSciNetCrossRef
14.
Cao XC, Wang X, Jin D, Cao Y, He DX (2014) Identifying overlapping communities as well as hubs and outliers via nonnegative matrix factorization. Sci Rep 3(10):2993–2993
15.
16.
Powell MJD (1969) A method for nonlinear constraints in minimization problems. Optimization 5(6):283–298MathSciNet
17.
Rockafellar RT (1974) Augmented Lagrange multiplier functions and duality in nonconvex programming. SIAM J Control Optim 12(2):268–285MathSciNetCrossRef
18.
Bertsekas DP (1982) Constrained optimization and Lagrangian multiplier methods. Academic Press, New YorkMATH
19.
Huang XX, Yang XQ (2001) Approximate optimal solutions and nonlinear Lagrangian functions. J Global Optim 21:51–65MathSciNetCrossRef
20.
21.
Polak E, Royset JO (2005) On the use of augmented Lagrangians in the solution of gengeralized semi-infinite min-max problems. Comput Optim Appl 31:173–192MathSciNetCrossRef
22.
Nocedal J, Wright SJ (2006) Numerical optimization. Springer series in operations research and financial engineering. Springer, New YorkMATH
23.
Pu DG, Yang P (2013) A class of new Lagrangian multiplier methods. In: 2013 sixth international conference on business intelligence and financial engineering, pp 647–651
24.
Liu BZ, Wang CY (2007) Zero duality gap properties for a class of Lagrangian dual problem and the convergence of its optimal path. OR Trans 11(1):73–84
25.
He B, Yang H, Wang S (2000) Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities. J Optim Theory Appl 106(2):337–356MathSciNetCrossRef
26.
He B, Liao L, Han D, Yang H (2002) A new inexact alternating directions method for monotone variational inequalities. Math Program 92(1, Ser. A):103–118MathSciNetCrossRef
27.
Wen Z, Goldfarb D, Yin W (2009) Alternating direction augmented lagrangian methods for semidefinite programming. Technical report, Dept of IEOR, Columbia University
28.
Tseng P (1997) Alternating projection-proximal methods for convex programming and variational inequalities. SIAM J Optim 7(4):951–965MathSciNetCrossRef
29.
Kontogiorgis S, Meyer RR (1998) A variable-penalty alternating directions method for convex optimization. Math Program 83(1,Ser. A):29–53MathSciNetMATH
30.
Yuan X, Yang J (2009) Sparse and low rank matrix decomposition via alternating direction method. Pac J Optim 9(1):1–11MathSciNet
31.
Lin Z, Chen M, Wu L, Ma Y (2010) The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. Eprint Arxiv 9:1–20
32.
Shen Y, Wen Z, Zhang Y (2012) Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization. Optim Method Softw 29(2):1–25MathSciNet
33.
34.
Wang D, Li T, Zhu S, Ding C (2008) Multi-document summarization via sentence-level semantic analysis and symmetric matrix factorization. In: Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval 5(2):307–314
35.
Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33:452–473CrossRef
36.
Lusseau D (2003) The emergent properties of dolphin social network. Proc Biol Sci 270(Suppl 2):186–188
37.
Newman MEJ (2006) Modularity and community structure in networks. Proc Ntl Acad Sci 103(23):8577–8582CrossRef
38.
Newman MEJ (2006) Finding community structure in networks using the eigenvectors of matrices. Phys Rev E Stat Nonlinear Soft Matter Phys 74(3 Pt 2):92–100MathSciNet
39.
Watts DJ, Strogatz SH (1998) Collective dynamics of ’small-world’ networks. Nature 393:440–442CrossRef
40.
Girvan M, Newman MEJ (2001) Community structure in social and biological networks. Proc Natl Acad Sci USA 99(12):7821–7826MathSciNetCrossRef
41.
Leskovec J, Lang KJ, Mahoney M (2010) Empirical comparison of algorithms for network community detection. In: Proceedings of the 19th international conference on World wide web, Raleigh, North Carolina, USA, 26–30 April 2010. ACM, New York, pp 631–640
42.
Blondel V, Guillaume J, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008(10):155–168CrossRef
43.
Palla G, Derenyi I, Farkas I, Vicsek T (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043):814–818CrossRef
44.
Zhang Y, Yeung D (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, pp 606–614
45.
Lu S, Hong M, Wang Z (2017) A nonconvex splitting method for symmetric nonnegative matrix factorization: convergence analysis and optimality. IEEE Int Confer Acoust 99:1–1MATH
46.
Borhani R, Watt J, Katsaggelos A (2016) Fast and effective algorithms for symmetric nonnegative matrix factorization. Cornell University Library. arXiv:​1609.​05342
Metadata
Title
An augmented Lagrangian alternating direction method for overlapping community detection based on symmetric nonnegative matrix factorization
Authors
Liying Hu
Gongde Guo
Publication date
24-07-2019
Publisher
Springer Berlin Heidelberg
Published in
International Journal of Machine Learning and Cybernetics / Issue 2/2020
Print ISSN: 1868-8071
Electronic ISSN: 1868-808X
DOI
https://doi.org/10.1007/s13042-019-00980-z

Other articles of this Issue 2/2020

International Journal of Machine Learning and Cybernetics 2/2020 Go to the issue

Original Article

Type-2 fuzzy cerebellar model articulation control system design for MIMO uncertain nonlinear systems

Original Article

Integration search strategies in tree seed algorithm for high dimensional function optimization

Original Article

Unlabelled text mining methods based on two extension models of concept lattices

Original Article

Improved variational inference with dynamic routing flow

Original Article

Interactive learning for joint event and relation extraction

Original Article

A two-stage hybrid probabilistic topic model for refining image annotation