4

对于以下场景，我很难在 gremlin 中找出查询。这是有向图（可能是循环的）。

在此处输入图像描述

我想从节点“Jane”开始获得前 N 个有利节点，其中青睐定义为：

favor(Jane->Lisa) = edge(Jane,Lisa) / total weight from outwards edges of Lisa
favor(Jane->Thomas) = favor(Jane->Thomas) + favor(Jane->Lisa) * favor(Lisa->Thomas)

favor(Jane->Jerryd) = favor(Jane->Thomas) * favor(Thomas->Jerryd) + favor(Jane->Lisa) * favor(Lisa->Jerryd)

favor(Jane->Jerryd) = [favor(Jane->Thomas) + favor(Jane->Lisa) * favor(Lisa->Thomas)] * favor(Thomas->Jerryd) + favor(Jane->Lisa) * favor(Lisa->Jerryd)


and so .. on

这是手动计算我的意思的相同图表，

在此处输入图像描述

这很容易通过编程进行传输，但我不确定如何使用 gremlin 甚至 sparql 来查询它。

这是创建此示例图的查询：

g
.addV('person').as('1').property(single, 'name', 'jane')
.addV('person').as('2').property(single, 'name', 'thomas')
.addV('person').as('3').property(single, 'name', 'lisa')
.addV('person').as('4').property(single, 'name', 'wyd')
.addV('person').as('5').property(single, 'name', 'jerryd')
.addE('favor').from('1').to('2').property('weight', 10)
.addE('favor').from('1').to('3').property('weight', 20)
.addE('favor').from('3').to('2').property('weight', 90)
.addE('favor').from('2').to('4').property('weight', 50)
.addE('favor').from('2').to('5').property('weight', 90)
.addE('favor').from('3').to('5').property('weight', 100)

我正在寻找的是：

[Lisa, computedFavor]
[Thomas, computedFavor]
[Jerryd, computedFavor]
[Wyd, computedFavor]

我正在努力配合循环图来调整重量。这是我到目前为止能够查询的地方：https ://gremlify.com/f2r0zy03oxc/2

g.V().has('name','jane').       // our starting node
   repeat(                      
      union(                    
         outE()                 // get only outwards edges
      ).
      otherV().simplePath()).   // produce simple path
   emit().  
   times(10).                   // max depth of 10
   path().                      // attain path
   by(valueMap())

解决斯蒂芬·马莱特的评论：

favor(Jane->Jerryd) = 
    favor(Jane->Thomas) * favor(Thomas->Jerryd) 
  + favor(Jane->Lisa) * favor(Lisa->Jerryd)

// note we can expand on favor(Jane->Thomas) in above expression
// 
// favor(Jane->Thomas) is favor(Jane->Thomas)@directEdge +
//                        favor(Jane->Lisa) * favor(Lisa->Thomas)
//

计算示例

Jane to Lisa                   => 20/(10+20)         => 2/3
Lisa to Jerryd                 => 100/(100+90)       => 10/19
Jane to Lisa to Jerryd         => 2/3*(10/19)

Jane to Thomas (directly)      => 10/(10+20)         => 1/3
Jane to Lisa to Thomas         => 2/3 * 90/(100+90)  => 2/3 * 9/19
Jane to Thomas                 => 1/3 + (2/3 * 9/19)

Thomas to Jerryd               => 90/(90+50)         => 9/14
Jane to Thomas to Jerryd       => [1/3 + (2/3 * 9/19)] * (9/14)

Jane to Jerryd:
= Jane to Lisa to Jerryd + Jane to Thomas to Jerryd
= 2/3 * (10/19) + [1/3 + (2/3 * 9/19)] * (9/14)

这是一些psedocode：

def get_favors(graph, label="jane", starting_favor=1):
  start = graph.findNode(label)
  queue = [(start, starting_favor)]
  favors = {}
  seen = set()
  
  while queue:
    node, curr_favor = queue.popleft()

    # get total weight (out edges) from this node
    total_favor = 0
    for (edgeW, outNode) in node.out_edges:
       total_favor = total_favor + edgeW

    for (edgeW, outNode) in node.out_edges:
    
       # if there are no favors for this node
       # take current favor and provide proportional favor
       if outNode not in favors:
          favors[outNode] = curr_favor * (edgeW / total_favor)

       # it already has some favor, so we add to it
       # we add proportional favor
       else:
          favors[outNode] += curr_favor * (edgeW / total_favor)

       # if we have seen this edge, and node ignore
       # otherwise, transverse
    
       if (edgeW, outNode) not in seen:
          seen.add((edgeW, outNode))
          queue.append((outNode, favors[outNode]))

   # sort favor by value and return top X
   return favors
4

2 回答 2

2

这是一个 Gremlin 查询，我相信它正确地应用了您的公式。我将首先粘贴完整的最终查询，然后对所涉及的步骤说几句话。

