Abstract
We present a family of networks, expanded deterministic Apollonian networks, which are a generalization of the Apollonian networks and are simultaneously scale-free, small-world, and highly clustered. We introduce a labeling of their vertices that allows to determine a shortest path routing between any two vertices of the network based only on the labels.
Introduction
In the study of complex networks—ranging from the Internet and social structures to metabolic pathways—three defining characteristics often emerge: they are scale-free (degree distribution follows a power law), small-world (short average path lengths), and highly clustered. While these models effectively describe real-world topologies, they often present significant challenges for efficient routing. Traditional routing protocols typically require extensive routing tables that store global network information, which becomes increasingly impractical as networks scale.
This paper introduces Expanded Apollonian Networks (EANs), a deterministic family of graphs that maintain these desirable structural properties while enabling a decentralized routing scheme. By employing a specific vertex labeling system, the authors demonstrate that the shortest path between any two nodes can be determined using only the local information contained within their labels.
Construction and Vertex Labeling
EANs are constructed through an iterative, fractal-like process. Starting from an initial clique, new vertices are added in successive steps. In each step $t$, for every existing sub-clique of a specific dimension, a new vertex is introduced and connected to all members of that sub-clique. This results in a dense, hierarchical architecture.
The core innovation lies in the labeling scheme. Each vertex is assigned a label that reflects its "genealogy" within the network's growth history. A node created at step $t$ receives a label consisting of a sequence of $t$ digits. These labels are not merely identifiers; they encode the structural relationships between nodes.
Shortest Path Routing Algorithm
The deterministic nature of EANs allows for a highly efficient routing protocol. To find the shortest path between two nodes, $U$ and $V$, the algorithm calculates the Longest Common Suffix (LCS) of their respective labels.
This suffix identifies the "Least Common Clique"—the specific branch in the network hierarchy where the paths of $U$ and $V$ intersect. Because the labels grow logarithmically ($O(\log N)$) relative to the total number of nodes $N$, the information required for routing is minimal and scales efficiently. This approach guarantees the discovery of the absolute shortest path without the need for global topology knowledge or large memory-intensive tables.
Structural Properties and Insights
The EAN model incorporates a dimension parameter $d$ that governs its structural evolution. When $d=1$, the network exhibits exponential growth; however, for $d \ge 2$, the network becomes scale-free, accurately mimicking the "hub-and-spoke" nature of many real-world systems.
Key results from the analysis include:
- Average Degree: In large-scale EANs, the average number of connections per node converges to approximately $2(d+1)$.
- Clustering: The networks maintain high clustering coefficients, reflecting the "small-world" phenomenon where neighbors of a node are likely to be connected to each other.
- Distributed Efficiency: The routing protocol is entirely distributed, requiring only simple string comparisons of labels at each hop.
Conclusion and Future Directions
While EANs provide a powerful framework for understanding routing in structured complex networks, their deterministic nature remains a limitation. Real-world networks often grow with stochastic elements and must be resilient to node or link failures—scenarios not addressed in this static, perfect model.
Nevertheless, the principles of suffix-based labeling and hierarchical routing offer a promising path forward. Future research may adapt these techniques to more flexible or random graph models, potentially leading to more robust and scalable communication protocols for large-scale man-made systems.
Summary updated