In the previous lesson you chained optimization, assignment and routing for Rutalia's operations. Now we change domain: social networks, probably the world's biggest consumer of graph algorithms. The good news is that there is almost no new machinery to learn: the BFS from 03-02, the union-find from 01-04, Dijkstra from 03-03 and the hierarchical clustering from 05-05 are exactly the pieces these systems use. What is new is the modeling: which business question ("who is influential?", "whom do I suggest as a friend?") translates into which property of the graph. We will develop one star piece — PageRank — and work on a synthetic network with fictional users U-nnn, inspired by Rutalia's community of couriers and customers.

1. A social network is a graph (and the modeling decisions matter)
2. Building the synthetic network: preferential attachment and hubs
3. Small world: the six-degrees experiment with BFS
4. Components and communities
5. Centralities: who matters in the network?
6. PageRank: the random surfer, developed in full
7. Friend recommendation: mutual friends and Jaccard
8. Diffusion and virality: BFS as a propagation model
9. Privacy: what you must not do with real social data

The base modeling is straightforward: every user is a node and every relationship an edge. But the very first decision already has algorithmic consequences:

It is the same representation dilemma you saw in 03-01 (adjacency list vs matrix) raised to the semantic level: back then you chose how to store the graph; now you choose what the graph is. In this lesson we will use an undirected graph (mutual relationships) except in PageRank, where the direction of the edge is the whole point.

Real social networks are not uniformly random: a few nodes accumulate an enormous number of connections (hubs) while most have few. The classic generative mechanism is preferential attachment (the Barabási-Albert model): each new user tends to connect to whoever is already well connected — "the rich get richer". We implement it with an elegant trick: keep a list where each node appears once per edge it touches; sampling uniformly from that list is equivalent to sampling proportionally to degree.

The typical result: the hubs exceed 30-40 connections while the median user has 2-4. That extreme inequality (a "long tail" distribution) is the signature of real social networks, and it explains why marketing hunts for hubs and why a failure at a hub (or its compromised account) affects half the network.

In 1967 Milgram asked people in Nebraska to get a letter to a stranger in Boston by passing it only between acquaintances: the median was ~6 hops. In our graph, "number of hops between two users" is exactly the distance in edges, and the algorithm to compute it from a source is the BFS from 03-02 — unchanged, just reinterpreted.

With 300 users and only 2 links per new user, the average distance hovers around 3-4 hops and almost never exceeds 6. That is the small world property: the diameter grows as O(log n), not O(n), because the hubs act as shortcuts. Practical consequence: anything that propagates through the network (information, rumors, malware) can reach almost everyone in very few steps — we will quantify it in the diffusion section.

Connected components — is the network whole or fragmented? Two tools you already have: repeated BFS/DFS (03-02) or union-find (01-04), which also supports the incremental case (friendships arrive as a stream of events and you want to know at any moment whether two users are connected, without recomputing anything). In preferential-attachment networks everything ends up in one giant component; in real networks there is usually one giant component (~90% of users) plus a dust of tiny components.

Communities are something else: groups inside the same component with many internal edges and few pointing outward (the neighborhood gang, the coworkers). Two approaches using pieces from the course:

• Agglomerative (bottom-up). This is the hierarchical clustering from 05-05 applied to the graph: if you define the similarity between users as the Jaccard of their neighborhoods (we will see it in the recommendation section) and merge the most similar pairs, the dendrogram reveals communities. Remember the equivalence you discovered in 05-05: single-linkage = Kruskal (03-04); here the "forest that keeps merging" is the communities growing.
• Divisive (top-down): the Girvan-Newman idea. Instead of joining what is similar, cut what separates. The "bridge" edges between communities have a measurable property: many shortest paths pass through them (if there is only one bridge between two neighborhoods, every inter-neighborhood path crosses it). That measure is called edge betweenness, and it is computed with BFS from every node. The conceptual algorithm:

We will not implement it in full (computing betweenness efficiently is delicate, and O(n·m) per iteration makes it expensive on large networks — which is why production systems use faster methods like Louvain, which optimize a measure called modularity), but the intuition is what transfers: community = dense region; boundary = the edges all the paths squeeze through.

