Computationally efficient sandbox algorithm for multifractal analysis of large-scale complex networks with tens of millions of nodes

Among various algorithms of multifractal analysis (MFA) for complex networks, the sandbox MFA algorithm behaves with the best computational efficiency. However, the existing sandbox algorithm is still computationally expensive for MFA of large-scale networks with tens of millions of nodes. It is also not clear whether MFA results can be improved by a largely increased size of a theoretical network. To tackle these challenges, a computationally efficient sandbox algorithm (CESA) is presented in this paper for MFA of large-scale networks. Distinct from the existing sandbox algorithm that uses the shortest-path distance matrix to obtain the required information for MFA of networks, our CESA employs the compressed sparse row format of the adjacency matrix and the breadth-first search technique to directly search the neighbor nodes of each layer of center nodes, and then to retrieve the required information. A theoretical analysis reveals that the CESA reduces the time complexity of the existing sandbox algorithm from cubic to quadratic, and also improves the space complexity from quadratic to linear. Then the CESA is demonstrated to be effective, efficient, and feasible through the MFA results of (u,v)-flower model networks from the fifth to the 12th generations. It enables us to study the multifractality of networks of the size of about 11 million nodes with a normal desktop computer. Furthermore, we have also found that increasing the size of (u,v)-flower model network does improve the accuracy of MFA results. Finally, our CESA is applied to a few typical real-world networks of large scale