Deterministic Scale-free Networks Created in a Recursive Manner

Zhongzhi Zhang, Lili RongarXiv 2006 · DOI · arXiv

Abstract

In a recursive way and by including a parameter, we introduce a family of deterministic scale-free networks. The resulting networks exhibit small-world effects. We calculate the exact results for the degree exponent, the clustering coefficient and the diameter. The major points of our results indicate: the degree exponent can be adjusted; the clustering coefficient of each individual vertex is inversely proportional to its degree and the average clustering coefficient of all vertices approaches to a nonzero value in the infinite network order; and the diameter grows logarithmically with the number of network vertices.

Introduction

Most real-world complex networks, from the internet to metabolic pathways, exhibit "scale-free" properties—where a few hubs have many connections while most nodes have few—and "small-world" effects, characterized by short paths between any two nodes. While stochastic models like the Barabási-Albert (BA) model successfully mimic these features, they are often difficult to solve exactly. This paper addresses the need for deterministic models that allow for precise, closed-form analytical solutions for structural properties.

Recursive Construction Method

The authors propose a recursive construction method for a network $R(q, t)$, where $q$ is the size of the initial clique and $t$ represents the time step.

  1. Initialization ($t=0$): Start with a complete graph (clique) of $q+1$ vertices.
  2. Recursion ($t \ge 1$): For every existing $q$-clique in the graph, add $m$ new vertices.
  3. Connectivity: Each of these $m$ new vertices is connected to all $q$ vertices of its parent clique.

The introduction of the parameter $m$ is the key innovation, allowing for a generalization of previous deterministic models like the pseudofractal scale-free web.

Visualization of the recursive network structure showing the hierarchical organization of hubs and nodes.

Key Insights and Structural Properties

The deterministic nature of the model allows for the derivation of exact equations for network metrics, providing a predictable alternative to traditional stochastic models.

Tunable Topology

Unlike many fixed deterministic models, the parameter $m$ allows researchers to "tune" the degree exponent ($\gamma$). This means the model can be adjusted to mimic the specific "hub-and-spoke" intensity of different real-world systems. The exact formula for the power-law exponent is derived as: $$\gamma \approx 1 + \frac{\ln(mq + 1)}{\ln[m(q - 1) + 1]}$$

Clustering and Hierarchical Organization

The authors found that the clustering coefficient of an individual vertex is inversely proportional to its degree ($C(k) \sim 1/k$). This specific scaling is a hallmark of hierarchical organization often observed in biological and social networks. Even as the network grows to an infinite size, the average clustering coefficient remains high and converges to a non-zero constant.

Average clustering coefficient $C$ as a function of parameter $m$ for different $q$ values, showing convergence to high values.

Small-World Effects and Average Degree

The "diameter" (the longest shortest path) grows as $\sim 2t/q$. Since the number of vertices $N_t$ grows exponentially with $t$, the diameter grows logarithmically with $N_t$, proving the "small-world" nature of the family. Additionally, for large networks, the average degree is shown to be approximately $2q$, remaining independent of the parameter $m$.

Conclusion

This family of deterministic networks provides a powerful analytical framework for studying scale-free and small-world properties. While real-world networks are rarely perfectly recursive, these models offer exact baselines for theoretical study. Future work may involve introducing controlled randomness by applying recursive rules selectively to a fraction of cliques, maintaining analytical advantages while increasing structural flexibility.

Summary updated

Abstract

In a recursive way and by including a parameter, we introduce a family of deterministic scale-free networks. The resulting networks exhibit small-world effects. We calculate the exact results for the degree exponent, the clustering coefficient and the diameter. The major points of our results indicate: the degree exponent can be adjusted; the clustering coefficient of each individual vertex is inversely proportional to its degree and the average clustering coefficient of all vertices approaches to a nonzero value in the infinite network order; and the diameter grows logarithmically with the number of network vertices.
BibTeX
@misc{zhang2006deterministic,
  author = {Zhongzhi Zhang and Lili Rong},
  title = {{Deterministic Scale-free Networks Created in a Recursive Manner}},
  year = {2006},
  eprint = {cond-mat/0512143},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cond-mat/0512143},
}
Figure