Clustering based on multiple paths

摘要

This paper deals with a separation of strongly touching clusters using a concept of n-connectedness between pattern pairs, i.e., the number of paths between patterns. This new concept is similar to the concept of n-connectedness of graphs. Classification algorithms based on the number of independent paths and edge-disjoint paths are presented. It is shown that the latter has a transitivity. Finally, a simpler algorithm, i.e., a classification method based on the total number of paths, is presented. The proposed algorithm may be seen as an intermediate one between the ordinary connectedness algorithm and the maximal complete subgraph (MCS) algorithm.