Генерация графа социальной сети с использованием Apache Spark


https://doi.org/10.18255/1818-1015-2016-6-777-783

Полный текст:


Аннотация

Планируется создать метод кластеризации графа социальной сети. Для тестирования будущего метода возникла необходимость в генерации графа, по своей структуре схожего с лежащими в основе существующих социальных сетей. В статье представлен алгоритм для распределенной генерации такого графа. Учитываются основные свойства социальной сети: степенное распределение количества сообществ для пользователей, плотные пересечения сообществ и другие. В данном алгоритме учтены проблемы, присутствующие в подобных работах других авторов, например, проблема кратных ребер при генерации. Особенностью созданного алгоритма стала реализация, зависящая от такого параметра как количество сообществ, а не от количества пользователей, как это делается в других работах. Это связано с особенностью развития структуры реальной существующей социальной сети. В работе перечислены свойства ее графа. Описана таблица, содержащая необходимые для алгоритма переменные. Составлен пошаговый алгоритм генерации. Для него определены соответствующие математические параметры. Генерация происходит распределенно с помощью фреймворка Apache Spark. Подробно описано, каким образом происходит разделение задач с помощью данного фреймворка. В алгоритме используется модель Эрдеша–Реньи для случайных графов как наиболее подходящая и достаточно простая для реализации. Основными преимуществами созданного метода являются использование малого количества ресурсов, по сравнению с другими подобными генераторами, и скорость выполнения. Быстрота достигается за счет распределенной работы и того, что при распределенной работе алгоритма в любой момент пользователи сети имеют свои уникальные номера и упорядочены по этим номерам, поэтому не требуется их сортировка. Разработанный алгоритм будет способствовать не только созданию эффективного метода кластеризации. Он может быть полезен в других областях, связанных, например, с поисковыми системами социальных сетей.


Об авторах

Ю. А. Белов
Ярославский государственный университет им. П.Г. Демидова
Россия

канд. физ.-мат. наук, доцент, ул. Советская 14, г. Ярославль, 150003 Россия



С. И. Вовчок
Ярославский государственный университет им. П.Г. Демидова
Россия

аспирант, ул. Советская 14, г. Ярославль, 150003 Россия



Список литературы

1. Чихрадзе К.К. и др., “Использование модели социальной сети с сообществами пользователей для распределенной генерации случайных социальных графов”, Машинное обучение и анализ данных, 1:8 (2014), 1027–1047.

2. Yang J., Leskovec J., “Community-affiliation graph model for overlapping network community detection”, IEEE 12th Conference (International) on Data Mining, 2012.

3. Raigorodskii A., “Models of Random Graphs and Their Applications to the Web-Graphs Analysis”, RUSSIR-2015, Lomonosov Moscow University, Moscow Istitute of Physics and Technology, Yandex, Moscow, Russia, 25–29 August, 2015.

4. Erdos P., Renyi A., “On the evolution of random graphs”, Bull. Inst. Int. Statist. Tokyo, 38 (1961), 343–347.

5. Aiello W., Chung F., Lu L., “On the evolution of random graphs”, A random graph model for power law graphs, http://people.math.sc.edu/lu/papers/power.pdf.

6. Карау Х., и др., Изучаем Spark: молниеносный анализ данных, ДМК Пресс, М., 2015, 304 с.

7. Вовчок С.И., “Создание метода кластеризации графа социальной сети”, Новые информационные технологии в науке: сборник статей Международной научно- практической конференции МЦИИ ОМЕГА САЙНС. Ч. 2, 2016, 34–36.


Дополнительные файлы

Для цитирования: Белов Ю.А., Вовчок С.И. Генерация графа социальной сети с использованием Apache Spark. Моделирование и анализ информационных систем. 2016;23(6):777-783. https://doi.org/10.18255/1818-1015-2016-6-777-783

For citation: Belov Y.A., Vovchok S.I. Generation of a Social Network Graph by Using Apache Spark. Modeling and Analysis of Information Systems. 2016;23(6):777-783. (In Russ.) https://doi.org/10.18255/1818-1015-2016-6-777-783

Просмотров: 291

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)