A computationally-efficient sandbox algorithm for multifractal analysis of large-scale complex networks with tens of millions of nodes
arXiv:2005.11187 · doi:10.1103/PhysRevE.103.043303
Abstract
Multifractal analysis (MFA) is a useful tool to systematically describe the spatial heterogeneity of both theoretical and experimental fractal patterns. One of the widely used methods for fractal analysis is box-covering. It is known to be NP-hard. More severely, in comparison with fractal analysis algorithms, MFA algorithms have much higher computational complexity. Among various MFA algorithms for complex networks, the sandbox MFA algorithm behaves with the best computational efficiency. However, the existing sandbox algorithm is still computationally expensive. It becomes challenging to implement the MFA for large-scale networks with tens of millions of nodes. It is also not clear whether or not 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. Our CESA employs the breadth-first search (BFS) technique to directly search the neighbor nodes of each layer of center nodes, and then to retrieve the required information. Our CESA's input is a sparse data structure derived from the compressed sparse row (CSR) format designed for compressed storage of the adjacency matrix of large-scale network. 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. MFA experiments are performed for typical complex networks to verify our CESA. Finally, our CESA is applied to a few typical real-world networks of large scale.
arXiv comment19 pages, 9 figures
References in corpus (22)
- Self-similarity of complex networks
- Multifractality in Human Heartbeat Dynamics
- New Model of Internet Topology Using k-shell Decomposition
- MEDUSA - New Model of Internet Topology Using k-shell Decomposition
- Origins of fractality in the growth of complex networks
- A small-world of weak ties provides optimal global integration of self-similar modules in functional brain networks
- Scaling theory of transport in complex networks
- Fractal and Transfractal Recursive Scale-Free Nets
- Small world-Fractal Transition in Complex Networks: Renormalization Group Approach
- Multifractal to monofractal evolution of the London's street network
- Measure representation and multifractal analysis of complete genomes
- Multifractal Network Generator
- A Multifractal Analysis of Asian Foreign Exchange Markets
- Determination of multifractal dimensions of complex networks by means of the sandbox algorithm
- Many-body Multifractality throughout Bosonic Superfluid and Mott Insulator Phases
- Multifractality of complex networks
- Fractal and multifractal properties of a family of fractal networks
- Multifractal analysis of complex networks
- Multifractal analysis of weighted networks by a modified sandbox algorithm
- Topological properties and fractal analysis of recurrence network constructed from fractional Brownian motions
- Multifractality in random networks with power-law decaying bond strengths
- A Fixed-Mass multifractal approach for unweighted complex networks