| Presentation | 2023-12-22 [Short Paper] A Study on the Applicability of Graph Reduction to Evaluating the Robustness of Complex Networks Murakawa Yamato, Ryotaro Matsuo, Ryo Nakamura, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Generally, the computational complexity of network simulation and machine learning based on graph structure such as GNN (Graph Neural Network) and GCN (Graph Convolution Network) is dominated by the scale of a given network topology. For this reason, it is undesirable to give real large-scale networks to inputs of such computations. One of promising solutions to alleviate this problem is {em graph reduction} which reduces the size of the network while preserving its structural features. However, previous researches on 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. In other words, the effective of the graph reduction at the application-level has not been clarified.Therefore, in this paper, we focus on evaluating the robustness of networks, which is one of the typical topics in the field of network science, and evaluate how well graphs reduced with various sampling strategies and graph coarsening algorithms maintain the robustness of the original graph in terms the size of the largest connected component. As a consequence, we show, for instance, that even if the graph is significantly reduced, the robustness of the original graph is maintained. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Graph Reduction / Graph Sampling / Graph Coarsening / Network Robustness |
| Paper # | IA2023-53 |
| Date of Issue | 2023-12-14 (IA) |
| Conference Information | |
| Committee | IN / IA |
|---|---|
| Conference Date | 2023/12/21(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Satellite Campus Hiroshima |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Performance Analysis and Simulation, Robustness, Traffic and Throughput Measurement, Quality of Service (QoS) Control, Congestion Control, Overlay Network/P2P, CCN, ICN, Multicast, Routing, Security, etc. |
| Chair | Kunio Hato(NTT) / Toyokazu Akiyama(Kyoto Sangyo Univ.) |
| Vice Chair | Tsutomu Murase(Nagoya Univ.) / Yusuke Sakumoto(Kwansei Gakuin Univ.) / Toshiki Watanabe(NEC) / Yuichiro Hei(KDDI) |
| Secretary | Tsutomu Murase(NTT) / Yusuke Sakumoto(NTT) / Toshiki Watanabe(KDDI Research) / Yuichiro Hei(Fukuoka Univ.) |
| Assistant | / Daisuke Kotani(Kyoto Univ.) / Ryo Nakamura(Fukuoka Univ.) / Ryo Nakamura(Univ. of Tokyo) |
| Paper Information | |
| Registration To | Technical Committee on Information Networks / Technical Committee on Internet Architecture |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | [Short Paper] A Study on the Applicability of Graph Reduction to Evaluating the Robustness of Complex Networks |
| Sub Title (in English) | |
| Keyword(1) | Graph Reduction |
| Keyword(2) | Graph Sampling |
| Keyword(3) | Graph Coarsening |
| Keyword(4) | Network Robustness |
| 1st Author's Name | Murakawa Yamato |
| 1st Author's Affiliation | Fukuoka University(Fukuoka Univ.) |
| 2nd Author's Name | Ryotaro Matsuo |
| 2nd Author's Affiliation | Fukuoka University(Fukuoka Univ.) |
| 3rd Author's Name | Ryo Nakamura |
| 3rd Author's Affiliation | Fukuoka University(Fukuoka Univ.) |
| Date | 2023-12-22 |
| Paper # | IA2023-53 |
| Volume (vol) | vol.123 |
| Number (no) | IA-318 |
| Page | pp.pp.48-52(IA), |
| #Pages | 5 |
| Date of Issue | 2023-12-14 (IA) |