"Important" is not one single thing. Each mathematical definition of centrality answers a different business question:

In hub-heavy networks, degree and closeness tend to agree at the very top, but they diverge as soon as the network has community structure: a node of modest degree sitting between two communities can have extremely high closeness (and above all betweenness). That nuance — popular ≠ well placed — is what motivates the next section.

Degree counts how many point at you; PageRank weighs who. It was born to rank the web (a recommendation from an important page is worth more than a hundred from irrelevant pages) and is used the same way in social networks: a "follow" from an influential user weighs more than ten from empty accounts. Here the graph is directed: the edge u→v means "u follows v" (or "u links to v").

The random surfer idea. Imagine a user who browses forever: at each step, with probability d (the damping factor, typically 0.85) they jump to a random followee/link of the current node, and with probability 1−d they teleport to any node in the network (they get "bored" and start over). A node's PageRank is the fraction of time the surfer spends on it in the long run. The teleport is not decoration: without it, the surfer would get trapped in dead ends and cycles, and the process would not converge to anything useful.

Iterative formulation. We translate the story into a fixed-point equation, with N nodes:

Each node splits its rank evenly among its outgoing edges; the (1−d)/N term is the teleport. We iterate from a uniform split until the values stop moving — the same iterate-to-a-fixed-point philosophy you saw in Bellman-Ford (03-03) and in k-means (05-05).

Look at the result: U-003 wins clearly (four nodes point at it), but the interesting part is everything else. U-001 scores higher than U-004 even though each has exactly one node pointing at it — because U-001 is pointed at by U-003 itself, which is important, while U-004 is pointed at by the peripheral U-007. That is precisely "it's not how many point at you, but who", and no degree count captures it. Code details that matter:

• Dangling nodes (no outgoing edges): if they did not distribute their rank, the system would "leak mass" on every iteration. The standard fix is to have them distribute it across the whole network.
• Convergence: guaranteed with d < 1; with d = 0.85 a few dozen iterations suffice. Each iteration costs O(nodes + edges): PageRank scales to graphs of billions of edges (that is how it was computed over the entire web).
• Damping as a knob: d → 1 gives more weight to the link structure (and converges more slowly); d → 0 flattens everything toward the uniform distribution.

"People you may know" is, at its core, a problem of paths of length 2: if U-042 and U-107 are not friends but share 8 friends, they probably know each other. Counting mutual friends favors hubs (they share friends with everyone); Jaccard similarity corrects that bias by normalizing by the size of the neighborhoods:

It is the same maneuver you performed in k-NN (05-01): define a similarity and rank by it. The space changes (graph neighborhoods instead of numeric coordinates), not the method. In 06-04 you will reuse exactly this idea with user-item matrices to recommend products.

What happens when a user posts something and each contact shares it with some probability? The simplest model is a probabilistic BFS: the information advances in levels (the BFS levels are "hours" or "rounds" of propagation), but each edge only transmits it with probability p.

Two phenomena show up when you run it several times: starting from a hub boosts reach in the first rounds (which is why campaigns look for nodes with high PageRank), and there is a threshold: with small p the diffusion dies out on its own; past a certain value, it reaches almost the whole component in a few rounds — the small-world property working for you (marketing) or against you (disinformation, viruses). Serious epidemiological models on networks (SIR and friends) are refinements of this very simulation.

Everything above was done on fictional users U-nnn, and that is no accident. A real social graph is personal data, and of the sensitive kind: it reveals a person's relationships, habits and circles even if their attributes are "anonymized" (someone's connection structure can be enough to re-identify them). If you ever analyze real networks — even internal company ones, like the network of interactions between couriers and customers —:

• Legal basis and purpose first: in Europe, the GDPR requires a legal basis and a declared purpose before touching the data; "it seemed interesting" is not a purpose.
• Aggregate and minimize: for most business questions (how many communities are there? what is the average distance?) aggregate metrics are enough; you do not need — and must not — look at individuals.
• Beware of re-identification: removing names does not anonymize a graph; connection patterns are fingerprints.
• Centralities over people are decisions about people: using internal PageRank to evaluate employees, for instance, enters the territory of automated decisions with effects on individuals, which require transparency and human oversight (we come back to this in 06-04).

