Permanence and Community Structure in Complex Networks

Abstract

The goal of community detection algorithms is to identify densely connected units within large networks. An implicit assumption is that all the constituent nodes belong equally to their associated community. However, some nodes are more important in the community than others. To date, efforts have been primarily made to identify communities as a whole, rather than understanding to what extent an individual node belongs to its community. Therefore, most metrics for evaluating communities, for example modularity, are global. These metrics produce a score for each community, not for each individual node. In this article, we argue that the belongingness of nodes in a community is not uniform. We quantify the degree of belongingness of a vertex within a community by a new vertex-based metric called permanence.

The central idea of permanence is based on the observation that the strength of membership of a vertex to a community depends upon two factors (i) the extent of connections of the vertex within its community versus outside its community, and (ii) how tightly the vertex is connected internally. We present the formulation of permanence based on these two quantities. We demonstrate that compared to other existing metrics (such as modularity, conductance, and cut-ratio), the change in permanence is more commensurate to the level of perturbation in ground-truth communities. We discuss how permanence can help us understand and utilize the structure and evolution of communities by demonstrating that it can be used to -- (i) measure the persistence of a vertex in a community, (ii) design strategies to strengthen the community structure, (iii) explore the core-periphery structure within a community, and (iv) select suitable initiators for message spreading.

We further show that permanence is an excellent metric for identifying communities. We demonstrate that the process of maximizing permanence (abbreviated as MaxPerm) produces meaningful communities that concur with the ground-truth community structure of the networks more accurately than eight other popular community detection algorithms. Finally, we provide mathematical proofs to demonstrate the correctness of finding communities by maximizing permanence. In particular, we show that the communities obtained by this method are (i) less affected by the changes in vertex ordering, and (ii) more resilient to resolution limit, degeneracy of solutions, and asymptotic growth of values.

References

