Paper Abstract and Keywords |
Presentation |
2021-05-13 14:50
Evaluation of the effect of vertex replication for random walk in autonomous distributed graphs Yoichi Ozaki, Kunitake Kaneko (Keio Univ.) NS2021-19 |
Abstract |
(in Japanese) |
(See Japanese page) |
(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) |
(in English) |
Autonomous distributed Graph / Random Walk / Degree Centrality / Vertex Replication / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 121, no. 17, NS2021-19, pp. 26-31, May 2021. |
Paper # |
NS2021-19 |
Date of Issue |
2021-05-06 (NS) |
ISSN |
Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
NS2021-19 |
Conference Information |
Committee |
NS |
Conference Date |
2021-05-13 - 2021-05-14 |
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. |
Paper Information |
Registration To |
NS |
Conference Code |
2021-05-NS |
Language |
Japanese |
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 |
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
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.) |
3rd Author's Name |
|
3rd Author's Affiliation |
() |
4th Author's Name |
|
4th Author's Affiliation |
() |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2021-05-13 14:50:00 |
Presentation Time |
25 minutes |
Registration for |
NS |
Paper # |
NS2021-19 |
Volume (vol) |
vol.121 |
Number (no) |
no.17 |
Page |
pp.26-31 |
#Pages |
6 |
Date of Issue |
2021-05-06 (NS) |
|