Community Discovery Methods for Complex Networks

05 Mar 2024 11:42

---

Given: a network, especially a large one, directed or not, weighted or not. Desired: a sensible decomposition of the graph into sub-graphs, where in some reasonable sense the nodes in each sub-graph have more to do with each other than with outsiders, i.e., form communities. This is also called "module detection".

This seems like a really useful idea to apply to problems I'm interested in, in neural synchronization; also a place where there could stand to be more interchange between statisticians and complex-network-wallahs. [That was written many years ago; I think that now (2013) the interchange is pretty well-established.]

Some of the methods in this area remind me of stuff Christopher Alexander did in his 1964 book Notes on the Synthesis of Form, but it's been a long time since I read that, so my memory may be faulty.

— Stochastic block models are a particular class of probabilistic network models which have turned out to be extremely useful for community discovery; they get their own notebook.

See also: Ecology; Neuroscience; Signal Transduction, Gene Regulation and Control of Metabolism; Social Networks; Sociology of Science; Statistical Mechanics; Stochastic Block Models; Synchronization

Recommended, big picture:
• Peter J. Bickel and Aiyou Chen, "A nonparametric view of network models and Newman-Girvan and other modularities", Proceedings of the National Academy of Sciences (USA) 106 (2009): 21068--21073 [See under Graph Limits and Infinite Exchangeable Arrays]
• Michelle Girvan and M. E. J. Newman, "Community structure in social and biological networks," Proceedings of the National Academy of Sciences (USA) 99 (2002): 7821--7826, cond-mat/0112110
• Jake M. Hofman, Chris H. Wiggins, "A Bayesian Approach to Network Modularity", arxiv:0709.3512 [For "Bayesian", read "smoothed maximum likelihood". But nonetheless: cool.]
• M. E. J. Newman
  • "Modularity and community structure in networks", physics/0602124 = Proceedings of the National Academy of Sciences (USA) 103 (2006): 87577--8582
  • "Finding community structure in networks using the eigenvectors of matrices", Physical Review E 74 (2006): 036104, physics/0605087
• M. E. J. Newman and Michelle Girvan
  • "Mixing patterns and community structure in networks", cond-mat/0210146
  • "Finding and evaluating community structure in networks", Physical Review E 69 (2003): 026113 = cond-mat/0308217

