Алгоритм распространения метки - Label propagation algorithm - Wikipedia

Распространение метки полууправляемый машинное обучение алгоритм, который присваивает метки ранее немаркированным точкам данных. В начале алгоритма (как правило, небольшое) подмножество точек данных имеет метки (или классификации). Эти метки распространяются на непомеченные точки на протяжении всего алгоритма.[1]

В сложные сети, реальные сети, как правило, имеют структура сообщества. Распространение метки - это алгоритм [2] для поиска сообществ. По сравнению с другими алгоритмами[3] Распространение метки имеет преимущества по времени выполнения и количеству необходимой априорной информации о структуре сети (заранее знать параметры не требуется). Недостатком является то, что он не дает уникального решения, а представляет собой совокупность множества решений.

Работа алгоритма

В исходном состоянии узлы имеют метку, обозначающую сообщество, к которому они принадлежат. Членство в сообществе меняется в зависимости от меток, которыми обладают соседние узлы. Это изменение зависит от максимального количества меток в пределах одного градуса узлов. Каждый узел инициализируется уникальной меткой, затем метки распространяются по сети. Следовательно, плотно связанные группы быстро приобретают общий ярлык. Когда в сети создается много таких плотных (консенсусных) групп, они продолжают расширяться вовне до тех пор, пока это становится невозможным.[2]

Процесс состоит из 5 шагов:[2]

1. Инициализируйте метки на всех узлах сети. Для данного узла x CИкс (0) = х.

2. Установите t = 1.

3. Расположите узлы в сети в случайном порядке и установите значение X.

4. Для каждого x ∈ X, выбранного в указанном порядке, пусть CИкс(t) = f (CИксi1(t), ..., CИкся(t), CИкся (м + 1) (t - 1), ..., СИксik (т - 1)). Здесь возвращается метка, встречающаяся с наибольшей частотой среди соседей. Выберите метку случайным образом, если существует несколько меток с самой высокой частотой.

5. Если каждый узел имеет метку, соответствующую максимальному количеству их соседей, остановите алгоритм. В противном случае установите t = t + 1 и перейдите к (3).

Множественная структура сообщества

В отличие от других алгоритмов, распространение меток может приводить к различным структурам сообщества из одного и того же начального состояния. Диапазон решений можно сузить, если некоторым узлам присвоить предварительные метки, а другим оставить метки без меток. Следовательно, немаркированные узлы с большей вероятностью адаптируются к помеченным. Для более точного определения сообществ Индекс Жаккара используется для объединения нескольких структур сообщества, содержащих всю важную информацию.[2]

Рекомендации

  1. ^ Чжу, Сяоцзинь. «Изучение данных с метками и без меток с помощью распространения меток». CiteSeerX  10.1.1.14.3864. Цитировать журнал требует | журнал = (помощь)
  2. ^ а б c d ООН Рагхаван - Р. Альберт - С. Кумара «Алгоритм, близкий к линейному по времени, для обнаружения структур сообществ в крупномасштабных сетях», 2007
  3. ^ М. Э. Дж. Ньюман, «Выявление структуры сообщества в сетях», 2004

внешняя ссылка