Сетевая кластерная группировка

в Networkx, как я могу класть узлы на основе цвета узлов? Например, у меня есть 100 узлов, некоторые из них близки к черным, а другие близки к белому. В графическом макете я хочу, чтобы узлы с похожим цветом оставались рядом друг с другом, а узлы с очень разным цветом держались подальше друг от друга. Как я могу это сделать? В основном, как влияет вес края на макет spring_layout? Если NetworkX не может этого сделать, есть ли какие-либо другие инструменты, которые помогут рассчитать макет?

Спасибо

1 ответ

Хорошо, давайте построим матрицу смежности W для этого графика, следуя простой процедуре: если обе соседние вершины i-го и j-го имеют один и тот же цвет, тогда вес края между ними W_ {i, j} - это большое число (которое вы будете настраивать в своих экспериментах позже), а также небольшое число которые вы увидите аналогичным образом.

Теперь давайте напишем лапласиан матрицы как L = D - W, где D - диагональная матрица с элементами d_ {i, i}, равными сумме W i-й строки.

Теперь нетрудно показать, что значение fLf ^ T, где f - некоторый произвольный вектор, мал, если вершины с огромными весами регулировки имеют близкие значения f. Вы можете думать об этом как о способе установки системы координат для графа с я - вершина имеет координату f_i в 1D пространстве.

Теперь выберем некоторое число таких векторов f ^ k, которые дают нам представление графа как множество точек в некотором евклидовом пространстве, в котором, например, k-означает работу: теперь у вас есть i-я вершина начальный граф, имеющий координаты f ^ 1_i, f ^ 2_i,..., а также смежные векторы того же цвета на начальном графе будут близки в этом новом координатном пространстве.

Вопрос о том, как выбирать векторы f, является простым: просто возьмите пару собственных векторов матрицы L как f, которые соответствуют малым, но отличным от нуля собственным значениям.

Это хорошо известный метод, называемый спектральной кластеризацией.

Дальнейшее чтение: Элементы статистического обучения: интеллектуальный анализ данных, вывод и прогнозирование. Тревор Хасти, Роберт Тиббирани и Джером Фридман

который доступен бесплатно со страницы авторов http://www-stat.stanford.edu/~tibs/ElemStatLearn/

licensed under cc by-sa 3.0 with attribution.