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.
- Initialization ($t=0$): Start with a complete graph (clique) of $q+1$ vertices.
- Recursion ($t \ge 1$): For every existing $q$-clique in the graph, add $m$ new vertices.
- 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.
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.
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