Маленькие секреты больших графов

Если вам интересно, какие знания можно извлечь из большого массива данных, насколько большими бывают графы и какие задачи по анализу социальных графов предлагают Facebook, Twitter и др., то эта статья именно для вас.

Итак, всего мы рассмотрим три задачи и первая из них – это Positive Link Prediction ^[1] от Facebook. Для скачивания данных нужно зарегистрироваться на kaggle.com ^[2].

Дан социальный граф, число тестовых вершин 262588, число ребер в графе 9437519, число вершин в графе 1862220 — это уже повод испугаться ;) Данный граф получен из реального путем удаления ребер. Задача: для заданных тестовой выборкой пользователей предсказать до 10 других пользователей, которых им бы стоило зафолловить.

Соревнование проходило под девизом: “Show them your talent, not just your resume”. Лучших участников Facebook попытается взять на работу.
Полезные ссылки:
1. cs.stanford.edu/people/jure/ ^[3]
2. www.machinedlearnings.com/2012/06/thought-on-link-prediction.html ^[4]
3. cs.stanford.edu/people/jure/ ^[3]

Следующая задача называется Community Detection и, соответственно, посвящена проблеме выделения сообществ в Twitter’е. Ознакомиться с материалами 19-ой конференции World Wide Web и скачать социальный граф от Twitter’а можно здесь ^[5]. Как это часто бывает, в общих чертах с темой поможет ознакомиться английская википедия: en.wikipedia.org/wiki/Community_structure ^[6]. Но если вы настроены решительно как никогда, вам пригодится источник посолиднее, например, этот ^[7].

Для тех, кому интересно, откуда ветер дует, последняя задача — Cascade Analysis. С моделями информационного противоборства в СМИ можно ознакомиться, прочитав статью Янга и Лесковца ^[8], полный список литературы статьи поможет вам найти ответы на множество вопросов. Данные для экспериментов: snap.stanford.edu/data/memetracker9.html ^[9] и snap.stanford.edu/data/bigdata/twitter7/ ^[10].
memetracker.org/quotes-kdd09.pdf ^[11] — бесценная ссылка для любителей промоделировать информационные баталии.

Если вы решите заняться какой-то из предложенных задач или похожей задачей, то это прекрасный повод оформить статью или постер (в зависимости от поставленных целей и достигнутых результатов) и отправить ее на конферецию “Graphs theory and application” CSEDays’12 ^[12].
Удачи вам и быстро сходящихся методов! :)
Ресурсы:
// Отчеты студентов
1. www.stanford.edu/class/cs224w/proj/jbank_Finalwriteup_v1.pdf ^[13]
2. www.stanford.edu/class/cs224w/proj/jieyang_Finalwriteup_v3.pdf ^[14]
// Наборы данных, публикации, библиотеки для анализа данных на C++, визуализация
3. snap.stanford.edu/ ^[15]
4. odysseas.calit2.uci.edu/doku.php/public ^[16]:online_social_networks
5. law.di.unimi.it/datasets.php ^[17]
6. rise4fun.com/agl ^[18]
// Jure Leskovec
7. cs.stanford.edu/people/jure ^[19]

Автор: Lakret