Software & Systems

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

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

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

В работе проводится сравнение известных алгоритмов выделения сообществ. Для этого используются графы, сгенерированные по модели l-partition [1], а также эгографы пользователей социальной сети Facebook, размещенные на платформе kaggle (https://www.kaggle.com/ c/learning-social-circles/data). В роли метрик качества алгоритмов выступают показатели Normalized Mutual Information (NMI) и split join distance [2–4].

Сравнение разбиений на графах

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

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

Метрика NMI. Одной из известных мер сходства двух разбиений является метрика NMI. Эта метрика взята из теории информации и звучит как «если два разбиения похожи, то необходимо немного информации, чтобы восстановить одно из другого». Количество этой информации и интерпретируется как мера расхождения двух разбиений. Мерой сходства является величина 1-NMI [5].

Представим результат работы двух алгоритмов по выделению сообществ {xi} и {yi}, где i – номер вершины, а xi, yi – метки, которые выдали алгоритмы вершине i. Предполагается, что метки x и y – это значения случайных величин X и Y, для которых задано совместное распределение P(X = x, Y = y) = nxy/n, где nxy – количество вершин, таких, что xi = x, yi = y, а n – общее число вершин в графе. По аналогии определяются распределения P(X = x) = nx/n и P(Y = y) = ny/n. Тогда информация между распределениями будет определяться следующим образом: I(X, Y) = H(X) – H(X|Y), где H(X), H(X|Y) – энтропия и условная энтропия: H(X) = = –SxP(x)logP(x), H(X|Y) = –Sx,yP(x, y)logP(x|y).

В качестве меры непохожести используется нормированная величина NMI: Inorm= [2I(X, Y)]/ / [H(X) + H(Y)]. Значение Inorm = 1 соответствует идентичным разбиениям. В качестве меры сходства двух разбиений далее применяется величина 1 – Inorm.

Метрика split join distance. Расстояние между разбиениями (split join distance) определяет минимально необходимое количество операций для перехода от одного разбиения к другому [6]. Такие операции включают добавление вершины, удаление вершины, создание разбиения с одной вершиной, удаление разбиения с одной вершиной.

Генерация графов для тестирования модели l-partition

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

Одним из методов генерации случайных графов со структурой сообществ является l‑partition. Метод генерирует граф с n = g*l вершин, где l – количество сообществ; g – количество вершин в сообществах. Вероятность pin определяет появление ребра между вершинами одного сообщества; pout – вероятность появления ребра между вершинами разных сообществ. При pin > pout плотность связей внутри сообщества выше, чем за его пределами, то есть в графе присутствуют сообщества.

Этому методу генерации графов присущи некоторые недостатки: сгенерированный граф имеет экспоненциальную степень распределения вершин, тогда как реальные сети – степенное распределение [7]; размер сообществ всегда фиксирован, что может внести некое смещение при сравнении качества работы алгоритмов. Для оценки качества алгоритмов на тестовых данных недостаточно одной генерации с заданными параметрами, необходимо провести анализ устойчивости алгоритмов к зашумлению структуры сообществ.

Для зашумления графа применяется следующая процедура: генерируется случайный граф с заданным параметром pin, далее итеративно добавляются ребра между вершинами из разных сообществ, регулируя их количество параметром pout. На каждой итерации значение pout увеличивается pstep, в данной работе выбран параметр pout = 0,01. Результатом является последовательность графов с постепенным зашумлением сообществ. На рисунке 1 представлена последовательность графов с сообществами в них, сгенерированных по методу l‑partition. В левом верхнем углу граф с ярко выраженной структурой сообществ, сгенерированных по схеме Гирвана–Ньюмана, вероятность появления ребра между сообществами pout = 0,01. В правом нижнем углу граф с за- шумлением и сложно различимой структурой сообществ с параметром pout = 0,45.

Анализ алгоритмов на модельных данных

Для тестирования алгоритмов c известной структурой сообществ сгенерированы случайные графы по схеме l-partition с количеством сообществ, равным , в каждом по  вершин. Вероятность появления ребра в сообществе pin = 0,5. Начальное значение вероятности появления ребра между вершинами разных сообществ pout = 0,01. Осуществляется зашумление структуры сообществ в графе до значения pout = 0,45 с шагом . Последовательность состояний моделируемого графа задана ранее (рис. 1).

Метрики NMI и split join distance показывают оценки качества работы алгоритмов, при этом чем ниже значение метрики, тем выше результативность алгоритма. На рисунках 2 и 3 визуализированы результаты работы алгоритмов.

На рисунке 2 алгоритмы Label Propagation и Infomap на уровне зашумления графа pout = 0,15 определяют весь граф как одно сообщество, о чем свидетельствуют значения метрики NMI, равные единице.

На рисунке 3 алгоритмы Label Propagation и Infomap сходятся к константе, что соответствует определению всего графа как одного сообщества.

Лучше всего с выделением сообществ справились алгоритмы multilevel и walktrap. Следует отметить порог pout = 0,25, вплоть до которого алгоритмы выдают верные разбиения графа.

На рисунке 4 показаны результаты работы агрегированного алгоритма MetaClust в сравнении с базовыми алгоритмами. Значения кривой метрик заданы пунктирной линией.

Предложенный алгоритм MetaClust по метрике качества split join distance работает не хуже лучшего из базовых алгоритмов на всем отрезке зашумления. Cогласно метрике NMI, агрегированный алгоритм справляется хуже методов multilevel и walktrap на отрезке зашумления pout Î (0,01;0,30), в то же время превосходя алгоритмы fastgreedy и eigenvector. В момент, когда структура сообществ в графе ока- зывается сильно зашумленной, pout Î (0,30; 0,45), агрегированный алгоритм демонстрирует наилучшее качество работы по обеим метрикам.

Агрегированный алгоритм MetaClust основан на методе кластеризации k-means и требует указания точного количества сообществ в отличие от всех базовых алгоритмов. Этот параметр определяется базовыми алгоритмами и затем используется для агрегированного алгоритма. В настоящей работе агрегированный алгоритм MetaClust состоит из 4 базовых и фактически имеет вычислительную сложность, сопоставимую с суммой этих базовых алгоритмов. Сравнение времени исполнения алгоритмов на модельных данных с зашумлением графа представлено на рисунке 5. Алгоритм multilevel, вычислительная сложность которого зависит практически линейно от количества вершин в графе, показал наилучшие результаты. Алгоритмы walktrap и eigenvector ожидаемо показали меньшую скорость работы в силу квадратичности вычислительной сложности.

Анализ эгографов социальной сети Facebook

На платформе kaggle.com размещена задача выделения сообществ (Learning social circles in network) на эгографах пользователей Facebook. Эгограф пользователя – это граф, вершинами которого являются друзья пользователя, а ребра отражают наличие дружбы с ними. Помимо эгографов, участникам предоставили анонимизированную социально-демографическую информацию из профилей пользователей. В качестве метрики в этой задаче была использована split join distance, а тестовой выборки – 110 эгосетей пользователей. Эгосети представляют интерес в данной работе для анализа качества работы алгоритмов на них с помощью модулярности.

Далее рассматриваются алгоритмы выделения сообществ в эгосетях пользователей социальной сети Facebook, включая label propogation и infomap, получившие низкие оценки метрик на модельных данных. Результаты работы алгоритмов приведены на рисунке 5. По оси ординат отражено распределение значений модулярностей для каждого алгоритма. Большие значения модулярности соответствуют более качественному выделению сообществ. Прежде всего стоит отметить, что эгосети у рассмотренных 104 пользователей неоднородны и размерность, плотность, зашумление их сообществ сильно отличаются. Об этом можно судить по разбросу значений модулярности, которые достаточно равномерно распределены на отрезке [0,2; 0,7].

Методы, которые на модельных данных по мере зашумления графа вырождались в константу, на реальных данных уже не сходились к константе. Тем не менее, оценка качества алгоритмов label propogation и infomap по модулярности также ниже, чем у остальных базовых алгоритмов (на рисунке это отражается в длинных «хвостах» распределений модулярностей). Остальные базовые алгоритмы справились примерно одинаково.

Предложенный алгоритм MetaClust показал высокую результативность по сравнению с базовыми. На рисунке (см. http://www.swsys.ru/ uploaded/image/2020-2/2020-2-dop/7.jpg) видно, что значения модулярности для его разбиений (в среднем) выше по оси ординат. Также о качестве алгоритма можно судить по отсутствию у распределения модулярности «хвоста».

В исследованных данных лишь один пользователь оказался с ярко выраженной структурой сообществ, все алгоритмы на его эгосети показывают значение модулярности больше 0,8. На рисунке 6 представлена эгосеть этого пользователя с результатом выделения сообществ посредством алгоритма MetaClust. Нужно заметить, что средние результаты, показанные алгоритмами на всей выборке, ранжируются в том же порядке, что и их качество на сети данного пользователя, откуда также заметно преимущество предложенного алгоритма. Разными цветами обозначены разбиение вершин графа на сообщества алгоритмом MetaClust, значение модулярности для алгоритма Q = 0,9.

Важно понимать, насколько качество агрегированного алгоритма отличается от качества лучшего из базовых. Гистограмма значений разности модулярности для агрегированного метода и лучшего из базовых (см. http://www. swsys.ru/uploaded/image/2020-2/2020-2-dop/8. jpg) показывает, что в большинстве случаев предложенный алгоритм MetaClust качественно выше, о чем можно судить по большей площади функции распределения, находящейся правее нуля.

Динамические и предфрактальные графы

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

Для генерации модельных данных представляется целесообразным использовать предфрактальные графы и шире применять класс динамических графов. Последовательность графов сообществ, сгенерированных с помощью метода l‑partition, соответствует траектории динамического графа, сообщества представляют собой затравки и блоки, а зашумление – добавление новых ребер разного ранга между затравками. Следующим этапом видится формальное описание зашумления графов в терминологии класса динамических и предфрактальных графов. Использование класса предфрактальных графов позволит вычислять структурные характеристики и свойства графов и сообществ в них [8–10].

Заключение

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

Развитие инструментальной базы моделирования, в частности, использование динамических и предфрактальных графов, позволит расширить круг задач в социальных сетях, в их числе многокритериальные (многопараметрические) задачи, задачи с множественными и нечеткими весами, разработка параллельных алгоритмов, прогнозные задачи с заданным уровнем надежности и многие другие [11, 12].

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

Работа выполнена при поддержке РФФИ, грант № 18-00-01103.

Литература

1.    Condon A., Karp R.M. Algorithms for Graph partitioning on the planted partition model. LNCS, 1999, vol. 1671, pp. 221–232. DOI: 10.1007/978-3-540-48413-4_23.

2.    Azaouzi M., Rhouma D., Ben Romdhane L. Community detection in large-scale social networks: sta- te-of-the-art and future directions. Soc. Netw. Anal. Min., 2019, no. 9. DOI: 10.1007/s13278-019-0566-x.

3.    Muhammad A.J., Muhammad S.Y., Siddique L., Junaid Q., Adeel B. Community detection in networks: A multidisciplinary review. J. of Network and Computer Applications, 2018, vol. 108, pp. 87–111. DOI: 10.1016/j.jnca.2018.02.011.

4.    Atay Y., Koc I., Babaoglu I., Kodaz H. Community detection from biological and social networks. Appl. Soft Comp., 2017, no. 50, pp. 194–211.

5.    Zhang Q., Liu E.Y., Sarkar A., Wang W. Split-order distance for clustering and classification hierarchies. Proc. SSDBM. LNCS, Springer, 2009, vol. 5566, pp. 517–534. DOI: 10.1007/978-3-642-02279-1_37.

6.    Shannon C.E. A mathematical theory of communication. Bell Syst. Tech. J., 1948, pp. 379–423.

7.    Réka A., Barabási A.-L. Statistical mechanics of complex networks. Rev. Mod. Phys., 2002, no. 74, pp. 47–97.

8.    Perepelitsa V.A., Kochkarov A.M., Sergienko I.V. Recognition of fractal graphs. Cybernetics and Syst. Analysis, 1999, vol. 35, no. 4, pp. 572–585.

9.    Кочкаров А.А., Кочкаров Р.А., Малинецкий Г.Г. Некоторые аспекты динамической теории графов // Журнал вычислительной математики и математической физики. 2015. Т. 55. № 9. С. 1623–1629. DOI: 10.7868/S0044466915090094.

10. Кочкаров А.А., Кочкаров Р.А. Параллельный алгоритм поиска кратчайшего пути на предфрактальном графе // Журнал вычислительной математики и математической физики. 2004. Т. 44. № 6. С. 1157–1162.

11. Биккузина А.И., Жуков А.О., Никольский Ю.В., Буханец Д.И. Подход к решению задачи упорядочения альтернатив в диалоговой системе моделирования принятия решений при информационно-аналитическом обеспечении оценки и прогноза экологического состояния территорий эксплуатации крупных технических комплексов // Новые исследования в разработке техники и технологий. 2014. № 1. С. 33–39.

12. Гладышев А.И., Жуков А.О. Использование в автоматизированной системе контроля полномочий биометрической идентификации // Вестн. Российского нового университета. 2013. № 4. С. 95–98.

References

1. Condon A., Karp R.M. Algorithms for graph partitioning on the planted partition model. LNCS, 1999, vol. 1671, pp. 221–232. DOI: 10.1007/978-3-540-48413-4_23.
2. Azaouzi M., Rhouma D., Ben Romdhane L. Community detection in large-scale social networks: state-of-the-art and future directions. Soc. Netw. Anal. Min., 2019, no. 9. DOI: 10.1007/s13278-019-0566-x.
3. Muhammad A.J., Muhammad S.Y., Siddique L., Junaid Q., Adeel B. Community detection in networks: A multidisciplinary review. J. of Network and Computer Applications, 2018, vol. 108, pp. 87–111. DOI: 10.1016/j.jnca.2018.02.011.
4. Atay Y., Koc I., Babaoglu I., Kodaz H. Community detection from biological and social networks. Appl. Soft Comp., 2017, no. 50, pp. 194–211.
5. Zhang Q., Liu E.Y., Sarkar A., Wang W. Split-order distance for clustering and classification hierarchies. Proc. SSDBM. LNCS, Springer, 2009, vol. 5566, pp. 517–534. DOI: 10.1007/978-3-642-02279-1_37.
6. Shannon C.E. A mathematical theory of communication. Bell Syst. Tech. J., 1948, pp. 379–423.
7. Réka A., Barabási A.-L. Statistical mechanics of complex networks. Rev. Mod. Phys., 2002, no. 74,
   pp. 47–97.
8. Perepelitsa V.A., Kochkarov A.M., Sergienko I.V. Recognition of fractal graphs. Cybernetics and Syst. Analysis, 1999, vol. 35, no. 4, pp. 572–585.
9. Kochkarov A.A., Kochkarov R.A., Malinetskii G.G. Issues of dynamic graph theory. Computational Mathematics and Mathematical Physics, 2015, vol. 55, no. 9, pp. 1590–1596 (in Russ.). DOI: 10.7868/S0044466915090094.
10. Kochkarov A.A., Kochkarov R.A. Parallel algorithm for finding the shortest path on a prefractal graph. Computational Mathematics and Mathematical Physics, 2004, vol. 44, no. 6, pp. 1157–1162 (in Russ.).
11. Bikkuzina A.I., Zhukov A.O., Nikolsky Yu.V., Bukhanets D.I. An approach to solving the problem of ordering alternatives in a dialogue system for decision-making modeling with information and analytical support for assessing and predicting the ecological state of the territories of operation of large technical complexes. New Studies in the Development of Equipment and Technologies, 2014, no. 1, pp. 33–39 (in Russ.).
12. Gladyshev A.I., Zhukov A.O. The use of biometric identification authority in an automated control system. Vestn. RosNOU, 2013, no. 4, pp. 95–98 (in Russ.).