gremlin> g.withSack(1).V().
......1>    has('name','jane').
......2>    repeat(outE().
......3>           sack(mult).
......4>             by(project('w','f').
......5>               by('weight').
......6>               by(outV().outE().values('weight').sum()).
......7>               math('w / f')).
......8>           inV().
......9>           simplePath()).
.....10>    until(has('name','jerryd')).
.....11>    sack().
.....12>    sum()     

==>0.768170426065163

查询从 Jane 开始并一直遍历，直到检查到 Jerry D 的所有路径。一路上，每个遍历器 asack都被维护，其中包含每个关系的计算权重值相乘。第 6 行的计算找到所有可能来自先前顶点的边权重值，math第 7 行的步骤用于将当前边上的权重除以该总和。最后，在第 12 行将每个计算结果相加。如果删除最后sum一步，您可以看到中间结果。

gremlin> g.withSack(1).V().
......1>    has('name','jane').
......2>    repeat(outE().
......3>           sack(mult).
......4>             by(project('w','f').
......5>               by('weight').
......6>               by(outV().outE().values('weight').sum()).
......7>               math('w / f')).
......8>           inV().
......9>           simplePath()).
.....10>    until(has('name','jerryd')).
.....11>    sack()

==>0.2142857142857143
==>0.3508771929824561
==>0.2030075187969925

要查看已采取的路线，path可以将步骤添加到查询中。

gremlin> g.withSack(1).V().
......1>    has('name','jane').
......2>    repeat(outE().
......3>           sack(mult).
......4>             by(project('w','f').
......5>               by('weight').
......6>               by(outV().outE().values('weight').sum()).
......7>               math('w / f')).
......8>           inV().
......9>           simplePath()).
.....10>    until(has('name','jerryd')).
.....11>    local(
.....12>      union(
.....13>        path().
.....14>          by('name').
.....15>          by('weight'),
.....16>        sack()).fold()) 

==>[[jane,10,thomas,90,jerryd],0.2142857142857143]
==>[[jane,20,lisa,100,jerryd],0.3508771929824561]
==>[[jane,20,lisa,90,thomas,90,jerryd],0.2030075187969925]

这种方法还考虑了根据您的公式添加任何直接连接，因为我们可以看到我们是否使用 Thomas 作为目标。

gremlin>  g.withSack(1).V().
......1>    has('name','jane').
......2>    repeat(outE().
......3>           sack(mult).
......4>             by(project('w','f').
......5>               by('weight').
......6>               by(outV().outE().values('weight').sum()).
......7>               math('w / f')).
......8>           inV().
......9>           simplePath()).
.....10>    until(has('name','thomas')).
.....11>    local(
.....12>      union(
.....13>        path().
.....14>          by('name').
.....15>          by('weight'),
.....16>        sack()).fold())    

==>[[jane,10,thomas],0.3333333333333333]
==>[[jane,20,lisa,90,thomas],0.3157894736842105]

这些额外的步骤不是必需的，但path在调试这样的查询时包含这些步骤很有用。此外，这不是必需的，但也许只是出于一般兴趣，我会补充一点，您也可以从这里获得最终答案，但我包含的第一个查询就是您真正需要的。

g.withSack(1).V().
   has('name','jane').
   repeat(outE().
          sack(mult).
            by(project('w','f').
              by('weight').
              by(outV().outE().values('weight').sum()).
              math('w / f')).
          inV().
          simplePath()).
   until(has('name','thomas')).
   local(
     union(
       path().
         by('name').
         by('weight'),
       sack()).fold().tail(local)).  
    sum() 
  
==>0.6491228070175439

如果其中有任何不清楚或我误解了公式，请告诉我。

编辑添加

为了找到所有可以从 Jane 联系到的人的结果，我不得不稍微修改一下查询。最后unfold的只是为了使结果更易于阅读。

gremlin> g.withSack(1).V().
......1>    has('name','jane').
......2>    repeat(outE().
......3>           sack(mult).
......4>             by(project('w','f').
......5>               by('weight').
......6>               by(outV().outE().values('weight').sum()).
......7>               math('w / f')).
......8>           inV().
......9>           simplePath()).
.....10>    emit().
.....11>    local(
.....12>      union(
.....13>        path().
.....14>          by('name').
.....15>          by('weight').unfold(),
.....16>        sack()).fold()).
.....17>        group().
.....18>          by(tail(local,2).limit(local,1)).
.....19>          by(tail(local).sum()).
.....20>        unfold()

==>jerryd=0.768170426065163
==>wyd=0.23182957393483708
==>lisa=0.6666666666666666
==>thomas=0.6491228070175439

第 17 行的最后group一步使用path结果来计算找到的每个唯一名称的总青睐度。要查看路径，您可以在group删除步骤的情况下运行查询。

