Как включить отрицательные веса в поиск пути, выявлять центральные и периферийные кластеры на основе заданной плотности, а также делать выборки из больших графов для масштабирования машинного обучения. Знакомимся с графовыми алгоритмами, недавно добавленными в библиотеку Neo4j Graph Data Science 2.4: декомпозиция K-ядра, алгоритм кратчайшего пути Беллмана-Форда и случайное блуждание с учетом общего соседства (CNARW).
Декомпозиция K-ядра
Алгоритм K-Core Decomposition основан на концепции разделения графа на слои, продвигаясь от периферийных к центральным узлам. Он рекурсивно идентифицирует подграфы, в которых каждый узел имеет не менее k соединений, где k находится в диапазоне от 0 до максимальной степени графа.
Декомпозиция K-ядра представляет собой процесс разделения узлов в графе на группы на основе последовательности степеней и топологии графа. Термин i-ядро относится к максимальному подграфу исходного графа, так что каждый узел в этом подграфе имеет степень не менее i. Такая максимальность гарантирует, что невозможно найти другой подграф с большим количеством узлов, где выполняется это свойство степени. Узлы в подграфе, обозначенном i-ядро также, принадлежат подграфу, обозначенному j-ядро для любого j<i. Однако обратное неверно. Каждый узел u связан с основным значением, которое обозначает наибольшее значение i, такое что u принадлежит i-core. Наибольшее значение ядра называется вырожденностью графа. Стандартные алгоритмы декомпозиции K-ядра итеративно удаляют узел низшей степени, пока граф не станет пустым. Когда узел удаляется из графа, все его отношения удаляются, а степень его соседей уменьшается на единицу. При таком подходе различные основные группы обнаруживаются одна за другой.
В Neo4j алгоритм работает во всех режимах: потоковом, режиме статистики, мутации и записи на направленных и ненаправленных графах с неоднородными узлами, гетерогенными и взвешенными отношениями. Декомпозиция K-ядра позволяет легко анализировать структуры сообществ и выявлять влиятельные узлы, обеспечивая гибкий и детальный подход к обнаружению сообществ в социальных сетях, исследовании белковым соединений при анализе и синтезе лекарств, а также оптимизации распространения информации при проектировании сетей. Этот алгоритм особенно полезен при работе с сообществами разной плотности и определении степени детализации уровня соединений каждого узла графа, что часто встречается во множестве задач, от анализа социальных сетей до биоинформатики.
Алгоритм кратчайшего пути Беллмана-Форда
Как и следует из названия, алгоритм кратчайшего пути Беллмана-Форда вычисляет кратчайший путь между узлами. Реализация этого алгоритма, представленная в библиотеке Neo4j Graph Data Science 2.4, позволяет вычислять кратчайшие пути в графах даже с отрицательными весами. Библиотека Neo4j GDS обеспечивает адаптацию исходного алгоритма Беллмана-Форда под названием Shortest-Path Faster Algorithm (SPFA). SPFA значительно сокращает время вычислений Беллмана-Форда, работая только с подмножеством узлов, а не перебирая множество узлов на каждом шаге. Кроме того, вычисления распараллелены для дальнейшего ускорения вычислений.
В улучшенной версии SPFA-алгоритма используются методы выборки и распараллеливания для значительного сокращения времени вычислений. Кратчайший путь Беллмана-Форда особенно полезен для таких задач маршрутизации и анализа топологии сетей, балансировки нагрузки и оптимизация затрат. В оптимизации цепочки поставок и финансах алгоритм Беллмана-Форда позволяет эффективно распределять ресурсы и принимать решения о маршрутизации, учитывая вес ребер на пути.
В отличие от алгоритма Дейкстры, который работает только для графов с неотрицательными весами отношений, алгоритм Беллмана-Форда может обрабатывать графы с отрицательными весами, если источник не может достичь ни одного узла, участвующего в отрицательном цикле. Напомним, цикл в графе — это путь, начинающийся и заканчивающийся в одном и том же узле. Для отрицательного цикла сумма весов отношений отрицательна. Когда существуют отрицательные циклы, определить кратчайшие пути не так-то просто из-за сокращения суммы весов при каждом прохождении отрицательного цикла.
Когда алгоритм Беллмана-Форда обнаруживает отрицательные циклы, он возвращает отрицательные циклы вместо кратчайших путей. Поскольку полный набор отрицательных циклов может быть слишком большим для перечисления, каждый узел будет включен не более чем в один возвращенный отрицательный цикл. Способность работать с отрицательными весами делает алгоритм Беллмана-Форда более универсальным, чем алгоритм Дейкстры, но и более медленным на практике. В Neo4j алгоритм Беллмана-Форда работает во всех режимах: потоковом, режиме статистики, мутации и записи на направленных и ненаправленных графах с неоднородными узлами, гетерогенными и взвешенными отношениями.
Выборка случайного блуждания с учетом общего соседства
Алгоритм Common Neighbor Aware Random Walk (CNARW) в Neo4j представляет собой метод выборки графа, который помогает масштабировать машинное обучение на больших графах. Это особенно полезно, когда выборка больших графов сопряжена с определенными трудностями, например, образцы поступают из разных кластеров данных. Пока эта функция находится в режиме бета-тестирования в Neo4j и работает с направленными и ненаправленными графами с неоднородными узлами, гетерогенными и взвешенными отношениями.
Алгоритмы выборки графов используются для уменьшения сложности больших и сложных графов при сохранении их основных свойств. Такие алгоритмы помогают ускорить вычисления, уменьшить систематическую ошибку и обеспечить конфиденциальность, делая анализ графов более управляемым и точным. Они широко используются в сетевом анализе, машинном обучении и анализе социальных сетей, а также в других приложениях. CNARW — это метод выборки графа, который включает в себя оптимизацию выбора узла следующего перехода. При этом учитывается количество общих соседей между текущим узлом и кандидатами на следующий переход. Основная причина, по которой простые случайные блуждания имеют тенденцию к медленной сходимости, связана с высокой характеристикой кластеризации, которая типична для некоторых видов графов, например, для онлайновых социальных сетей (OSN). При равномерном случайном перемещении к соседям легко попасть в локальные петли и повторно посетить ранее посещенные узлы, что замедляет сходимость.
Решить эту проблему можно, определив приоритеты узлов, которые предлагают более высокую вероятность изучения непосещенных узлов на каждом этапе. Узлы с более высокими степенями могут иметь общих соседей с ранее посещенными узлами, что увеличивает вероятность повторных посещений. Следовательно, выбор узла с более высокой степенью и меньшим количеством общих соседей с ранее посещенными узлами (или текущим узлом) не только увеличивает шансы обнаружения непосещенных узлов, но и снижает вероятность повторного посещения ранее посещенных узлов на будущих шагах.
Принимая во внимание общих соседей узлов, CNARW снижает вероятность выборки дублирующихся узлов. Это улучшает репрезентативность выбранных подграфов и уменьшает смещение в сторону плотно связанных областей, что приводит к более точному и сбалансированному представлению структуры графа. CNARW подходит для использования в рекомендательных системах, обнаружении аномалий и сегментации рынка, позволяя выявить интересы пользователей на основе общих соседей через идентификацию отклоняющихся узлов и эффективное определение плотно связанных групп, которые соответствуют сообществам. Читайте в нашей новой статье об алгоритме разделения по медоидам для выявления сообществ, который не поддерживается в Neo4j, но может быть имплементирован в этой графовой СУБД.
Узнайте больше про использование графовых алгоритмов и средств работы с ними для практического применения в реальных проектах аналитики больших данных на специализированных курсах нашего лицензированного учебного центра обучения и повышения квалификации для разработчиков, менеджеров, архитекторов, инженеров, администраторов, Data Scientist’ов и аналитиков Big Data в Москве:
Источники
