Community Discovery for Complex Networks

Given: a network, especially a large one, directed or not, weighted or not.

Desired: a sensible decomposition of the graph into sub-graphs, wherein 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“.

Ref from here

Recent (2016~)

  • Manlio De Domenico, “Diffusion Geometry Unravels the Emergence of Functional Clusters in Collective Phenomena”, Phys. Rev. Lett. 118, 168301 (2017)

Overview

Higher Priority

  1. M. E. J. Newman and Tiago P. Peixoto, “Generalized communities in networks”, Physical Review Letters 115 (2015): 088701arxiv:1505.07478
  2. M. E. J. Newman, “Spectral methods for network community detection and graph partitioning”, Physical Review E 88 (2013): 042822arxiv:1307.7729
  3. 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
  4. Andrea Bettinelli, Pierre Hansen, Leo Liberti, “Algorithm for parametric community detection in networks”, Physical Review E 86 (2012): 016107
  5. Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová, “Inference and Phase Transitions in the Detection of Modules in Sparse Networks”, Physical Review Letters 107 (2011): 065701,arxiv:1102.1182

  6. Brian Karrer, M. E. J. Newman, “Stochastic blockmodels and community structure in networks”, Physical Review E 83 (2011): 016107arxiv:1008.3926
  7. 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–878arxiv:0911.1824
  8. 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
  9. Martin Rosvall and Carl T. Bergstrom
  10. M. B. Hastings, “Community detection as an inference problem”,Physical Review E 74 (2006): 035102 = cond-mat/0604429
  11. Jim Bagrow and Erik Bollt, “A Local Method for Detecting Communities”, Physical Review E 72 (2005): 046108, cond-mat/0412482

