Heapsters gonna heapst

На прошлой неделе нашел немого времени просмотреть материалы 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).

Heapsters gonna heapst

В поисках соседей (таких как я)

Закончил чтение для нового курса Model Thinker про модель Шеллинга, которая говорит о том, что люди стараются поселиться, чтобы вокруг было как минимум некоторое количество соседей были ровней (по доходу/образованию или другим признакам).

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

В самом простом случае на кольце могут проживать m магистров и n аспирантов + некоторое количество свободных мест. Каждый воспринимает как личное пространство двух (или какое-то другое) человек справа и слева.

Далее на каждом шаге выбирается недовольный индивид, доля похожих на него соседей для которому кажется неприемлемой, и переселяется на случайное свободное место. Процедура повторяется до тех пор пока не останется недовольных/надоест.

Я построил небольшую демонстрацию для Mathematica, которая позволяет посмотреть на процесс:
1) До массовых переселений

2) Все счастливы:
На Demonstrations уже есть иллюстрация модели Шеллинга, но она не слишком хороша, так как автор решает проблему определения соседей жестко задавая их индексы (там это в коде сразу видно), что лишает его возможности:
1) изменять размер личного пространства для индивидов (кол-во соседей которые учитываются при расчете доли похожих).
2) использовать другие способы расселения индивидов (например, на случайном графе).
В моем случае, населить случайных граф очень просто:
  
В поисках соседей (таких как я)