Записки Юной Старперши. Web-студия Татьяны Самойловой

Социальные сети / Алгоритм для выявления сообществ в больших сетях

Опубликовано Янв 27, 2011 в WEB,. WEB-news | Нет комментариев


В последнее время предпринимаются многочисленные попытки разработать эффективный алгоритм для выявления сообществ в социальных сетях из миллионов узлов, которые невозможно визуализировать или анализировать на уровне отдельных узлов.

Бельгийские разработчики представили новый алгоритм, который превосходит все существующие аналоги по вычислительной скорости. Вследствие этого его можно применять на базах беспрецедентного размера: анализ типичной сети из 2 млн нодов занимает 2 минуты. Он получил название Лувенский метод (Louvain Method), поскольку создан в то время, когда все разработчики трудились в Лувене (Бельгия).

Лувенский метод доказал свою точность при тестировании на сетях с известной структурой сообществ, где можно было проверить результат. Благодаря своей иерархической структуре он подходит для анализа сообществ в различных масштабах. В частности, его проверяли также для сообществ в сети бельгийского оператора мобильной связи (2,6 млн абонентов) и на базе веб-страниц, собранной краулером Stanford WebBase (118 млн узлов и более 1 млрд ссылок).

387da e01903b5 Социальные сети / Алгоритм для выявления сообществ в больших сетях
Результат анализа базы абонентов в сети бельгийского оператора сотовой связи. Красным цветом отмечены сообщества, разговаривающие на французском языке, зелёным — на голландском. Зуммирован участок «промежуточных» сообществ, которые общаются на обоих языках. В этом масштабе отображены группы людей более 100 человек.

Метод состоит из двух стадий. На первой происходит поиск «малых» сообществ путём оптимизации модульности на локальном уровне. На второй стадии узлы одного сообщества агрегируются и строится новая сеть большего масштаба, после чего эти стадии повторяются до тех пор, пока не будет достигнут максимальный уровень модульности.

51dac 6de405fe Социальные сети / Алгоритм для выявления сообществ в больших сетях

Таким образом, после каждого этапа программа отображает сообщества всё большего масштаба.

Более подробная информация приведена в статье Fast unfolding of communities in large networks. Например, там содержится таблица качества и скорости работы алгоритма по сравнению с алгоритмами Clauset/Newman/Moore, Pons/Latapy и Wakita/Tsurumi. Для каждой задачи указан уровень модульности и время выполнения на машине Opteron 2,2 ГГц с 24 ГБ RAM (прочерк, если время превышает 24 часа). Судя по результатам, Лувенский метод буквально не имеет себе равных.

0b07e 184ef3bc Социальные сети / Алгоритм для выявления сообществ в больших сетях

Программа на C++ и matlab распространяется бесплатно.

VN:F [1.9.11_1134]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.11_1134]
Rating: 0 (from 0 votes)

Читатели рекомендуют также прочесть по этой тематике:

  1. Папа Римский благословил общение в социальных сетях
  2. WiMAX: сеть поколения 4G / [Из песочницы] Что такое 1G, 2G, 3G, 4G и все что между ними
  3. В декабре 172 миллиона американцев смотрели видео в Сети
  4. Стартапы / UVoiceMe — сервис интеграции шлюзов IP-телефонии
  5. Linux для всех / [Из песочницы] Один компьютер на двоих (и более) или multiseat на базе Ubuntu 10.04 LTS
Интересная статья? Поделитесь ею пожалуйста с другими:

Приглашаю присоединиться ко мне:

Оставить комментарий