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

b-images.preview.jpg

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

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

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

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

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

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

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