Modularity-like objective function in annotated networks

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.

Keywords

community structure / annotated networks / modularity / objective function

References

[1] S. Fortunato, Community detection in graphs, Phys. Rep. 486(3–5), 75 (2010)

[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)

[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)

[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)

[6] B. Karrer and M. E. J. Newman, Stochastic blockmodels and community structure in networks, Phys. Rev. E 83(1), 016107 (2011)

[7] M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69(2), 026113 (2004)

[8] M. E. J. Newman and T. Peixoto, Generalized communities in networks,Phys. Rev. Lett. 115(8), 088701 (2015)

[9] M. E. J. Newman and G. Reinert, Estimating the number of communities in a network, Phys. Rev. Lett. 117(7), 078301 (2016)

[10] M. E. J. Newman and A. Clauset, Structure and inference in annotated networks, Nat. Commum. 7, 11863 (2016)

[11] M. E. J. Newman, Analysis of weighted networks, Phys. Rev. E 70(5), 056131 (2004)

[12] E. A. Leicht and M. E. J. Newman, Community structure in directed networks, Phys. Rev. Lett. 100(11), 118703 (2008)

[13] M. J. Barber, Modularity and community detection in bipartite networks, Phys. Rev. E 76(6), 066102 (2007)

[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)

[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)

[16] M. E. J. Newman, Equivalence between modularity optimization and maximum likelihood methods for community detection, Phys. Rev. E 94(5), 052315 (2016)

[17] A. Condon and R. M. Karp, Algorithms for graph partitioning on the planted partition model, Random Structures Algorithms 18(2), 116 (2001)

[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)

[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)

[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 (http://www.cpc.unc.edu/addhealth). 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)

[24] L. Danon, A. Díaz-Guilera, J. Duch, and A. Arenas, Comparing community structure identification, J. Stat. Mech. 09, P09008 (2005)

RIGHTS & PERMISSIONS

2017 Higher Education Press and Springer-Verlag Berlin Heidelberg