Abstract
Measuring the self-similarity, or fractality, of massive graphs is a computationally intensive task due to the NP-hard nature of the box-covering problem and the $O(n^2)$ space requirements of existing heuristics. This paper introduces Sketch-Box-Cover, a highly scalable algorithm that leverages bottom-k min-hash sketches to solve the box-covering problem in "sketch space." By achieving near-linear time and space complexity, the algorithm enables the analysis of networks with millions of nodes, a feat previously unattainable. Empirical results on synthetic and real-world datasets, including a 1.38-million-node web graph, demonstrate that the algorithm maintains high accuracy while providing orders-of-magnitude speedups over state-of-the-art methods.
Introduction
Many real-world networks, ranging from social webs to biological systems, exhibit fractality. A network is considered fractal if its structure remains self-similar across different scales. This property is typically quantified using the box-covering problem, which seeks the minimum number of boxes $N_B(\ell)$ of radius $\ell$ required to cover all nodes in the graph. For fractal networks, this relationship follows a power law: $N_B(\ell) \propto \ell^{-d_B}$, where $d_B$ is the fractal dimension.
Despite its importance, identifying fractality is challenging. The box-covering problem is NP-hard, and existing heuristics suffer from a severe memory bottleneck. Storing neighbor sets for all nodes requires $O(n^2)$ space, making it impossible to analyze massive graphs with millions of vertices on standard hardware.
Methodology: The Sketch-Box-Cover Algorithm
The core innovation of this work is moving the computation from the explicit graph domain into a compact "sketch space."
1. Sketching with Bottom-k Min-Hash
Instead of explicitly listing every node within distance $\ell$ of a vertex, the algorithm represents these sets using bottom-k min-hash sketches. These sketches allow for unbiased estimation of set cardinality and efficient merging of sets. This drastically reduces the memory footprint from $O(n^2)$ to near-linear $O(nk)$.
2. Efficient Construction and Selection
The algorithm consists of two main phases:
- Build-Sketches: A message-passing-like approach constructs sketches for all vertices in near-linear time by iterating $\ell$ times over the graph's edges.
- Select-Greedily-Fast: Once sketches are built, the problem is treated as a Set Cover problem. The authors utilize event-driven data structures (priority queues and binary search trees) to avoid redundant calculations, ensuring an execution time of $O(nk \log n)$.
Theoretical analysis proves that this approach provides a solution within a factor of $1 + 2 \ln n$ of the optimum with high probability.
Experimental Evaluation
The algorithm was evaluated against synthetic models (SHM, (u,v)-flower, and BA models) and a massive real-world dataset: the in-2004 web graph, containing 1.38 million vertices and 16.9 million edges.
Accuracy and Approximation
Despite the probabilistic nature of sketches, the algorithm correctly distinguished between fractal and non-fractal networks in all synthetic test cases. As shown in Figure 3, the approximation ratio remains stable and close to 1.0 across various values of the sketch parameter $k$, indicating that even small sketches provide high-quality results.
Key Results
- Unprecedented Scalability: The algorithm processed the 1.38-million-node
in-2004graph in approximately 11.7 hours. All competing algorithms failed due to memory exhaustion or excessive runtime. - Performance Gains: Sketch-Box-Cover is orders of magnitude faster than previous state-of-the-art heuristics like MEMB or CBB. On medium-sized graphs, it reduced computation time from thousands of seconds to mere seconds.
- Memory Efficiency: The near-linear memory usage allows for the analysis of massive graphs on a single standard server with 96GB of RAM.
Conclusion
By solving the box-covering problem in sketch space, this work overcomes the long-standing memory bottleneck in fractal analysis of graphs. The ability to analyze millions of nodes enables new discoveries in network topology, such as confirming the fractal nature of large-scale web graphs. Future work includes applying these techniques to graph coarsening to preserve essential fractal structures in reduced representations.
Summary updated