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

Noa Slater, Royi Itzchack and Yoram Louzoun

Network Science, 2014, vol. 2, issue 3, 387-402

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.

Date: 2014
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.cambridge.org/core/product/identifier/ ... type/journal_article link to article abstract page (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cup:netsci:v:2:y:2014:i:03:p:387-402_00

Access Statistics for this article

More articles in Network Science from Cambridge University Press Cambridge University Press, UPH, Shaftesbury Road, Cambridge CB2 8BS UK.
Bibliographic data for series maintained by Kirk Stebbing ().