Presentation | 2021-05-13 Evaluation of the effect of vertex replication for random walk in autonomous distributed graphs Yoichi Ozaki, Kunitake Kaneko, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | 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. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Autonomous distributed Graph / Random Walk / Degree Centrality / Vertex Replication |
Paper # | NS2021-19 |
Date of Issue | 2021-05-06 (NS) |
Conference Information | |
Committee | NS |
---|---|
Conference Date | 2021/5/13(2days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | Online |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | 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. |
Chair | Akihiro Nakao(Univ. of Tokyo) |
Vice Chair | Tetsuya Oishi(NTT) |
Secretary | Tetsuya Oishi(NTT) |
Assistant | Shinya Kawano(NTT) |
Paper Information | |
Registration To | Technical Committee on Network Systems |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Evaluation of the effect of vertex replication for random walk in autonomous distributed graphs |
Sub Title (in English) | |
Keyword(1) | Autonomous distributed Graph |
Keyword(2) | Random Walk |
Keyword(3) | Degree Centrality |
Keyword(4) | Vertex Replication |
1st Author's Name | Yoichi Ozaki |
1st Author's Affiliation | Keio University(Keio Univ.) |
2nd Author's Name | Kunitake Kaneko |
2nd Author's Affiliation | Keio University(Keio Univ.) |
Date | 2021-05-13 |
Paper # | NS2021-19 |
Volume (vol) | vol.121 |
Number (no) | NS-17 |
Page | pp.pp.26-31(NS), |
#Pages | 6 |
Date of Issue | 2021-05-06 (NS) |