gremlin> g.withSack(1).V().
......1>    has('name','jane').
......2>    repeat(outE().
......3>           sack(mult).
......4>             by(project('w','f').
......5>               by('weight').
......6>               by(outV().outE().values('weight').sum()).
......7>               math('w / f')).
......8>           inV().
......9>           simplePath()).
.....10>    emit().
.....11>    local(
.....12>      union(
.....13>        path().
.....14>          by('name').
.....15>          by('weight').unfold(),
.....16>        sack()).fold())

==>[jane,10,thomas,0.3333333333333333]
==>[jane,20,lisa,0.6666666666666666]
==>[jane,10,thomas,50,wyd,0.11904761904761904]
==>[jane,10,thomas,90,jerryd,0.2142857142857143]
==>[jane,20,lisa,90,thomas,0.3157894736842105]
==>[jane,20,lisa,100,jerryd,0.3508771929824561]
==>[jane,20,lisa,90,thomas,50,wyd,0.11278195488721804]
==>[jane,20,lisa,90,thomas,90,jerryd,0.2030075187969925]
于 2020-09-24T18:34:28.563 回答
1

这个答案非常优雅，最适合涉及 Neptune 和 Python 的环境。我提供第二个供参考，以防其他人遇到这个问题。从我看到这个问题的那一刻起，我只能把它想象成用 OLAP 方式的VertexProgramGraphComputer和. 结果，我很难以其他方式思考它。当然，使用 aVertexProgram需要像 Java 这样的 JVM 语言，并且不能直接与 Neptune 一起使用。我想我最接近的解决方法是使用 Java，subgraph()从 Neptune 中获取一个，然后VertexProgram在本地运行 TinkerGraph 中的自定义，这将很快完成。

更一般地说，在没有 Python/Neptune 要求的情况下，将算法转换为 aVertexProgram并不是一个坏方法，具体取决于图的性质和需要遍历的数据量。由于没有很多关于这个主题的内容，我想我会在这里提供代码的核心。这是它的胆量：

        @Override
        public void execute(final Vertex vertex, final Messenger<Double> messenger, final Memory memory) {
            // on the first pass calculate the "total favor" for all vertices
            // and pass the calculated current favor forward along incident edges
            // only for the "start vertex" 
            if (memory.isInitialIteration()) {
                copyHaltedTraversersFromMemory(vertex);

                final boolean startVertex = vertex.value("name").equals(nameOfStartVertrex);
                final double initialFavor = startVertex ? 1d : 0d;
                vertex.property(VertexProperty.Cardinality.single, FAVOR, initialFavor);
                vertex.property(VertexProperty.Cardinality.single, TOTAL_FAVOR,
                        IteratorUtils.stream(vertex.edges(Direction.OUT)).mapToDouble(e -> e.value("weight")).sum());

                if (startVertex) {
                    final Iterator<Edge> incidents = vertex.edges(Direction.OUT);
                    memory.add(VOTE_TO_HALT, !incidents.hasNext());
                    while (incidents.hasNext()) {
                        final Edge incident = incidents.next();
                        messenger.sendMessage(MessageScope.Global.of(incident.inVertex()),
                                (double) incident.value("weight") /  (double) vertex.value(TOTAL_FAVOR));
                    }
                }
            } else {
                // on future passes, sum all the incoming "favor" and add it to
                // the "favor" property of each vertex. then once again pass the
                // current favor to incident edges. this will keep happening 
                // until the message passing stops.
                final Iterator<Double> messages = messenger.receiveMessages();
                final boolean hasMessages = messages.hasNext();
                if (hasMessages) {
                    double adjacentFavor = IteratorUtils.reduce(messages, 0.0d, Double::sum);
                    vertex.property(VertexProperty.Cardinality.single, FAVOR, (double) vertex.value(FAVOR) + adjacentFavor);

                    final Iterator<Edge> incidents = vertex.edges(Direction.OUT);
                    memory.add(VOTE_TO_HALT, !incidents.hasNext());
                    while (incidents.hasNext()) {
                        final Edge incident = incidents.next();
                        messenger.sendMessage(MessageScope.Global.of(incident.inVertex()),
                                adjacentFavor * ((double) incident.value("weight") / (double) vertex.value(TOTAL_FAVOR)));
                    }
                }
            }
        }

然后上面的执行如下：

ComputerResult result = graph.compute().program(FavorVertexProgram.build().name("jane").create()).submit().get();
GraphTraversalSource rg = result.graph().traversal();
Traversal elements = rg.V().elementMap();

并且“元素”遍历产生：

{id=0, label=person, ^favor=1.0, name=jane, ^totalFavor=30.0}
{id=2, label=person, ^favor=0.6491228070175439, name=thomas, ^totalFavor=140.0}
{id=4, label=person, ^favor=0.6666666666666666, name=lisa, ^totalFavor=190.0}
{id=6, label=person, ^favor=0.23182957393483708, name=wyd, ^totalFavor=0.0}
{id=8, label=person, ^favor=0.768170426065163, name=jerryd, ^totalFavor=0.0}
于 2020-09-24T19:03:23.073 回答