Building k-connected neighborhood graphs for isometric data embedding.
Isometric data embedding using geodesic distance requires the construction of a connected neighborhood graph so that the geodesic distance between every pair of data points can be estimated. This paper proposes an approach for constructing k-connected neighborhood graphs. The approach works by applying a greedy algorithm to add each edge, in a nondecreasing order of edge length, to a neighborhood graph if end vertices of the edge are not yet k-connected on the graph. The k-connectedness between vertices is tested using a network flow technique by assigning every vertex a unit flow capacity. This approach is applicable to a wide range of data. Experiments show that it gives better estimation of geodesic distances than other approaches, especially when the data are undersampled or nonuniformly distributed.
Yang
Li
L
Department of Computer Science, Western Michigan University, Kalamazoo 49008, USA. li.yang@wmich.edu
D000465:Algorithms; D001185:Artificial Intelligence; D016208:Databases, Factual; D016247:Information Storage and Retrieval / Q000379:methods*