Способы кластеризаци на графе
Материал из MachineLearning.
Способы кластеризаци на графе
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Граф состоит из двух типов объектов 1) вершин(узлов)- V 2)ребер (пар вершин соединенных между собой) - E. Более формальная запись G:=(V,E)
Кроме этого каждый граф можно представить в виде матрицы смежности (M) размером V*V. Где Mij= растоянию между узлом i и узлом j.
Графы часто возникают при упрощении сложных систем. К примеру в виде графа удобно отображать:
- взамосвязи различных сайтов в интернете
- Социальные сети (сети контактов)
- Генные сети в молекулярной биологии
- порты, аэропорты, города (в качестве узлов графа)и пути их соединяюющие (в качестве ребер).
И в связи с необходимостью распозновать образы и кластера в больших графах необходимы способы кластеризации.
В качестве метрики растояния можно использовать суммы длин ребер (или их количества) между двумя точками, что по сути является евклидовой метрикой.
Парадигма кластеризации графа. Парадигма кластеризации графа постулирует, что
«Естественные» группы в графах, обладают следующей характеристикой:
При случайном обходе графа и поподании в кластер, мы не выйдем из него пока не обойдем многие вершины в нем.
Марковский алгоритм кластеризации
Кластеризация графов без использования метрик (пример)
Spectral
SCAN
CPM
Walktrap
Bigclam
LPA
NewmanGreedy
CNM
