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.