1. Yong-Yeol Ahn, James P. Bagrow, and Sune Lehmann. 2010. Link communities reveal multiscale complexity in networks. Nature 466, (August 2010), 761--764.
2. A. Arenas, A. Fernández, and S. Gómez. 2008. Analysis of the structure of complex networks at different resolution levels. New Journal of Physics 10, 5 (2008), 053039.
3. David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner (Eds.). 2013. Graph partitioning and graph clustering. In Proceedings of the10th DIMACS Implementation Challenge Workshop. Contemporary Mathematics, vol. 588. American Mathematical Society.
4. Jeffrey Baumes, Mark Goldberg, and Malik Magdon-Ismail. 2005. Efficient identification of overlapping communities. In Proceedings of the 2005 IEEE International Conference on Intelligence and Security Informatics (ISI’05). Springer-Verlag, Berlin, 27--36.
5. Jonathan W. Berry, Bruce Hendrickson, Randall A. LaViolette, and Cynthia A. Phillips. 2011. Tolerating the community detection resolution limit with edge weighting. Physical Review E 83, 5 (May 2011), 056119.
6. Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of Statistical Mechanics 2008 (2008), P10008.
7. Tanmoy Chakrabort, Sandipan Sikdar, Vihar Tammana, Niloy Ganguly, and Animesh Mukherjee. 2013. Computer science fields as ground-truth communities: Their impact, rise and fall. In Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM’13). ACM, New York, NY, 426--433.
8. Tanmoy Chakraborty. 2015. Leveraging disjoint communities for detecting overlapping community structure. Journal of Statistical Mechanics: Theory and Experiment 2015, 5 (2015), P05017.
9. Tanmoy Chakraborty, Ayushi Dalmia, Animesh Mukherjee, and Niloy Ganguly. 2016a. Metrics for community analysis: A survey. CoRR abs/1604.03512 (2016).
10. Tanmoy Chakraborty, Suhansanu Kumar, Niloy Ganguly, Animesh Mukherjee, and Sanjukta Bhowmick. 2016b. GenPerm: A unified method for detecting non-overlapping and overlapping communities. CoRR abs/1604.03454 (2016).
11. Tanmoy Chakraborty, Sriram Srinivasan, Niloy Ganguly, Sanjukta Bhowmick, and Animesh Mukherjee. 2013. Constant communities in complex networks. Scientific Reports 3, (May 2013). DOI:10.1038/srep01825
12. Tanmoy Chakraborty, Sriram Srinivasan, Niloy Ganguly, Animesh Mukherjee, and Sanjukta Bhowmick. 2014. On the permanence of vertices in network communities. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’14). ACM, New York, NY, 1396--1405. DOI:http://dx.doi.org/10.1145/2623330.2623707
13. Mingming Chen, Tommy Nguyen, and Boleslaw Szymanski. 2013. A new metric for quality of network community structure. ASE Human Journal 1, 4 (2013), 226--240.
14. Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi. 2010. Rumour spreading and graph conductance. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1657--1663.
15. Aaron Clauset, M. E. J. Newman, and Cristopher Moore. 2004. Finding community structure in very large networks. Physical Review E 70, 6 (2004), 066111.
16. L. Danon, A. Diaz-Guilera, J. Duch, and A. Arenas. 2005. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment 9, (2005), P09008.
17. Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, and Alessandro Provetti. 2013. Enhancing community detection using a network weighting strategy. Journal of Information Science 222, (Feb. 2013), 648--668.
18. J.-C. Delvenne, S. N. Yaliraki, and M. Barahona. 2010. Stability of graph communities across time scales. Proceedings of the National Academy of Sciences 107, 29 (2010), 12755--12760.
19. Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry. 1987. Epidemic algorithms for replicated database maintenance. In Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing (PODC). New York, 1--12.
20. T. S. Evans and R. Lambiotte. 2009. Line graphs, link partitions, and overlapping communities. Physical Review E 80, 1 (July 2009), 016105.
21. Illés Farkas, Dániel Ábel, Gergely Palla, and Tamás Vicsek. 2007. Weighted network modules. New Journal of Physics 9, 6 (2007), 180.
22. Santo Fortunato. 2010. Community detection in graphs. Physics Reports 486, 3--5 (2010), 75--174.
23. Santo Fortunato and M. Barthelemy. 2007. Resolution limit in community detection. Proceedings of the National Acadamy of Sciences of the United States of America (PNAS) 104, 1 (2007), 36--41.
24. Saptarshi Ghosh, Avishek Banerjee, Naveen Sharma, Sanket Agarwal, and Niloy Ganguly. 2011. Statistical analysis of the indian railway network: A complex network approach. Acta Physica Polonica B Proceedings Supplement 4, (March 2011), 123--137.
25. M. Girvan and M. E. Newman. 2002. Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99, 12 (June 2002), 7821--7826.
26. B. H. Good, Y. A. De Montjoye, and A. Clauset. 2010. Performance of modularity maximization in practical contexts. Physical Review E 81, 4 (2010), 046106.
27. Roger Guimera and Luis A. Nunes Amaral. 2005. Functional cartography of complex metabolic networks. Nature 433, 7028 (Feb. 2005), 895--900.
28. Dongxiao He, Dayou Liu, Weixiong Zhang, Di Jin, and Bo Yang. 2013. Discovering link communities in complex networks by exploiting link dynamics. CoRR abs/1303.4699 (2013).
29. Paul W. Holland and Samuel Leinhardt. 1971. Transitivity in structural models of small groups. Small Group Research 2, 2 (1971), 107--124.
30. L. Hubert and P. Arabie. 1985. Comparing partitions. Journal of Classification 2, 1 (1985), 193--218.
31. R. Kannan, S. Vempala, and A. Veta. 2000. On clusterings-good, bad and spectral. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS’00). IEEE Computer Society, Washington, DC, 367.
32. David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the spread of influence through a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’03). ACM, New York, NY, 137--146. DOI:http://dx.doi.org/10.1145/956750.956769
33. Renaud Lambiotte. 2010. Multi-scale modularity in complex networks. In Proceedings of the 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt’10). IEEE, 546--553.
34. Andrea Lancichinetti and Santo Fortunato. 2009. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E 80, 1 (July 2009), 016118.
35. Andrea Lancichinetti and Santo Fortunato. 2011. Limits of modularity maximization in community detection. Physical Review E 84, (2011), 066122.
36. Andrea Lancichinetti and Santo Fortunato. 2012. Consensus clustering in complex networks. Scientific Reports 2 (2012). DOI:10.1038/srep00336
37. Andrea Lancichinetti, Santo Fortunato, and János Kertész. 2009. Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics 11, 3 (2009), 033015.
38. Andrea Lancichinetti, Filippo Radicchi, Jose J. Ramasco, and Santo Fortunato. 2010. Finding statistically significant communities in networks. CoRR abs/1012.2363 (2010).
39. E. A. Leicht and M. E. J. Newman. 2008. Community structure in directed networks. Physical Review Letters 100, 11 (March 2008), 118703.
40. Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, and Michael W. Mahoney. 2009. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics 6, 1 (2009), 29--123.
41. Jure Leskovec, Kevin J. Lang, and Michael Mahoney. 2010. Empirical comparison of algorithms for network community detection. In Proceedings of the 19th International Conference on World Wide Web (WWW’10). ACM, New York, NY, 631--640.
42. Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. 2008. Introduction to Information Retrieval. Cambridge University Press, New York, NY.
43. M. E. Newman. 2006. Modularity and community structure in networks. Proceedings of the National Academy of Sciences 103, 23 (June 2006), 8577--8582.
44. M. E. J. Newman. 2003. Mixing patterns in networks. Physical Review E 67, 2 (Feb. 2003), 026126. DOI:http://dx.doi.org/10.1103/PhysRevE.67.026126
45. M. E. J. Newman. 2004a. Analysis of weighted networks. Physical Review E 70, 5 (Nov. 2004), 056131.
46. M. E. J. Newman. 2004b. Fast algorithm for detecting community structure in networks. Physical Review E 69, 6 (June 2004), 066133.
47. M. E. J. Newman. 2013. Community detection and graph partitioning. CoRR abs/1305.4974 (2013).
48. M. E. J. Newman and M. Girvan. 2004. Finding and evaluating community structure in networks. Physical Review E 69, (2004) 026113.
49. Günce Keziban Orman, Vincent Labatut, and Hocine Cherifi. 2012. Comparative evaluation of community detection algorithms: A topological approach. CoRR abs/1206.4987 (2012).
50. Gergely Palla, Imre Dernyi, Ills Farkas, and Tams Vicsek. 2005. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 7043 (June 2005), 814--818.
51. Pascal Pons and Matthieu Latapy. 2006. Computing communities in large networks using random walks. Journal of Graph Algortihms and Applications 10, 2 (2006), 191--218.
52. Ioannis Psorakis, Stephen Roberts, Mark Ebden, and Ben Sheldon. 2011. Overlapping community detection using Bayesian non-negative matrix factorization. Physical Review E 83, 6 (June 2011), 066114.
53. Usha N. Raghavan, Réka Albert, and Soundar Kumara. 2007. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E 76, 3 (Sep. 2007), 036106.
54. J. Reichardt and S. Bornholdt. 2006. Statistical mechanics of community detection. Phys. Rev. E 74, 1 (2006), 016110.
55. Thomas Richardson, Peter J. Mucha, and Mason A. Porter. 2009. Spectral tripartitioning of networks. Physical Review E 40, (2009), 027104.
56. Jason Riedy, David A. Bader, Karl Jiang, Pushkar Pande, and Richa Sharma. 2011. Detecting Communities from Given Seeds in Social Networks. Technical Report GT-CSE-11-01. Georgia Institute of Technology.
57. M. Rosvall and C. T. Bergstrom. 2007. An information-theoretic framework for resolving community structure in complex networks. Proceedings of the National Academy of Sciences 104, 18 (2007), 7327.
58. Martin Rosvall and Carl T. Bergstrom. 2008. Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences 105, 4 (2008), 1118--1123.
59. Massoud Seifi, Ivan Junier, Jean-Baptiste Rouquier, Svilen Iskrov, and Jean-Loup Guillaume. 2013. Stable community cores in complex networks. In Complex Networks, Ronaldo Menezes, Alexandre Evsukoff, and Marta C. Gonzlez (Eds.), Studies in Computational Intelligence, vol. 424. Springer, Berlin, 87--98. DOI:http://dx.doi.org/10.1007/978-3-642-30287-9_10
60. Jianbo Shi and Jitendra Malik. 2000. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22, 8 (Aug. 2000), 888--905. DOI:http://dx.doi.org/10.1109/34.868688
61. Peng-Gang Sun, Lin Gao, and Shan Shan Han. 2011. Identification of overlapping and non-overlapping community structure by fuzzy clustering in complex networks. Information Sciences 181, 6 (2011), 1060--1071.
62. Jierui Xie and Boleslaw K. Szymanski. 2011. Community detection using a neighborhood strength driven label propagation algorithm. CoRR abs/1105.3264 (2011).
63. Jierui Xie and Boleslaw K. Szymanski. 2012. Towards linear time overlapping community detection in social networks. CoRR abs/1202.2465 (2012).
64. Jaewon Yang and Jure Leskovec. 2012. Defining and evaluating network communities based on ground-truth. In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics (MDS’12). ACM, New York, NY, 3:1--3:8.
65. Jaewon Yang and Jure Leskovec. 2014. Overlapping communities explain core-periphery organization of networks. Proceedings of IEEE 102, (2014), 1892--1902.

Index Terms

• Information systems

  • Information systems applications

    • Data mining

      • Clustering

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms