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