Extracting High-Fidelity Smaller Scale Subgraphs of Complex Networks by Edge-Reinforced Random Walk

Real-world networks have properties such as complex interactions and large-scale structures, which pose significant computational challenges when analyzing their structural and dynamical behavior. Network reduction algorithms, such as renormalization group and subgraph extraction, have emerged as potential solutions to address these challenges. These algorithms aim to reveal critical properties hidden within the original network, such as self-similarity and scale invariance. However, existing reduction procedures often rely on specific assumptions or have high computational complexity, which severely limits their practicality. To overcome these limitations, this article proposes a subgraph extraction strategy based on edge-reinforced random walks to achieve network reduction. In comparison with traditional renormalization procedures, our method offers lower computational complexity while effectively preserving most of the crucial structural properties of real networks. Specifically, the proposed method selects nodes with higher degree values in the network as candidate starting nodes for the random walk and then obtains smaller scale subgraphs of the original network through a random walk method that depends on the edge weights. Extensive experiments on synthetic and real networks show that the critical properties of most networks exhibit strong self-similarity behavior under the presented subgraph extraction method.