A Study on the Applicability of Graph Reduction to Evaluating the Robustness of Complex Networks

Generally, performing network simulations and deep learning using graph structure such as GNN (Graph Neural Network) requires network topologies. However, it is undesirable to directly give real large-scale networks to input of such computation tasks since the computational complexity is mainly dominated by the network size. One of promising solutions to alleviate this problem is graph reduction which reduces the size of the network, i.e., the number of nodes, while preserving its structural properties. Previous researches on the graph reduction have mainly focused on the extent to which structural property of the network is preserved with respect to the reduction in network size; this means that it is questionable that the graph reduction is actually useful at the application-level. Therefore, in this paper, we focus on evaluating the robustness of networks, which is one of typical topics in the field of network science, and evaluate whether graphs reduced with various sampling strategies and coarsening algorithms maintain the robustness of the original graph in terms the size of the largest connected component. As a consequence, we reveal, for instance, that even though the graph size is halved, reduced graphs can maintain the robustness of an original graph, in particular, random graph.