  In a standard cluster analysis, such as k-means, in addition to clusters
locations and distances between them, it's important to know if they are
connected or well separated from each other. The main focus of this paper is
discovering the relations between the resulting clusters. We propose a new
method which is based on pairwise overlapping k-means clustering, that in
addition to means of clusters provides the graph structure of their relations.
The proposed method has a set of parameters that can be tuned in order to
control the sensitivity of the model and the desired relative size of the
pairwise overlapping interval between means of two adjacent clusters, i.e.,
level of overlapping. We present the exact formula for calculating that
parameter. The empirical study presented in the paper demonstrates that our
approach works well not only on toy data but also compliments standard
clustering results with a reasonable graph structure on real datasets, such as
financial indices and restaurants.
