Mock Final Exam — Part II

Exercise A1: Who is the most central node?

Consider the following undirected, unweighted graph on 7 nodes. The edge list is:

\(\{A\!-\!B,\; A\!-\!C,\; B\!-\!C,\; C\!-\!D,\; D\!-\!E,\; E\!-\!F,\; E\!-\!G,\; F\!-\!G\}\)

(a) Give the degree of every node. Which node(s) have the highest degree?

(b) Compute the closeness centrality of nodes \(A\), \(C\), and \(D\). Use \(C_{\text{clo}}(v) = \dfrac{n-1}{\sum_{u} d(v,u)}\), where \(d\) is shortest-path distance and \(n=7\).

(c) Compute the (un-normalized) betweenness centrality of nodes \(A\), \(C\), and \(D\) — i.e. for each, the number of shortest paths between other pairs of nodes that pass through it (count each unordered pair once).

(d) A manager asks: "Which single node is the most important one in this network?" Explain why degree, closeness, and betweenness do not all give the same answer here, and which measure you would trust if the network represented a communication relay system. Be specific about node \(D\).

Exercise A2: Eigenvector centrality & PageRank — conceptual

(a) For the graph above, eigenvector centrality ranks \(C\) and \(E\) above the bridge node \(D\) (it gives \(C\!\approx\!E\!\approx\!0.45\) vs \(D\!\approx\!0.38\)). This is the opposite of the betweenness ranking. Explain, in one or two sentences, why eigenvector centrality "demotes" the bridge even though the bridge is structurally critical.

(b) PageRank is computed with a damping factor (typically \(\alpha = 0.85\)) — at each step the random surfer follows an out-link with probability \(\alpha\) and "teleports" to a random node with probability \(1-\alpha\). Give one concrete failure mode of the random walk that the teleportation term fixes, and name the kind of node responsible for it.

Exercise A3: Open questions

Answer in a few sentences each — in your own words. We are looking for understanding, not memorised definitions.

(a) What are centrality measures, and why would they help? Give one realistic situation where computing centrality changes a decision you would make.

(b) Suppose you must run a GCN on a graph but you have no node features (only the structure — who connects to whom). How could you assign features to the nodes so the GCN can run? Give at least two options. Does it make sense to do this — and when would it work well versus badly?

Exercise A4: MinHash and Jaccard

(a) For two sets \(S\) and \(T\), write the Jaccard similarity \(J(S,T)\) and say in one sentence what it measures.

(b) State the key property that links MinHash to Jaccard: under a single random hash (permutation), what is the probability that two sets have the same MinHash value? Write it as an equation.

(c) You compare two MinHash signatures of length \(K = 200\) and find they agree in 150 of the 200 positions. What is your estimate of \(J(S,T)\), and why is that the right estimate? What would change if you used \(K = 1000\) instead of 200?

Exercise A5: Why MinHash, and LSH banding

(a) If we can compute exact Jaccard directly, why bother building MinHash signatures at all? Give one or two reasons.

(b) Even with signatures, comparing every pair of \(M\) documents costs \(O(M^2)\). Explain what LSH banding does to avoid this: what are the bands \(b\) and rows \(r\), and when do two documents become a candidate pair?

(c) The probability that a pair with true Jaccard \(s\) becomes a candidate is \(P(s) = 1 - (1 - s^{\,r})^{b}\). Describe the shape of this curve as \(s\) goes from 0 to 1, and explain how \(b\) and \(r\) set the similarity threshold. If you wanted to catch only very near-duplicates (\(s \geq 0.9\)), would you choose more or fewer rows per band? Explain the consequence of getting it wrong (think precision vs recall).

Exercise A6: Choosing the representation

(a) Documents are turned into shingles (length-\(k\) token sequences) before MinHashing. What goes wrong if \(k\) is too small (say \(k = 1\))? What goes wrong if \(k\) is too large (say \(k = 10\))?

(b) MinHash + Jaccard compares documents by exact shingle overlap. When would you instead represent documents as embeddings and compare them with cosine similarity? Give one thing embeddings capture that shingle-Jaccard misses, and one advantage shingle-Jaccard keeps.

Exercise B1: Estimate similarity with MinHash

Use the six short documents below. You may use any library or write your own code; AI assistants are permitted. Represent each document as its set of words (ignore order and repetition).

1. d1: "the quick brown fox jumps over the lazy dog"
2. d2: "the quick brown fox leaps over the lazy dog"
3. d3: "a fast brown fox jumps over a sleepy dog"
4. d4: "machine learning models need careful evaluation"
5. d5: "careful evaluation is needed for machine learning models"
6. d6: "the stock market rallied after the announcement"

(a) Compute the exact Jaccard similarity for the pairs (d1, d2), (d4, d5), and (d1, d6).

(b) Estimate the same three similarities using MinHash. State the number of hash functions \(K\) you chose, and present a small table comparing your estimate to the exact value for each pair.

Exercise B2: Designing an approach — near-duplicate listings

Scenario. You join a second-hand marketplace. Sellers game search by re-posting the same item many times with small edits — a changed word, a new caption, a tweaked price — so results fill up with near-duplicates and buyers complain. Your manager asks: "Flag near-duplicate listings so we show each item once." You have ~3 million active listings, each a short text blob (title + description). There are no labels telling you which are duplicates.

Your task — before writing any code, design the approach. Address each of the following:

1. Representation. How do you turn a listing into something comparable — words, shingles, embeddings? Why that choice for this problem?
2. Similarity & scale. What similarity measure fits "near-duplicate"? Why is all-pairs comparison infeasible at 3M listings, and what from the course makes it feasible?
3. Parameters & threshold. What knobs does your method have, and how do you set them to catch near-duplicates specifically (not merely "similar" items)?
4. No ground truth. You have no labels. How would you build a small evaluation, and what would you measure (think precision vs recall)?
5. Failure modes. Name two ways your design could be wrong, and what you'd watch for.

There is no single correct answer. Marks are for justified, internally consistent choices — and for spotting the weaknesses of your own design.

Exercise C1: Read your own results

(a) Looking at your table from B1: for which pair did the MinHash estimate differ most from the exact Jaccard, and why does that happen? What would raising \(K\) do to that gap?

(b) You were allowed to use a library or an AI assistant to produce the MinHash code. Describe one concrete sanity check you ran to convince yourself the numbers are correct — rather than trusting the output blindly.

(c) Documents d4 and d5 say almost the same thing in a different word order. As word sets they look similar; as 3-word shingles they would look quite different. Which representation is "right" — and what does your answer tell you about choosing a similarity measure for a real task?