Local network evolution rules drive shortest path multiplicity

Technical Summary: Local Network Evolution Rules Drive Shortest Path Multiplicity

Problem Statement
The paper addresses a fundamental question in network science: determining the minimum set of properties and models required to explain observed features in real networks. Specifically, it investigates a recent observation by Deng et al. [1] regarding a correlation between the number of network communities and the density of multiple shortest paths in real networks. While this correlation suggests a link between community structure and path multiplicity, the underlying cause remains unclear. The author hypothesizes that "local evolution rules"—mechanisms of network growth where new nodes connect based on existing local structures (e.g., copying, triadic closure, or link splitting)—are the upstream factor driving both the emergence of communities and high shortest path multiplicity.

Methodology
The study employs numerical simulations to test the hypothesis that local growth dynamics naturally lead to high shortest path multiplicity. The methodology involves:

1. Network Generation Models: Three distinct local evolution models were simulated:

   • Local Search (LS): A new node performs a random walk of $d$ steps from a random starting node and connects to all visited nodes. This model induces preferential attachment and triadic closure (forming 3-cycles).
   • Duplication-Split (DS): A new node either duplicates an existing node (connecting to all its neighbors) with probability $q$, or splits an existing link between two neighbors. This model favors the formation of 4-cycles (squares).
   • Bubble Model (BB): A chain of $L$ new nodes is added and connected to the ends of a randomly selected existing link, creating a cycle of length $L+2$.
   • Deterministic Model: A recursive growth model similar to the bubble model with $L=1$ was also tested for comparison.

2. Community Detection: Network communities were inferred using the stochastic block model (implemented in graph-tool) with degree correction, minimizing the description length to determine the optimal number of communities ($\kappa$).

3. Baseline Comparison: To isolate the effect of local structure, the author compared the local-rule networks against "non-structured" networks. These were generated by taking the local-rule networks and applying degree-preserving link rewiring (configuration model) to destroy local motifs while maintaining the degree distribution.

4. Metrics: The primary metric is the average shortest path multiplicity ($\langle \mu \rangle$), calculated as the average number of shortest paths between all pairs of nodes across 100 realizations. The study analyzes the scaling of $\langle \mu \rangle$ with network size ($n$) and the inferred number of communities ($\langle \kappa \rangle$).

Key Results
The simulations reveal distinct scaling behaviors for shortest path multiplicity depending on the presence of local structural rules:

• Non-Structured Networks: In sparse random networks (where local structure is removed via rewiring), the average shortest path multiplicity scales logarithmically with network size: $\langle \mu \rangle_{S,0} = a + b \log n$. This growth is slower than the linear scaling observed in dense Erdős-Rényi graphs.
• Local-Structure Networks (Log-Quadratic Scaling): For the Local Search (LS) and Bubble (BB) models, $\langle \mu \rangle$ scales log-quadratically with network size: $\langle \mu \rangle_{S,I} = a + b \log n + c(\log n)^2$. This model also exhibits a linear scaling relationship between $\langle \mu \rangle$ and the number of communities $\langle \kappa \rangle$.
• Local-Structure Networks (Exponential Scaling): The Duplication-Split (DS) model displays a significantly faster growth rate. Here, $\langle \mu \rangle$ scales exponentially with network size ($\langle \mu \rangle_{S,II} = ae^{bn}$) and also shows an exponential scaling with $\langle \kappa \rangle$.
• Role of Cycle Length: The difference in scaling between models appears related to the typical cycle lengths induced. The LS model creates 3-cycles (triangles), which offer limited path multiplicity, whereas the DS model creates 4-cycles (squares), where opposite nodes have two distinct shortest paths. The Bubble model confirms that cycle length parity (odd vs. even) affects community detection but follows the log-quadratic scaling regardless.
• Deterministic vs. Stochastic: A deterministic version of the bubble model yields log-linear scaling, suggesting that the stochasticity inherent in the local models contributes to the log-quadratic scaling observed in the LS and BB models.

Significance and Claims
The paper claims to demonstrate that high shortest path multiplicity in real networks is a natural expectation of local evolution rules, rather than an independent feature requiring separate explanation. The author posits that local evolution rules and network communities are "two sides of the same coin." Since local rules induce community formation and simultaneously increase shortest path multiplicity, the observed correlation between communities and path multiplicity in real networks is a direct consequence of these growth dynamics.

The study concludes that local evolution rules are the driving mechanism; the resulting network communities and high path multiplicity are emergent properties that follow from these rules. The work provides a theoretical basis for the correlation observed by Deng et al. [1], attributing it to the upstream factor of local network growth dynamics.