  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.
