PageRank

The PageRank algorithm ranks entities in a network based on their importance by analyzing connections between them. Each entity (e.g., nodes in a social network, documents, or proteins) gets a score, with higher scores for those linked to by other high-scoring entities. Scores are iteratively calculated, distributing an entity’s rank across its outgoing connections, until stable. In general domains, like citation networks or recommendation systems, it identifies influential nodes, such as highly cited papers or key influencers.

Kuzu implements a parallelized version of PageRank based on Ligra.

Syntax

CALL page_rank(
    graph_name,
    dampingFactor := 0.85,
    maxIterations := 20,
    tolerance := 0.0000001
    normalizeInitial := true
)
RETURN node, rank

Alias: pr

Parameters

Parameter	Type	Optional	Default	Description
graph_name	STRING	No	-	Name of the projected graph to run the algorithm on
dampingFactor	FLOAT64	Yes	0.85	Probability of following an outgoing edge, must between 0 and 1
maxIterations	INT64	Yes	20	Maximum number of iterations to run
tolerance	FLOAT64	Yes	0.00001	Minimum change in scores between iterations to continue
normalizeInitial	BOOLEAN	Yes	true	Whether to normalize initial scores to sum to 1

Return

Column	Type	Description
node	NODE	Node object
rank	FLOAT64	PageRank score of the node

Example

Define schema

CREATE NODE TABLE Node(id STRING PRIMARY KEY);
CREATE REL TABLE Edge(FROM Node to Node);

Insert nodes and edges

CREATE (u0:Node {id: 'A'}),
        (u1:Node {id: 'B'}),
        (u2:Node {id: 'C'}),
        (u3:Node {id: 'D'}),
        (u4:Node {id: 'E'}),
        (u0)-[:Edge]->(u1),
        (u0)-[:Edge]->(u4),
        (u1)-[:Edge]->(u4),
        (u2)-[:Edge]->(u4),
        (u3)-[:Edge]->(u4);

We’ll first create a projected graph from the node and edge tables.

CALL project_graph('Graph', ['Node'], ['Edge']);

Run PageRank on the projected graph as follows:

CALL page_rank('Graph') RETURN node.id, rank ORDER BY rank DESC;

┌─────────┬──────────┐
│ node.id │ rank     │
│ STRING  │ DOUBLE   │
├─────────┼──────────┤
│ E       │ 0.130088 │
│ B       │ 0.042750 │
│ D       │ 0.030000 │
│ C       │ 0.030000 │
│ A       │ 0.030000 │
└─────────┴──────────┘