Тема: graph

RFC GRAPH

As you may know since early days of Internet the main specs, algorithms and innovations are submitted, discussed and published in the form of RFC (which stays for Request For Comments). All the core protocols of the TCP/IP stack along with dozens of others are described here.

There are almost 7200 of RFC right now, and the number keeps growing rapidly. Recently I’ve found a nice index with the citations and connections between RFCs. So I decided to build a graph of this network and to draw some clusters from it.

You can play with the graph online here (I’ve filtered out a lot of small standalone clusters as a noise)

And here it goes a list of some interesting snippets:

the main cluster of RFC graph
Continue reading

Tags: , , , , | Make a comment

GRAPH CHI

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

Авторы предлагают подход, позволяющий гонять на обычном десктопе обработку больших графов с эффективностью, сопоставимой с работой среднего кластера. Так, три итерации расчёта по этому методу PageRank-а над графом из 1.5 миллиардов ребёр на Mac Mini с SSD-диском заняли 13 минут (сравнить Spark-кластером из 50 машин, где эта же задача заняла 8.1 минуты).

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

Не очень понятно, сколько в таком режиме протянет обычная SSD-шка, но сама идея выглядит очень изящной.

Сама система (с несколькими уже готовыми примерами применения, типа PageRank, Community Detection, etc) доступна в исходном коде на C++ здесь. Кроме того, есть её частичный порт на Java, он лежит тут. Жду, когда кто-нибудь сподобится переписать на питоне ;)

Tags: , , , , | Make a comment