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

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

Перейти к: навигация, поиск

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

Данная статья является непроверенным учебным заданием.
Студент: Участник: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

Личные инструменты