Comments 21
Я вижу графы повсюду и использую их для анализа всевозможных систем
Может быть вы знаете, вдруг где-то случайно есть где-нибудь граф Википедии, который можно визуально посмотреть, позумить и понажимать?
Я просто видимо слишком туп ленив, для того чтобы хотя бы на Пайтоне набросать код, который всё это выведет. :(
А какие базы (опенсорс / платные) хорошо масштабируется, кто что использует для больших графов?
Для работы с большими графами хорошо подходят специализированные графовые базы данных. Вот несколько популярных решений, как опенсорсных, так и коммерческих:
Опенсорсные:
Neo4j (https://neo4j.com/) - одна из самых известных и зрелых графовых БД. Имеет Community Edition с открытым кодом. Хорошо масштабируется горизонтально за счет использования кластеров. Предоставляет декларативный язык запросов Cypher.
JanusGraph (https://janusgraph.org/) - масштабируемая графовая БД с открытым исходным кодом. Поддерживает различные бэкенды для хранения, такие как Cassandra, HBase, Google Cloud Bigtable. Имеет интеграцию с фреймворками обработки больших данных Apache Spark и Apache Giraph.
Коммерческие:
DataStax Enterprise Graph (https://www.datastax.com/products/datastax-enterprise-graph) - графовая БД, основанная на Apache Cassandra и Apache TinkerPop. Предназначена для работы с большими графами в распределенной среде.
Amazon Neptune (https://aws.amazon.com/ru/neptune/) - полностью управляемый облачный сервис графовой БД от Amazon. Поддерживает масштабирование и репликацию из коробки. Имеет совместимость с открытыми фреймворками Apache TinkerPop и RDF/SPARQL.
Microsoft Azure Cosmos DB (https://docs.microsoft.com/en-us/azure/cosmos-db/graph-introduction) - мульти-модельная облачная БД от Microsoft. Имеет графовый API на основе Apache TinkerPop.
При выборе БД нужно обращать внимание на требуемую производительность, масштабируемость, удобство языка запросов, интеграцию с экосистемой (напр. Hadoop, Spark), а также стоимость в случае коммерческих продуктов. Многие компании используют комбинацию из этих решений, в зависимости от объема и типа графовых данных.
Кроме специализированных БД, для обработки больших графов также используются графовые фреймворки и библиотеки для парадигмы MapReduce, такие как Apache Giraph (www.giraph.apache.org) и GraphX (https://spark.apache.org/graphx/). Они позволяют эффективно выполнять разные графовые алгоритмы (поиск путей, PageRank и т.д.) используя распределенные вычисления на кластере.
Neo4j достаточно резко начинает требовать коммерческую лицензию. Про Nebula не увидел. А кроме описания, есть опыт внедрения? Скажем для 0,5 млрд вершин и более млрд ребер?
Вы правы, при достижении определенного масштаба Neo4j начинает требовать переход на коммерческую Enterprise Edition для использования расширенных функций кластеризации и высокой доступности. Бесплатная Community Edition имеет ограничения по объему данных и производительности.
Упущением с моей стороны было не упомянуть Nebula Graph (https://nebula-graph.io/) - это относительно новая, но быстро развивающаяся опенсорсная распределенная графовая БД, заточенная под работу с очень большими графами. Архитектура основана на разделении вычислений и хранения. Имеет свой высокопроизводительный движок хранения на C++.
Что касается личного опыта - да, я участвовала во внедрениях графовых БД. В основном использовали связку из JanusGraph в качестве хранилища и Spark GraphFrames/GraphX для аналитики.
Один из проектов был в сфере телекома - мы строили граф звонков и взаимодействий между абонентами для выявления мошеннических схем и аномального поведения. Источником был стриминг из системы биллинга, порядка 5-7млн звонков в сутки. Суммарный размер графа составлял около 100 млн абонентов (вершин) и 1 млрд звонков (ребер).
А Gremlin разве не популярный язык запросов?
tl;dr: it depends.
Что лучше подойдет для макета Semantic BPM?
"Mathematica, MATLAB, Maple ..." А вы рассматривали реализацию библиотек графов в Octava? Сейчас задумываюсь о переходе на нее как раз из Матлаба.
Примерно два года назад делал тестовое задание на шарпе и столкнулся с задачей, которая решается графами - поиском в глубину. Я тоже рассматривал использование нескольких NuGet-пакетов, но по причине их слабой документации и ограничения по времени, для меня было проще найти похожий алгоритм, понять его работу и сделать на его основе тот, что подходит для моей задачи.
https://github.com/MaklakovSB/RailwayPark.git
В целом, статья получилась очень познавательной, спасибо что поделились!
Мне кажется, что графы - это одна из фундаментальных структур данных в computer science, сравнимая по важности со списками, деревьями, хэш-таблицами. При этом про графы говорят намного меньше. Как вы думаете, почему так происходит?
Всё то же самое можно сказать и про обычные словари, что не мешает иметь их в качестве примитивов в современных языках, которые закрывают 90% потребностей.
Касательно графов. Самое оптимальное их представление как раз через пару словарей, где одна вершина выступает ключом, а вторая - значением, и наоборот. Это позволяет быстро ходить по графу во всех направлениях.
Ну и в качестве примера: $mol_graph - обобщённая реализация графа на TS всего в несколько сотен строк кода, работающая с любыми типами узлов и рёбер и позволяющая топологически сортировать даже графы с циклами.
Согласен с автором, - графы территория неисчерпаемая, именно в силу их многообразия, но это не повод отступать! Стандартный алгоритм поиска в глубину из либы типа NetworkX наверняка проиграет самописному, заточенному под специфику предметной области, но позволит накидать прототип.
Мой любимый подход - неявные графы, изначально предназначен для описания бесконечных структур, но он еще и неплохо абстрагирует алгоритмы от данных. Хороший пример реализации для С++ есть в Boost Graph Library. А вот для питона всё грустнее, хотя именно там подход напрашивается, есть https://github.com/HeWeMel/nographs в процессе становления.
Охота на недостающий тип данных