Lower Priority

  1. Pan Zhang and Cristopher Moore, “Scalable detection of statistically significant communities and hierarchies, using message passing for modularity”, 
  2. 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–2122arxiv:1207.2340
  3. Aurelien Decelle, Florent Krzakala, Cristopher Moore and Lenka Zdeborova, “Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications”, Physical Review E 84 (2011): 066106, arxiv:1109.3041
  4. Yong-Yeol Ahn, James P. Bagrow and Sune Lehmann, “Link communities reveal multiscale complexity in networks”, Nature455 (2010): 761–764arxiv:0903.3178 [Lehmann’s blog-poston this]
  5. 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]
  6. Aaron Clauset, “Finding local community structure in networks”, Physical Review E 72 (2005): 026132physics/0503036
  7. 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
  8. 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
  9. 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
  10. J. A. Henderson and P. A. Robinson, “Geometric Effects on Complex Network Structure in the Cortex”, Physical Review Letters 107 (2011): 018102
  11. 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
  12. Andreas Noack, “Modularity clustering is force-directed layout”, Physical Review E 79 (2009): 026102arxiv:0807.4052
  13. Jörg Reichardt and Stefan Bornholdt
  14. Grant Schoenebeck, “Potential Networks, Contagious Communities, and Understanding Social Network Structure”, WWW 2013, arxiv:1304.1845
  15. Laura M. Smith, Kristina Lerman, Cristina Garcia-Cardona, Allon G. Percus, Rumi Ghosh, “Spectral Clustering with Epidemic Diffusion”, Physical Review E 88 (2013): 042813arxiv:1303.2663
  16. Greg Ver Steeg, Cristopher Moore, Aram Galstyan, Armen E. Allahverdyan, “Phase Transitions in Community Detection: A Solvable Toy Model”, arxiv:1312.0631
  17. CRS, Marcelo F. Camperi and Kristina Lisa Klinkner, “Discovering Functional Communities in Dynamical Networks”, q-bio.NC/0609008
  18. 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
  19. James P. Bagrow, “Communities and bottlenecks: Trees and treelike networks have high modularity”, Physical Review E 85(2012): 066118
  20. Michael J. Barber, John W. Clark, “Detecting network communities by propagating labels under constraints”, Physical Review E 80 (2009): 026129, arxiv:0903.3138
  21. 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
  22. 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
  23. Sanjeev Chauhan, Michelle Girvan and Edward Ott, “Spectral properties of networks with community structure”, Physical Review E 80 (2009): 056114
  24. Jordi Duch and Alex Arenas, “Community detection in complex networks using extremal optimization”, Physical Review E 72(2005): 027104
  25. 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
  26. Santo Fortunato and Claudio Castellano, “Community Structure in Graphs”, arxiv:0712.2716 [Review paper]
  27. 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
  28. Sergio Gomez, Pablo Jensen, Alex Arenas, “Analysis of community structure in networks of correlated data”, Physical Review E 80 (2009): 016114arxiv:0812.2030
  29. I. Ispolatov, I. Mazo, A. Yuryev, “Finding mesoscopic communities in sparse networks”, Journal of Statistical Mechanics (2006): P09014, q-bio.MN/0512038
  30. Adel Javanmard, Andrea Montanari, and Federico Ricci-Tersenghi, “Phase transitions in semidefinite relaxations”, Proceedings of the National Academy of Sciences 113 (2016): E2218–E2223
  31. Alireza Khadivi, Ali Ajdari Rad, and Martin Hasler, “Network community-detection enhancement by proper weighting”, Physical Review E 83 (2011): 046104
  32. Jongkwang Kim and Thomas Wilhelm, “Spanning tree separation reveals community structure in networks”, Physical Review E 87 (2013): 032816
  33. Darong Lai, Christine Nardini and Hongtao Lu, “Partitioning networks into communities by message passing”, Physical Review E 83 (2011): 016115
  34. 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
  35. Jing Lei, Alessandro Rinaldo, “Consistency of Spectral Clustering in Sparse Stochastic Block Models”, Annals of Statistics 43(2015): 215–237arxiv:1312.2050
  36. Claire P. Massen, Jonathan P. K. Doye, “Thermodynamics of Community Structure”, cond-mat/0610077
  37. A. D. Medus and C. O. Dorso, “Alternative approach to community detection in networks”, Physical Review E 79(2009): 066111
  38. Stefanie Muff, Francesco Rao, and Amedeo Caflisch, “Local modularity measure for network clusterizations”, Physical Review E 72 (2005): 056107
  39. 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–818physics/0506133
  40. Tiago P. Peixoto
  41. Josep M. Pujol, Javier Béjar, and Jordi Delgado, “Clustering algorithm for determining community structure in large networks”, Physical Review E 74 (2006): 016107
  42. Filippo Radicchi, Andrea Lancichinetti and José J. Ramasco, “Combinatorial approach to modularity”, Physical Review E 82(2010): 026102, arxiv:1004.5283
  43. Thomas Richardson, Peter J. Mucha, Mason A. Porter, “Spectral tripartitioning of networks”, Physical Review E 80 (2009): 036111, arxiv:0812.2852
  44. Peter Ronhovde and Zohar Nussinov, “Local resolution-limit-free Potts model for community detection”, Physical Review E 81(2010): 046114arxiv:0812.1072
  45. Ryan Rossi, Brian Gallagher, Jennifer Neville, Keith Henderson, “Role-Dynamics: Fast Mining of Large Dynamic Networks”, arxiv:1203.2200
  46. Somwrita Sarkar and Andy Dong, “Community detection in graphs using singular value decomposition”, Physical Review E83 (2011): 046114
  47. 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): 056125arxiv:1006.0418
  48. I. Vragovic and E. Louis, “Network community structure and loop coefficient method”, Physical Review E 74 (2006): 016105
  49. 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
  50. Se-Young Yun, Alexandre Proutier, “Community Detection via Random and Adaptive Sampling”, pp. 138–175 in COLT 2014
  51. Shuqin Zhang and Hongyu Zhao
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s