1

私は現在、ノードが確率的エッジを介して接続されているグラフに取り組んでいます。各エッジの重みは、エッジの存在確率を定義します。

開始するためのグラフの例を次に示します。

(A)-[0.5]->(B)
(A)-[0.5]->(C)
(B)-[0.5]->(C)
(B)-[0.3]->(D)
(C)-[1.0]->(E)
(C)-[0.3]->(D)
(E)-[0.3]->(D)

Neo4j トラバーサル フレームワークを使用して、このグラフを (A) からトラバースし、途中で見つかったエッジの確率に基づいて、到達したノードの数を返したいと思います。

重要：

  • 到達した各ノードは 1 回だけカウントできます。→ (A) が (B) と (C) に到達する場合、(C) は (B) に到達する必要はありません。一方、(A) が (B) に到達できず (C) に到達した場合、(C) は (B) に到達しようとします。
  • (B) が (C) に到達した場合も同様で、(C) は (B) に再び到達しようとはしません。
  • これは離散時間ステップ関数で、ノードは隣接ノードに 1 回だけ到達しようとします。
  • エッジの存在をテストする (トラバースするかどうか) ために、乱数を生成し、エッジの重みよりも小さいかどうかを確認できます。

トラバーサル記述の一部を次のようにコーディングしました。(ここでは、複数のノードから開始することは可能ですが、問題を解決するために必要ではありません。)

TraversalDescription traversal = db.traversalDescription()
            .breadthFirst()
            .relationships( Rels.INFLUENCES, Direction.OUTGOING )
            .uniqueness( Uniqueness.NODE_PATH )
            .uniqueness( Uniqueness.RELATIONSHIP_GLOBAL )
            .evaluator(new Evaluator() {

              @Override
              public Evaluation evaluate(Path path) {

                // Get current
                Node curNode = path.endNode();

                // If current node is the start node, it doesn't have previous relationship,
                // Just add it to result and keep traversing
                if (startNodes.contains(curNode)) {
                    return Evaluation.INCLUDE_AND_CONTINUE;
                }
                // Otherwise...
                else {
                  // Get current relationhsip
                  Relationship curRel = path.lastRelationship();

                  // Instantiate random number generator
                  Random rnd = new  Random();

                  // Get a random number (between 0 and 1)
                  double rndNum = rnd.nextDouble();


                  // relationship wc is greater than the random number
                  if (rndNum < (double)curRel.getProperty("wc")) {


                    String info = "";
                    if (curRel != null) {
                        Node prevNode = curRel.getOtherNode(curNode);
                        info += "(" + prevNode.getProperty("name") + ")-[" + curRel.getProperty("wc") + "]->";
                    }
                    info += "(" + curNode.getProperty("name") + ")";
                    info += " :" + rndNum;
                    System.out.println(info);

                    // Keep node and keep traversing
                    return Evaluation.INCLUDE_AND_CONTINUE;
                  } else {

                    // Don't save node in result and stop traversing
                    return Evaluation.EXCLUDE_AND_PRUNE;
                  }
                }
              }
            });

次のように、到達したノードの数を追跡します。

long score = 0;
for (Node currentNode : traversal.traverse( nodeList ).nodes())
{
    System.out.print(" <" + currentNode.getProperty("name") + "> ");
    score += 1;
}

このコードの問題は、NODE_PATH が定義されていても、望ましくないサイクルが存在する可能性があることです。

したがって、私は知りたいです：

  • サイクルを回避し、到達したノードの数を正確にカウントするソリューションはありますか?
  • そして理想的には、PathExpander を使用して同じことを行うことは可能 (またはそれ以上) でしょうか?

ありがとう

4

1 に答える 1