Abstract
We present a family of scale-free network model consisting of cliques, which is established by a simple recursive algorithm. We investigate the networks both analytically and numerically. The obtained analytical solutions show that the networks follow a power-law degree distribution, with degree exponent continuously tuned between 2 and 3. 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. Interestingly, we find that a special case of our model can be mapped into the Yule process.
Introduction
Most real-world networks, ranging from social circles to biological protein interactions, exhibit three fundamental characteristics: a scale-free degree distribution, high clustering, and the small-world effect. While established models like the Barabási-Albert (BA) model capture the scale-free nature, they often struggle to replicate the high clustering coefficients observed in empirical data. Conversely, models with high clustering frequently lack scale-free properties. This research introduces Evolving Pseudofractal Networks (EPNs), a unified recursive model that naturally incorporates cliques—fully connected groups—as building blocks to simultaneously achieve all three hallmarks.
Methods: Recursive Clique Construction
The EPN model is governed by three parameters: $m$, $p$, and $q$. The network construction begins with a complete graph (a clique) of $q+1$ nodes. In each subsequent time step, every existing $q$-clique in the network is considered. With a probability $p$, $m$ new vertices are added and connected to every vertex within that specific clique.
The authors utilize rate equations and recursive analytical solutions to derive topological properties. This mathematical rigor allows for the determination of exact formulas for degree distribution, clustering, and path lengths as the network scales toward infinity.
Key Results and Topological Properties
The EPN model serves as a general framework that can be tuned to represent various network types. By adjusting $m, p,$ and $q$, the model can transition between deterministic and random versions, such as the pseudofractal scale-free network (PSFN).
Scale-Free Degree Distribution
Numerical simulations confirm that the networks follow a power-law degree distribution $P(k) \sim k^{-\gamma}$. The degree exponent $\gamma$ is determined by the formula: $$\gamma \approx 1 + \frac{\ln(1 + mpq)}{\ln[1 + mp(q - 1)]}$$ This exponent is continuously tunable between 2 and 3, allowing the model to mimic a wide range of real-world systems.
Small-World and High Clustering
The model successfully replicates the small-world effect, with the average path length (APL) growing logarithmically with the total number of nodes ($\sim \ln N$). Furthermore, because the network is built from cliques, it maintains a remarkably high clustering coefficient (often $> 0.8$) that remains stable even as the network grows to a massive size.
Connection to the Yule Process
A significant finding is that a specific limiting case ($m=1, p \to 0$) maps onto the Yule process, a classic model for the evolution of biological taxa. This connection suggests that the EPN model may have profound applications in evolutionary biology and the study of diversification.
Conclusion
The EPN model provides a mathematically elegant and flexible framework for generating complex networks. By using cliques as fundamental units, it bridges the gap between scale-free and highly clustered models. Future research will explore dynamical processes on these topologies, such as synchronization and diffusion, and apply renormalization-group techniques to study physical phenomena like the Ising model on EPN structures.
Summary updated