PageRank and network centrality are tools for measuring importance in a network, such as websites, social media accounts, airports, or scientific papers. This cheat sheet helps students connect graph ideas to matrix calculations and real applications. It is useful when learning how links, paths, and probabilities can be used to rank nodes.
These ideas appear in search engines, recommendation systems, transportation planning, and data science.
Key Facts
- A directed network has edges with direction, so an edge from A to B means A points to B, but B does not necessarily point to A.
- Degree centrality for an undirected node is C_D(v) = degree(v) / (n - 1), where n is the number of nodes.
- In-degree counts links pointing into a node, and out-degree counts links leaving a node in a directed network.
- Closeness centrality can be written as C_C(v) = (n - 1) / sum of distances from v to all other reachable nodes.
- Betweenness centrality measures how often a node lies on shortest paths, using C_B(v) = sum over s,t of sigma_st(v) / sigma_st.
- Eigenvector centrality gives higher scores to nodes connected to other high-scoring nodes, often written as A x = lambda x.
- A PageRank transition matrix is column-stochastic when each column sums to 1 and represents probabilities of moving from one page to another.
- The PageRank update with damping is r_new = d M r_old + (1 - d) u, where d is often 0.85 and u is the uniform teleportation vector.
Vocabulary
- Network
- A network is a set of nodes connected by edges that represent relationships or links.
- Node
- A node is an individual object in a network, such as a web page, person, airport, or paper.
- Edge
- An edge is a connection between two nodes, and it may be directed or undirected.
- Centrality
- Centrality is a numerical measure of how important or influential a node is in a network.
- Transition Matrix
- A transition matrix gives the probabilities of moving from each node to other nodes in one step.
- Damping Factor
- The damping factor is the probability that a random surfer follows a link instead of jumping to a random page.
Common Mistakes to Avoid
- Confusing in-degree with out-degree is wrong because PageRank depends strongly on links pointing into a node, not just links leaving it.
- Treating every centrality measure as the same is wrong because degree, closeness, betweenness, eigenvector centrality, and PageRank reward different network roles.
- Forgetting to normalize transition matrix columns is wrong because PageRank probabilities must sum to 1 from each starting page.
- Ignoring dangling nodes is wrong because a page with no outgoing links creates a column with total probability 0, which breaks the random surfer model.
- Assuming the node with the most links always has the highest PageRank is wrong because links from important nodes can matter more than many links from unimportant nodes.
Practice Questions
- 1 A network has 6 nodes, and node A is connected to 4 other nodes in an undirected graph. What is the degree centrality of A?
- 2 In a directed network, page P receives links from 5 pages and links out to 2 pages. What are the in-degree and out-degree of P?
- 3 Using r_new = d M r_old + (1 - d) u, if d = 0.85, what percentage of the PageRank update comes from teleportation?
- 4 A page has fewer incoming links than another page but receives a link from a very highly ranked page. Explain why it could still have a higher PageRank.
Understanding PageRank & Network Centrality
A network model starts by choosing what the nodes and links mean. This choice controls the result. In a citation network, a node may be a paper and a directed link may mean one paper cites another.
In a transit network, nodes can be stations and links can represent direct routes. An adjacency matrix records whether links exist. A transition matrix goes further by describing a random move.
Each node divides its outgoing probability among the places it links to. A node with four outgoing links sends one quarter of its probability along each link when all links are treated equally.
PageRank treats importance as a flow that moves through the network over many rounds. A page gains score when pages pointing to it pass along some of their own score. A link from a heavily ranked page can matter more than a link from an isolated page.
The calculation does not stop after one update. Starting scores are repeatedly updated until the values change by only a tiny amount. Damping prevents the random traveler from becoming trapped in a closed group of nodes.
It gives every node a small baseline chance of being visited. Nodes with no outgoing links need special handling because they cannot distribute their score. A common method treats such a node as linking evenly to every node.
Centrality measures answer different practical questions. Degree is useful for finding highly connected nodes, such as a person with many direct contacts. Closeness favors nodes that can reach others through few steps.
This can matter when information or supplies need to spread quickly. Betweenness identifies bridges between groups. A station connecting two rail lines may have high betweenness even if it has few direct connections.
Eigenvector centrality and PageRank reward links from influential nodes, but PageRank is designed for directed movement with probabilities. A node can rank highly under one measure and modestly under another.
That is not a mistake. It shows that importance depends on the task being studied.
When working problems, draw a small network before building a matrix. Check the direction of every arrow carefully. For a transition matrix, verify that each column totals one.
Then perform one update by hand to see where score flows. In software, inspect whether the final scores sum to one and whether repeated updates have settled down. Be careful with disconnected parts of a network, missing data, and links created by automated accounts.
Centrality describes the structure represented in the data. It does not prove that a person, page, or location is valuable in every sense. Good interpretation requires knowing what the links mean and what the model leaves out.