Портрет Русского ЖЖ - как это делается
Общую картинку удобно смотреть через http://ljstructure.livejournal.com/tag/
Далее технические подробности
Получение исходных данных:
- Через Рейтинг блогов LiveJournal получаем список первых 100 тысяч блогеров. Число 100 000 взято с потолка, чтобы ограничить расходы на трафик и вычисления ( которые, заметим линейны по числу блогеров)
- Через API LJ получаем список друзей и сообществ , в которых состоит(читает) конкретный блогер.
- Через API LJ получаем список "интересов" блогера
- Через запрос http://username.livejournal.com/tag получаем список тегов, которые использует блогер.
В итоге получили :
- Число тэгов- 919 654
- Число интересов-765 407
- Число сообществ-108 636
Извлеченные данные можно представить в виде набора графов (User-->User), (User-->Tag) ,(User-->Community) или гиперграфов (например (User, Tag, Coommunity)). Далее можно применить один из алгоритмов поиска Community_structure . Для определенности выбрана версия ненаправленного графа "взаимных друзей" . Полученный граф состоит из ~100 000 узлов и ~10 050 000 ребер. В качестве алгоритма разбиения (кластеризации) графа был выбран алгоритм максимизации Modularity . Применяемая версия алгоритма имеет один свободный параметр, позволяющий контролировать так называемый Resolution limit кластеризации. Полученное разбиение порождает фактор-граф ( уже взвешенный ), к которому снова применяется та же процедура. В итоге имеем иерархическое разбиение исходного графа. В текущей версии получено ~ 500 кластеров ( с числом блогеров >=50) на первом уровнe. Глубина иерархического дерева получилась равной 4 .
Для характеризации кластера использовались характерные для него тэги ("О чем пишут" ) , интересы ("Интересы") и сообщества ("Популярные сообщества"). В качестве меры "характерности" была использована F-measure . В итоге получаем минималистский пресс-портрет кластера
Каков "смысл" полученной кластеризации социального графа ? По крайней мере сразу видно два типа связи, по которому происходит объединение. Это некая общая тема(интерес, личность) и(или) география. Обнаружились и целые спам-кластеры (впрочем последние можно отнести к специфическому интересу). Видимо не все кластеры значимы в предъявленных смыслах. Жесткий характер кластеризации ( каждый блогер принадлежит отдельному классу) конечно условен. Можно говорить о вероятности принадлежности блогера к конкретному кластеру ( например через относительное число друзей в других кластерах) или сразу применяя алгоритмы 'soft clustering" . Сама процедура кластеризации достаточно гибка и позволяет добавлять внешниe (ручные) классификации как специфические граничные условия.
И еще кластеризация должна быть динамичной (меняться во времени)
Ниже будут выкладываться относительно случайно части классификации. Комментарии и добавления приветствуются.