Hostname: page-component-848d4c4894-75dct Total loading time: 0 Render date: 2024-06-04T17:48:18.425Z Has data issue: false hasContentIssue false
  • English
  • Français

Walk-modularity and community structure in networks

Published online by Cambridge University Press:  29 July 2015

DAVID MEHRLE ,
AMY STROSSER  and
ANTHONY HARKIN
DAVID MEHRLE
Affiliation:
Department of Mathematics, Cornell University, Ithaca, NY, USA (e-mail: dfm223@cornell.edu)
AMY STROSSER
Affiliation:
Department of Mathematics and Statistics, Villanova University, Villanova, PA, USA (e-mail: astrosse@villanova.edu)
ANTHONY HARKIN
Affiliation:
School of Mathematical Sciences, Rochester Institute of Technology, Rochester, NY, USA (e-mail: harkin@rit.edu)
Get access Rights & Permissions [Opens in a new window]

Abstract

Modularity maximization has been one of the most widely used approaches in the last decade for discovering community structure in networks of practical interest in biology, computing, social science, statistical mechanics, and more. Modularity is a quality function that measures the difference between the number of edges found within clusters minus the number of edges one would statistically expect to find based on some equivalent random graph model. We explore a natural generalization of modularity based on the difference between the actual and expected number of walks within clusters, which we refer to as walk-modularity. Walk-modularity can be expressed in matrix form, and community detection can be performed by finding the leading eigenvector of the walk-modularity matrix. We demonstrate community detection on both synthetic and real-world networks and find that walk-modularity maximization returns significantly improved results compared to traditional modularity maximization.

Keywords

community detectionmodularity
Type
Research Article
Information
Network Science , Volume 3 , Issue 3 , September 2015 , pp. 348 - 360
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Agarwal, G., & Kempe, D. (2008). Modularity-maximizing graph communities via mathematical programming. The European Physical Journal B, 66 (3), 409–418.Google Scholar
Arenas, A., Fernández, A., Fortunato, S., & Gómez, S. (2008). Motif-based communities in complex networks. Journal of Physics A: Mathematical and Theoretical, 41 (22), 224001.Google Scholar
Barber, M. J. (2007). Modularity and community detection in bipartite networks. Physical Review E, 76 (6), 066102.Google Scholar
Berry, J. W., Hendrickson, B., LaViolette, R. A., & Phillips, C. A. (2011). Tolerating the community detection resolution limit with edge weighting. Physical Review E, 83 (5), 056119.Google Scholar
Blondel, V. D., Guillaume, J., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008 (10), P10008.Google Scholar
Brandes, U., Delling, D., Gaertler, M., Görke, R., Hoefer, M., Nikoloski, Z., & Wagner, D. (2008). On modularity clustering. IEEE Transactions on Knowledge and Data Engineering, 20 (2), 172–188.Google Scholar
Clauset, A., Newman, M. E. J., & Moore, C. (2004). Finding community structure in very large networks. Physical Review E, 70 (6), 066111.Google Scholar
Crescenzi, P., Grossi, R., Habib, M., Lanzi, L., & Marino, A. (2012). On computing the diameter of real-world undirected graphs. Theoretical Computer Science, 514, 84–95.Google Scholar
Decelle, A., Krzakala, F., Moore, C., & Zdeborová, L. (2011a). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84 (6), 066106.Google Scholar
Decelle, A., Krzakala, F., Moore, C., & Zdeborová, L. (2011b). Inference and phase transitions in the detection of modules in sparse networks. Physical Review Letters, 107 (6), 065701.Google Scholar
Duch, J., & Arenas, A. (2005). Community detection in complex networks using extremal optimization. Physical Review E, 72 (2), 027104.Google Scholar
Estrada, E. (2011a). Community detection based on network communicability. Chaos: An Interdisciplinary Journal of Nonlinear Science, 21 (1), 016103.Google Scholar
Estrada, E. (2011b). The structure of complex networks: Theory and applications. Oxford, England: Oxford University Press.Google Scholar
Estrada, E., & Hatano, N. (2008). Communicability in complex networks. Physical Review E, 77 (3), 036111.Google Scholar
Estrada, E., & Hatano, N. (2009). Communicability graph and community structures in complex networks. Applied Mathematics and Computation, 214 (2), 500–511.Google Scholar
Estrada, E., Hatano, N., & Benzi, M. (2012). The physics of communicability in complex networks. Physics Reports, 514 (3), 89–119.Google Scholar
Fortunato, S. (2009). Community detection in graphs. Physics Reports, 486 (3), 75–174.Google Scholar
Fortunato, S., & Barthelemy, M. (2007). Resolution limit in community detection. Proceedings of the National Academy of Sciences, 104 (1), 36–41.Google Scholar
Good, B. H., de Montjoye, Y., & Clauset, A. (2010). Performance of modularity maximization in practical contexts. Physical Review E, 81 (4), 046106.Google Scholar
Lancichinetti, A., Fortunato, S., & Radicchi, F. (2008). Benchmark graphs for testing community detection algorithms. Physical Review E, 78 (4), 046110.Google Scholar
Lusseau, D., Schneider, K., Boisseau, O. J., Haase, P., Slooten, E., & Dawson, S. M. (2003). The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology, 54 (4), 396–405.Google Scholar
Nadakuditi, R. R., & Newman, M. E. J. (2012). Graph spectra and the detectability of community structure in networks. Physical Review Letters, 108 (18), 188701.Google Scholar
Nepusz, T., Petróczi, A., Négyessy, L., & Bazsó, F. (2008). Fuzzy communities and the concept of bridgeness in complex networks. Physical Review E, 77 (1), 016107.Google Scholar
Newman, M. E. J. (2004). Fast algorithm for detecting community structure in networks. Physical Review E, 69 (6), 066133.Google Scholar
Newman, M. E. J. (2006a). Finding community structure in networks using the eigenvectors of matrices. Physical Review E, 74 (3), 036104.Google Scholar
Newman, M. E. J. (2006b). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103 (23), 8577–8582.Google Scholar
Newman, M. E. J. (2011). Communities, modules and large-scale structure in networks. Nature Physics, 8 (1), 25–31.Google Scholar
Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69 (2), 026113.Google Scholar
Nicosia, V., Mangioni, G., Carchiolo, V., & Malgeri, M. (2009). Extending the definition of modularity to directed graphs with overlapping communities. Journal of Statistical Mechanics: Theory and Experiment, 2009 (03), P03024.Google Scholar
Porter, M. A., Onnela, J., & Mucha, P. J. (2009). Communities in networks. Notices of the AMS, 56 (9), 1082–1097.Google Scholar
Radicchi, F. (2013). Detectability of communities in heterogeneous networks. Physical Review E, 88 (1), 010801.Google Scholar
Radicchi, F. (2014a). Driving interconnected networks to supercriticality. Physical Review X, 4 (2), 021014.Google Scholar
Radicchi, F. (2014b). A paradox in community detection. EPL (Europhysics Letters), 106 (3), 38001.Google Scholar
Reichardt, J., & Bornholdt, S. (2006). Statistical mechanics of community detection. Physical Review E, 74 (1), 016110.Google Scholar
Zachary, W. W. (1977). An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33 (4), 452–473.Google Scholar