Building k-edge-connected neighborhood graph for distance-based data projection

摘要

Neighborhood graph construction is the first step of data projection based on geodesic distances. This paper presents an approach for constructing a k-edge-connected neighborhood graph. The approach works by applying a greedy algorithm to add edges in a non-decreasing order of edge length to the neighborhood graph if end vertices of each edge are not yet k-edge-connected on the graph. The approach is applicable to a wide range of data including data distributed in clusters. It is compared with other approaches through experiments.