Алгоритмы ранжирования графа предназначены для отображения сложной графической структуры на числовой вектор. Для данного алгоритма единственное числовое значение в результирующем векторе соответствует значению конкретной вершины в графе. В коде предыдущие структуры определены ниже с использованием
Groovy и
Blueprints .
def g = new Neo4jGraph('/tmp/neo4j'); // the graph
def m = new HashMap<Vertex,Double>(); // the rank vector
Ранжирование графа может быть разбито на две под-концепции: глобальные и локальные ранги. Это различие раскрывается в этом посте.
Глобальные метрики ранга
Многие из популярных алгоритмов ранжирования графов являются глобальными. Хороший список прачечной представлен на центральной странице Википедии . Стандарты учебника включают алгоритмы на основе собственных векторов (например, PageRank, центральность собственных векторов) и алгоритмы на основе геодезических (например, между близости, центральности близости). Общим для этих алгоритмов является то, что они ранжируют все вершины графа относительно всех вершин графа. Таким образом, весь граф анализируется для определения оценки какой-либо одной вершины, где возвращаемый вектор ранга представляет собой размер общего числа вершин в графе. Эта идея выражена в Groovy, Blueprints и Gremlin ниже.
public Map<Vertex,Double> global(Graph g) {
g.V.each{ ... }
}
def g = new Neo4jGraph('/tmp/neo4j');
assert global(g).size() == g.V.count();
Обратите внимание, что метод глобального ранга принимает только один аргумент графа. Это связано с тем, что граф содержит всю информацию, необходимую для расчета ранжирования — все вершины могут быть получены из графа. Однако ничто не мешает подмножеству вершин ранжироваться относительно некоторого подмножества вершин. Такие алгоритмы называются метриками локального ранга и обсуждаются далее.
Метрики локального ранга
Ключевой статьей, формулирующей концепцию локального ранга, являются Алгоритмы оценки относительной важности в сетях Скотта Уайта и Падрейк Смит. В этой статье авторы решили исследовать вопрос:
«Какие объекты наиболее важны в [графе] по отношению к конкретному человеку или группе лиц?
Структура этого утверждения приведена ниже.
public Map<Vertex,Double> local(Set<Vertex> roots) {
roots.each{ ... }
}
def g = new Neo4jGraph('/tmp/neo4j');
def roots = g.V[0..10]; // some subset of V
assert local(roots).size() <= g.V.count();
С локальными метриками ранга источником корневых вершин служит источник ранжирования. Все вершины в графе (или некоторые его подмножества, поскольку не все вершины могут быть достижимы или достаточно близки, чтобы их можно было коснуться) затем ранжируются относительно этого корневого набора. Когда этот корневой набор содержит только одну вершину, это называется
эго-рангом . Когда этот корневой набор содержит все вершины, это называется глобальным рангом. Таким образом, понятие локального ранга нечетко.
Интересным классом метрик локального ранга являются рекомендательные метики . Например, веб-сайт может иметь много пользователей и много элементов. Пользователям могут понравиться предметы. Когда конкретный пользователь вошел в систему, может появиться рекомендация, которая ранжирует элементы на графике относительно пользователя. Учитывая, что рекомендация относится к одной пользовательской вершине, алгоритм является эго-рангом. Базовая совместная фильтрация является примером локальной метрики эго-ранга. Фрагмент Gremlin ниже ранжирует / рекомендует элементы, относящиеся к пользовательской вершине 1, с использованием базовой совместной фильтрации.
def m = new HashMap<Vertex,Double>()
g.v(1).outE('likes').inV.inE('likes').outV.outE('likes').inV.groupCount(m);
На английском языке код гласит: «Получите вершину 1 из графика», определите, какие элементы нравятся пользователю 1, определите, какие пользователи также любят эти понравившиеся элементы, определите, какие элементы нравятся этим пользователям, и, наконец, оцените эти элементы по тому, сколько раз они были пройдены. Таким образом, возвращается рейтинг с корнем в вершине 1.
Существует также концепция локальной центральности. То есть определите, какие вершины являются наиболее важными для некоторого корневого набора вершин. Классическим алгоритмом такого рода является распространение активации . При распространяющей активации набор корневых вершин «стимулируется энергией», и эта энергия исходит от этих корней, когда она диффундирует по краям графа. Вершины с наибольшим потоком энергии за некоторое количество шагов считаются самыми центральными относительно корневого множества. Теоретически интересным примером алгоритма активации распространения является PageRank Priors, который обсуждается в ранее упомянутой статье Уайта и Смита.
Вывод
Большая часть обсуждения ранжирования графов сосредоточена на глобальных метриках ранга. Однако во многих ситуациях локальные показатели являются более полезными и более эффективными. Они более полезны в ситуациях, таких как персонализация. Они более эффективны тем, что не требуют полного обхода графа и обычно выполняются всего за несколько прыжков из корневого набора.
Если вы используете Gremlin и ваш код имеет вид
g.V.something.groupCount(m).loop{ }
|
тогда вы делаете алгоритм глобального ранга. Если ваш код Gremlin имеет вид
g.v(1).something.groupCount(m).loop{ }
|
тогда вы делаете алгоритм локального ранга. Оба типа алгоритмов ранжирования имеют свое место и, как правило, полезны для распределения сложной структуры в ранжированный список чисел. Другими словами, оба полезны для понимания графика.
Ссылки
Уайт С., Смит П., Алгоритмы оценки относительной важности в сетях , Специальная группа по интересам в области обнаружения знаний и добычи данных (SIGKDD), 24–27 августа 2003 г.
Источник:
http://markorodriguez.com/2011/03/30/global-vs-local-graph-ranking/