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

Высокий редактор

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

Рукопись следует направлять в адрес редакции (***) в двух экземплярах и на дискете в редакторе WORD и выше либо по Е-mail: **@***.ru.

Сначала не понял, но, наверное, редакция имеет в виду версию WORD или наиболее высокую WORD.

Высокий редактор

Python 101


 В личных целях нужно научиться пользоваться COM из Python, к чему должна привести книжка справа —>

Однако, как оказалось, нужно начинать с самого начала – мой навык письма на Python на столько плох, что однажды пришлось переписать готовый код для раскрашивания карт только потому, что не смог понять как работает ‘import’.
В части “Problem solving” попавшегося под руку/замечательного “Byte of Python” предлагается использовать  GNUwin32 для того, чтобы архивировать содержание каталога в zip с указанием даты и других подробностей. 
Решение этой задачки дается в BoP, но так же легко возможно проделать это и в Mathematica, используя   Run[], которая походит на os.system():

dirA = "d:\a\" <> DateString[Date[], {"Year", "Month", "Day"}] <> 
".zip"
dirB = "d:\b"
cmd = "zip -qr " <> dirA <> " " <> dirB
Run[cmd]

Теперь, когда базовые вещи позади, нужно немного практики, чтобы набить руку.

Python 101