Hostname: page-component-8448b6f56d-m8qmq Total loading time: 0 Render date: 2024-04-20T09:07:33.626Z Has data issue: false hasContentIssue false
  • English
  • Français

Mid size cliques are more common in real world networks than triangles

Published online by Cambridge University Press:  18 November 2014

NOA SLATER ,
ROYI ITZCHACK  and
YORAM LOUZOUN
NOA SLATER
Affiliation:
Department of Mathematics and Gonda Brain Research Center, Bar-Ilan University, Ramat Gan 52900, Israel. (e-mail: noa.slater@gmail.com, royi.its@gmail.com, louzouy@math.biu.ac.il)
ROYI ITZCHACK
Affiliation:
Department of Mathematics and Gonda Brain Research Center, Bar-Ilan University, Ramat Gan 52900, Israel. (e-mail: noa.slater@gmail.com, royi.its@gmail.com, louzouy@math.biu.ac.il)
YORAM LOUZOUN
Affiliation:
Department of Mathematics and Gonda Brain Research Center, Bar-Ilan University, Ramat Gan 52900, Israel. (e-mail: noa.slater@gmail.com, royi.its@gmail.com, louzouy@math.biu.ac.il)
Get access Rights & Permissions [Opens in a new window]

Abstract

Real world networks typically have large clustering coefficients. The clustering coefficient can be interpreted to be the result of a triangle closing mechanism. We have here enumerated cliques and maximal cliques in multiple networks to show that real world networks have a high number of large cliques. While triangles are more frequent than expected, large cliques are much more over-expressed, and the largest difference between real world networks and their random counterpart occurs in many networks at clique sizes of 5–7, and not at a size of 3. This does not result from the existence of few very large cliques, since a similar feature is observed when studying only maximal cliques (cliques that are not contained in other larger cliques). Moreover, when the large cliques are removed, triangles are often under-expressed.

In all networks studied but one, all node members of large cliques produce a single connected component, which represent the central “core” of the network. The observed clique distribution can be explained by multiple models, mainly hidden variables model, such as the gravitation model, or the collapse of bipartite networks. These models can explain other properties of these networks, including the sub-graph distribution and the distance distribution of the networks. This suggests that node connectivity in real world networks may be determined by the similarity between the contents of the networks' nodes. This is in contrast with models of network formation that incorporate only the properties of the network, and not the internal properties of the nodes.

Keywords

networkscliquesclustering coefficientgravitation modelpercolation
Type
Research Article
Information
Network Science , Volume 2 , Issue 3 , December 2014 , pp. 387 - 402
Copyright
Copyright © Cambridge University Press 2014 

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

