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


    Если вам интересно, какие знания можно извлечь из большого массива данных, насколько большими бывают графы и какие задачи по анализу социальных графов предлагают 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
    Поделиться публикацией

    Комментарии 11

      +1
      Ого! Очень вдохновляющий пост, чтения на все выходные. Спасибо!
      • НЛО прилетело и опубликовало эту надпись здесь
          +2
          число тестовых вершин 262588, число ребер в графе 9437519

          Как скромно.
          Вот ссылка на статью Your Laptop Can Now Analyze Big Data про софтину GraphChi, которая на обычном мак мини перемалывает граф с данными твитера 2010 года (40 миллионов пользователей, 1.2 миллиарда соединений) за час(!).
          Сайт проекта — graphlab.org/graphchi
          Тут есть ссылки на данные ЖЖ(65 млн ребер) и Твитер(1.5 млрд) — graphchi example apps
          Собственно исходные тексты (С++) и документация — code.google.com/p/graphchi
          На сайте проекта есть также ссылка на ранние исходники написанные на Java.
            0
            Я бы поостерёгся называть задачи, связанные с кластеризацией графов френдов, «выявлением сообществ». Всё-таки сообщества, даже он-лайн, подразумевают постоянство участников, общность их целей/интересов, длительность и регулярность взаимодействий. Членство в сообществах, обладающих для своих участников какой-либо ценностью, требует затрат ресурсов. В контексте Интернета это в первую очередь время и внимание (на чтение/написание постов, комментов, ведение дискуссий и т.д.).

            В то же время, для создания «дружбы» в любой он-лайн соцальной сети как правило требуется пара кликов мышью, а поддержание данного типа отношений зачастую и вовсе не требует усилий (вы поздравляете все свои контакты с днём рождения?). Более того, люди вкладывают различные смыслы и цели в контакты в социальных мидиях (поддержание офф-лайн отношений, адресная книга, демонстрация связи с примечательной персоной и т.д.).

            Это, как показывает мой опыт и исследования, делает графы, основанные на списках контактов в ЖЖ, Твиттере и прочих сервисах, достаточно сложными (а иногда и вовсе бессмысленными) для содержательной интерпретации.

            Математическое моделирование в данном контексте и вовсе отдельная песнь.
              0
              Не буду вдаваться в длинную дискуссию, но замечу, что «содержательная интерпретация» таких графов вполне возможна. Для того, чтобы на самом деле получить много актуальной информации из них, впрочем, одного анализа графа недостаточно; но граф может и должен быть использован при таком анализе.
                0
                «содержательная интерпретация» таких графов вполне возможна.


                Например?
                  0
                  Например, я могу выделить сильносвязные компоненты и предположить, что все люди в таких компонентах относятся к определённым социальным группам — а по информации из профайла я могу понять, что именно их объединяет. Или же, можно сравнить аккаунт пользователя с аккаунтами его друзей по отдельным факторам, и таким образом определить, насколько значимыми являются выбранные факторы для данного пользователя при выборе круга общения. Второй пример я на самом деле делал для небольшого графа и был слегка поражён результатами — это правда работает.
                    0
                    Например, я могу выделить сильносвязные компоненты и предположить, что все люди в таких компонентах относятся к определённым социальным группам — а по информации из профайла я могу понять, что именно их объединяет.

                    По моему опыту это работает на эгоцентрических сетях Вконтакта и Фейсбука, т.к. они более-менее связаны с офф-лайн знакомствами. В графе френдов ЖЖ ситуация несколько иная, т.к. там контексты «дружбы» сильно различаются.

                    можно сравнить аккаунт пользователя с аккаунтами его друзей по отдельным факторам, и таким образом определить, насколько значимыми являются выбранные факторы для данного пользователя при выборе круга общения

                    Это зовётся «гомофилией» — склонностью контактировать с похожими на себя людьми. Однако, тут нужно быть аккуратным с направлением каузальности, ведь существует другой процесс (в западной литературе он зовётся «social contagion», адекватного перевода на русский я еще не нашел), согласно которому близкие люди со временем становятся во многом похожими.
                      0
                      Меня не особо интересует ЖЖ и его граф :)
                      Ну, проблема различения следствия и причины вообще характерна для статистики.
                        0
                        Я это всё к тому, что в последнее время физики/математики/компьютерщики сильно возбудились по поводу «социальных сетей» и начали перекладывать на них модели и алгоритмы из своих областей (зачастую совершенно бездумно), приходя таким образом не к самым корректным выводам. Поэтому называть кластеризацию на графах «обнаружением сообществ» не совсем корректно.
              0
              «содержательная интерпретация» таких графов вполне возможна.

              Например?

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое