Summary
International Conference on Emerging Technologies for Communications
2020
Session Number:N1
Session:
Number:N1-5
A Study on the Relation between Shortest Path Lengths of Original and Coarsened Graphs
Takeaki IWATA, Keita KITAURA, Ryotaro MATSUO, Hiroyuki OHSAKI,
pp.-
Publication Date:2020/12/2
Online ISSN:2188-5079
PDF download
Summary:
Recently, a variety of large-scale data with a graph structure,such as exchange relationships in social networks, observational information and communication records, on communication networks,have been generated, collected, and used,and one of the data mining techniques for such large-scale graphs is the reduction of the density of graphs (graph sparsification) and graph coarsening have been actively studied. The graph coarsening method, which is a method to reduce the number of dimensions of occasional data with features of large graphs, has been considered as a means to solve complex problems such as node clustering and graph partitioning problems at high speed. We believe it may also have potential application to the shortest length problem of graphs. In this paper, we investigate to what extent the shortest path length between any two vertices in a large-scale graph can be estimated by the corresponding shortest path length between two vertices in a coarsened graph of a large scale graph.