Adamcsek, B., Palla, G., Farkas, I. J., Derényi, I., & Vicsek, T. (2006). CFinder: Locating cliques and overlapping modules in biological networks. Bioinformatics, 22 (8), 1021–1023.CrossRefGoogle ScholarPubMed
Adamic, L. A., & Glance, N. (2005). The political blogosphere and the 2004 US election: divided they blog.CrossRefGoogle Scholar
Alba, R. D. (1973). A graph-theoretic definition of a sociometric clique†. Journal of Mathematical Sociology, 3 (1), 113–126.CrossRefGoogle Scholar
Albert, R., & Barabasi, A. L. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics, 74 (1), 47.CrossRefGoogle Scholar
Amaral, L. A. N., Scala, A., Barthélémy, M., & Stanley, H. E. (2000). Classes of small-world networks. Proceedings of the National Academy of Sciences, 97 (21), 11149.CrossRefGoogle ScholarPubMed
Artzy-Randrup, F., Ben Tal, Stone (2004). Comment on “network motifs: Simple building blocks of complex networks” and “superfamilies of evolved and designed networks” Science “Technical Commets”, 305, 1107.Google Scholar
Békéssy, A., Bekessy, P. & Komlós, J. (1972). Asymptotic enumeration of regular matrices. Studies Science Mathematical Hungaricae, 7, 343–353.Google Scholar
Bender, E. A., & Canfield, E. R. (1978). The asymptotic number of labeled graphs with given degree sequences. Journal of Combinatorial Theory, Series A, 24 (3), 296–307.CrossRefGoogle Scholar
Bianconi, G., & Marsili, M. (2006a). Emergence of large cliques in random scale-free networks. EPL (Europhysics Letters), 74, 740.CrossRefGoogle Scholar
Bianconi, G., & Marsili, M. (2006b). Number of cliques in random scale-free network ensembles. Physica D: Nonlinear Phenomena, 224 (1–2), 1–6.CrossRefGoogle Scholar
Boguñá, M., Pastor-Satorras, R., Díaz-Guilera, A., & Arenas, A. (2004). Models of social networks based on social distance attachment. Physical Review E, 70 (5), 056122.CrossRefGoogle ScholarPubMed
Boost C++ Source Libraries.Google Scholar
Borchers, B., & Mitchell, J. E. (1994). An improved branch and bound algorithm for mixed integer nonlinear programs. Computers & Operations Research, 21 (4), 359–367.CrossRefGoogle Scholar
Bron, C., & Kerbosch, J. (1973). Algorithm 457: Finding all cliques of an undirected graph. Communications of the ACM, 16 (9), 575–577.CrossRefGoogle Scholar
Brot, H., Muchnik, L., Goldenberg, J., & Louzoun, Y. (2012). Feedback between node and network dynamics can produce real-world network properties. Physica A: Statistical Mechanics and its Applications, 391 (24), 6645–6654.CrossRefGoogle Scholar
Caldarelli, G., Capocci, A., De Los Rios, P., & Muñoz, M. A. (2002). Scale-free networks from varying vertex intrinsic fitness. Physical Review Letters, 89 (25), 258702.CrossRefGoogle ScholarPubMed
Clauset, A., Moore, C., & Newman, M. E. J. (2008). Hierarchical structure and the prediction of missing links in networks. Nature, 453 (7191), 98–101.CrossRefGoogle ScholarPubMed
Der nyi, I., Palla, G., & Vicsek, T. (2005). Clique percolation in random networks. Physical Review Letters, 94 (16), 160202.CrossRefGoogle Scholar
Dorogovtsev, S. N., & Mendes, J. F. F. (2002). Evolution of networks. Advances in Physics, 51 (4), 1079–1187.CrossRefGoogle Scholar
Du, N., Wu, B., Xu, L., Wang, B., & Pei, X. (2006, Dec. 2006). A parallel algorithm for enumerating all maximal cliques in complex network. Paper presented at the Sixth IEEE International Conference on Data Mining Workshops, Hong Kong.Google Scholar
Duch, J., & Arenas, A. (2005). Community detection in complex networks using extremal optimization. Physical Review E, 72 (2), 027104.CrossRefGoogle ScholarPubMed
Eppstein, D., Löffler, M., & Strash, D. (2010). Listing all maximal cliques in sparse graphs in near-optimal time. Algorithms and Computation, 403–414.CrossRefGoogle Scholar
Eppstein, D., & Strash, D. (2011). Listing all maximal cliques in large sparse real-world graphs. Experimental Algorithms, 364–375.CrossRefGoogle Scholar
Erdos, P., & Rényi, A. (1960). On the evolution of random graphs. Public Mathematica Institut Hungarica. Academic Science, 5, 17–61.Google Scholar
Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486 (3–5), 75–174.CrossRefGoogle Scholar
Fortunatoa, S., & Castellanob, C. (2007). Community Structure in Graphs. Arxiv Preprint Arxiv:0712.2716.Google Scholar
Girvan, M., & Newman, M. E. J. (2002). Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99 (12), 7821.CrossRefGoogle ScholarPubMed
Gleeson, J. P. (2009). Bond percolation on a class of clustered random networks. ArXiv Preprint ArXiv:0904.4292.Google Scholar
Gleiser, P., & Danon, L. (2003). Community structure in Jazz adv. Complex Systems, 6, 565.CrossRefGoogle Scholar
Guillaume, J.-L., & Latapy, M. (2006). Bipartite graphs as models of complex networks. Physica A: Statistical Mechanics and its Applications, 371 (2), 795–813.CrossRefGoogle Scholar
Itzhack, R., & Louzoun, Y. (2010). Random distance dependent attachment as a model for neural network generation in the Caenorhabditis elegans. Bioinformatics, 26 (5), 647.CrossRefGoogle Scholar
Itzhack, R., Muchnik, L., Erez, T., Tsaban, L., Goldenberg, J., Solomon, S., & Louzoun, Y. (2010). Empirical extraction of mechanisms underlying real world network generation. Physica A: Statistical Mechanics and its Applications, 389 (22), 5308–5318.CrossRefGoogle Scholar
Janson, S., Luczak, T., & Rucinski, A. (2000). Random graphs (Vol. 333): Citeseer.CrossRefGoogle Scholar
Jensen, T. R. (1994). Graph coloring problems: John Wiley & Sons.CrossRefGoogle Scholar
Kaczor, G., & Gros, C. (2008). Evolving complex networks with conserved clique distributions. Physical review. E, Statistical, Nonlinear, and Soft Matter Physics, 78 (1 Pt 2), 016107.CrossRefGoogle ScholarPubMed
Kalveram, K. T. (1992). A neural network model rapidly learning gains and gating of reflexes necessary to adapt to an arm's dynamics. Biological Cybernetics, 68 (2), 183–191.CrossRefGoogle Scholar
Kimura, D., & Hayakawa, Y. (2008). Coevolutionary networks with homophily and heterophily. Physical Review E, 78 (1), 016103.CrossRefGoogle ScholarPubMed
Kleinberg, J. (2002). Small-world phenomena and the dynamics of information. Advances in Neural Information Processing Systems, 1, 431–438.Google Scholar
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. S. (1999). The web as a graph: Measurements, models, and methods Computing and Combinatorics (pp. 1–17): Springer.Google Scholar
Knuth, D. E. (1993). The Stanford GraphBase: a platform for combinatorial computing: AcM Press.Google Scholar
Koch, I. (2001). Enumerating all connected maximal common subgraphs in two graphs. Theoretical Computer Science, 250 (1–2), 1–30.CrossRefGoogle Scholar
Kumpula, J. M., Kivelä, M., Kaski, K., & Saramäki, J. (2008). Sequential algorithm for fast clique percolation. Physical Review E, 78 (2), 026109.CrossRefGoogle ScholarPubMed
Lee, C., Reid, F., McDaid, A., & Hurley, N. (2010). Detecting highly overlapping community structure by greedy clique expansion. Arxiv Preprint ArXiv:1002.1827.Google Scholar
Luce, R. D. (1950). Connectivity and generalized cliques in sociometric group structure. Psychometrika, 15 (2), 169–190.CrossRefGoogle ScholarPubMed
Manski, C. F. (1993). Identification of endogenous social effects: The reflection problem. Review of Economic Studies, 60 (3), 531–542.CrossRefGoogle Scholar
Marchiori, E. (1998). A simple heuristic based genetic algorithm for the maximum clique problem. Paper presented at the the 1998 ACM symposium on Applied Computing Atlanta, Georgia.CrossRefGoogle Scholar
Maslov, S., Sneppen, K., & Zaliznyak, A. (2004). Detection of topological patterns in complex networks: Correlation profile of the internet. Physica A: Statistical Mechanics and its Applications, 333, 529–540.CrossRefGoogle Scholar
McPherson, M., Smith-Lovin, L., & Cook, J. M. (2001). Birds of a feather: Homophily in social networks. Annual Review of Sociology, 415–444.CrossRefGoogle Scholar
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002). Network motifs: Simple building blocks of complex networks. Science, 298 (5594), 824.CrossRefGoogle ScholarPubMed
Mokken, R. J. (1979). Cliques, clubs and clans. Quality & Quantity, 13 (2), 161–173.CrossRefGoogle Scholar
Molloy, M., & Reed, B. (1995). A critical point for random graphs with a given degree sequence. Random Structures & Algorithms, 6 (2–3), 161–180.CrossRefGoogle Scholar
Molloy, M., & Reed, B. (1998). The size of the giant component of a random graph with a given degree sequence. Combinatorics Probability and Computing, 7 (3), 295–305.Google Scholar
Nelson, D., McEvoy, C., & Schreiber, T. (1998). The University of South Florida word association, rhyme, and word fragment norms. http.w3.usf.edu/FreeAssociation.Google Scholar
Newman, M. E. (2003). The structure and function of complex networks. SIAM Review, 45 (2), 167–256.CrossRefGoogle Scholar
Newman, M. E. (2009). Random graphs with clustering. Physical Review Letters, 103 (5), 58701.CrossRefGoogle ScholarPubMed
Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Review, 45 (2), 167–256.CrossRefGoogle Scholar
Newman, M. E. J. (2006). Finding community structure in networks using the eigenvectors of matrices. Physical Review E, 74 (3), 036104.CrossRefGoogle ScholarPubMed
Noh, J. D. (2003). Exact scaling properties of a hierarchical network model. Physical Review E, 67 (4), 045103.CrossRefGoogle ScholarPubMed
Ostergard, P. R. J. (2002). A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120 (1–3), 197–207.CrossRefGoogle Scholar
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.CrossRefGoogle ScholarPubMed
Palla, G., Derényi, I., & Vicsek, T. (2007). The Critical Point of k-Clique Percolation in the Erdős–Rényi Graph. Journal of Statistical Physics, 128 (1), 219–227.CrossRefGoogle Scholar
Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., & Parisi, D. (2004). Defining and identifying communities in networks. Proceedings of the National Academy of Sciences of the United States of America, 101 (9), 2658–2663.CrossRefGoogle ScholarPubMed
Ravasz, E. & Barabási, A. L. (2003). Hierarchical organization in complex networks. Physical Review E, 67 (2), 026112.CrossRefGoogle ScholarPubMed
Ravasz, E., Somera, A. L., Mongru, D. A., Oltvai, Z. N., & Barabási, A. L. (2002). Hierarchical organization of modularity in metabolic networks. Science, 297 (5586), 1551–1555.CrossRefGoogle ScholarPubMed
Schmidt, M. C., Samatova, N. F., Thomas, K., & Park, B. H. (2009). A scalable, parallel algorithm for maximal clique enumeration. Journal of Parallel and Distributed Computing, 69 (4), 417–428.CrossRefGoogle Scholar
Seidman, S. B. (1983). Network structure and minimum degree. Social Networks, 5 (3), 269–287.CrossRefGoogle Scholar
Seidman, S. B., & Foster, B. L. (1978). A graph-theoretic generalization of the clique concept*. Journal of Mathematical Sociology, 6 (1), 139–154.CrossRefGoogle Scholar
Shen, H., Cheng, X., Cai, K., & Hu, M. B. (2009). Detect overlapping and hierarchical community structure in networks. Physica A: Statistical Mechanics and its Applications, 388 (8), 1706–1712.CrossRefGoogle Scholar
Skiena, S. S. (1998). The algorithm design manual (Vol. 1): Springer.Google Scholar
Söderberg, B. (2002). General formalism for inhomogeneous random graphs. Physical Review E, 66 (6), 066121.CrossRefGoogle ScholarPubMed
Tarjan, R. (1972). Depth-first search and linear graph algorithms. SIAM Journal Computer, 1, 146–160.CrossRefGoogle Scholar
Tomita, E., Tanaka, A., & Takahashi, H. (2006). The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 363 (1), 28–42.CrossRefGoogle Scholar
Trapman, P. (2007). On analytical approaches to epidemics on networks. Theoretical Population Biology, 71 (2), 160.CrossRefGoogle ScholarPubMed
Tsourakakis, C. E. (2008, Dec. 2008). Fast counting of triangles in large real networks without counting: Algorithms and laws. Paper presented at the Eighth IEEE International Conference on Data Mining, Pisa.CrossRefGoogle Scholar
Wan, L., Wu, B., Du, N., Ye, Q., & Chen, P. (2006). A new algorithm for enumerating all maximal cliques in complex network. Advanced Data Mining and Applications, 606–617.CrossRefGoogle Scholar
Watts, D. J., Dodds, P. S., & Newman, M. E. J. (2002). Identity and search in social networks. Science, 296 (5571), 1302–1305.CrossRefGoogle ScholarPubMed
Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’networks. Nature, 393 (6684), 440–442.CrossRefGoogle ScholarPubMed
Wood, D. R. (1997). An algorithm for finding a maximum clique in a graph. Operations Research Letters, 21 (5), 211–217.CrossRefGoogle Scholar
Xiao, W. K., Ren, J., Qi, F., Song, Z. W., Zhu, M. X., Yang, H. F.,. .. Zhou, T. (2007). Empirical study on clique-degree distribution of networks. Physical Review E, 76 (3), 037102.CrossRefGoogle Scholar
Yan, B., & Gregory, S. (2009, Nov. 2009). Detecting communities in networks by merging cliques. Paper presented at the IEEE International Conference on Intelligent Computing and Intelligent Systems, ShanghaiCrossRefGoogle Scholar
Zhang, Q., Sun, J., & Tsang, E. (2005). An evolutionary algorithm with guided mutation for the maximum clique problem. IEEE Transactions on Evolutionary Computation, 9 (2), 192–200.CrossRefGoogle Scholar
Zhang, X., & Jarrett, D. F. (1998). Chaos in a dynamic model of traffic flows in an origin-destination network. Chaos, 8 (2), 503–513.CrossRefGoogle Scholar
Supplementary material: PDF

Slater Supplementary Material

Supplementary Material

Download Slater Supplementary Material(PDF)
PDF 1.1 MB