На прошлой неделе нашел немого времени просмотреть материалы UDACITY CS215 Crunching Social Networks и должен сказать, что курс, если и неплохой, то не оправдывает своего названия. Вместо того, чтобы действительно поделиться подходами к анализу структуры отношений между вершинами графа (будь они люди или, скажем, публикации) Михаил Литтман рассказывает об алгоритмах поиска и сортировки, об их сложности и скорости, что на самом деле не так интересно, особенно если набор данных не астрономических масштабов.

Ниже хочу поделиться примером решения игрушечной задачки, которую мне бы хотелось уметь решать лучше:
Возьмем данные о ссылках американских политических блогов друг на друга[1] со страницы Марка Ньюмана здесь и попробуем найти самых влиятельных блоггеров.

Решение
Попробуем напрямую импортировать данные, надеясь, что Mathematica сама все поймет:
lesmis = Import[“polblogs.gml”];

Программа покажет ошибку, которая говорит о том, что граф сложный. Обычно это значит, что одно из ребер повторяется два раза*. Предлагаю избавиться от дублей, импортировав граф в виде текста и удалив все задвоения. Если открыть сам файл “.gml” в блокноте можно увидеть, что устроен он несложно. Итак:
lesmis = Import[“polblogs.gml”, “Text”];

s1 = Reverse[
   StringCases[lesmis,
    RegularExpression[“(?s)(node|edge) [.*? ]”]]];
s2 = StringJoin[Riffle[Union[s1], “n”]];

Export[FileNameJoin[{NotebookDirectory[], “better.gml”}],
 StringJoin[
  “Creator “Lada Adamic on Tue Aug 15 2006″ngraph [n  directed 1n
“,
  s2, “n]”], “Text”]

Попытаемся импортировать граф снова:
lesmis2 = Import[“better.gml”];
…и все впорядке.

Теперь возможно увидеть на кого ссылались много (out-degree) и какие блоги сами часто ссылались на других (out-degree):

(нажать, чтобы увеличить)

Из графика видим, что безусловным лидером был blogsforbush.com в обеих номинациях, но довольно много ссылок на себя получил и atrios.blogspot.com, на который частенько ссылается Кругман.

У меня есть ощущение, что было бы интересно (и не сложно) собрать данные и сделать граф ссылок между дневниками наших местных экономистов, но проблема в том, что мне не известно так уж много хороших дневников с которых можно было бы начать. Есть идеи? Это не должны быть обязательно очень популярные блоги, взгяните на график – большинство из дневников имеют в сумме менее 50 ссылок.

Скачать расчет и данные.

* Пакет Combinatorica должен справиться и с таким графом, но здесь мне бы не хотелось выходить за пределы встроенных функций.

Источник
[1] Lada A. Adamic and Natalie Glance, “The political blogosphere and the 2004 US Election”, in Proceedings of the WWW-2005 Workshop on the Weblogging Ecosystem (2005).