Китайский шепот (метод кластеризации) - Chinese Whispers (clustering method)

Китайский шепот метод кластеризации, используемый в сетевой науке, названный в честь известного шепчущая игра.[1] Методы кластеризации в основном используются для идентификации сообществ узлов или ссылок в данной сети. Этот алгоритм был разработан Крис Биманн и Свен Тересняк в 2005 году.[1] Название происходит от того факта, что процесс можно смоделировать как разделение сообществ, когда узлы отправляют друг другу информацию одного типа.[1]

Chinese Whispers - это жесткое разбиение, рандомизированная, плоская кластеризация (нет иерархические отношения между кластерами ) метод.[1] Свойство random означает, что запуск процесса в одной и той же сети несколько раз может привести к разным результатам, в то время как из-за жесткого разбиения один узел может принадлежать только одному кластеру в данный момент. Исходный алгоритм применим к неориентированным, взвешенным и невзвешенным графам. Китайский шепот является линейным по времени, что означает, что он чрезвычайно быстр, даже если количество узлов и ссылок в сети очень велико.[1]

Алгоритм

Пример того, как работает Chinese Whispers в действии. Разные цвета представляют разные классы.

В неориентированном невзвешенном графе алгоритм работает следующим образом:[1]

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

Заранее установленный порог количества итераций необходим, потому что возможно, что процесс не сходится. С другой стороны, в сети с примерно 10000 узлов кластеры не претерпевают значительных изменений после 40-50 итераций, даже если нет сходимости.[1]

Сильные и слабые стороны

Основная сила китайского шепота заключается в его линейности во времени. Поскольку время обработки линейно увеличивается с количеством узлов, алгоритм может очень быстро определять сообщества в сети. По этой причине Chinese Whispers - хороший инструмент для анализа структур сообщества в графе с очень большим количеством узлов. Эффективность метода возрастает еще больше, если в сети есть маленький мир собственности.[1]

С другой стороны, поскольку алгоритм не является детерминированным в случае небольшого количества узлов, результирующие кластеры часто значительно отличаются друг от друга. Причина этого в том, что в случае небольшой сети больше имеет значение, с какого узла начинается процесс итерации, в то время как в больших сетях релевантность начальных точек исчезает.[1] По этой причине для небольших графов рекомендуются другие методы кластеризации.

Приложения

Китайский шепот используется во многих областях сетевой науки. Чаще всего упоминается в контексте обработка естественного языка проблемы.[2][3] С другой стороны, алгоритм применим к любой проблеме идентификации сообщества, которая связана с сетевой структурой. Chinese Whispers доступен для личного использования в качестве пакета расширения для Gephi[4] который является Открытый исходный код программа, предназначенная для сетевого анализа.

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

  1. ^ а б c d е ж грамм час я Крис Биманн,"Chinese Whispers - эффективный алгоритм кластеризации графов и его приложения к задачам обработки естественного языка", 2006
  2. ^ Антонио Ди Марко - Роберто Навигили,«Кластеризация и диверсификация результатов веб-поиска с помощью индукции Word Sense на основе графиков», 2013
  3. ^ Иоаннис Корконцелос - Суреш Манандхар,«Обнаружение композиционности в выражениях из нескольких слов», 2009
  4. ^ ""Gephi Marketplace"". Архивировано из оригинал на 2015-09-23. Получено 2015-06-02.

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