Доклад посвящён исследованию графовых свойств и характеристик социальных сетей (эффективный диаметр, средняя степень вершин, распределение степеней вершин, коэффициент кластеризации и др.), а также их вычислению с помощью Stanford Network Analysis Platform и распределённому вычислению на базе GraphLab при помощи эффективных алгоритмов (например, HADI для диаметра графа). Почему распределение степеней вершин подчиняется закону power law? Каковы средняя степень вершины и эффективный диаметр графа Facebook? Как за приемлемое время вычислить диаметр графа порядка ~1М вершин? Какими топологическими свойствами обладает граф Facebook? Вот лишь некоторое множество вопросов, которые будут раскрыты на семинаре.

Докладчик: Кирилл Чихрадзе

Материалы:

  1. 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.
  2. Jure Leskovec. “Dynamics of Large Networks”. CMU-ML-08-111, 2008.
  3. Johan Ugander, Brian Karrer, Lars Backstrom, Cameron Marlow. “The Anatomy of the Facebook Social Graph”. CoRR(2011)
  4. Emilio Ferrara, Giacomo Fiumara. “Topological Features of Online Social Networks”. Communications on Applied and Industrial Mathematics, 2(2):1-20, 2011

Презентация с семинара