Пользователь
0,0
рейтинг
19 января 2010 в 15:13

Анализ социального графа

социальный граф UkrTweet
Количество американских патентных заявок связанных с социальными сетями последние 5 лет росло на 250% каждый год (ссылка). Так, например, одна корпорация подала патентную заявку на метод ценообразования который учитывает положение покупателя в социальном графе (обсуждение на Slashdot). Другая корпорация недавно воплотила максимально упрощенный вариант этой схемы, продавая свои новые телефоны влиятельным узлам социального графа за $0, а остальным за $530.

Анализ социальных сетей (Social Network Analysis) существовал задолго до Интернета, но в последнее время набирает обороты.

Мне было интересно посмотреть, как эффективно алгоритм, выделяющий кластеры в графах, сработает для некоторых групп в Twitter, которые представляют для меня интерес.

23 января в Запорожье пройдет #UKRTWEET — первый всеукраинский баркэмп посвященный Twitter. Граф выше показывает, кто из его участников, с кем разговаривает и кого упоминает.

Заметка ниже посвящена анализу этого графа. Весь код используемых здесь скриптов лежит на github. Изложение, в какой-то мере, вдохновлено недавно упомянутой на Хабре книгой Тоби Сегаран «Программируем коллективный разум», код примеров которой доступен на сайте автора.

Также о data mining в Twitter я говорил 16 января на первой в этом году донецкой встрече "Кофе и код". Поэтому здесь параллельно проведу анализ группы людей из Донецка, которые пишут в Twitter. Кстати, в этом году донецкие встречи будут регулярными — каждую третью субботу месяца (следующая 20 февраля). Следите за группой.

1. Получение информации


Для начала, получаем список всех участников групп. Список участников #UKRTWEET есть на странице баркэмпа. Скачиваем и парсим его при помощи BeautifulSoup (код). Для людей, которые твитят из Донецка, я веду список @dudarev/donetsk. Сохраняем его участников при помощи библиотеки tweepy (код).

Для каждого из участников скачиваем последние 100 твитов и сохраняем их. Tweepy автоматически парсит JSON, а так как в этот раз мы хотим сохранить данные такими какие они есть, то немного подправляем класс tweepy.API (код).

2. О чем говорят


Теперь можно анализировать информацию. И сначала — пара наблюдений не связанных с социальным графом. Давайте посмотрим какие хэштеги наиболее часто употреблялись каждой группой. Для этого напишем утилиту, которая принимая строку возвращает список всех встречающихся в ней хэштегов. Для ее написания TDD — весьма кстати (смотрим код). С помощью этой утилиты парсим все твиты (код).

Наиболее часто-упоминаемые хэштеги участниками #UKRTWEET (число в скобках — количество разных людей, которые использовали этот хэштег):
  1. ukrtweet (20)
  2. sledui (20)
  3. elect_ua (16)
  4. ru_ff (10)
  5. zp_ua (9)
  6. nicua (9)
  7. google (9)
  8. twitter (7)
  9. habr (7)

Люди из Донецка упоминали:
  1. donetsk (31)
  2. habr (12)
  3. radiot (8)
  4. sledui (7)
  5. ru_ff (7)
  6. google (7)
  7. wave (6)
  8. linux (6)

Как видим, в каждой группе, хэштег, описывающий группу — на первом месте по употреблению. Есть и общие интересы: habr, ru_ff, sledui, google.

3. Когда говорят


Давайте посмотрим, в какое время, группа проявляет наибольшую активность. Для этого воспользуемся тем же самым скриптом, пробегающим по всем твитам, но на этот раз сформируем списки количества твитов в данный час дня и сохраним их в отдельных файлах (опция '-t' при вызове из коммандной строки). Изобразим диаграмы при помощи библиотеки Matplotlib (код).
https://habrastorage.org/getpro/geektimes/post_images/183/5c9/dde/1835c9ddecc7715c9f0f2b30c1c98bcf.jpg

Участники #UKRTWEET проявляют активность выше средней с 10 утра до 1 часа ночи по киевскому времени, с пиком около 5 часов вечера.
https://habrastorage.org/getpro/geektimes/post_images/046/a0e/b07/046a0eb07b9427fb84c21fb28823c6d1.jpg

Дончане активны в то же время, но пик наблюдается около 11 вечера. Быть может, это потому что люди собирающиеся на баркэмп рассматривают Twitter как рабочий инструмент и активны в нем в рабочее время. Хотя, из-за недавних праздников, эти данные могут быть не показательными.

4. Социальный граф


Граф из данных Twitter можно строить различными способами. Здесь мы будем следовать следующей конструкции: если человек А упомянул человека Б хотя бы один раз (не важно ретвит или ответ), от вершины А к вершине Б строим ориентированное ребро. Граф не взвешенный, то есть ребро строим только единожды.

