Source-linked AI summary
How to calculate the fractal dimension of a complex network: the box covering algorithm
Chaoming Song, Lazaros K. Gallos, Shlomo Havlin, Hernan A. Makse
TL;DR
The paper addresses how to efficiently find minimum box coverings that characterize self-similar and fractal complex networks. It maps box covering to vertex coloring, compares coloring and burning algorithms, and concludes that the proposed methods produce similar, near-optimal coverings while an alternative box-size definition improves fractal-dimension measurement.
Problem
Finding minimum box coverings is computationally difficult, yet these coverings are needed to study self-similar and fractal characteristics of complex networks.
Method
The paper maps box covering to vertex coloring and compares a greedy coloring algorithm with two geometric burning algorithms.
Results
The algorithms yield similar optimal numbers of boxes, while the alternate box-size definition provides a more precise measurement of network fractal dimension.
Takeaways & Limitations
The greedy coloring approach is very accurate, and the presented algorithms provide practical ways to estimate network fractal properties.
Takeaways & Limitations
Exact vertex-coloring solutions are generally feasible only for small networks because the optimization problem is NP-hard.
Abstract
from arXiv · showhide
Covering a network with the minimum possible number of boxes can reveal interesting features for the network structure, especially in terms of self-similar or fractal characteristics. Considerable attention has been recently devoted to this problem, with the finding that many real networks are self-similar fractals. Here we present, compare and study in detail a number of algorithms that we have used in previous papers towards this goal. We show that this problem can be mapped to the well-known graph coloring problem and then we simply can apply well-established algorithms. This seems to be the most efficient method, but we also present two other algorithms based on burning which provide a number of other benefits. We argue that the presented algorithms provide a solution close to optimal and that another algorithm that can significantly improve this result in an efficient way does not exist. We offer to anyone that finds such a method to cover his/her expenses for a 1-week trip to our lab in New York (details in http://jamlab.org).
1. Introduction
The paper studies algorithms for minimum box coverings of complex networks, linking the optimization to vertex coloring and comparing it with burning-based approaches. It also relates these methods to fractal and self-similar network structure.
- The paper systematically studies and compares box-covering algorithms for characterizing complex-network topology and fractal dimension.The comparison includes model and real-world networks and builds on earlier use of box covering to identify self-similarity.
- Optimal network covering can be mapped directly to the well-studied vertex coloring problem.This mapping allows established graph-coloring algorithms to be applied to box covering.
- The authors present two breadth-first-search burning methods alongside coloring-based covering.These methods address disadvantages such as disconnected or non-compact boxes.
- The study compares its approaches with prior random-burning methods for node and edge covering.The cited random-burning variation assigns neighboring unburned nodes to a box seeded by a random node.
2. The greedy coloring algorithm
The paper maps minimum network box covering to vertex coloring on a dual graph, then uses greedy coloring to obtain efficient, near-optimal coverings across box sizes. Randomized evaluations show results close to the minimum, while variance scaling differs between fractal and non-fractal networks.
- Mapping to graph coloring: Minimum box covering maps to vertex coloring: the required boxes equal the chromatic number of a dual network G′.G′ connects node pairs in G whose distance is at least ℓB; same-colored vertices then form valid boxes in G.
- Computational scope: Exact vertex coloring is feasible only for small networks because the optimization problem is NP-hard, motivating greedy approximation.Other established coloring algorithms could also be applied to box covering.
- Greedy algorithm: The greedy implementation constructs G′ and assigns colors for all ℓB values in one network pass.Nodes receive colors unavailable to their sufficiently distant predecessors, producing box assignments for successive box sizes.
- Accuracy and uncertainty: The coloring sequence can affect greedy results, but 10,000 random reshuffles produced narrow Gaussian NB distributions close to the optimum.For the E.coli cellular network, the mean and minimum box counts were very close across box sizes.
- Accuracy and uncertainty: For ℓB << ℓmax B, normalized variance follows a power law in both fractal and non-fractal networks.The exponent δ varies with fractal network structure, whereas non-fractal networks show δ close to 1.5.
- Accuracy and uncertainty: Computing fractal dimension from NB ∼ ℓB^-dB requires the minimum NB for each box size.Although an optimal greedy coloring sequence exists theoretically, the algorithm does not indicate when that minimum has been reached.
3. Burning algorithms
The paper presents breadth-first burning algorithms that construct compact boxes under diameter or radius constraints, including the faster Compact-Box-Burning method. It compares these methods with greedy coloring and examines their coverage quality, connectivity, and fractal-dimension estimates.
- Basic burning: Burning grows a box from a randomly selected uncovered node, retaining candidates within the box-size distance until no further nodes can be added.The chosen nodes form a compact box, and the procedure repeats until the network is covered.
- Compact-Box-Burning: Compact-Box-Burning (CBB) produces the same results as the basic burning algorithm with substantially lower computational cost.CBB iteratively selects candidate nodes within the union of previously constructed diameter-ℓB neighborhoods.
- Comparison with greedy coloring: CBB yields a mean box count at most 2% larger than greedy coloring, while the two algorithms have very similar normalized variances.The comparison used 10,000 realizations on fractal and non-fractal networks.
- Radius burning and MEMB: Radius-based burning can perform poorly in heterogeneous networks because starting from a non-hub may produce inefficient, non-compact coverage.Hub and non-hub starting points can require very different numbers of boxes for the same network.
- Radius burning and MEMB: MEMB seeks central nodes with maximum excluded mass to improve radius-based coverage, while greedy coloring and CBB do not guarantee connected boxes.MEMB is described as the appropriate method when box connectivity is required.
- Fractal dimension: All presented algorithms produce the same fractal dimension dB despite differences in their box counts and coverage behavior.The scaling of the number of boxes is reported as stable across the algorithms, although stabilization of random-burning averages remains unclear.
4. Box-size correction
The paper replaces the cutoff box size with an average actual box size, enabling more precise fractal-dimension measurements, particularly for inhomogeneous networks.
- The alternative box size ℓ∗_B is the maximum distance within each box plus one, and is always smaller than or equal to the cutoff ℓB.The average ℓ∗_B across boxes replaces ℓB when replotted against the number of boxes.
- Connected boxes are required for measuring ℓ∗_B consistently, so the authors use the MEMB algorithm for this calculation.
- For critical Erdos-Renyi networks, box-size correction makes the measured fractal dimension converge faster to the analytical prediction dB = 2.The inset indicates that the theoretical value is reached at smaller corrected box sizes.
- The correction smooths the tail of the plot, which may improve dB estimation for the small box sizes common in real networks.
- For the highly modular fractal network model, correction produces a robust slope across almost the entire range, whereas the uncorrected dimension is difficult to estimate.The corrected dB is practically always equal to the theoretical value in the inset.
5. Summary
The paper establishes an equivalence between box covering and vertex coloring, develops and compares greedy and geometric algorithms, and proposes an alternate box-size definition for more precise fractal-dimension measurement.
- Box covering in arbitrary networks is equivalent to vertex coloring, enabling a greedy algorithm that the authors find very accurate.
- Two geometric algorithms are compared with the greedy algorithm, and all produce a similar optimal number of boxes.
- An alternate definition of ℓB can yield a more precise measurement of a network’s fractal dimension.