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)