Modularity-like objective function in annotated networks

doi:10.1007/s11467-017-0657-y

Frontiers of Physics

2017, Vol. 12

Issue (6): 128903 https://doi.org/10.1007/s11467-017-0657-y

本期目录

Modularity-like objective function in annotated networks

Jia-Rong Xie,Bing-Hong Wang(

)

Department of Modern Physics, University of Science and Technology of China, Hefei 230026, China

全文: PDF(2052 KB)

Abstract：

We ascertain the modularity-like objective function whose optimization is equivalent to the maximum likelihood in annotated networks. We demonstrate that the modularity-like objective function is a linear combination of modularity and conditional entropy. In contrast with statistical inference methods, in our method, the influence of the metadata is adjustable; when its influence is strong enough, the metadata can be recovered. Conversely, when it is weak, the detection may correspond to another partition. Between the two, there is a transition. This paper provides a concept for expanding the scope of modularity methods.

Key words： community structure annotated networks modularity objective function

收稿日期: 2016-11-04 出版日期: 2017-02-09

Corresponding Author(s): Bing-Hong Wang

引用本文:

. [J]. Frontiers of Physics, 2017, 12(6): 128903.
Jia-Rong Xie,Bing-Hong Wang. Modularity-like objective function in annotated networks. Front. Phys. , 2017, 12(6): 128903.

链接本文:

https://academic.hep.com.cn/fop/CN/10.1007/s11467-017-0657-y
https://academic.hep.com.cn/fop/CN/Y2017/V12/I6/128903

1	S. Fortunato, Community detection in graphs, Phys. Rep. 486(3–5), 75 (2010) https://doi.org/10.1016/j.physrep.2009.11.002
2	M. E. J. Newman, Communities, modules and largescale structure in networks, Nat. Phys. 8(1), 25 (2011)
3	S. Fortunato and D. Hric, Community detection in networks: A user guide, Phys. Rep. 659, 1 (2016) https://doi.org/10.1016/j.physrep.2016.09.002
4	A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová, Inference and phase transitions in the detection of modules in sparse networks, Phys. Rev. Lett. 107(6), 065701 (2011) https://doi.org/10.1103/PhysRevLett.107.065701
5	A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová, Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications, Phys. Rev. E 84(6), 066106 (2011) https://doi.org/10.1103/PhysRevE.84.066106
6	B. Karrer and M. E. J. Newman, Stochastic blockmodels and community structure in networks, Phys. Rev. E 83(1), 016107 (2011) https://doi.org/10.1103/PhysRevE.83.016107
7	M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69(2), 026113 (2004) https://doi.org/10.1103/PhysRevE.69.026113
8	M. E. J. Newman and T. Peixoto, Generalized communities in networks,Phys. Rev. Lett. 115(8), 088701 (2015) https://doi.org/10.1103/PhysRevLett.115.088701
9	M. E. J. Newman and G. Reinert, Estimating the number of communities in a network, Phys. Rev. Lett. 117(7), 078301 (2016) https://doi.org/10.1103/PhysRevLett.117.078301
10	M. E. J. Newman and A. Clauset, Structure and inference in annotated networks, Nat. Commum. 7, 11863 (2016) https://doi.org/10.1038/ncomms11863
11	M. E. J. Newman, Analysis of weighted networks, Phys. Rev. E 70(5), 056131 (2004) https://doi.org/10.1103/PhysRevE.70.056131
12	E. A. Leicht and M. E. J. Newman, Community structure in directed networks, Phys. Rev. Lett. 100(11), 118703 (2008) https://doi.org/10.1103/PhysRevLett.100.118703
13	M. J. Barber, Modularity and community detection in bipartite networks, Phys. Rev. E 76(6), 066102 (2007) https://doi.org/10.1103/PhysRevE.76.066102
14	P. J. Mucha, T. Richardson, K. Macon, M. A. Porter, and J. P. Onnela, Community structure in timedependent, multiscale, and multiplex networks, Science 328(5980), 876 (2010) https://doi.org/10.1126/science.1184819
15	P. Zhang and C. Moore, Scalable detection of statistically significant communities and hierarchies, using message passing for modularity, Proc. Natl. Acad. Sci. USA 111(51), 18144 (2014) https://doi.org/10.1073/pnas.1409770111
16	M. E. J. Newman, Equivalence between modularity optimization and maximum likelihood methods for community detection, Phys. Rev. E 94(5), 052315 (2016) https://doi.org/10.1103/PhysRevE.94.052315
17	A. Condon and R. M. Karp, Algorithms for graph partitioning on the planted partition model, Random Structures Algorithms 18(2), 116 (2001) https://doi.org/10.1002/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2
18	R. Guimerà, M. Sales-Pardo, and L. A. N. Amaral, Modularity from fluctuations in random graphs and complex networks, Phys. Rev. E 70, 025101(R) (2004)
19	T. P. Peixoto, Hierarchical block structures and highresolution model selection in large networks, Phys. Rev. X 4(1), 011047 (2014) https://doi.org/10.1103/PhysRevX.4.011047
20	B. H. Good, Y. A. de Montjoye, and A. Clauset, Performance of modularity maximization in practical contexts, Phys. Rev. E 81(4), 046106 (2010) https://doi.org/10.1103/PhysRevE.81.046106
21	This research uses data from Add Health, a program project directed by K. M. Harris and designed by J. R. Udry, P. S. Bearman, and K. M. Harris at the University of North Carolina at Chapel Hill, and funded by grant P01-HD31921 from the Eunice Kennedy Shriver National Institute of Child Health and Human Development, with cooperative funding from 23 other federal agencies and foundations. Special acknowledgment is dueR. R. Rindfuss and B. Entwisle for assistance in the original design. Information on how to obtain the Add Health data files is available on the Add Health website (). No direct support was received from grant P01-HD31921 for this analysis.
22	M. Bastian, S. Heymann, and M. Jacomy, Gephi: An open source software for exploring and manipulating networks, in: International AAAI Conference on Weblogs and Social Media, 2009
23	M. Jacomy, T. Venturini, S. Heymann, and M. Bastian, ForceAtlas2, a continuous graph layout algorithm for handy network visualization designed for the Gephi software, PLoS One 9(6), e98679 (2014) https://doi.org/10.1371/journal.pone.0098679
24	L. Danon, A. Díaz-Guilera, J. Duch, and A. Arenas, Comparing community structure identification, J. Stat. Mech. 09, P09008 (2005) https://doi.org/10.1088/1742-5468/2005/09/p09008

Viewed

Full text

Abstract

Cited

Shared

Discussed