Evolving networks consist of cliques

Zhongzhi Zhang, Shuigeng ZhouarXiv 2006 · DOI · arXiv

Abstract

Many real networks have cliques as their constitutional units. Here we present a family of scale-free network model consist of cliques, which is established by a simple recursive algorithm. We investigate the networks both analytically and numerically. The obtained analytical solution shows that the networks follow a power-law degree distribution, with degree exponent continuously tuned between 2 and 3, coinciding with the empirically found results. The exact expression of clustering coefficient is also provided for the networks. Furthermore, the investigation of the average path length reveals that the networks possess small-world feature.

Introduction

Traditional network models, such as the Barabási-Albert (BA) model, primarily focus on node-to-node preferential attachment. However, many real-world systems—including scientific co-authorship, movie actor collaborations, and biological protein-protein interaction networks—are fundamentally organized into cliques (fully connected subgraphs). In these systems, interactions often occur simultaneously among a group of entities rather than just between pairs. This paper introduces a recursive model that uses cliques as the primary building blocks to better capture the architecture of such networks.

The Recursive Growth Model

The model is defined by a recursive algorithm governed by three parameters: $q$ (clique size), $m$ (number of new vertices added per step), and $p$ (the probability of growth at a specific site).

  1. Initialization: The process begins at $t=0$ with a complete graph $K_{q+1}$.
  2. Evolution: At each subsequent time step $t \ge 1$, for every existing subgraph (clique) in the network, $m$ new vertices are added with probability $p$. Each new vertex is connected to every vertex within that specific subgraph.

This recursive nature allows the network's properties to be derived analytically, providing a rigorous mathematical foundation for its topological features.

Topological Properties and Results

Scale-Free Degree Distribution

A defining characteristic of many complex networks is a power-law degree distribution, $P(k) \sim k^{-\gamma}$. The proposed model successfully reproduces this "scale-free" property. Analytical derivations show that the degree exponent $\gamma$ can be continuously tuned between 2 and 3 by adjusting the parameters $p, q,$ and $m$. This range is particularly significant as it matches many empirical observations in real-world networks.

Cumulative degree distribution $P_{cum}(k)$ for various values of $p$, showing the power-law behavior across different growth regimes.

Numerical simulations confirm the analytical results, showing that the cumulative degree distribution $P_{cum}(k)$ follows a straight line on a log-log scale, characteristic of power-law behavior.

High Clustering and Small-World Property

Unlike many scale-free models where the clustering coefficient vanishes as the network size increases, this model maintains a high, size-independent clustering coefficient. This is a direct consequence of using cliques as the fundamental unit: every new node is immediately integrated into a fully connected group.

Furthermore, the model exhibits the "small-world" property, where the average path length (APL) grows logarithmically with the total number of nodes $N$.

Average path length (APL) as a function of the number of nodes $N$. The linear trend on a log-linear scale indicates that $APL \sim \ln N$.

As shown in the figure above, the APL remains small even as the network grows to thousands of nodes, confirming that the model effectively captures the "six degrees of separation" found in social and biological systems.

Conclusion

By shifting the focus from individual nodes to cliques, this recursive model provides a more accurate framework for understanding networks where group interactions are the norm. It simultaneously achieves a tunable power-law degree distribution, high clustering, and small-world properties, making it a versatile tool for modeling complex real-world systems. Future work may explore the effects of heterogeneous clique sizes and dynamic processes like node deletion or edge rewiring.

Summary updated

Abstract

Many real networks have cliques as their constitutional units. Here we present a family of scale-free network model consist of cliques, which is established by a simple recursive algorithm. We investigate the networks both analytically and numerically. The obtained analytical solution shows that the networks follow a power-law degree distribution, with degree exponent continuously tuned between 2 and 3, coinciding with the empirically found results. The exact expression of clustering coefficient is also provided for the networks. Furthermore, the investigation of the average path length reveals that the networks possess small-world feature.
BibTeX
@misc{zhang2006evolving,
  author = {Zhongzhi Zhang and Shuigeng Zhou},
  title = {{Evolving networks consist of cliques}},
  year = {2006},
  eprint = {cond-mat/0611622},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cond-mat/0611622},
}
Figure