Тезисы

Сети вокруг нас. Любой объект окружающего нас мира можно представить в виде совокупности объектов и связей между ними. Если объектов становится слишком много, а связи между ними слишком сложны, поневоле приходится задуматься о том, как эффективно хранить и обрабатывать такую сеть. Классические алгоритмы и структуры данных "пасуют" уже на сравнительно небольших графах.

Что делать, если объект вашего исследования - это весь веб-граф Рунета, граф Твиттера, дорожная сеть Европейского союза или граф знаний Google? Как корректно и быстро вычислить диаметр графа, найти компоненты связности, кратчайшее расстояние между всеми парами вершин или разрушить минимальное остовное дерево?

Многие без оглядки "бросаются в омут" Neo4j и других графовых баз данных, кто-то изобретает свои способы компактного хранения графа в оперативной памяти, а некоторые прибегают к мощи парадигмы MapReduce.

Традиционная MapReduce-парадигма не оправдывает себя при выполнении расчетов на больших графах. Большинство современных фреймворков обработки графов построены по модели "Bulk Synchronous Parallel", в том числе и знаменитые Pregel и Apache Giraph.

Дивный мир Graph Mining и Large-Scale Graph Processing приковывает к себе взгляды многих исследовательских компаний и увлеченных теорией графов программистов, вовлекая их в процесс создания новых алгоритмов и открытых инструментов. Это увлекательный, но тернистый путь, но дорогу, как известно, осилит идущий.