English
!

Доклады

Метод распределенной генерации графа социальной сети

Белов Ю.А., Вовчок С.И.

Ярославский государственный университет им. П.Г. Демидова, ул. Салтыкова-Щедрина, 59-12, г. Ярославль, 150014 Россия, e-mail: belov45@yandex.ru

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

© 2004 Дизайн Лицея Информационных технологий №1533