Хорошо, давайте построим нам матрицу смежности W для этого графа, следуя простой процедуре:
если обе смежные вершины i-й и j-й имеют один и тот же цвет, тогда вес ребра между ними W_ {i, j} является большим числом (которое вы настроите позже в своих экспериментах), а в противном случае это небольшое число который вы поймете аналогично.
Теперь давайте запишем лапласиан матрицы как
L = D - W, где D - диагональная матрица с элементами d_ {i, i}, равными сумме W i-й строки.
Теперь можно легко показать, что значение
fLf ^ T, где f - произвольный вектор, мал, если вершины с огромными корректирующими весами имеют близкие значения f. Вы можете думать об этом как о способе установки системы координат для графа с i-вершиной, имеющей координату f_i в одномерном пространстве.
Теперь давайте выберем некоторое количество таких векторов f ^ k, которые дают нам представление графа в виде набора точек в некотором евклидовом пространстве, в котором, например, работает k-means: теперь у вас есть i-я вершина исходный граф, имеющий координаты f ^ 1_i, f ^ 2_i, ..., а также смежные векторы того же цвета на исходном графе, будет близок в этом новом координатном пространстве.
Вопрос о том, как выбрать векторы f, прост: просто возьмите пару собственных векторов матрицы L в качестве f, которые соответствуют небольшим, но ненулевым собственным значениям.
Это хорошо известный метод спектральная кластеризация .
Дальнейшее чтение:
Элементы статистического обучения: сбор данных, вывод и прогнозирование. от Тревор Хасти, Роберт Тибширани и Джером Фридман
, которая доступна бесплатно на странице авторов http://www -stat.stanford.edu / ~ tibs / ElemStatLearn /