Fractality of Massive Graphs: Scalable Analysis with Sketch-Based Box-Covering Algorithm

Takuya Akiba, Kenko Nakamura, Taro Takaguchi

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.

Figure 1: Comparison of box-covering counts $b(\ell)$ for fractal (power-law decay) and non-fractal (exponential decay) models.

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.

Figure 3: Approximation ratio as a function of the sketch parameter $k$ for different graph models.

Key Results

  • Unprecedented Scalability: The algorithm processed the 1.38-million-node in-2004 graph 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

Abstract

Analysis and modeling of networked objects are fundamental pieces of modern data mining. Most real-world networks, from biological to social ones, are known to have common structural properties. These properties allow us to model the growth processes of networks and to develop useful algorithms. One remarkable example is the fractality of networks, which suggests the self-similar organization of global network structure. To determine the fractality of a network, we need to solve the so-called box-covering problem, where preceding algorithms are not feasible for large-scale networks. The lack of an efficient algorithm prevents us from investigating the fractal nature of large-scale networks. To overcome this issue, we propose a new box-covering algorithm based on recently emerging sketching techniques. We theoretically show that it works in near-linear time with a guarantee of solution accuracy. In experiments, we have confirmed that the algorithm enables us to study the fractality of million-scale networks for the first time. We have observed that its outputs are sufficiently accurate and that its time and space requirements are orders of magnitude smaller than those of previous algorithms.
BibTeX
@inproceedings{akiba2016fractality,
  author = {Takuya Akiba and Kenko Nakamura and Taro Takaguchi},
  title = {{Fractality of Massive Graphs: Scalable Analysis with Sketch-Based Box-Covering Algorithm}},
  booktitle = {ICDM},
  year = {2016},
  url = {https://openreview.net/forum?id=Q9q0oZqsgX},
}
Figure