Recommended, close-ups:
• Yong-Yeol Ahn, James P. Bagrow and Sune Lehmann, "Link communities reveal multiscale complexity in networks", Nature 455 (2010): 761--764, arxiv:0903.3178 [Lehmann's blog-post on this]
• Arash A. Amini, Aiyou Chen, Peter J. Bickel, Elizaveta Levina, "Pseudo-likelihood methods for community detection in large sparse networks", Annals of Statistics 41 (2013): 2097--2122, arxiv:1207.2340
• Peter J. Bickel, Purnamrita Sarkar, "Hypothesis Testing for Automated Community Detection in Networks", arxiv:1311.2694
• Kehui Chen, Jing Lei, "Network Cross-Validation for Determining the Number of Communities in Network Data", arxiv:1411.1715
• David S. Choi, Patrick J. Wolfe, "Co-clustering separately exchangeable network data", arxiv:1212.4093
• Aaron Clauset, "Finding local community structure in networks", Physical Review E 72 (2005): 026132, physics/0503036
• Aaron Clauset, M. E. J. Newman and Cristopher Moore, "Finding Community Structure in Very Large Networks", cond-mat/0408187 = Physical Review E 70 (2004): 066111
• J.-J. Daudin, F. Picard and S. Robin, "A Mixture Model for Random Graphs", Statistics and Computing 18 (2008): 173--183
• Aurelien Decelle, Florent Krzakala, Cristopher Moore and Lenka Zdeborova
  • "Phase transition in the detection of modules in sparse networks", Physical Review Letters 107 (2011): 065701, arxiv:1102.1182
  • "Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications", Physical Review E 84 (2011): 066106, arxiv:1109.3041
• Daniel J. Fenn, Mason A. Porter, Mark McDonald, Stacy Williams, Neil F. Johnson, Nick S. Jones, "Dynamic communities in multichannel data: An application to the foreign exchange market during the 2007--2008 credit crisis", Chaos 19 (2009): 033119, arxiv:0811.3988
• Daniel J. Fenn, Mason A. Porter, Peter J. Mucha, Mark McDonald, Stacy Williams, Neil F. Johnson, Nick S. Jones, "Dynamical Clustering of Exchange Rates", Quantitative Finance 12 (2012): 1493--1520, arxiv:0905.4912
• Prem K. Gopalan and David M. Blei, "Efficient discovery of overlapping communities in massive networks", Proceedings of the National Academy of Sciences (USA) 110 (2013): 14534--14539
• Roger Guimera, Marta Sales-Pardo and Luis A. N. Amaral, "Modularity from Fluctuations in Random Graphs", cond-mat/0403660 = Physical Review E 70 (2004): 025101
• Mark S. Handcock, Adrian E. Raftery and Jeremy Tantrum, "Model-Based Clustering for Social Networks" Journal of the Royal Statistical Society A 170 (2007): 301--354 [PDF preprint]
• J. A. Henderson and P. A. Robinson, "Geometric Effects on Complex Network Structure in the Cortex", Physical Review Letters 107 (2011): 018102
• Matthew O. Jackson and Evan C. Storms, "Behavioral Communities and the Atomic Structure of Networks", arxiv:1710.04656 [This is an interesting but fundamentally different notion of "community" than most of the literature: the "atoms" here are groups of agents who always act the same way in certain coordination games played with neighbors in the network. This is much more of a behavioral/strategic notion, as befits economists, than the ones based on structure and mere connectivity which come out of sociology and physics. It'd be interesting to know when the two kinds of communities match up, and when they differ.]
• Jiashun Jin, "Fast network community detection by SCORE", arxiv:1211.5803
• Brian Karrer, M. E. J. Newman, "Stochastic blockmodels and community structure in networks", Physical Review 83 (2011): 016107, arxiv:1008.3926
• Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, Pan Zhang, "Spectral redemption: clustering sparse networks", arxiv:1306.5550
• Andrea Lancichinetti, Santo Fortunato, Janos Kertesz, "Detecting the overlapping and hierarchical community structure of complex networks", arxiv:0802.1218 [An interesting approach, but not quite as novel as they claim --- cf. Reichardt and Bornholdt --- and I'd really like to see more evidence of superior accuracy and/or robustness]
• E. A. Leicht, M. E. J. Newman, "Community structure in directed networks", arxiv:0709.4500
• Jure Leskovec, Kevin J. Lang, Anirban Dasgupta and Michael W. Mahoney, "Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters", arxiv:0810.1355
• Vince Lyzinski, Daniel Sussman, Minh Tang, Avanti Athreya, Carey Priebe, "Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding", arxiv:1310.0532
• Shawn Mankad and George Michailidis, "Structural and Functional Discovery in Dynamic Networks with Non-negative Matrix Factorization", Physical Review E 88 (2013): 042812, arxiv:1305.7169
• Mahendra Mariadassou, Stéphane Robin, and Corinne Vacher, "Uncovering latent structure in valued graphs: A variational approach", Annals of Applied Statistics 4 (2010): 715-774
• Elchanan Mossel, Joe Neeman, Allan Sly, "Stochastic Block Models and Reconstruction", arxiv:1202.1499
• Peter J. Mucha, Thomas Richardson, Kevin Macon, Mason A. Porter, Jukka-Pekka Onnela, "Community Structure in Time-Dependent, Multiscale, and Multiplex Networks", Science 328 (2010): 876--878, arxiv:0911.1824
• M. E. J. Newman, "Spectral methods for network community detection and graph partitioning", Physical Review E 88 (2013): 042822, arxiv:1307.7729
• M. E. J. Newman and Tiago P. Peixoto, "Generalized communities in networks", Physical Review Letters 115 (2015): 088701, arxiv:1505.07478
• Andreas Noack, "Modularity clustering is force-directed layout", Physical Review E 79 (2009): 026102, arxiv:0807.4052
• Jörg Reichardt and Stefan Bornholdt
  • "Detecting Fuzzy Community Structures in Complex Networks with a Potts Model", Physical Review Letters 93 (2004): 218701 = cond-mat/0402349
  • "Statistical Mechanics of Community Detection", cond-mat/0603718, Physical Review E 74 (2006): 016110
  • "Clustering of sparse data via network communities — a prototype study of a large online market", Journal of Statistical Mechanics: Theory and Experiment (2007): P06016
• Jörg Reichardt and Douglas R. White, "Role models for complex networks", arxiv:0708.0958 [Discussion]
• Karl Rohe, Tai Qin, "The blessing of transitivity in sparse and stochastic networks", arxiv:1307.2302
• Martin Rosvall and Carl T. Bergstrom
  • "An information-theoretic framework for resolving community structure in complex networks", Proceedings of the National Academy of Sciences (USA) 104 (2007): 7327--7331, physics/0612035 [Or, MDL to the rescue!]
  • "Maps of random walks on complex networks reveal community structure", Proceedings of the National Academy of Sciences (USA) 105 (2008): 1118--1123, arxiv:0707.0609
• M. Sales-Pardo, R. Guimera, A. Moreira, L. Amaral, "Extracting the hierarchical organization of complex systems", arxiv:0705.1679
• Purnamrita Sarkar, Peter J. Bickel, "Role of Normalization in Spectral Clustering for Stochastic Blockmodels", arxiv:1310.1495
• Grant Schoenebeck, "Potential Networks, Contagious Communities, and Understanding Social Network Structure", WWW 2013, arxiv:1304.1845
• Laura M. Smith, Kristina Lerman, Cristina Garcia-Cardona, Allon G. Percus, Rumi Ghosh, "Spectral Clustering with Epidemic Diffusion", Physical Review E 88 (2013): 042813, arxiv:1303.2663
• Greg Ver Steeg, Cristopher Moore, Aram Galstyan, Armen E. Allahverdyan, "Phase Transitions in Community Detection: A Solvable Toy Model", arxiv:1312.0631
• James D. Wilson, Simi Wang, Peter J. Mucha, Shankar Bhamidi, Andrew B. Nobel, "A Testing Based Extraction Algorithm for Identifying Significant Communities in Networks", arxiv:1308.0777
• Pan Zhang and Cristopher Moore, "Scalable detection of statistically significant communities and hierarchies: message-passing for modularity", arxiv:1403.5787
• Weituo Zhang and Chjan C. Lim, "The Concentration and Stability of the Community Detecting Functions on Random Networks", arxiv:1203.5974
• Yunpeng Zhao, Elizaveta Levina, and Ji Zhu
  • "On Consistency of Community Detection in Networks", arxiv:1110.3854
  • "Community extraction for social networks", arxiv:1005.3265
• Yaojia Zhu, Xiaoran Yan, Cristopher Moore, "Oriented and Degree-generated Block Models: Generating and Inferring Communities with Inhomogeneous Degree Distributions", arxiv:1205.7009
• Etay Ziv, Manuel Middendorf and Chris Wiggins, "Information-Theoretic Approach to Network Modularity", Physical Review E 71 (2005): 046117, q-bio.QM/0411033 =

Modesty forbids me to recommend:
• Edward McFowland III and CRS, "Estimating Causal Peer Influence in Homophilous Social Networks by Inferring Latent Locations", Journal of the American Statistical Association forthcoming (2021), arxiv:1607.06565
• CRS, Marcelo F. Camperi and Kristina Lisa Klinkner, "Discovering Functional Communities in Dynamical Networks", pp. 140--157 in Edo Airoldi, David M. Blei, Stephen E. Fienberg, Anna Goldenberg, Eric P. Xing and Alice X. Zheng (eds.), Statistical Network Analysis: Models, Issues and New Directions, q-bio.NC/0609008
• Xiaoran Yan, CRS, Jacob E. Jensen, Florent Krzakala, Cristopher Moore, Lenka Zdeborova, Pan Zhang and Yaojia Zhu, forthcoming in Journal of Statistical Mechanics, "Model Selection for Degree-corrected Block Models", arxiv:1207.3994

To read:
• Aaron B. Adcock, Blair D. Sullivan, Michael W. Mahoney, "Tree decompositions and social graphs", arxiv:1411.1546
• Nir Ailon, Yudong Chen, Xu Huan, "Breaking the Small Cluster Barrier of Graph Clustering", arxiv:1302.4549
• Nelson Augusto Alves, "Unveiling community structures in weighted networks", physics/0703087
• Diego R. Amancio, Osvaldo N. Oliveira Jr., Luciano da F. Costa, "Efficient community detection via sampling processes in complex networks", arxiv:1308.6295
• Arash A. Amini, Elizaveta Levina, "On semidefinite relaxations for the block model", arxiv:1406.5647
• Anima Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, "A Tensor Spectral Approach to Learning Mixed Membership Community Models", arxiv:1302.2684
• Leonardo Angelini, Stefano Boccaletti, Daniele Marinazzo, Mario Pellicoro, and Sebastiano Stramaglia, "Fast identification of network modules by optimization of ratio association", cond-mat/0610182
• L. Angelini, D. Marinazzo, M. Pellicoro and S. Stramaglia, "Natural clustering: the modularity approach", cond-mat/0607643
• Alex Arenas, Javier Borge-Holthoefer, Sergio Gomez, Gorka Zamora-Lopez, "Optimal map of the modular structure of complex networks", New Journal of Physics 12 (2010): 053009, arxiv:0911.2651
• A. Arenas, J. Duch, A. Fernandez, S. Gomez, "Size reduction of complex networks preserving modularity", physics/0702015 [Do you really need all those links? Wouldn't your life be simpler if you could just ignore some of them?]
• Alex Arenas, Alberto Fernandez, Sergio Gomez, "Multiple resolution of the modular structure of complex networks", physics/0703218
• Alex Arenas, Alberto Fernandez, Santo Fortunato, Sergio Gomez, "Motif-based communities in complex networks", arxiv:0710.0059
• Sanjeev Arora, Rong Ge, Sushant Sachdeva, Grant Schoenebeck, "Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach", arxiv:1112.1831 [By "rigorous", they mean "rigorous analysis of the algorithm", not, e.g., a statistically or scientifically rigorous approach.]
• Franco Bagnoli, Andrea Guazzini, Emanuele Massaro, "Community-detection cellular automata with local and long-range connectivity", arxiv:1206.2262
• James P. Bagrow, "Communities and bottlenecks: Trees and treelike networks have high modularity", Physical Review E 85 (2012): 066118
• Jim Bagrow and Erik Bollt, "A Local Method for Detecting Communities", Physical Review E 72 (2005): 046108, cond-mat/0412482
• James Bagrow, Erik Bollt, Luciano da F. Costa, "Network Structure Revealed by Short Cycles", cond-mat/0612502
• Brian Ball, Brian Karrer, M. E. J. Newman, "An efficient and principled method for detecting communities in networks", arxiv:1104.3590
• Michael J. Barber, "Detecting hierarchical and overlapping network communities using locally optimal modularity changes", arxiv:1305.6228
• Michael J. Barber, John W. Clark, "Detecting network communities by propagating labels under constraints", Physical Review E 80 (2009): 026129, arxiv:0903.3138
• Danielle S. Bassett, Mason A. Porter, Nicholas F. Wymbs, Scott T. Grafton, Jean M. Carlson, Peter J. Mucha, "Robust Detection of Dynamic Community Structure in Networks", arxiv:1206.4358
• Mariano Beguerisse-Díaz, Borislav Vangelov, Mauricio Barahona, "Finding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning Tree", arxiv:1309.1795
• Michele Berlingerio, Fabio Pinelli, Francesco Calabrese, "ABACUS: Apriori-BAsed Community discovery in mUltidimensional networkS", arxiv:1303.2025
• Jonathan W. Berry, Bruce Hendrickson, Randall A. LaViolette, Cynthia A. Phillips, "Tolerating the Community Detection Resolution Limit with Edge Weighting", arxiv:0903.1072 [I have to say that their abstract sounds like a recipe for over-fitting, but I haven't read the paper so that could be totally unfair.]
• Andrea Bettinelli, Pierre Hansen, Leo Liberti, "Algorithm for parametric community detection in networks", Physical Review E 86 (2012): 016107
• Sharmodeep Bhattacharyya, Peter J. Bickel, "Community Detection in Networks using Graph Distance", arxiv:1401.3915
• S. Boccaletti, M. Ivanchenko, V. Latora, A. Pluchino and A. Rapisarda, "Dynamical clustering methods to find community structures", physics/0607179
• Marianna Bolla, "Penalized versions of the Newman-Girvan modularity and their relation to normalized cuts and k-means clustering", Physical Review E 84 (2011): 016108
• Michael James Bommarito II, Daniel Martin Katz, Jon Zelner, "On the Stability of Community Detection Algorithms on Longitudinal Citation Data", arxiv:0908.0449
• U. Brandes, D. Delling, M. Gaertler, R. Goerke, M. Hoefer, Z. Nikoloski, and D. Wagner, "Maximizing Modularity is hard", physics/0608255 [i.e., maximizing the Girvan-Newman modularity is NP hard. I haven't read beyond the abstract yet, so I don't know if they address the question of what makes it hard in the hard cases, and whether those are properties we should expect to see in real-world networks. Conceivably, actual social networks are, on average, easy to modularize...]
• Andrea Capocci, Vito D. P. Servedio, Guido Caldarelli, Francesca Colaiori, "Detecting communities in large networks", cond-mat/0402499
• Horacio Castellini and Lilia Romanelli, "Social network from communities of electronic mail", nlin.CD/0509021
• Federica Cerina, Vincenzo De Leo, Marc Barthelemy, Alessandro Chessa, "Spatial correlations in attribute communities", arxiv:1112.3308
• Sanjeev Chauhan, Michelle Girvan and Edward Ott, "Spectral properties of networks with community structure", Physical Review E 80 (2009): 056114
• Yudong Chen, Vikas Kawadia, Rahul Urgaonkar, "Detecting Overlapping Temporal Community Structure in Time-Evolving Networks", arxiv:1303.7226
• Yudong Chen, Sujay Sanghavi, Huan Xu, "Clustering Sparse Graphs", arxiv:1210.3335
• Hocine Cherifi, Gergely Palla, Boleslaw K. Szymanski, Xiaoyan Lu, "On community structure in complex networks: challenges and opportunities", arxiv:1908.04901
• Gennaro Cordasco, Luisa Gargano, "Community Detection via Semi-Synchronous Label Propagation Algorithms", arxiv:1103.4550
• Michele Coscia, Fosca Giannotti, Dino Pedreschi, "A Classification for Community Discovery Methods in Complex Networks", arxiv:1206.3552
• Michele Coscia, Giulio Rossetti, Fosca Giannotti, Dino Pedreschi, "DEMON: a Local-First Discovery Method for Overlapping Communities", arxiv:1206.0629
• Leon Danon, Albert Díaz-Guilera, and Alex Arenas, "The effect of size heterogeneity on community identification in complex networks", Journal of Statistical Mechanics: Theory and Experiment (2006): P11010 = physics/0601144
• Leon Danon, Albert Díaz-Guilera, Jordi Duch and Alex Arenas, "Comparing community structure identification", Journal of Statistical Mechanics: Theory and Experiment (2005): P09008 = cond-mat/0505245
• Bhaskar DasGupta, Devendra Desai, "On the Complexity of Newman's Community Finding Approach for Biological and Social Networks", arxiv:1102.0969
• Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, Alessandro Provetti, "Enhancing community detection using a network weighting strategy", arxiv:1303.1741
• J-.C. Delvenne, S. N. Yaliraki and M. Barahona, "Stability of Graph Communities across Time Scales", Proceedings of the National Academy of Sciences (USA) 107 (2010): 12755--12760
• Yash Deshpande, Emmanuel Abbe, Andrea Montanari, "Asymptotic Mutual Information for the Two-Groups Stochastic Block Model", arxiv:1507.08685
• Charanpal Dhanjal, Romaric Gaudel, Stéphan Clémen&ccdeil;on, "Efficient Eigen-updating for Spectral Graph Clustering", arxiv:1301.1318
• Jordi Duch and Alex Arenas, "Community detection in complex networks using extremal optimization", Physical Review E 72 (2005): 027104
• Oliver Dürr, Arnd Brandenburg, "Using Community Structure for Complex Network Layout", arxiv:1207.6282
• Lilia Efimova and Stephanie Hendrick, "In search for a virtual settlement: An exploration of weblog community boundaries" [PDF reprint]
• Xuhui Fan, Longbing Cao, Richard Yi Da Xu, "Dynamic Infinite Mixed-Membership Stochastic Blockmodel", arxiv:1306.2999
• Illes J. Farkas, Daniel Abel, Gergely Palla, Tamas Vicsek, "Weighted network modules", cond-mat/0703706
• S. Feldt, J. Waddell, V. L. Hetrick, J. D. Berke, and M. Zochowski, "Functional clustering algorithm for the analysis of dynamic network data", Physical Review E 79 (2009): 056104
• Sam Field, Kenneth A. Frank, Kathryn Schiller, Catherine Riegle-Crumb and Chandra Muller, "Identifying positions from affiliation networks: Preserving the duality of people and events", Social Networks 28 (2006): 97--123
• Donniell E. Fishkind, Daniel L. Sussman, Minh Tang, Joshua T. Vogelstein, Carey E. Priebe, "Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown", arxiv:1205.0309
• G. W. Flake, S. R. Lawrence, C. L. Giles and F. M. Coetzee, "Self-organization and identification of Web communities", IEEE Computer 36 (2002): 66--71
• Lucio Floretta, Jonas Liechti, Alessandro Flammini, Paolo De Los Rios, "Stochastic fluctuations and the detectability limit of network communities", arxiv:1306.2230
• Santo Fortunato, "Community detection in graphs", arxiv:0906.0612
• Santo Fortunato and Marc Bathélemy, "Resolution limit in community detection", cite>Proceedings of the National Academy of Sciences (USA) 104 (2007): 36--41, physics/0607100
• Santo Fortunato and Claudio Castellano, "Community Structure in Graphs", arxiv:0712.2716 [Review paper; thanks to Ed Vielmetti for the pointer]
• Santo Fortunato, Vito Latora and Massimo Marchiori, "A Method to Find Community Structures Based on Information Centrality", cond-mat/0402522
• Santo Fortunato and Mark E. J. Newman, "20 years of network community detection", Nature Physics forthcoming (2022)
• Kenneth A. Frank, "Identifying Cohesive Subgroups", Social Networks 17 (1995): 27--56
• Antonino Freno, Mikaela Keller, Gemma C. Garriga, Marc Tommasi, "Spectral Estimation of Conditional Random Graph Models for Large-Scale Network Data", UAI 2012, arxiv:1210.4860
• Adrien Friggeri, Guillaume Chelius, Eric Fleury, "Triangles to Capture Social Cohesion", arxiv:1107.3231
• David Gfeller, Jean-Cédric Chappelier, and Paolo De Los Rios, "Finding instabilities in the community structure of complex networks", Physical Review E 72 (2005): 056135
• Rumi Ghosh, Kristina Lerman, "Structure of Heterogeneous Networks", arxiv:0906.2212
• V. Gol'dshtein and G. A. Koganov, "An indicator for community structure", physics/0607159
• Sergio Gomez, Pablo Jensen, Alex Arenas, "Analysis of community structure in networks of correlated data", Physical Review E 80 (2009): 016114, arxiv:0812.2030
• Benjamin H. Good, Yves-Alexandre de Montjoye, Aaron Clauset, "The performance of modularity maximization in practical contexts", arxiv:0910.0165
• Clara Granell, Sergio Gomez, Alex Arenas, "Mesoscopic analysis of networks: applications to exploratory analysis and data clustering", arxiv:1101.1811
• Olivier Guédon, Roman Vershynin, "Community detection in sparse networks via Grothendieck's inequality", arxiv:1411.4686
• M. B. Hastings, "Community detection as an inference problem", Physical Review E 74 (2006): 035102 = cond-mat/0604429
• Frank Havemann, Jochen Gläser, Michael Heinz, Alexander Struck, "Evaluating Overlapping Communities with the Conductance of their Boundary Nodes", arxiv:1206.3992
• Frank Havemann, Michael Heinz, Alexander Struck, Jochen Gläser, "Identification of Overlapping Communities by Locally Calculating Community-Changing Resolution Levels", Journal of Statistical Mechanics: Theory and Experiment (2011): P01023, arxiv:1008.1004
• Qirong Ho, Le Song, Eric Xing, "Evolving Cluster Mixed-Membership Blockmodel for Time-Evolving Networks", AISTATS 2011
• Qirong Ho, Ankur Parikh, Le Song, Eric Xing, "Multiscale Community Blockmodel for Network Exploration", AISTATS 2011
• Erik Holmström, Nicolas Bock and Joan Brännlund, "Density Analysis of Network Community Divisions", cond-mat/0608612
• Yanqing Hu, Yuchao Nie, Hua Yang, Jie Cheng, Ying Fan, and Zengru Di, "Measuring the significance of community structure in complex networks", Physical Review E 82 (2010): 066106
• I. Ispolatov, I. Mazo, A. Yuryev, "Finding mesoscopic communities in sparse networks", Journal of Statistical Mechanics (2006): P09014, q-bio.MN/0512038
• Adel Javanmard, Andrea Montanari, and Federico Ricci-Tersenghi, "Phase transitions in semidefinite relaxations", Proceedings of the National Academy of Sciences 113 (2016): E2218--E2223
• Maximilian Jerdee, Alec Kirkley, M. E. J. Newman, "Normalized mutual information is a biased measure for classification and community detection", arxiv:2307.01282
• Lucas G. S. Jeub, Prakash Balachandran, Mason A. Porter, Peter J. Mucha, Michael W. Mahoney, "Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks", arxiv:1403.3795
• Antony Joseph, Bin Yu, "Impact of regularization on Spectral Clustering", arxiv:1312.1733
• Brian Karrer, Elizaveta Levina, M. E. J. Newman, "Robustness of community structure in networks", arxiv:0709.2108
• Athanasios Kehagias, "Bad Communities with High Modularity", arxiv:1209.2678
• Alireza Khadivi, Ali Ajdari Rad, and Martin Hasler, "Network community-detection enhancement by proper weighting", Physical Review E 83 (2011): 046104
• Dae Il Kim, Michael Hughes, Erik Sudderth, "The Nonparametric Metadata Dependent Relational Model", ICML 2012, arxiv:1206.6414
• Jongkwang Kim and Thomas Wilhelm, "Spanning tree separation reveals community structure in networks", Physical Review E 87 (2013): 032816
• Sungmin Kim, Tao Shi, "Scalable Spectral Algorithms for Community Detection in Directed Networks", arxiv:1211.6807
• Tomoki Kobayashi, Koji Eguchi, "Sequential Monte Carlo Inference of Mixed Membership Stochastic Blockmodels for Dynamic Social Networks", arxiv:1312.2154
• Jussi M. Kumpula, Jari Saramaki, Kimmo Kaski, and Janos Kertesz, "Resolution limit in complex network community detection with Potts model approach",cond-mat/0610370
• Vincent Labatut, "Generalized Measures for the Evaluation of Community Detection Methods", arxiv:1303.5441
• Darong Lai, Christine Nardini and Hongtao Lu, "Partitioning networks into communities by message passing", Physical Review E 83 (2011): 016115
• Renaud Lambiotte, "Multi-scale Modularity in Complex Networks", arxiv:1004.4268
• Andrea Lancichinetti, Santo Fortunato
  • "Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities", arxiv:0904.3940
  • "Community detection algorithms: A comparative analysis", Physical Review E 80 (2009): 056117
  • "Limits of modularity maximization in community detection", Physical Review E 84 (2011): 066122, arxiv:1107.1155
  • "Consensus clustering in complex networks", arxiv:1203.6093
• Andrea Lancichinetti, Filippo Radicchi, Jose' Javier Ramasco, Santo Fortunato, "Finding statistically significant communities in networks", arxiv:1012.2363
• Daniel B. Larremore, Aaron Clauset, Abigail Z. Jacobs, "Efficiently inferring community structure in bipartite networks", arxiv:1403.2933
• P. Latouche, E. Birmelé, C. Ambroise, "Model Selection in Overlapping Stochastic Block Models", arxiv:1405.2722
• Can M. Le, Elizaveta Levina, "Estimating the number of communities in networks by spectral methods", arxiv:1507.00827
• Can M. Le, Elizaveta Levina, Roman Vershynin, "Optimization via Low-rank Approximation, with Applications to Community Detection in Networks", arxiv:1406.0067
• Conrad Lee, Pádraig Cunningham, "Benchmarking community detection methods on social media data", arxiv:1302.0739
• Sune Lehmann, Martin Schwartz, Lars Kai Hansen, "Bi-clique Communities", arxiv:0710.4867
• Jing Lei, "A Goodness-of-fit Test for Stochastic Block Models", arxiv:1412.4857
• Jing Lei, Alessandro Rinaldo, "Consistency of Spectral Clustering in Sparse Stochastic Block Models", Annals of Statistics 43 (2015): 215--237, arxiv:1312.2050
• Jing Lei, Lingxue Zhu, "A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models", arxiv:1411.1469
• Erwan Le Martelot, Chris Hankin
  • "Fast Multi-Scale Detection of Relevant Communities", arxiv:1204.1002
  • "Fast Multi-Scale Community Detection based on Local Criteria within a Multi-Threaded Algorithm", arxiv:1301.0955
• Michele Leone, Sumedha, Martin Weigt, "Clustering by soft-constraint affinity propagation: Applications to gene-expression data", arxiv:0705.2646
• Hoai An Le Thi, Manh Cuong Nguyen and Tao Pham Dinh, "A DC Programming Approach for Finding Communities in Networks", Neural Computation 26 (2014): 2827--2854
• Ian X.Y. Leung, Pan Hui, Pietro Lio', Jon Crowcroft, "Towards Real Time Community Detection in Large Networks", arxiv:0808.2633
• D. Liu, N. Blenn, P. Van Mieghem, "Modeling Social Networks with Overlapping Communities Using Hypergraphs and Their Line Graphs", arxiv:1012.2774
• Michael W. Mahoney, Lorenzo Orecchia, Nisheeth K. Vishnoi, "A Local Spectral Method for Graphs: With Applications to Improving Graph Partitions and Exploring Data Graphs Locally", Journal of Machine Learning Research 13 (2012): 2339--2365, arxiv:0912.0681
• Claire P. Massen, Jonathan P. K. Doye, "Thermodynamics of Community Structure", cond-mat/0610077
• Aaron F. McDaid, Derek Greene, Neil Hurley, "Normalized Mutual Information to evaluate overlapping community finding algorithms", arxiv:1110.2515
• Aaron F. McDaid, Thomas Brendan Murphy, Nial Friel, Neil J Hurley, "Clustering in networks with the collapsed Stochastic Block Model", arxiv:1203.3083
• A. D. Medus and C. O. Dorso, "Alternative approach to community detection in networks", Physical Review E 79 (2009): 066111
• Atieh Mirshahvalad, Johan Lindholm, Mattias Derlen, Martin Rosvall, "Significant communities in large sparse networks", arxiv:1110.0305
• Anirban Mitra, Konasale Prasad, Joshua Cape, "On inference for modularity statistics in structured networks", arxiv:2402.15489
• Bivas Mitra, Lionel Tabourier, Camille Roth, "Intrinsically Dynamic Network Communities", arxiv:1111.2018
• Stefanie Muff, Francesco Rao, and Amedeo Caflisch, "Local modularity measure for network clusterizations", Physical Review E 72 (2005): 056107
• M. E. J. Newman, "Community Detection and Graph Partitioning", arxiv:1305.4974
• Takashi Nishikawa, Adilson E. Motter, "Discovering Network Structure Beyond Communities", arxiv:1111.6115
• Günce Orman, Vincent Labatut, Hocine Cherifi [These papers look very similar...]
  • "Comparative Evaluation of Community Detection Algorithms: A Topological Approach", arxiv:1206.4987
  • "Qualitative Comparison of Community Detection Algorithms", arxiv:1207.3603
  • "An Empirical Study of the Relation Between Community Structure and Transitivity", arxiv:1207.3234
• Gergely Palla, Imre Derenyi, Illes Farkas and Tamas Vicsek, "Uncovering the overlapping community structure of complex networks in nature and society", Nature 435 (2005): 814--818 = physics/0506133
• Gergely Palla, Illes J. Farkas, Peter Pollner, Imre Derenyi, Tamas Vicsek, "Directed network modules", physics/0703248
• Konstantina Palla, David Knowles, Zoubin Ghahramani, "An Infinite Latent Attribute Model for Network Data", arxiv:1206.6416
• Tiago P. Peixoto
  • "Parsimonious Module Inference in Large Networks", Physical Review Letters 110 (2013): 148701, arxiv:1212.4794
  • "Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models", arxiv:1310.4378
  • "Hierarchical block structures and high-resolution model selection in large networks", arxiv:1310.4377
• Lijun Peng, Luis Carvalho, "Bayesian Degree-Corrected Stochastic Block Models for Community Detection", arxiv:1309.4796
• Carlo Piccardi, "Finding and testing network communities by lumped Markov chains", arxiv:1106.0596
• Stefan Pinkert, Joerg Schultz, Joerg Reichardt, "Protein-Interaction-Networks: More than mere modules", arxiv:0812.2184
• Nicolas Pissard and Houssem Assadi, "Detecting overlapping communities in linear time with P&A algorithm", physics/0509254
• Pascal Pons, "Post-Processing Hierarchical Community Structures: Quality Improvements and Multi-scale View", cs.DS/0608050
• Mason A. Porter, Jukka-Pekka Onnela, Peter J. Mucha, "Communities in Networks", arxiv:0902.3788
• Arnau Prat-Pérez, David Dominguez-Sal, Josep M. Brunat, Josep-Lluis Larriba-Pey, "Shaping Communities out of Triangles", arxiv:1207.6269
• Ioannis Psorakis, Stephen Roberts, Ben Sheldon, "Efficient Bayesian Community Detection using Non-negative Matrix Factorisation", arxiv:1009.2646
• Josep M. Pujol, Javier Béjar, and Jordi Delgado, "Clustering algorithm for determining community structure in large networks", Physical Review E 74 (2006): 016107
• Francisco A. Rodrigues, Gonzalo Travieso, Luciano da F. Costa, "Fast Community Identification by Hierarchical Growth", physics/0602144
• Tai Qin, Karl Rohe, "Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel", arxiv:1309.4111
• Huaijun Qiu and Edwin R. Hancock, "Graph matching and clustering using spectral partitions", Pattern Recognition 39 (2006): 22--34 [In this context, for the ideas on hierarchical decomposition, which sounds like it might work for community discovery, if in fact it's not equivalent to some existing community-discovery algorithm.]
• Filippo Radicchi, Andrea Lancichinetti and José J. Ramasco, "Combinatorial approach to modularity", Physical Review E 82 (2010): 026102, arxiv:1004.5283
• Usha Nandini Raghavan, Reka Albert, Soundar Kumara, "Near linear time algorithm to detect community structures in large-scale networks", arxiv:0709.2938 ["every node is initialized with a unique label and at every step each node adopts the label that most of its neighbors currently have"]
• Anil Raj, Chris H. Wiggins, "An information-theoretic derivation of min-cut based clustering", arxiv:0811.4208 [I'm not sure if "explained over drinks" counts as "heard the talk"]
• Jörg Reichardt and Stefan Bornholdt, "When are networks truly modular?", cond-mat/0606220
• Jörg Reichardt and Michele Leone, "(Un)detectable cluster structure in sparse networks", arxiv:0711.1452
• Fergal Reid, Aaron McDaid, Neil Hurley, "Partitioning Breaks Communities", arxiv:1105.5344
• Thomas Richardson, Peter J. Mucha, Mason A. Porter, "Spectral tripartitioning of networks", Physical Review E 80 (2009): 036111, arxiv:0812.2852
• Daniel M. Romero, Chenhao Tan, Johan Ugander, "Social-Topical Affiliations: The Interplay between Structure and Popularity", arxiv:1112.1115
• Peter Ronhovde and Zohar Nussinov, "Local resolution-limit-free Potts model for community detection", Physical Review E 81 (2010): 046114, arxiv:0812.1072
• Ryan Rossi, Brian Gallagher, Jennifer Neville, Keith Henderson, "Role-Dynamics: Fast Mining of Large Dynamic Networks", arxiv:1203.2200
• Somwrita Sarkar and Andy Dong, "Community detection in graphs using singular value decomposition", Physical Review E 83 (2011): 046114
• Erin N. Sawardecker, Marta Sales-Pardo, Luís A. Nunes Amaral, "Detection of node group membership in networks with group overlap", arxiv:0812.1243
• Michael T. Schaub, Renaud Lambiotte, Mauricio Barahona, "Coding of Markov dynamics for multiscale community detection in complex networks", arxiv:1109.6642
• Dominik J. Schindler, Matthew Fuller, "Community as a Vague Operator: Epistemological Questions for a Critical Heuristics of Community Detection Algorithms", arxiv:2210.02753
• Christophe Schülke, Federico Ricci-Tersenghi, "Multiple phases in modularity-based community detection", arxiv:1506.04506
• Devavrat Shah, Tauhid Zaman, "Community Detection in Networks: The Leader-Follower Algorithm", arxiv:1011.0774
• Hua-Wei Shen, Xue-Qi Cheng, and Jia-Feng Guo, "Exploring the Structural Regularities in Networks", Physical Review E 84 (2011): 056111
• Janne Sinkkonen, Janne Aukia, Samuel Kaski, "Component models for large networks", arxiv:0803.1628
• Ryan W. Solava, Ryan P. Michaels, Tijana Milenkovic, "Identifying edge clusters in networks via edge graphlet degree vectors (edge-GDVs) and edge-GDV-similarities", arxiv:1204.2255
• Matthew Steen, Satoru Hayasaka, Karen Joyce, Paul Laurienti, "Assessing the consistency of community structure in complex networks", Physical Review E 84 (2011): 016111, arxiv:1106.0041
• S. Stramaglia, Guo-Rong Wu, M. Pellicoro, D. Marinazzo, "Expanding the Transfer Entropy to Identify Information Subgraphs in Complex Systems", arxiv:1203.3037
• Chayant Tantipathananandh, Tanya Berger-Wolf and David Kempe, "A Framework For Community Identification in Dynamic Social Networks" [PDF]
• Gergely Tibely, Marton Karsai, Lauri Kovanen, Kimmo Kaski, Janos Kertesz, Jari Saramaki, "Communities and beyond: mesoscopic analysis of a large social network with complementary methods", Physical Review E 83 (2011): 056125, arxiv:1006.0418
• V. A. Traag, G. Krings, P. Van Dooren, "Significant Scales in Community Structure", arxiv:1306.3398
• V. A. Traag, P. Van Dooren, Y. Nesterov, "Narrow scope for resolution-free community detection", arxiv:1104.3083
• Joshua R. Tyler, Dennis M. Wilkinson and Bernardo A. Huberman, "Email as Spectroscopy: Automated Discovery of Community Structure within Organizations," cond-mat/0303264
• Yves van Gennip, Blake Hunter, Raymond Ahn, Peter Elliott, Kyle Luh, Megan Halvorson, Shannon Reid, Matt Valasik, James Wo, George E. Tita, Andrea L. Bertozzi, P. Jeffrey Brantingham, "Community detection using spectral clustering on sparse geosocial data", arxiv:1206.4969
• Twan van Laarhoven, Elena Marchiori, "Axioms for Graph Clustering Quality Functions", Journal of Machine Learning Research 15 (2014): 193--215 [Not sure what this sort of axiom system is really supposed to achieve...]
• I. Vragovic and E. Louis, "Network community structure and loop coefficient method", Physical Review E 74 (2006): 016105
• Duy Quang Vu, David R. Hunter, Michael Schweinberger, "Model-Based Clustering of Large Networks", Annals of Applied Statistics 7 (2013): 1010--1039, arxiv:1207.0188
• Matthew L. Wallace, Yves Gingras, Russell Duhon, "A new approach for detecting scientific specialties from raw cocitation networks", arxiv:0807.4903
• Haoran Wen, E. A. Leicht and Raissa M. D'Souza, "Improving community detection in networks by targeted node removal", Physical Review E 83 (2011): 016114
• Kevin S. Xu, Alfred O. Hero III, "Dynamic stochastic blockmodels: Statistical models for time-evolving networks", arxiv:1304.5974
• Bowen Yan, Steve Gregory, "Identifying Communities and Key Vertices by Reconstructing Networks from Samples", PLoS ONE 8 (2013): e61006,arxiv:1304.6554
• Huijie Yang, Wenxu Wang, Tao Zhou, Binghong ang and Fangcui Zhao, "Reconstruct the Hierarchical Structure in a Complex Network", physics/0508026 ["Based upon the eigenvector centrality (EC) measure, a method is proposed to reconstruct the hierarchical structure of a complex network. It is tested on the Santa Fe Institute collaboration network, whose structure is well known."]
• Jaewon Yang, Jure Leskovec
  • "Defining and Evaluating Network Communities based on Ground-truth", arxiv:1205.6233
  • "Structure and Overlaps of Communities in Networks", arxiv:1205.6228
• Se-Young Yun, Alexandre Proutier, "Community Detection via Random and Adaptive Sampling", pp. 138--175 in COLT 2014
• Hugo Zanghi, Franck Picard, Vincent Miele, Christophe Ambroise, "Strategies for Online Inference of Model-Based Clustering in large Networks", arxiv:0910.2034
• Anderson Y. Zhang, Harrison H. Zhou, "Minimax Rates of Community Detection in Stochastic Block Models", arxiv:1507.05313
• Pan Zhang, "A revisit to evaluating accuracy of community detection using the normalized mutual information", arxiv:1501.03844
• Pan Zhang, Florent Krzakala, Jörg Reichardt, Lenka Zdeborová, "Comparative Study for Inference of Hidden Classes in Stochastic Block Models", arxiv:1207.2328
• Shuqin Zhang and Hongyu Zhao
  • "Community identification in networks with unbalanced structure", Physical Review E 85 (2012): 066114
  • "Normalized modularity optimization method for community identification with degree adjustment", Physical Review E 88 (2013): 052802
• Yuan Zhang, Elizaveta Levina, Ji Zhu, "Detecting Overlapping Communities in Networks Using Spectral Methods", arxiv:1412.3432
• Zhong-Yuan Zhang, Yong Wang, Yong-Yeol Ahn, "Overlapping Community Detection in Complex Networks using Symmetric Binary Matrix Factorization", arxiv:1303.5855
• Haijun Zhou
  • "Distance, dissimilarity index, and network community structure," physics/0302032
  • "Network Landscape from a Brownian Particle's Perspective," physics/0302030
• Ales Ziberna, "Blockmodeling of multilevel networks", Social Networks 39 (2014): 46--61, arxiv:1405.5978

To finish writing:
• "Functional Community Discovery II"