Все тот же скрипт с опцией '-g' выстраивает из сохраненных твитов словарь представляющий такой граф и сохраняет его в формате JSON для последующего анализа (код).

Несколько количественных наблюдений. В группе #UKRTWEET 58% упоминают кого-то из группы (61/106). А всего упоминают 1221 человека что в 11.5 раз больше самой группы (1221/106).

В донецкой же группе 51.6% вовлечены в группу (116/225), а всего различных упоминаний в 6 раза больше самой группы (1341/225). Явно, что люди, которые собираются посетить баркэмп о Twitter более активно используют его как средство общения.


5. Авторитетность


Авторитетность в социальном графе можно анализировать разными способами. Самый простой — отсортировать участников по количеству входящих ребер. У кого больше — тот больше авторитетен. Такой способ годен для небольших графов. В поиске по Интернету Google в качестве одного из критериев для авторитетности страниц использует PageRank. Он вычисляется при помощи случайного блуждания по графу, где в качестве узлов — страницы, а ребро между узлами — если одна страница ссылается на другую. Случайный блуждатель двигается по графу и время от времени перемещается на случайный узел и начинает блуждание заново. PageRank равен доли пребывания на каком-то узле за все время блуждания. Чем он больше, тем узел более авторитетен.

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

Одна из распространенных библиотек Python для работы с графами — NetworkX. Ее и будем использовать. Создав граф G, считать различные его параметры очень удобно. Так, например, чтобы посчитать PageRank всех узлов, достаточно написать:

pr = networkx.pagerank(G)


Хочется подчеркнуть, что все числа ниже — для искуственно выделенных из твиттерсферы групп. Другие участники этих групп, могут быть глобально более влиятельными и авторитетными. Числа ниже — для комуникаций внутри данных групп.

Давайте отобразим зависимость PageRank для всех узлов от количества узлов, которые на них указывают (код).
https://habrastorage.org/getpro/geektimes/post_images/adc/0fe/c9f/adc0fec9f6531e8ab446f6d1230a1762.jpg

Естественно, большой авторитет у двух организаторов (@karelina и @u02). У известного украинского блогера @woofer_kyyiv авторитетность измеряемая в PageRank высока, хотя и упоминают меньше людей, но упоминают равномерно по группе (из разных сообществ). Авторитетность официального аккаунта баркэмпа (@ukrtweet) ниже при большем упоминании. Одна из интерпретаций: люди предпочитают общаться и упоминать людей. Быть может поэтому во многих официальных западных аккаунтах явно указываются имена вещающих.
https://habrastorage.org/getpro/geektimes/post_images/005/e70/bdb/005e70bdb1425bb8a76144191ed70491.jpg

Безусловный лидер внутри донецкой группы — @quantizer. Различия в PageRank при схожих количествах упоминаний для следующих участников можно трактовать, например, так: @olchik_terl и @lancerenok больше общаются с людьми из разных частей социального графа группы, тогда как @medialex, @lapidarius, @meesix, @alderko больше взаимодействуют со своими локальными сообществами (в основном выделенными по профессиональному признаку, об этом ниже), поэтому у второй группы PageRank чуть ниже, чем у первой.

6. Влияющие извне


Люди вне групп тоже влияют на группы. Определим самых влиятельных подобно тому как делали это с хэштегами: отсортируем людей вне групп по количеству людей, которые их упоминают в группе (скрипт тот же, что парсит, но с опциями '-g -o' создает файл data/friends_outside_counts.txt).

Для #UKRTWEET (в скобках — число разных людей из группы упоминавших):
  1. podarok (16)
  2. taras (11)
  3. artemzeleny (11)
  4. blogoreader (10)
  5. yaroslavazhnyuk (9)
  6. wedmid (9)
  7. matteush (9)

Для Донецка:
  1. bobuk (12)
  2. olyapka (11)
  3. ekozlov (8)
  4. boomburum (7)
  5. abakala (7)

Такой подход можно использовать для поиска интересных людей. Если вам интересна какая-то группа, то вероятно те люди, которых эта группа упоминает, тоже могут быть вам интересны.

Как усовершенствование, можно складывать не единицы, а PageRank упоминающих. Так те, которые извне больше влияют на влиятельных в группе, будут иметь больший вес. Оставляем это для желающих в качестве упражнения с кодом.

7. Сообщества


Для алгоритмического поиска кластеров в графах наиболее популярны методы оптимизирующие модулярность. Модулярность — количественный параметр использующий количество внутренних связей внутри предполагаемых сообществ и связей с внешними сообществами. Все результаты, что будут обсуждены ниже, получены при помощи кода выложеному на сайте бельгийской группы, который они описали в статье выложенной на arxiv. Другие люди тоже выкладывали свой код для подобных целей. Также алгоритм кластеризации встроен в другую популярную библиотеку для работы с графами — igraph.

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

