Анализ социальных сетей

Социальная аналитика стремительно набирает популярность во всём мире, благодаря появлению в 1990-х годах онлайновых сервисов социальных сетей (SixDegrees, LiveJournal, Facebook, Twitter, YouTube и другие). С этим связан феномен социализации персональных данных: стали публично доступными факты биографии, переписка, дневники, фото-, видео-, аудиоматериалы, заметки о путешествиях и т.д. Таким образом, социальные сети являются уникальным источником данных о личной жизни и интересах реальных людей

Анализ социальных сетей – активно развивающееся направление западной и российской социологии. Исследования, направленные на изучение социальных сетей, используют различные подходы по оценки зрелости онлайн сообществ. Также изучается вопрос автоматизации жизни современного человека при помощи онлайн социальных сетей. Рассматриваются два направления автоматизации - информатизация бизнеса и государственной деятельности, и расширение спектра общения с друзьями, бывшими коллегами и одноклассниками. Автоматизация позволяет более полно удовлетворять потребности в информации и в самовыражении, существенно увеличивает число инструментов самообслуживания. Интерес исследователей к этому направлению связан с тем, что оно предоставляет новый набор объяснительных моделей и аналитических инструментальных средств, которые находятся вне рамок обычных количественных методов.

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

К настоящему моменту существует большое количество методов кластеризации графов – каждый со своими преимуществами и недостатками.

Далее будет предоставлен набор основных инструментов и библиотек используемых алгоритмы кластеризации.

• 1.    Современный и развивающийся на сегодняшний день GraphX. К сожалению у него как таковых готовых алгоритмов кластеризации пока нет (версия 1.4.1). Есть подсчет треугольников и связных компонент, что, совместно со стандартными операциями над Spark RDD, можно использовать для написания своих алгоритмов. Пока что у GraphX есть API только для scala, что также может усложнить его использование.

• 2.    Библиотека для Apache Giraph под названием Okapi использует несколько алгоритмов, в том числе достаточно новый алгоритм собственной разработки под названием Spinner, основанный на label propagation. Giraph — это надстройка над Hadoop, предназначенная для обработки графов. В ней почти нет машинного обучения, и для компенсации этого в компании Telefonica и был создан Okapi. Вероятно, сейчас Giraph выглядит уже не так перспективно на фоне GraphX, но сам алгоритм Spinner хорошо ложится и на парадигму Spark.

• 3.    Библиотека graph-tool для Python содержит несколько новейших алгоритмов кластеризации и очень быстро работает. Все, что можно, распараллелено по ядрам процессора, и для локальных вычислений (графы размером до пары сотен тысяч узлов) это самый быстрый вариант.

• 4.     Gephi — известный инструмент, который на данный момент обошли вниманием, возможно, незаслуженно. Долгое время Gephi практически не развивался, зато у него появились хорошие плагины, в том числе для выделения сообществ. В последнее время проект вновь ожил и ожидается версия 0.9.

• 5.     GraphLab Create. Это обертка Python над C++, позволяющая прогонять машинное обучение как локально, так и распределенно (на Yarn). Кластеризации графов там все ещё нет, только нахождение k-ядер.

• 6.    Популярный networkX, несмотря на обилие алгоритмов, не умеет кластеризовать графы, но только анализировать связные компоненты и клики. Вдобавок он намного медленнее graph-tool, и по части визуализации уступает тому же graph-tool и gephi.

• 7.    Реализация алгоритма марковской кластеризации (MCL) от его изобретателя. Автор снизил сложность обычного MCL в худшем случае с до, где – число узлов, а – максимальная степень узла, поэтому часто алгоритм MCL называют не масштабируемым. Также он добавил новшества для регулировки числа кластеров. Однако у MCL было несколько других серьезных проблем, решение которых до сих пор не найдено. Например, проблема нестабильности размера кластеров (небольшой эксперимент выдал

• 8.    Разные реализации одного из самых популярных алгоритмов Louvain: для C, для Python. Кроме относительной гибкость реализации, она также хорошо масштабируется и может быть запущен на графах миллионов узлов (как долго, как они могут поместиться в памяти).

• 9.     Сайт, посвященный алгоритму Infomap и его модификациям, от авторов метода. Как и везде, есть открытый код. Помимо хорошей поддержки и документации, есть изумительные демо-версии, иллюстрирующие работу алгоритма.

• 10.    Пакет для R под названием igraph. В нем реализовано довольно много алгоритмов кластеризации.

одну гигантскую связную компоненту и много маленьких кластеров по 2-3 узла).

Если цель – провести воспроизводимый эксперимент на небольших данных, а не выкладывать в продажу готовый продукт, то среди всего вышеперечисленного лучшими вариантами являются, graph-tool, Gephi или Infomap.

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

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