Доклад посвящён исследованию графовых свойств и характеристик социальных сетей (эффективный диаметр, средняя степень вершин, распределение степеней вершин, коэффициент кластеризации и др.), а также их вычислению с помощью Stanford Network Analysis Platform и распределённому вычислению на базе GraphLab при помощи эффективных алгоритмов (например, HADI для диаметра графа). Почему распределение степеней вершин подчиняется закону power law? Каковы средняя степень вершины и эффективный диаметр графа Facebook? Как за приемлемое время вычислить диаметр графа порядка ~1М вершин? Какими топологическими свойствами обладает граф Facebook? Вот лишь некоторое множество вопросов, которые будут раскрыты на семинаре.
Докладчик: Кирилл Чихрадзе
Материалы:
- U Kang, Charalampos Tsourakakis, Ana Paula Appel, Christos Faloutsos, Jure Leskovec. «HADI: Fast Diameter Estimation and Mining in Massive Graphs with Hadoop». CMU-ML-08-117, 2008.
- Jure Leskovec. «Dynamics of Large Networks». CMU-ML-08-111, 2008.
- Johan Ugander, Brian Karrer, Lars Backstrom, Cameron Marlow. «The Anatomy of the Facebook Social Graph». CoRR(2011)
- Emilio Ferrara, Giacomo Fiumara. «Topological Features of Online Social Networks». Communications on Applied and Industrial Mathematics, 2(2):1-20, 2011
Comments are closed.