Get number of nodes at each relationship depth

Question

I'm working on a project where each user is represented as a node in Neo4j. Users can 'endorse' other users, creating a relationship. I want to be able to rank users based on their trust, where the weighting of each relationship is based on the weighting of the user which endorsed them. For example, a user who has been endorsed by 20+ users should have more weighting to their own endorsements than another user with only a couple of endorsements.

The way I'm querying it at the moment gives me the number of nodes for each depth, but it doesn't group by the parent node (e.g. all level 3 nodes are returned in one array, you don't know which nodes from level 2 each relates to).

MATCH (n)-[r:TRUSTS*]->(u)
WHERE u.name = 'XYZ' WITH n.name AS n, LENGTH(r) AS depth
RETURN COLLECT(DISTINCT n) AS endorsers, depth
ORDER BY depth

Here's what the network looks like, along with the result of a query for Ben.

As you can see, there are 2 first-level endorsers of Ben, and two 2nd-level endorsers of JM, which you can see from the graph image, but not from the query result.

Can anyone advise on either how to return the results grouped by parent node AND depth, so I can calculate the trust ranking in my code, or a better way to perform a weighted average to achieve the goal in the first paragraph?

This is an example of the sort of tree structure output I'm imagining for Ben:

Ben
├── JM
│   ├── Simon
│   └── Rus
│       ├── Robbie
│       │   ├── Ben
│       │   │   └──/ should terminate here
│       │   ├── Simon
│       │   └── JM
│       └── Ben
│           └──/ should terminate here
└── Simon

Here is another one for Rus:

Rus
├── Robbie
│   ├── Simon
│   ├── Ben
│   │   ├── Simon
│   │   └── JM
│   │       ├── Simon
│   │       └── Rus
│   └── JM  
│       ├── Simon
│       └── Rus            
└── Ben
    ├── Simon
    └── JM
        ├── Simon
        └── Rus

Obviously it should terminate when it reaches the user I'm querying for (otherwise it would be a circular structure).

The closest match I've found is a query provided by Tezra, which is:

MATCH (target:User{name:"Rus"}), (person:User), p=((person)-[:TRUSTS*]->(target))
WHERE ALL(n in NODES(p)[1..-1] WHERE n<>target)
RETURN NODES(p)[-2].name as endorser, COLLECT(person.name) as endorsed_by, SIZE(RELATIONSHIPS(p)) as depth
ORDER BY depth

This query returns the 1st level endorsers of "Rus", then the n-level endorsers 1st level endorsers:

| endorser | endorsed_by           | depth |
|----------|-----------------------|-------|
| Robbie   | Robbie                | 1     | // 1st level endorsers of Rus
| Ben      | Ben                   | 1     | // 1st level endorsers of Rus

| Robbie   | JM, Simon, Ben        | 2     | // 1st level endorsers of Robbie
| Ben      | JM, Simon             | 2     | // 1st level endorsers of Ben

| Ben      | Rus, Simon            | 3     | // 2nd level endorsers of Ben
| Robbie   | Rus, Simon, JM, Simon | 3     | // 2nd level endorsers of Robbie

| Robbie   | Rus, Simon            | 4     | // 3rd level endorsers of Robbie

This isn't quite correct, you only know who has indirectly endorsed Ben and Robbie, but not the nodes in between.

For example, from that output we know that the 1st level endorsers of Robbie are JM, Simon and Ben. The 2nd level endorsers are Rus, Simon, JM and Simon (column 4 in the tree), however there is no way to know the relationship between the 1st and 2nd level endorsers. As far as this query is concerned, the following trees are identical:

Rus
└── Robbie
    ├── Simon
    ├── Ben         <--- here Ben has 3 children (so should be weighted higher)
    │   ├── Simon
    │   ├── Rus
    │   └── JM
    └── JM
        └── Simon 


Rus
└── Robbie
    ├── Simon
    ├── Ben
    │   └── Simon
    └── JM          <--- here JM has 3 children instead
        ├── Simon     
        ├── Rus
        └── JM

What I'm looking for is a query which returns something like this (with the parent of each endorsement so the full tree can be reconstructed), this is the imagined output for Rus:

+--------+----------+-------+
| parent | children | depth |
+--------+----------+-------+
| Rus    | Robbie   | 1     |
+--------+----------+-------+
| Rus    | Ben      | 1     |
+--------+----------+-------+
| Robbie | Simon    | 2     |
+--------+----------+-------+
| Robbie | Ben      | 2     |
+--------+----------+-------+
| Robbie | JM       | 2     |
+--------+----------+-------+
| Ben    | Simon    | 3     |
+--------+----------+-------+
| Ben    | JM       | 3     |
+--------+----------+-------+
| JM     | Simon    | 4     |
+--------+----------+-------+
| JM     | Rus      | 4     |
+--------+----------+-------+
| JM     | Simon    | 3     |
+--------+----------+-------+
| JM     | Rus      | 3     |
+--------+----------+-------+
| Ben    | Simon    | 2     |
+--------+----------+-------+
| Ben    | JM       | 2     |
+--------+----------+-------+
| JM     | Simon    | 3     |
+--------+----------+-------+
| JM     | Rus      | 3     |
+--------+----------+-------+

user_6893866 · Answer

First, here is a console to play/test with the data.

Here are some commented queries. Let me know which most closely meets your needs. (ordered by relevance)

// Match the query target, and everyone who can endorse
MATCH (target:User{name:"Ben"}), (person:User),

// Match all endorse chains, length limit 5 
p=((person)-[:TRUSTS*..5]->(target)) 

// Our target may start, and will end; our chain, so no other path nodes can be him. 
// Normal matching will not match cycles.
// Adjust further path termination conditions here.
WHERE ALL(n in NODES(p)[1..-1] WHERE n<>target) 

//  Return target (extra), the 1'st tier endorser, their endorsers, and rank(depth) of each of those endorsers.
RETURN target.name, NODES(p)[-2] as endorser, COLLECT(person.name), SIZE(RELATIONSHIPS(p)) as depth 
ORDER BY depth

// one line copy for copy-paste into console
MATCH (target:User{name:"Ben"}), (person:User), p=((person)-[:TRUSTS*..5]->(target)) WHERE ALL(n in NODES(p)[1..-1] WHERE n<>target) RETURN target.name, NODES(p)[-2] as endorser, COLLECT(person.name), SIZE(RELATIONSHIPS(p)) as depth ORDER BY depth

An alternate return format

WITH NODES(p)[-2] as endorser, {people:COLLECT(person.name), depth:SIZE(RELATIONSHIPS(p))} as auth 
RETURN endorser, COLLECT(auth)

// one line copy for copy-paste into console
MATCH (target:User{name:"Ben"}), (person:User), p=((person)-[:TRUSTS*..5]->(target)) WHERE ALL(n in NODES(p)[1..-1] WHERE n<>target) WITH NODES(p)[-2] as endorser, {people:COLLECT(person.name), depth:SIZE(RELATIONSHIPS(p))} as auth RETURN endorser, COLLECT(auth)

UPDATE: Alternate return format to match OP's return table

MATCH (target:User{name:"Rus"}), (person:User), p=((person)-[:TRUSTS*]->(target)) WHERE ALL(n in NODES(p)[1..-1] WHERE n<>target) WITH NODES(p) as n, SIZE(RELATIONSHIPS(p)) as depth RETURN DISTINCT n[-depth] as parent, n[-depth-1] as child, depth ORDER BY depth

Get number of nodes at each relationship depth

1 Answers