Кластерный анализ на взвешенных графах

Методы кластерного анализа, использующие взвешенные графы, рассматривают анализируемые объекты, как принадлежащие набору вершин V [5]. Две вершины v_a и v_b (соответствующие векторам x_a и x_b) могут быть соединены ненаправленным ребром Е_ab с положительным весом (мера близости между векторами). Количество ребер графа |E| равно количеству ненулевых значений близости между всеми парами точек. Набор ребер, удаление которых разбивает граф G = (V,E) на k попарно непересекающихся под-графов называется разделителем ребер. Таким образом, задача кластерного анализа сводиться к нахождению разделителя с минимальной суммой входящих в него ребер [5]. Часто при этом преследуется дополнительная цель – примерно равное количество объектов (узлов) в каждом кластере (под-графе).