| 講演名 | 2021-05-13 自律分散グラフにおけるRandom Walkのための頂点複製効果の評価 尾崎 耀一(慶大), 金子 晋丈(慶大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 分散管理されたグラフからRandom Walkによって，全体グラフの大まかな構造を維持したまま部分グラフを取得することは重要である．ここで，全体グラフの粗密に合わせてグラフを分割管理する集中的な管理形態とは異なり，グラフの頂点が自律分散に管理される場合，グラフのコミュニティと単一サーバが管理する頂点集合（パーティション）は一致せず，サーバ間通信が頻繁に発生することが予想される．そこでlouvain法によるモジュラリティに基づいたグラフデータのコミュニティと自律分散管理のパーティションが一致する状態をRW時のサーバ間通信が最小となる理想状態と定義し，その状態からいくつか頂点を選び別のパーティションに移動させることでさまざまなパターンの自律分散管理を再現した上で，6つの頂点複製戦略に基づいて頂点の複製を行い，自律分散管理における頂点の複製がもたらすRandom Walk時のサーバ間通信回数の削減効果を実世界グラフを用いて実験的に明らかにした．この結果，AS間の接続関係を表すグラフにおける実験において，複製対象頂点を次数中心性の大きい順に全体の5%選択し，各複製対象頂点の隣接頂点の属するパーティションに複製を配置すると，全サーバで管理する頂点数が頂点の複製をしていないときに比べて23.5%増加する一方で，Random Walkにおけるサーバ間通信が38.8%減ることが分かった． |
| 抄録(英) | It is important to obtain a subgraph from a distributed graph by Random Walk while maintaining the rough structure of the whole graph. In contrast to the centralized management where graphs are partitioned and managed according to the coarseness of the overall graph, when graph vertices are managed in an autonomous distributed manner, the graph community and the vertex set managed by a single server (called "partition") do not coincide, and inter-server communication is expected to occur frequently. We defined the state where the community of graph data based on the modularity coincides with the partition as the ideal state that minimizes inter-server communication during Random Walk. We simulated various patterns of autonomous decentralized management by picking up some vertices and moving them to other partitions. After simulating autonomous decentralized management of the graph, we replicated vertices based on six vertex replication strategies, and experimentally clarified the effect of vertex replication in autonomous decentralized management on reducing the number of server-to-server communications during Random Walk using real-world graphs. In the experiment using the AS graph, inter-server communication in Random Walk is reduced by 38.8% and the number of vertices managed by all servers (including replicas) increases by 23.5% when the top 5% of vertices ordered by its degree centrality is selected as the target vertices and the replicas are placed in the partitions to which the neighboring vertices of each target vertex belong. |
| キーワード(和) | 自律分散グラフ / ランダムウォーク / 次数中心性 / 頂点複製 |
| キーワード(英) | Autonomous distributed Graph / Random Walk / Degree Centrality / Vertex Replication |
| 資料番号 | NS2021-19 |
| 発行日 | 2021-05-06 (NS) |
| 研究会情報 | |
| 研究会 | NS |
|---|---|
| 開催期間 | 2021/5/13(から2日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | 高度プロトコル・ネットワーキング技術(IP及び高位レイヤルーチング・フィルタリング，マルチキャスト，品質・経路制御)，IPNWの利用技術(P2P，P4P，オーバレイ，SIP，NGN)，ネットワークシステム関連技術(システム構成法，インタフェース，アーキテクチャ，ハードウェア・ソフトウェア・ミドルウェア)，セキュリティ，ブロックチェーン，一般 |
| テーマ（英） | High level protocol, Networking technologies (IP and high-layer routing/filtering, Multicast, Quality/Routing control), IP network application technologies (P2P, P4P, Overlay, SIP, NGN), Network system related technologies (System configuration, Interface, Architecture, Hardware/Software/Middleware), Security, Blockchain etc. |
| 委員長氏名（和） | 中尾 彰宏(東大) |
| 委員長氏名（英） | Akihiro Nakao(Univ. of Tokyo) |
| 副委員長氏名（和） | 大石 哲矢(NTT) |
| 副委員長氏名（英） | Tetsuya Oishi(NTT) |
| 幹事氏名（和） | 水野 志郎(NTT) / 吉田 雅裕(中大) |
| 幹事氏名（英） | Shiro Mizuno(NTT) / Masahiro Yoshida(Chuo Univ.) |
| 幹事補佐氏名（和） | 河野 伸也(NTT) |
| 幹事補佐氏名（英） | Shinya Kawano(NTT) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Network Systems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 自律分散グラフにおけるRandom Walkのための頂点複製効果の評価 |
| サブタイトル（和） | |
| タイトル（英） | Evaluation of the effect of vertex replication for random walk in autonomous distributed graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 自律分散グラフ / Autonomous distributed Graph |
| キーワード(2)（和/英） | ランダムウォーク / Random Walk |
| キーワード(3)（和/英） | 次数中心性 / Degree Centrality |
| キーワード(4)（和/英） | 頂点複製 / Vertex Replication |
| 第 1 著者 氏名（和/英） | 尾崎 耀一 / Yoichi Ozaki |
| 第 1 著者 所属（和/英） | 慶應義塾大学(略称：慶大) Keio University(略称：Keio Univ.) |
| 第 2 著者 氏名（和/英） | 金子 晋丈 / Kunitake Kaneko |
| 第 2 著者 所属（和/英） | 慶應義塾大学(略称：慶大) Keio University(略称：Keio Univ.) |
| 発表年月日 | 2021-05-13 |
| 資料番号 | NS2021-19 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | NS-17 |
| ページ範囲 | pp.26-31(NS), |
| ページ数 | 6 |
| 発行日 | 2021-05-06 (NS) |