Способы кластеризаци на графе

Материал из MachineLearning.

Версия 14:57, 5 ноября 2018

Способы кластеризаци на графе

Данная статья является непроверенным учебным заданием. Студент: Участник:Konstantinov_bionet Преподаватель: Участник:Nvm Срок: 31 декабря 2018 До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Граф состоит из двух типов объектов 1) вершин(узлов)- V 
2)ребер (пар вершин соединенных между собой) - E. Более формальная запись G:=(V,E)

Кроме этого каждый граф можно представить в виде матрицы смежности (M) размером V*V. Где Mij= растоянию между узлом i и узлом j.

Графы часто возникают при упрощении сложных систем. К примеру в виде графа удобно отображать:

1. взамосвязи различных сайтов в интернете
2. Социальные сети (сети контактов)
3. Генные сети в молекулярной биологии
4. порты, аэропорты, города (в качестве узлов графа)и пути их соединяюющие (в качестве ребер).

Spectral SCAN CPM Walktrap Bigclam LPA NewmanGreedy CNM

И в связи с необходимостью распозновать образы и кластера в больших графах необходимы способы кластеризации.

В качестве метрики растояния можно использовать суммы длин ребер (или их количества) между двумя точками, что по сути является евклидовой метрикой.

Парадигма кластеризации графа. Парадигма кластеризации графа постулирует, что «Естественные» группы в графах, обладают следующей характеристикой: При случайном обходе графа и поподании в кластер, мы не выйдем из него пока не обойдем многие вершины в нем.

Марковский алгоритм кластеризации

Spectral

SCAN

CPM

Walktrap

Bigclam

LPA

NewmanGreedy

CNM