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.

Figure 1

An example of the existing sandbox scheme.

Figure 2

Obtaining $C\left[2E\right]$ and $R[N+1]$ from the adjacency matrix $A\left[N\right]\left[N\right]$.

Figure 3

Obtaining the $M_i\left(r\right)$ with the BFS algorithm for the center node $i\in S_c$.

Figure 4

The first, second, and third generation ($u,v$)-flower network with $u=2$ and $v=2$.

Figure 5

Solid lines (black lines) show the linear regressions for calculating the mass exponents ${\tau }_q$ of the 12th generation ($u,v$)-flower network with $u=2$ and $v=2$. The range between two dashed lines is used for linear regressions.

Figure 6

Mass exponents ${\tau }_q$ for the 12th generation ($u,v$)-flower network with $u=2$ and $v=2$. Solid line (black line) represents the mass exponent ${\tau }_q$ given by Eq. (6). The circles represent the numerical estimation of the ${\tau }_q$ calculated by the CESA. Each error bar takes twice the length of the standard deviation for all the results.

Figure 7

Error analysis for the mass exponents ${\tau }_q$ of the ($u,v$)-flower network with $u=2$ and $v=2$ from 684 nodes of the fifth generation to $11184812$ nodes of the 12th generation: (a) relative standard error $E_{rs}$, (b) absolute square error $E_{\mathrm{as}}$, (c) absolute error $E_a$.

Figure 8

(a) Time complexity of the CESA and the existing sandbox algorithm when $N_c=N$. (b) CPU time of the CESA when $N_c=N/10$.

Figure 9

MFA results of some real-world and large-scale networks for $q=0$ by using the CESA.