Page, Brin, Motwani & Winograd, The PageRank Citation Ranking, Stanford InfoLab 1998
You have an 80-node directed graph and need to rank its nodes by importance. Counting inbound links is the obvious approach and it is the one the paper argues against: it treats a link from a page nobody visits as worth exactly as much as a link from a page everybody does.
PageRank defines importance recursively instead. A page is important if important pages link to it:
where L(q) is q's out-degree and d=0.85. Read as a random surfer: with probability d they follow a link, and with probability 1−d they jump to a page at random.
This graph contains both pathologies that make the naive version fail.
A rank sink. Nodes 70 and 71 link only to each other. Without damping they absorb all the rank and everything else goes to zero.
Dangling nodes. Nodes 75 to 79 have no outlinks at all. Their rank goes nowhere each iteration, so the total mass shrinks and the whole vector decays toward zero.
Find the structure that is going to cause trouble.
train_df is an edge list with columns source, target, plus constant columns n_nodes and damping.
Implement explore_graph(train_df) returning n_nodes, n_edges, damping (5 places), n_dangling, dangling_nodes (a sorted list of ints), max_out_degree, top_in_degree_node and top_in_degree.
A dangling node is one that appears in no source row: it has no outlinks. Build the out-degree over all n_nodes positions, not just the ones that appear, or you will miss them entirely.
damping column rather than hardcodedEvaluated server-side against a hidden test set.