Graph Mining with PageRank and HITS

Turn relationships into a testable graph

You will build a directed graph, run PageRank and inspect how edge direction and dangling nodes affect the score.

• Define directed, undirected, weighted and bipartite graphs.
• Explain degree, paths, components and centrality as distinct properties.
• Describe PageRank’s random-surfer interpretation and damping.
• Distinguish HITS authority scores from hub scores.

Centrality depends on the graph you chose to build

A node represents an entity and an edge represents a declared relationship. Edge direction matters: a page linking to another page differs from the reverse. Weight might represent count, strength or confidence. Mixing meanings in one edge table makes centrality hard to interpret.

PageRank distributes score through incoming links, with a damping factor that allows random jumps. Links from a well-ranked node contribute more, divided among its outgoing links. Dangling nodes without outgoing edges need a redistribution policy so probability does not disappear.

HITS calculates two coupled values. Authorities receive links from good hubs, while hubs link to good authorities. Scores are query or graph dependent. Link farms and duplicated edges can manipulate both methods.

Degree is local, while betweenness uses shortest paths and PageRank uses recursive endorsements. Each answers a different question. Pick the measure from the decision, not from the most impressive chart.

Graph data can reveal sensitive relationships even without profile fields. Apply access control, aggregation and release review. Avoid ranking people for high-impact decisions from a centrality score alone.

Calculate PageRank on five pages

NetworkX handles iteration and dangling-node behaviour. The score sum should be approximately one.

Install the lesson dependencies

python -m pip install networkx

Rank a directed link graph

import networkx as nx

graph = nx.DiGraph()
graph.add_edges_from([
    ("A", "B"), ("A", "C"),
    ("B", "C"), ("C", "A"),
    ("D", "C"), ("E", "C"),
])

rank = nx.pagerank(graph, alpha=0.85)
hubs, authorities = nx.hits(graph, max_iter=1000, normalized=True)

for node, score in sorted(rank.items(), key=lambda item: item[1], reverse=True):
    print(node, round(score, 3))
print("PageRank sum:", round(sum(rank.values()), 6))
print("top authority:", max(authorities, key=authorities.get))
print("top hub:", max(hubs, key=hubs.get))

Expected invariants

<five nodes printed in descending PageRank order>
PageRank sum: 1.0
top authority: <node receiving strong hub links>
top hub: <node linking to strong authorities>

Exact ordering depends on the graph and library implementation. Explain it through incoming and outgoing edges rather than memorizing one result.

Graph defects to audit

Plotting a graph does not validate its construction. Check the edge table first.

• Duplicate edges can unintentionally create weight.
• A crawler or API limit can exclude low-visibility nodes and bias centrality.
• Reversing source and target columns answers the opposite question.
• Disconnected components can make global rank comparisons misleading.

Build a small citation or navigation graph

Use synthetic pages or a dataset with clear rights. Compare indegree, PageRank and HITS authority.

• Document node, edge, direction and weight semantics.
• Test one edge removal and one duplicated-edge correction.
• Report scores with the component and node count.
• Write one reason a centrality score should not drive an automated decision.

Graph evidence

• Validated edge list.
• Centrality comparison.
• Sensitivity and privacy note.

Official references and further reading

• NetworkX PageRank (Primary API and parameter reference)
• NetworkX HITS (Primary HITS implementation reference)

Review note for Graph Mining with PageRank and HITS: recheck the linked documentation after a dependency changes the relevant API, metric or modelling assumption, then record the tested version beside your result.