UkrTweet — seadragon, файл.
Донецк — seadragon, файл.


Использовались скрипт для нахождения сообществ и скрипт для рисования графа.

8. Метки для сообществ


Хотелось бы получить какую-нибудь характеристику сформировавшихся сообществ. Один из способов — посмотреть в какие списки включались люди из сообществ. Скачиваем все списки, в которые были включены люди из групп (код). Сортируем группы по суммарному PageRank и печатаем десять названий списков, которые встречались для наибольшего количества людей в группе (код). В некоторых сообществах нельзя выделить говорящие метки, но во многих метки участников о многом говорят. В таблице ниже сообщества отсортированы по суммарном PageRank, двое самых авторитетных участника, количество участников, несколько говорящих общих меток (в скобках количество человек из сообществ которые были в соответствующих списках):

UkrTweet

Участники Всего участников Метки Комментарии
u02, karelina, ... 12 zp-ua (10), zp (10) Вокруг организаторов, в основном из Запорожья
woofer_kyyiv, gasique, ... 12 kyiv (8), mckyiv09 (6), bloggers (6) Киевляне-блогеры, встречавшиеся на Media Camp 2009
o_saltan, netocrat, ... 13 journalists (7), zp (6) Журналисты, много из Запорожья
b2blogger, maxzalevski, ... 7 seo (5), belseo (5), web-marketing (4) Веб-маркетологи и SEO-специалисты


Еще о четырех сообществах трудно что-то сказать на основе списков. Я, например, попал в сообщество, из которого многи ретвитили о tweetingplaces, одном моем проекте. Но общих названий списков у нас, кроме ukrtweet, нет.

Донецк

Участники Всего участников Метки Комментарии
quantizer, alderko, ... 21 donntu (10) Одно сообщество из ДонНТУ
decoy, andrulik, ... 21 cnc-donetsk (9) Многие бывшие на встречах "Кофе и код"
medialex, iammarat, ... 13 christians (13) Верующие
lapidarius, kolgushev, ... 11 seo (2), medianext-ua (2) Имеющие отношение к новым медиа
meesix, bezlik, ... 9 donntu (2) Второе сообщество имеющее отношение к ДонНТУ
alexeyosipenko, a_djo, ... 8 donetsk-rubyists (5), cnc-donetsk (3) Поклонники Ruby, также бывшие на КиК


Что интересно, olchik_terl и lancerenok, которые упоминались ранее, и у кого PageRank был больше, чем у других людей, которые так же часто упоминаются, попадают в активные сообщества, которые плохо описываются списками. Они же больше общаются со всей группой, а не внутри профессиональных сообществ.

Упражнения


Twitter, благодаря своему API, предоставляет плодородное поля для добычи и анализа информации о социальных графах. Вот несколько упражнений для тех, кто захочет больше покопаться.
  1. Какими средствами в группе чаще всего пользуются чтобы твитить (web, TweetDeck, Echofon,...)?
  2. Упоминались центральности. Изобразить betweenness_centrality в зависимости от eigenvector_centrality при помощи NetworkX.
  3. Получить влияния извне взвешенные через PageRank.
  4. С помощью кода книги «Программируем коллективный разум» выделить кластеры в группе не на основе графа, а на основе общих списков.

Используемые библиотеки


BeautifulSoup
для парсинга HTML
tweepy
интерфейс для доступа к Twitter API
NetworkX.
для работы с графами
Matplotlib
позволяет рисовать графики и диаграммы
igraph
пакет для работы с графами, есть интерфейс на Python (здесь не использовался, но упоминался)


texamus @texamus
карма
62,2
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

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

