| 講演名 | 2023-12-22 ［ショートペーパー］複雑ネットワークの堅牢性評価に対するグラフ低減の適用可能性に関する一検討 村川 大和(福岡大), 松尾 涼太郎(福岡大), 中村 遼(福岡大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 一般に、ネットワークシミュレーションの計算量や、GNN (Graph Neural Network)/GCN (Graph Convolution Network) に代表されるグラフ構造に基づく機械学習の計算量は、入力に与えられるネットワークの規模に大きく依存する。このため、現実の大規模ネットワークをそのまま入力に与えるのは望ましくない。このような問題を緩和するための方策として、ネットワークの構造的特徴を保持したまま、その規模を低減させるグラフ低減が有望視されている。ただし、これまでのグラフ低減の研究は、ネットワーク規模の低減に対して、ネットワークの構造的特徴がどの程度保持されるか、ということに主眼を置いており、応用レベルでの有用性は明らかにされていない。そこで、本稿では、ネットワーク科学の分野における典型的なトピックの一つである、複雑ネットワークの堅牢性評価に着目し、様々なサンプリング方式やグラフ粗視化アルゴリズムによって低減されたグラフが、元のグラフの堅牢性をどの程度維持できているかを、最大連結成分の大きさという指標の観点で、評価する。その結果として、グラフを大幅に低減したとしても、元のグラフが有する堅牢性は維持されることなどを示す。 |
| 抄録(英) | 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. |
| キーワード(和) | グラフ低減 / グラフサンプリング / グラフ粗視化 / ネットワークの堅牢性 |
| キーワード(英) | Graph Reduction / Graph Sampling / Graph Coarsening / Network Robustness |
| 資料番号 | IA2023-53 |
| 発行日 | 2023-12-14 (IA) |
| 研究会情報 | |
| 研究会 | IN / IA |
|---|---|
| 開催期間 | 2023/12/21(から2日開催) |
| 開催地（和） | サテライトキャンパスひろしま 5階 501・502大講義室 |
| 開催地（英） | Satellite Campus Hiroshima |
| テーマ（和） | 性能評価とシミュレーション、信頼性技術、スループットやトラヒックの計測、品質(QoS)制御、輻輳制御、トラヒック・フロー制御、オーバーレイネットワーク・P2P、CCN・ICN、マルチキャスト、ルーティング、セキュリティ及び一般 |
| テーマ（英） | 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. |
| 委員長氏名（和） | 波戸 邦夫(NTT) / 秋山 豊和(京都産大) |
| 委員長氏名（英） | Kunio Hato(NTT) / Toyokazu Akiyama(Kyoto Sangyo Univ.) |
| 副委員長氏名（和） | 村瀬 勉(名大) / 作元 雄輔(関西学院大) / 渡辺 俊貴(NEC) / 屏 雄一郎(KDDI) |
| 副委員長氏名（英） | Tsutomu Murase(Nagoya Univ.) / Yusuke Sakumoto(Kwansei Gakuin Univ.) / Toshiki Watanabe(NEC) / Yuichiro Hei(KDDI) |
| 幹事氏名（和） | 濱田 浩気(NTT) / 秦泉寺 久美(NTT) / 加藤 尭彦(KDDI総合研究所) / 三角 真(福岡大) / 大平 健司(阪大) / 坂野 遼平(工学院大) / 野林 大起(九工大) |
| 幹事氏名（英） | Koki Hamada(NTT) / Kumi Jinzenji(NTT) / Takahiko Kato(KDDI Research) / Makoto Misumi(Fukuoka Univ.) / Kenji Ohira(Osaka Univ.) / Ryohei Banno(Kogakuin Univ.) / Daiki Nobayashi(Kyushu Inst. of Tech.) |
| 幹事補佐氏名（和） | / 小谷 大祐(京大) / 中村 遼(福岡大) / 中村 遼(東大) |
| 幹事補佐氏名（英） | / Daisuke Kotani(Kyoto Univ.) / Ryo Nakamura(Fukuoka Univ.) / Ryo Nakamura(Univ. of Tokyo) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Networks / Technical Committee on Internet Architecture |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ［ショートペーパー］複雑ネットワークの堅牢性評価に対するグラフ低減の適用可能性に関する一検討 |
| サブタイトル（和） | |
| タイトル（英） | [Short Paper] A Study on the Applicability of Graph Reduction to Evaluating the Robustness of Complex Networks |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ低減 / Graph Reduction |
| キーワード(2)（和/英） | グラフサンプリング / Graph Sampling |
| キーワード(3)（和/英） | グラフ粗視化 / Graph Coarsening |
| キーワード(4)（和/英） | ネットワークの堅牢性 / Network Robustness |
| 第 1 著者 氏名（和/英） | 村川 大和 / Murakawa Yamato |
| 第 1 著者 所属（和/英） | 福岡大学(略称：福岡大) Fukuoka University(略称：Fukuoka Univ.) |
| 第 2 著者 氏名（和/英） | 松尾 涼太郎 / Ryotaro Matsuo |
| 第 2 著者 所属（和/英） | 福岡大学(略称：福岡大) Fukuoka University(略称：Fukuoka Univ.) |
| 第 3 著者 氏名（和/英） | 中村 遼 / Ryo Nakamura |
| 第 3 著者 所属（和/英） | 福岡大学(略称：福岡大) Fukuoka University(略称：Fukuoka Univ.) |
| 発表年月日 | 2023-12-22 |
| 資料番号 | IA2023-53 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | IA-318 |
| ページ範囲 | pp.48-52(IA), |
| ページ数 | 5 |
| 発行日 | 2023-12-14 (IA) |