As a working rule: develop and validate with synthetic data (as we did here), and when you move to real data, do it within your organization's legal and data-governance framework, not on your own.

• Getting directed/undirected wrong. Modeling "follow" as mutual friendship (or vice versa) invalidates every subsequent analysis: PageRank on a symmetrized graph degenerates almost into plain degree. The first modeling decision is the cheapest to fix at the start and the most expensive later.
• Confusing component with community. A component is a topological fact (a path exists or it does not); a community is a matter of relative density and always depends on a criterion. There is no such thing as "the" one true community partition.
• Forgetting the dangling nodes in PageRank. Without the special redistribution, the sum of ranks decays on every iteration and the results stop being comparable. Always check that sum(pr.values()) ≈ 1.
• Recommending by mutual friends without normalizing. Without Jaccard (or another normalization), you will recommend hubs to everyone — correct according to the metric, useless for the user.
• Drawing conclusions from a single diffusion simulation. It is a random process: report the mean and spread of many runs, as you did with genetic algorithms in 02-04.
• Tip: before computing anything sophisticated, print the basics — number of nodes, edges, degree distribution, size of the giant component. Five lines that catch 90% of loading or modeling errors.

1. Network robustness. On the 300-user network, simulate two attacks: (a) removing the 10 highest-degree nodes; (b) removing 10 nodes at random. After each one, measure the size of the giant component with union-find or BFS. Which one fragments the network more? What does that imply for protecting a social infrastructure (or for vaccinating in an epidemic)?
2. PageRank with bought followers. Start from the directed follows network of the example and add 20 new accounts U-9xx that only follow U-007. Recompute PageRank. How much does U-007 rise? Does U-004 (whom U-007 follows) rise too? Explain why this "attack" works less well than the attacker expects and which parameter dampens it.
3. An evaluated recommender. Design an evaluation of the friend recommender: randomly hide 10% of the network's edges, generate top-5 recommendations for each affected user, and measure what fraction of the hidden edges shows up recommended (recall). Compare "mutual friends" against Jaccard.

1. The targeted attack on hubs is devastating: the giant component usually loses a large fraction of its nodes or shatters into pieces, while 10 random removals are barely noticeable (almost always degree-2-or-3 nodes fall). It is the two-faced nature of long-tail networks: robust against random failures, fragile against targeted attacks. In epidemiology, the reading is that immunizing hubs (high-contact people) pays off far more than immunizing at random.
2. U-007 rises clearly (it goes from minimal rank to a notable one: 20 accounts transfer it their amplified (1−d)/N), and U-004 rises too — rank flows through the edge U-007→U-004 and from there to U-003: the inflation propagates but dilutes at every hop (the d factor and the split among outgoing edges). It works less well than expected because the new accounts only contribute their teleport rank (nobody points at them), and the damping d limits how much "manufactured" rank can accumulate. It is, on a small scale, the link-spam arms race against search engines; real defenses also add anomalous-pattern detection (classification from 05-02!).
3. Sketch: hidden = random sample of 10% of the edges → remove them from network → for each user with hidden edges, generate the top-5 → recall = |recommended ∩ hidden| / |hidden|. It is the graph equivalent of the train/test split you used in 05-02: never evaluate with information the model was allowed to see. Jaccard usually wins in hub-heavy networks because "mutual friends" fills the top-5 with the same popular nodes for everyone; if your synthetic network is small and dense, the difference may be modest — one more reason to report averages over several seeds.

You have analyzed a social network end to end while learning almost no new algorithm: BFS (03-02) gave you distances, the small world, closeness and the diffusion model; union-find (01-04) the components; hierarchical clustering (05-05) and the Girvan-Newman idea, the communities; and the only piece developed from scratch — PageRank — turned out to be another fixed-point iteration from the family you already knew from Bellman-Ford and k-means. The underlying lesson of the case study: in a new domain, the work is mapping business questions to graph properties, choosing the right definition (directed? which centrality? which normalization?) and respecting the ethical and legal limits of the data. In the next lesson the challenge changes shape: it is not the structure of the problem but its size — what happens to search and sorting when Rutalia's 200 million historical records do not fit in any machine's memory.