Комментарии (18)

  • +2
    Я к твиттеру отношусь прохладно, но расписанная методика анализа весьма интересна. Для себя выделил несколько интересных моментов. Таких как использование алгоритма PageRank для поиска влиятельных лиц.
  • 0
    Крутой взгляд.
    Я стараюсь анализировать твитер более субьективно.
    Тогда получаю отдачу в виде потока, реализующего мои желания в отличие от анализа на основе статистики, который пахнет «сухостью» и «неочеловеченостью».
  • +1
    Кстати.
    Если набор инструментария, описанного здесь кто-то соберет в онлайн софтинку, заплачу 50000р сразу за доступ к ней!
    • 0
      Все же получаемая информация носит больше развлекательный характер. Навряд ли она того стоит :)
      Если найдутся желающие — пожалуйста, пользуйтесь кодом.
      • 0
        Нет нет.

        Она не особо развлекаловка!

        Есть здесь тема.

        Естественно, что в контексте твитера есть много субьективности, посему и получается, что используя инструментарий для статистики — получаем не совсем то.
        Но в контексте статистики часто получаем совсем не те, что есть субьективно, а это помогает взглянуть на анализ совсем с другой стороны.

        Извините за сложные слова. 8)
        • 0
          Все же и вы меня не совсем так поняли.

          Поясню на примере. Если человек ставит целью считать PageRank страниц в Интернете — это развлечение. Если потом это число используется чтобы более авторитетные страницы всплывали в поиске — это польза.

          Или еще. Если человек категоризирует страницы по ключевым словам — это развлечение. Если потом на основе этих ключевых слов на этих страницах продается реклама — это польза.

          Если в твиттере строятся рейтинги, выделяются группы и т.п. — это развлечение. Если на основе этого что-то еще происходит — это может быть пользой.

          У меня есть мысли о том что может быть пользой для этих упражнений, но они пока зреют.
          • 0
            попробую отзеркализироваться…

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

            — Организация баркемпов, акций
            — Анализ сегмента для прощупывания почвы в сфере рекламы и PR
            — Нахождение опытных учасников в теме, которая интересует с професиональной стороны или со стороны развлекаловки… ю
            — …
  • +1
    Огромное спасибо.

    Если не секрет, насколько большие сообщества вы исследовали?
    Возмножно ли с помощью данных библиотек обрабатывать граф, ну допустив русскоговорящего сообщества Твиттера (около 100 тыс. акаунтов)? Какие требования к памяти?

    Запускали на GAE?
    • 0
      Другие сообщества не смотрел, т.е. не больше 250 узлов.

      Код на C++ для расчета кластеризации, который выложила бельгийская группа, использовался в их статье arxiv.org/abs/0803.0476 Там они проанализировали бельгийского оператора сотовой связи (2.6 миллиона узлов). И веб-граф с 118 миллиона узлами.

      О требованиях к памяти не задумывался, но, скорее всего они пропорциональны сумме числа узлов и ребер, т.к. модулярность оптимизируется более-менее локально.

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

      На GAE не запускал. Все-таки не вижу это как единое веб-приложение, а как набор скриптов для анализа. Еще и много сторонних библиотек.
    • 0
      Не получится так просто взять и запустить на GAE. Алгоритмы обработки графов предполагают что все данные уже находятся в оперативной памяти и не думают как их эффективно вытягивать и сохранять в datastore. Я в своей системе рекомендаций строю граф твиттерян и выполняю по нему поиск. Количество узлов около 20 000. Но использую специальный алгоритм, оптимизированный под хранилище AppEngine.
  • 0
    >Другая корпорация недавно воплотила максимально упрощенный вариант этой схемы, продавая свои новые телефоны влиятельным узлам социального графа за $0, а остальным за $530.

    >Другая корпорация
    Google?
    >продавая свои новые телефоны
    Nexus One?
    >влиятельным узлам социального графа за $0
    Тим О'Рейлли? (например)
    >а остальным за $530
    =((((((
    • 0
      В моей потоке промелькало упоминание Fred Wilson :)

      Все же не расстраивайтесь так. Это бизнес. Любопытный пример маркетинга.
  • 0
    Спасибо большое, очень люблю эту тему, в своё время тоже зачитывался Сегараном :)
  • 0
    :) О! А я о том, как визуализировать соцсети графами защищал диплом бакалавра свой. Правда я не кодил, а разрабатывал концепт визуализации большого-большого графа. Но воспоминания об этом всем остались исключительно теплые.
  • 0
    В любом случае было интересно =))
  • 0
    Спасибо, отличная статья! Вообще открытый социальный граф — это то что мне очень нравится в твиттере. Он абсолютно доступен через Twitter API. Есть еще хоть одна популярная соц. сеть, которая позволяет скопировать часть графа на свой сервер и работать с ним?
    • 0
      identi.ca/ — аналог твиттера, полностью открытый и распределенный, пока массами не принимаем.

      В декабре некоторые новостные сервисы шумели о том что wordpress.com а потом tumblr.com реализовали Twitter API. То есть Twitter API постепенно становится стандартом. Не знаю до какой степени социальный граф можно привязать в этих двух сервисах.

      Facebook, в принципе, дает доступ к графу через API. Тут проблема в том что можно по настоящему считать проявлением социального графа. В заметке я выделял тех, кто общается и упоминает, а не фоловит. В Facebook тоже имеет смысл выделять тех, кто отмечен на одной фотографии, пишет на стену… Только такие вещи часто закрыты пользователями.

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

      Вот еще один интересный проект от Google (API объединяющий многие социальные сети)
      code.google.com/apis/socialgraph/

      • 0
        Facebook, насколько я понял их terms, запрещает сохранять информацию порльзователей, в том числе список их друзей, на своем сервере более чем 24 часа.

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