title: A stochastic model for detecting overlapping and hierarchical community structure.
abstract: Community detection is a fundamental problem in the analysis of complex networks. Recently, many researchers have concentrated on the detection of overlapping communities, where a vertex may belong to more than one community. However, most current methods require the number (or the size) of the communities as a priori information, which is usually unavailable in real-world networks. Thus, a practical algorithm should not only find the overlapping community structure, but also automatically determine the number of communities. Furthermore, it is preferable if this method is able to reveal the hierarchical structure of networks as well. In this work, we firstly propose a generative model that employs a nonnegative matrix factorization (NMF) formulization with a l(2,1) norm regularization term, balanced by a resolution parameter. The NMF has the nature that provides overlapping community structure by assigning soft membership variables to each vertex; the l(2,1) regularization term is a technique of group sparsity which can automatically determine the number of communities by penalizing too many nonempty communities; and hence the resolution parameter enables us to explore the hierarchical structure of networks. Thereafter, we derive the multiplicative update rule to learn the model parameters, and offer the proof of its correctness. Finally, we test our approach on a variety of synthetic and real-world networks, and compare it with some state-of-the-art algorithms. The results validate the superior performance of our new method.
authors.affiliation: School of Computer Science and Technology, Tianjin University, Tianjin 300072, China; State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China.
authors.forename: Xiaochun
authors.initials: X
authors.lastname: Cao
authors.affiliation: School of Computer Science and Technology, Tianjin University, Tianjin 300072, China.
authors.forename: Xiao
authors.initials: X
authors.lastname: Wang
authors.affiliation: School of Computer Science and Technology, Tianjin University, Tianjin 300072, China.
authors.forename: Di
authors.initials: D
authors.lastname: Jin
authors.affiliation: State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China.
authors.forename: Xiaojie
authors.initials: X
authors.lastname: Guo
authors.affiliation: School of Computer Science and Technology, Tianjin University, Tianjin 300072, China.
authors.forename: Xianchao
authors.initials: X
authors.lastname: Tang
mesh_terms: D000465:Algorithms; D015233:Models, Statistical; D016571:Neural Networks, Computer; D013269:Stochastic Processes
references.citation: Proc Natl Acad Sci U S A. 2008 Jan 29;105(4):1118-23
references.pmid: 18216267
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2005 Aug;72(2 Pt 2):027104
references.pmid: 16196754
references.citation: Science. 1999 Oct 15;286(5439):509-12
references.pmid: 10521342
references.citation: Nature. 2005 Jun 9;435(7043):814-8
references.pmid: 15944704
references.citation: Nature. 1999 Oct 21;401(6755):788-91
references.pmid: 10548103
references.citation: PLoS One. 2011;6(8):e23829
references.pmid: 21887325
references.citation: Proc Natl Acad Sci U S A. 2010 Jul 20;107(29):12755-60
references.pmid: 20615936
references.citation: Proc Natl Acad Sci U S A. 2004 Mar 23;101(12):4164-9
references.pmid: 15016911
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2011 Jun;83(6 Pt 2):066114
references.pmid: 21797448
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2006 Sep;74(3 Pt 2):036104
references.pmid: 17025705
references.citation: Nature. 2010 Aug 5;466(7307):761-4
references.pmid: 20562860
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2009 Mar;79(3 Pt 2):036111
references.pmid: 19392022
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2008 Oct;78(4 Pt 2):046110
references.pmid: 18999496
references.citation: Proc Natl Acad Sci U S A. 2002 Jun 11;99(12):7821-6
references.pmid: 12060727
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Feb;69(2 Pt 2):026113
references.pmid: 14995526
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2011 Jan;83(1 Pt 2):016107
references.pmid: 21405744
references.citation: IEEE Trans Pattern Anal Mach Intell. 2013 Jul;35(7):1592-605
references.pmid: 23681989
references.citation: Sci Rep. 2013 Oct 21;3:2993
references.pmid: 24129402
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2013 Jun;87(6):062803
references.pmid: 23848725
references.citation: Proc Biol Sci. 2004 Dec 7;271 Suppl 6:S477-81
references.pmid: 15801609
references.citation: Proc Natl Acad Sci U S A. 2007 Jan 2;104(1):36-41
references.pmid: 17190818
references.citation: PLoS One. 2011;6(4):e18209
references.pmid: 21494658
references.citation: Nature. 1998 Jun 4;393(6684):440-2
references.pmid: 9623998
references.citation: Proc Natl Acad Sci U S A. 2006 Jun 6;103(23):8577-82
references.pmid: 16723398
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2011 Nov;84(5 Pt 2):056111
references.pmid: 22181477