| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2021-05-13 14:50 自律分散グラフにおけるRandom Walkのための頂点複製効果の評価 ○尾崎耀一・金子晋丈（慶大）  NS2021-19 |
|
| 抄録 | （和） | 分散管理されたグラフから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 / / / / | |
| 文献情報 | 信学技報, vol. 121, no. 17, NS2021-19, pp. 26-31, 2021年5月. | |
| 資料番号 | NS2021-19 | |
| 発行日 | 2021-05-06 (NS) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | NS2021-19 |
|
| 研究会情報 | |
| 研究会 | NS |
| 開催期間 | 2021-05-13 - 2021-05-14 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | 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. |
| 講演論文情報の詳細 | |
| 申込み研究会 | NS |
| 会議コード | 2021-05-NS |
| 本文の言語 | 日本語 |
| タイトル（和） | 自律分散グラフにおける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 |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 尾崎 耀一 / Yoichi Ozaki / オザキ ヨウイチ |
| 第1著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 金子 晋丈 / Kunitake Kaneko / カネコ クニタケ |
| 第2著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2021-05-13 14:50:00 |
| 発表時間 | 25分 |
| 申込先研究会 | NS |
| 資料番号 | NS2021-19 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | no.17 |
| ページ範囲 | pp.26-31 |
| ページ数 | 6 |
| 発行日 | 2021-05-06 (NS) |
[研究会発表申込システムのトップページに戻る]