Handshake between Fibonacci series and pure preferential attachment mechanism on a graph-model

Fei Ma, Ding Wang, Ping Wang, Bing YaoarXiv 2019 · arXiv

Abstract

This paper introduces a deterministic graph model, $N(t)$, that bridges classical number theory with network science. By employing a hybrid growth mechanism governed by the Fibonacci sequence, the model replicates key characteristics of real-world complex systems, such as scale-free degree distributions and small-world properties. Through rigorous mathematical induction, the authors provide exact solutions for the network's structural features, offering a formal link between Zipf’s Law and the Power-Law in deterministic environments.

Introduction

In the study of complex networks—ranging from social interactions to the infrastructure of the internet—researchers often encounter two defining characteristics: "scale-free" properties, where a few hubs possess the majority of connections, and "small-world" properties, where any two nodes are separated by a short path. While stochastic models like the Barabási-Albert (BA) model capture these phenomena through preferential attachment, they often lack the analytical precision of deterministic models.

This paper addresses the need for deterministic models that utilize mixed growth rules to explain realistic network features. The authors propose that the Fibonacci sequence can naturally drive the "rich-get-richer" mechanism, providing a predictable yet complex framework for network evolution.

Methods: The Fibonacci-Driven Growth Model

The researchers developed a deterministic graph model, $N(t)$, which evolves through discrete time steps. The growth is dictated by three fundamental operations:

  1. Triangle-growth: A new vertex is added for an existing edge and linked to its endpoints.
  2. Star-growth: Multiple new vertices are linked to a single high-degree "hub" vertex.
  3. Rectangle-growth: Parallel edges and vertices are added to create rectangular sub-structures.
The three growth operations: (a) Triangle-growth, (b) Star-growth, and (c) Rectangle-growth.

By combining these operations in a specific hybrid iteration, the number of components added at each step follows the Fibonacci recurrence relation ($F_n = F_{n-1} + F_{n-2}$). This "Fibonacci handshake" ensures that the network's growth is both structured and capable of producing massive hubs.

Network Evolution and Structural Properties

The evolution of the network from its initial state ($t=0$) through subsequent iterations demonstrates how these simple rules lead to complex global structures.

Evolution of the graph model $N(t)$ from $t=0$ to $t=2$, showing the increasing complexity and emergence of hubs.

Using rigorous induction and recursive equations, the authors derived several key results:

  • Scale-Free Nature: The model yields a power-law degree distribution with an exponent of $\gamma = 3$, matching the gold standard of the BA model.
  • Small-World Property: The network's diameter grows logarithmically ($D \propto \ln |V|$), ensuring efficient communication across the network.
  • Sparsity and Clustering: The average degree converges to approximately 3.294, maintaining a sparse yet highly clustered structure typical of social networks.

Theoretical Insights: Bridging Zipf and Power-Law

A significant contribution of this work is the formal mathematical bridge between Zipf’s Law (rank-frequency relationship) and the Power-Law (probability distribution). In this deterministic model, these two laws are shown to be different perspectives of the same underlying structural reality. Furthermore, the paper identifies a unique relationship between the total number of spanning trees and "maximum leaves" spanning trees, which has implications for network reliability and synchronization.

Conclusion and Future Work

While the model is deterministic and does not capture the stochastic noise of real-world systems, it provides a powerful analytical tool for understanding the fundamental drivers of network topology. Future research may explore generalizing the Fibonacci link to other sequences or applying this model to digital security, where password distributions often mirror the Zipfian patterns described here.

Summary updated

BibTeX
@misc{ma2019handshake,
  author = {Fei Ma and Ding Wang and Ping Wang and Bing Yao},
  title = {{Handshake between Fibonacci series and pure preferential attachment mechanism on a graph-model}},
  year = {2019},
  eprint = {1905.03039},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.03039},
}
Figure