синтаксис гремлина для вычисления метрики подобия Жакара

Question

Мне интересно вычислить метрику подобия Жакара для всех пар вершин в графе, которые не связаны напрямую. Метрика Жакара определяется как норма пересечения соседей двух вершин, деленная на норму объединения тех же множеств.

, где

До сих пор мне удавалось получить все пары узлов, не связанных напрямую (интересует только этот случай для предсказания канала, если прямая связь уже существует, тогда мне не нужно вычислять метрику Жакара) так, чтобы для пары (x, y) где x не равно y:

g.V().as('v1').V().where(neq('v1')).as('v2').filter(__.not(inE().where(outV().as('v1'))))

В дополнение к этому я также включаю соседей для каждого члена пары с метками v1out и v2out:

g.V().as('v1').out().as('v1out').V().where(neq('v1')).as('v2').filter(__.not(inE().where(outV().as('v1')))).out().as('v2out')

Отсюда, как мне выполнить операции над множествами, чтобы получить количество элементов в пересечении и объединении двух соседних множеств? После этого я полагаю, что могу добавить математический шаг (в настоящее время использующий TinkerPop 3.4.0), чтобы вычислить коэффициент подобия Jaccard, а затем шаг выбора, чтобы добавить ребро, когда значение превышает пороговое значение. Если у совершенно другого подхода есть преимущества по сравнению с частичным решением, описанным выше, я был бы рад принять его и, наконец, заставить работать.

Answer 1

Давайте сделаем это шаг за шагом:

Найдите пары вершин, а также соберите их соответствующих соседей:

g.V().match(
      __.as('v1').out().dedup().fold().as('v1n'),
      __.as('v1').V().as('v2'),
      __.as('v2').out().dedup().fold().as('v2n')).
    where('v1', neq('v2'))

Убедитесь, что v1 не является соседом v2и наоборот:

g.V().match(
      __.as('v1').out().dedup().fold().as('v1n'),
      __.as('v1').V().as('v2'),
      __.as('v2').out().dedup().fold().as('v2n')).
    where('v1', neq('v2').and(without('v2n'))).
    where('v2', without('v1n'))

Затем вычислите количество пересекающихся соседей и общее количество соседей:

g.V().match(
      __.as('v1').out().dedup().fold().as('v1n'),
      __.as('v1').V().as('v2'),
      __.as('v2').out().dedup().fold().as('v2n')).
    where('v1', neq('v2').and(without('v2n'))).
    where('v2', without('v1n')).as('m').
  project('v1','v2','i','u').
    by(select('v1')).
    by(select('v2')).
    by(select('v1n').as('n').
       select('m').
       select('v2n').unfold().
         where(within('n')).
       count()).
    by(union(select('v1n'),
             select('v2n')).unfold().
       dedup().count())

И, наконец, вычислите сходство по Джакарду, разделив i наu (также убедитесь, что вершины без соседей отфильтрованы для предотвращения деления на 0):

g.V().match(
      __.as('v1').out().dedup().fold().as('v1n'),
      __.as('v1').V().as('v2'),
      __.as('v2').out().dedup().fold().as('v2n')).
    where('v1', neq('v2').and(without('v2n'))).
    where('v2', without('v1n')).as('m').
  project('v1','v2','i','u').
    by(select('v1')).
    by(select('v2')).
    by(select('v1n').as('n').
       select('m').
       select('v2n').unfold().
         where(within('n')).
       count()).
    by(union(select('v1n'),
             select('v2n')).unfold().
       dedup().count()).
  filter(select('u').is(gt(0))).
  project('v1','v2','j').
    by(select('v1')).
    by(select('v2')).
    by(math('i/u'))

И последнее: поскольку сравнение вершин v1 и v2 такое же, как сравнение v2 и v1, запрос должен учитывать только один случай.Один из способов сделать это - убедиться, что идентификатор v1 меньше идентификатора v2:

g.V().match(
      __.as('v1').out().dedup().fold().as('v1n'),
      __.as('v1').V().as('v2'),
      __.as('v2').out().dedup().fold().as('v2n')).
    where('v1', lt('v2')).
      by(id).
    where('v1', without('v2n')).
    where('v2', without('v1n')).as('m').
  project('v1','v2','i','u').
    by(select('v1')).
    by(select('v2')).
    by(select('v1n').as('n').
       select('m').
       select('v2n').unfold().
         where(within('n')).
       count()).
    by(union(select('v1n'),
             select('v2n')).unfold().
       dedup().count()).
  filter(select('u').is(gt(0))).
  project('v1','v2','j').
    by(select('v1')).
    by(select('v2')).
    by(math('i/u'))

Выполнение этого обхода над современным игрушечным графом даетследующий результат:

gremlin> g = TinkerFactory.createModern().traversal()
==>graphtraversalsource[tinkergraph[vertices:6 edges:6], standard]
gremlin> g.V().match(
......1>       __.as('v1').out().dedup().fold().as('v1n'),
......2>       __.as('v1').V().as('v2'),
......3>       __.as('v2').out().dedup().fold().as('v2n')).
......4>     where('v1', lt('v2')).
......5>       by(id).
......6>     where('v1', without('v2n')).
......7>     where('v2', without('v1n')).as('m').
......8>   project('v1','v2','i','u').
......9>     by(select('v1')).
.....10>     by(select('v2')).
.....11>     by(select('v1n').as('n').
.....12>        select('m').
.....13>        select('v2n').unfold().
.....14>          where(within('n')).
.....15>        count()).
.....16>     by(union(select('v1n'),
.....17>              select('v2n')).unfold().
.....18>        dedup().count()).
.....19>   filter(select('u').is(gt(0))).
.....20>   project('v1','v2','j').
.....21>     by(select('v1')).
.....22>     by(select('v2')).
.....23>     by(math('i/u'))
==>[v1:v[1],v2:v[5],j:0.0]
==>[v1:v[1],v2:v[6],j:0.3333333333333333]
==>[v1:v[2],v2:v[4],j:0.0]
==>[v1:v[2],v2:v[6],j:0.0]
==>[v1:v[4],v2:v[6],j:0.5]
==>[v1:v[5],v2:v[6],j:0.0]