Graph ranking algorithms for entity importance scoring.
Provides PageRank, betweenness centrality, closeness centrality, and degree centrality implementations that operate on the immutable Graph data structure.
These scores are used by GraphQAPipeline to prioritize which entities to include in LLM context when the result set exceeds context limits.
Attributes
Example
val graph = Graph.empty
.addNode(Node("a", "Person"))
.addNode(Node("b", "Person"))
.addNode(Node("c", "Person"))
.addEdge(Edge("a", "b", "KNOWS"))
.addEdge(Edge("b", "c", "KNOWS"))
val scores = GraphRanking.pageRank(graph)
val centrality = GraphRanking.degreeCentrality(graph)
Computes betweenness centrality for all nodes in the graph.
Computes betweenness centrality for all nodes in the graph.
Betweenness centrality measures the fraction of shortest paths between all pairs of nodes that pass through a given node. High betweenness indicates a node is a bridge or broker in the network.
Uses Brandes' algorithm for efficient computation.
Value parameters
graph
The graph to analyze
Attributes
Returns
Map of node ID to betweenness centrality score (normalized by (n-1)(n-2)/2)
Computes closeness centrality for all nodes in the graph.
Computes closeness centrality for all nodes in the graph.
Closeness centrality measures the reciprocal of the average shortest path distance from a node to all other reachable nodes. Nodes that are "close" to all others have high closeness centrality.
Value parameters
graph
The graph to analyze
Attributes
Returns
Map of node ID to closeness centrality score (0.0 to 1.0)