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

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

Презентация в формате PDF: chikhradze20140424.pdf

Видеозапись семинара: https://www.youtube.com/watch?v=uyuvpE-sAYI

Литература:

1. Erdos, P., and Renyi, A. On the evolution of random graphs. Bull. Inst. Int. Statist. Tokyo 38 (1961), 343–347.
2. Lancichinetti, A., and Fortunato, S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys. Rev. 80(1) (2009).
3. Leskovec, J., Lang, K. J., Dasgupta, A., and Mahoney, M. Statistical properties of community structure in large social and information networks.
4. Yang, J., and Leskovec, J. Community-afliation graph model for overlapping network community detection. In IEEE 12th International Conference on Data Mining (2012).
5. Yang, J., and Leskovec, J. Structure and overlaps of communities in networks. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (2012).