Китайский шепот (метод кластеризации)
Китайский шепот — это метод кластеризации, используемый в сетевых науках, названный в честь знаменитой игры шепота . [1] Методы кластеризации в основном используются для идентификации сообществ узлов или связей в данной сети. Этот алгоритм был разработан Крисом Биманном и Свеном Тересняком в 2005 году. [1] Название происходит от того факта, что процесс можно смоделировать как разделение сообществ, где узлы отправляют друг другу информацию одного и того же типа. [1]
Китайский шепот — это метод жесткого разделения, рандомизированной плоской кластеризации (без иерархических отношений между кластерами ). [1] Свойство случайности означает, что запуск процесса в одной и той же сети несколько раз может привести к разным результатам, при этом из-за жесткого секционирования один узел в данный момент может принадлежать только одному кластеру. Оригинальный алгоритм применим к неориентированным, взвешенным и невзвешенным графам. Китайский шепот работает в линейном времени, а это означает, что он чрезвычайно быстр, даже если в сети очень много узлов и ссылок. [1]
Алгоритм
[ редактировать ]
Алгоритм работает на неориентированном невзвешенном графе следующим образом: [1]
- Все узлы отнесены к отдельному классу, так что количество исходных классов равняется количеству узлов.
- Все узлы сети выбираются один за другим в случайном порядке. Для каждого выбранного узла метка кластера меняется на кластер, с которым у него больше всего соединений. Если есть ничья, один из связанных кластеров выбирается случайным образом.
- Второй шаг повторяется до тех пор, пока не будет выполнено заранее определенное количество итераций или пока процесс не сойдется. В конечном итоге возникающие классы представляют собой кластеры сети.
Заранее определенный порог количества итераций необходим, поскольку возможно, что процесс не сходится. С другой стороны, в сети примерно с 10 000 узлов кластеры существенно не меняются после 40-50 итераций, даже если нет сходимости. [1]
Сильные и слабые стороны
[ редактировать ]Основная сила китайского шепота заключается в его линейности во времени. Поскольку время обработки линейно увеличивается с количеством узлов, алгоритм способен очень быстро идентифицировать сообщества в сети. По этой причине китайский шепот является хорошим инструментом для анализа структур сообщества в графе с очень большим количеством узлов. Эффективность метода еще больше возрастает, если сеть обладает свойством малого мира . [1]
С другой стороны, поскольку алгоритм не является детерминированным, в случае небольшого числа узлов полученные кластеры часто существенно отличаются друг от друга. Причина этого в том, что в случае небольшой сети большее значение имеет, с какого узла начинается итерационный процесс, тогда как в больших сетях актуальность стартовых точек исчезает. [1] По этой причине для небольших графов рекомендуются другие методы кластеризации.
Приложения
[ редактировать ]Китайский шепот используется во многих областях сетевой науки. Чаще всего он упоминается в контексте проблем обработки естественного языка . [2] [3] С другой стороны, алгоритм применим к любой задаче идентификации сообщества, связанной с сетевой структурой. Китайский шепот доступен для личного использования как пакет расширения для Gephi. [4] это программа с открытым исходным кодом, предназначенная для сетевого анализа.
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с д и ж г час я Крис Биманн, «Китайский шепот — эффективный алгоритм кластеризации графов и его применение к задачам обработки естественного языка» , 2006 г.
- ^ Антонио Ди Марко - Роберто Навигили, «Кластеризация и диверсификация результатов веб-поиска с помощью графической индукции смысла слов» , 2013 г.
- ^ Иоаннис Корконцелос - Суреш Манандхар, «Обнаружение композиционности в многословных выражениях» , 2009 г.
- ^ " "Рынок Гефи" " . Архивировано из оригинала 23 сентября 2015 г. Проверено 2 июня 2015 г.