Abstract
Considering a clique as a conservative definition of community structure, we examine how graph partitioning algorithms interact with cliques. Many popular community-finding algorithms partition the entire graph into non-overlapping communities. We show that on a wide range of empirical networks, from different domains, significant numbers of cliques are split across the separate partitions produced by these algorithms. We then examine the largest connected component of the subgraph formed by retaining only edges in cliques, and apply partitioning strategies that explicitly minimise the number of cliques split. We further examine several modern overlapping community finding algorithms, in terms of the interaction between cliques and the communities they find, and in terms of the global overlap of the sets of communities they find. We conclude that, due to the connectedness of many networks, any community finding algorithm that produces partitions must fail to find at least some significant structures. Moreover, contrary to traditional intuition, in some empirical networks, strong ties and cliques frequently do cross community boundaries; much community structure is fundamentally overlapping and unpartitionable in nature.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
Idiro Technologies.
References
Ahn Y, Bagrow J, Lehmann S (2010) Link communities reveal multiscale complexity in networks. Nature 466(7307):761–764
Blondel V, Guillaume J, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008:P10008
Bron C, Kerbosch J (1973) Finding all cliques of an undirected graph. Commun ACM 16(9):575–577
Centola D, Macy M (2007) Complex contagions and the weakness of long ties. Am J Sociol 113(3):702–734
Collins S, Kemmeren P, Zhao X, Greenblatt J, Spencer F, Holstege F, Weissman J, Krogan N (2007) Toward a comprehensive atlas of the physical interactome of Saccharomyces cerevisiae. Mol Cell Proteomics 6(3):439
Dhillon I, Guan Y, Kulis B (2007) Weighted graph cuts without eigenvectors: a multilevel approach. IEEE Trans Pattern Anal Mach Intell 1944–1957
Ellson J, Gansner E, Koutsofios E, North S, Woodhull G (2004) Graphviz and dynagraph static and dynamic graph drawing tools. In: Graph drawing software
Evans T (2010) Clique graphs and overlapping communities. J Stat Mech Theory Exp 2010:P12037
Evans T, Lambiotte R (2009) Line graphs, link partitions, and overlapping communities. Phys Rev E 80(1):016105
Everett M, Borgatti S (1998) Analyzing clique overlap. Connections 21(1):49–61
Fortunato S (2010) Community detection in graphs. Phys Rep 486:75–174
Grabowicz P, Ramasco J, Moro E, Pujol J, Eguiluz V (2012) Social features of online networks: the strength of intermediary ties in online social media. PLoS ONE 7(1):e29358
Granovetter M (1973) The strength of weak ties. Am J Sociol 78(6):1360
Havemann F, Heinz M, Struck A, Gläser J (2010) Identification of overlapping communities by locally calculating community-changing resolution levels. arXiv:1008.1004
Karypis G, Kumar V (1999) Multilevel k-way hypergraph partitioning. In: Proceedings of the 36th annual ACM/IEEE design automation conference. ACM, New York
Kernighan B, Lin S (1970) An efficient heuristic procedure for partitioning graphs. Bell Syst Tech J 49(2):291–307
Kwak H, Lee C, Park H, Moon S (2010) What is Twitter, a social network or a news media? In: Proceedings of the 19th international conference on world wide web. ACM, New York, pp 591–600
Lancichinetti A, Fortunato S (2009) Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys Rev E 80(1):16118
Lancichinetti A, Radicchi F, Ramasco J, Fortunato S (2011) Finding statistically significant communities in networks. PLoS ONE 6(4):e18961
Lee C, Reid F, McDaid A, Hurley N (2010) Detecting highly overlapping community structure by greedy clique expansion. In: KDD SNA 2010
Leskovec J, Lang K, Dasgupta A, Mahoney M (2008) Statistical properties of community structure in large social and information networks. In: Proceeding of the 17th international conference on world wide web. ACM, New York, pp 695–704
Luce R, Perry A (1949) A method of matrix analysis of group structure. Psychometrika 14(2):95–116
McDaid A, Hurley N (2010) Detecting highly overlapping communities with model-based overlapping seed expansion. In: Advances in social networks analysis and mining (ASONAM), 2010 international conference on. IEEE Comput Soc, Los Alamitos, pp 112–119
Newman M (2004) Detecting community structure in networks. Eur Phys J B, Condens Matter Complex Systems 38(2):321–330
Palla G, Derényi I, Farkas I, Vicsek T (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043):814–818
Reid F, McDaid A, Hurley N (2011) Partitioning breaks communities. In: 2011 Advances in social network analysis and mining
Shen H, Cheng X, Cai K, Hu M (2009) Detect overlapping and hierarchical community structure in networks. Phys A, Stat Mech Appl 388(8):1706–1712
Shi X, Adamic L, Strauss M (2007) Networks of strong ties. Phys A, Stat Mech Appl 378(1):33–47
Traud A, Kelsic E, Mucha P, Porter M (2011) Comparing community structure to characteristics in online collegiate social networks. SIAM Rev 53(3):526–543
van der Leij M, Goyal S (2006) Strong ties in a small world. Tinbergen Institute
Xie J, Kelley S, Szymanski B (2011) Overlapping community detection in networks: the state of the art and comparative study. arXiv:1110.5813
Yan B, Gregory S (2009) Detecting communities in networks by merging cliques. In: Intelligent computing and intelligent systems, 2009, ICIS 2009, IEEE international conference on, vol 1. IEEE Comput Soc, Los Alamitos, pp 832–836
Acknowledgements
This work is supported by Science Foundation Ireland under grant 08/SRC/I1407: Clique: Graph and Network Analysis Cluster. An earlier version of this work appeared in ASONAM ’11 [26].
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer Science+Business Media Dordrecht
About this chapter
Cite this chapter
Reid, F., McDaid, A., Hurley, N. (2013). Partitioning Breaks Communities. In: Özyer, T., Erdem, Z., Rokne, J., Khoury, S. (eds) Mining Social Networks and Security Informatics. Lecture Notes in Social Networks. Springer, Dordrecht. https://doi.org/10.1007/978-94-007-6359-3_5
Download citation
DOI: https://doi.org/10.1007/978-94-007-6359-3_5
Publisher Name: Springer, Dordrecht
Print ISBN: 978-94-007-6358-6
Online ISBN: 978-94-007-6359-3
eBook Packages: Computer ScienceComputer Science (R0)