Social Media and Communication: Probabilistic Models and Algorithms

Contents

• Introduction and overview
• 0. Background: probability and graphs
• 1. Random graphs: Erdős–Rényi
• 2. Prescribed degrees, small worlds, scale-free
• 3. Epidemic processes on graphs
• 4. Rumors, push-pull and influence
• 5. Large-scale distributed systems
• 6. The stochastic block model
• 7. Community detection and applications
• 8. Hands-on: networkx simulations
• 9. Course research notes (Massoulié, Inria)
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: a graphs / social-product engineer who wants generative models, not only metrics. Empirical first: “small world” seen everywhere for lack of a null model; a simulated epidemic that explodes if \beta is mis-set — then we name Erdős–Rényi, scale-free, SBM, cascades.

Statistical physics of networks ↔︎ influence / community algorithms.

What you will be able to do

• Handle the major random graph models — Erdős–Rényi, prescribed degrees, small worlds, scale-free — and their emergent properties.
• Analyze epidemic processes spreading on a graph.
• Study rumor spreading (push-pull) and influence mechanisms.
• Understand the stochastic block model as a generative model of communities, and use it to detect them.
• Connect these models to the large-scale distributed systems that run the platforms.
• Simulate random graphs and processes with networkx, and confront simulations with real data.

Official objectives and syllabus (2026-2027 catalog)

Course unit absent from the 2026-2027 catalog. The last published sheet (SynapseS 2025-2026) has no “Learning objectives” section: official objectives not communicated.

Its official description presents the course as a toolkit for apprehending networks in the broad sense — from the communication networks underlying the Internet to social networks, online or not — along three axes: models of the systems and phenomena of interest, algorithmic methods for their control (ideally decentralized), and mathematical tools for the analysis of behavior and performance.

Official reference: L. Massoulié, “Réseaux : contrôle distribué et phénomènes émergents”, 2016. No prerequisites are listed on the sheet. The detailed syllabus below is that of the 2025-2026 sheet.

Where this course fits in the program

A former period 2 option of M1, not carried over into the 2026–2027 catalogue: these notes are kept for reference, and the last official sheet (2025–2026) lists no prerequisites. The module builds on the two P1 refreshers: Refresher in Statistics for probabilistic calculus and Refresher in Computer Science for graphs, both reactivated in chapter 0.

It is not a prerequisite of any LLGA course. Graph Machine and Deep Learning for Generative AI, in the same period, teaches Erdős–Rényi and the SBM itself (its ch. 9); read alongside it, this module adds the probabilistic side of those models (thresholds, detectability). It is also useful background for Advanced Graph Neural Networks (M2), where these structures meet deep learning.

Course outline

• Background: probability and graphs — the two languages of the module, put back in hand before any use.
• Random graphs: Erdős–Rényi — the founding model and its threshold phenomena.
• Prescribed degrees, small worlds, scale-free — bringing the models closer to real networks, and measuring what each one misses.
• Epidemic processes on graphs — how a spread depends on the structure of the graph that carries it.
• Rumors, push-pull and influence — the dissemination protocols and the influence questions that follow.
• Large-scale distributed systems — what these models say about the systems that run the platforms.
• The stochastic block model — communities that are generated by a model, and therefore detectable.
• Community detection and applications — the algorithms that exploit the SBM and their uses.
• Hands-on: networkx simulations — going from theorems to numerical experiments (the three labs run alongside chapters 2, 3 and 6).
• Course research notes (Massoulié, Inria) — the team’s papers, read with the tools of the module.
• Exercises — threshold computations, spreads, and detections to carry out yourself.
• References — the founding papers of each chapter.

Session plan

36 h in class = 12 sessions of 3 h. The volume is the 36 h in person given in the module’s fiche; the course unit is absent from the 2026–2027 SynapseS catalogue (last published sheet: 2025–2026), and no sheet publishes a session-by-session programme, so the split below is our proposal for covering these notes in that time. Level 1 = foundations (reviews, definitions, first worked examples), 2 = core models and theorems, 3 = advanced material (sharp thresholds proved in recent research, open debates); the level never goes down from one session to the next.

Self-study, outside the 36 h (about 3 h in total): ch. 9 Course research notes (Massoulié, Inria) — five research axes and their founding papers (≈ 3 h, with Ex. 12).

How to study this module

• Work through chapter 0 in full: discrete probability and graph vocabulary are needed from the very first theorem.
• Simulate early and often: a random graph model is better understood plotted than stated — the networkx chapter is made for that.
• For each model, ask yourself which real property it captures and which one it misses: that is the question that structures the module.
• Plot the distributions (degrees, component sizes) instead of relying on averages.
• Connect epidemics and rumors to platform news: the same models describe widely publicized phenomena.
• Cross-reference with the Graph ML module of the same period: the SBM returns there as the foundation of learning on graphs.

0. Background: probability and graphs

The module’s guiding thread: a social network is a random graph (who follows whom?), traversed by stochastic processes (what spreads, and how fast?). The two mathematical pillars are therefore discrete probability — distributions, moments, convergence — and graph theory. This chapter puts back in place the definitions and the three basic tools: the first and second moment methods, branching processes, and random walks.

1. Random graphs: Erdős–Rényi

Concrete scene: a “community” detected in a network turns out to be a mere density artifact. To tell structure from chance, one needs a model of a graph with no structure at all; this chapter sets up that model, G(n,p), and its threshold phenomena.

The G(n, p) model of Gilbert–Erdős–Rényi is the primitive atom: n vertices, each pair connected independently with probability p. It has no structure — and that is precisely what makes it the touchstone: a phenomenon observed on a real network is “significant” only if it is improbable under G(n, p) at the same size and density (this is the role of the null model in modularity, ch. 7).

2. Prescribed degrees, small worlds, scale-free

Real networks have hubs and many triangles, two features G(n,p) cannot produce. This chapter builds three models that add them one at a time — imposed degrees, local clustering with a few shortcuts, growth by preferential attachment — and checks what each one gains.

3. Epidemic processes on graphs

A meme, a virus, a rumor: the same mathematics. The canonical model is the SIR epidemic (Susceptible → Infectious → Recovered) or its relapse version SIS, posed no longer on a homogeneous population but on a contact graph. The central question: is there a threshold below which the epidemic dies out quickly — and what does this threshold become when the graph is heterogeneous?

4. Rumors, push-pull and influence

Spreading information to n machines without a directory or a coordinator: the gossip protocol is the elegant solution — each node calls a random neighbor every round. It is the building block of rumors (Karp et al. 2000), of distributed aggregation (ch. 5) and the distant ancestor of blockchain blocks disseminated by “flooding”. The quantitative question: how many rounds until everyone is informed?

5. Large-scale distributed systems

Behind every feed: millions of requests per second, caches everywhere, load balancers. These systems consume exactly the same mathematics as the previous chapters — balls into bins, Poisson processes, random walks — and part of the advances come from the French school (Massoulié, ch. 9). This chapter gives its three building blocks: load balancing, caching, and resource sharing.

6. The stochastic block model

Communities: groups of vertices better connected within themselves than between each other. The stochastic block model (SBM) is its canonical generative model — the equivalent, for graphs, of Gaussians for point clouds. It makes it possible to ask the right questions: when is the block structure detectable? Which algorithm achieves it? The answers involve exact thresholds — two of which are due to the module’s instructor (ch. 9).

7. Community detection and applications

The SBM says when communities can be detected; practitioners also need an algorithm that runs on millions of vertices without knowing the model. This chapter presents the most used one, modularity maximization, compares it with SBM inference, and reviews what community structure is used for.

8. Hands-on: networkx simulations

The theorems of chapters 1 to 6 all predict a number — a giant-component fraction, an epidemic threshold, a detection accuracy. The three labs below check these predictions by simulation; each one is meant to be run right after the chapter it illustrates (Lab 1 after ch. 2, Lab 2 after ch. 3, Lab 3 after ch. 6).

# Lab 1 -- Erdos-Renyi vs Barabasi-Albert: degree laws and giant component
import numpy as np, networkx as nx
rng = np.random.default_rng(0)

G_er  = nx.gnp_random_graph(2000, 6/2000, seed=1)      # c = 6
G_ba  = nx.barabasi_albert_graph(2000, 3, seed=1)      # m = 3, mean degree 6
for name, G in (("ER", G_er), ("BA", G_ba)):
    ccs = sorted((len(c) for c in nx.connected_components(G)), reverse=True)
    degs = [d for _, d in G.degree()]
    print(f"{name}: largest component {ccs[0]/G.number_of_nodes():.4f}"
          f" | max degree {max(degs)} | clustering {nx.average_clustering(G):.4f}")
# expected (theorems 1.3 + 2.5): ER ~ 0.997 = the rho of 1.3 (rho = 1 - exp(-6 rho)),
# max degree ~ 15; BA = 1.0 (connected by construction), max degree of the order
# of m sqrt(n) ~ 134 (this run: ER 0.9965 and 15; BA 1.0000 and 115)

# Lab 2 -- discrete-time SIR: does the threshold depend on the degree law?
def sir(G, p, patient0):
    """Discrete SIR: infection p per edge per step, recovery in 1 step.
    Returns the final size of the epidemic."""
    inf, seen = {patient0}, {patient0}
    while inf:
        new = set()
        for u in inf:
            new |= {v for v in G[u] if v not in seen and rng.random() < p}
        seen |= new
        inf = new
    return len(seen)

def outbreak(G, p, trials=200):
    n = G.number_of_nodes()
    sizes = [sir(G, p, int(rng.integers(n))) for _ in range(trials)]
    return np.mean(sizes) / n            # final fraction of the population

for tau in (0.1, 0.15, 0.2, 0.25, 0.3, 0.5, 1.0):  # tau = beta/delta; recovery in 1 step,
    p = 1 - np.exp(-tau)                 # infection per edge per step
    print(f"tau={tau:4.2f}  ER {outbreak(G_er, p):.3f}   BA {outbreak(G_ba, p):.3f}")
# ER threshold: c p = 1, i.e. p = 1/6, tau ~ 0.18. Theorem 3.5 predicts a lower
# threshold for BA (E[D]/E[D(D-1)] ~ 0.074 on this graph): at tau = 0.2 a run gives
# BA ~ 0.15 against ER ~ 0.03. From tau ~ 0.3 the ER curve is at or above: heterogeneity
# lowers the threshold but also the final size, since the many degree-3 vertices of
# BA are harder to reach. Plot both curves and locate the two takeoffs.

# Lab 3 -- SBM: spectral detection (adjacency in dense, non-backtracking in sparse)
from scipy.sparse.linalg import eigsh

sizes, p_in, p_out = [500, 500], 0.10, 0.02
G = nx.stochastic_block_model(sizes, [[p_in, p_out], [p_out, p_in]], seed=3)
A = nx.to_scipy_sparse_array(G).astype(float)
truth = np.concatenate([np.zeros(sizes[0]), np.ones(sizes[1])])

w, V = eigsh(A, k=2, which="LA")    # eigsh returns eigenvalues in ASCENDING order
v2 = V[:, np.argsort(w)[-2]]          # 2nd largest eigenvalue (column 1 = Perron vector)
hat = (v2 > np.median(v2)).astype(int)
acc = max(np.mean(hat == truth), np.mean(hat != truth))
print("accuracy (adjacency, dense):", round(acc, 3))   # expected ~ 1.0

# in the sparse regime (p_in = 8/n, p_out = 2/n): build the non-backtracking matrix B
# (rows/columns = oriented edges; B[(u,v),(v,w)] = 1 if w != u), extract its
# first 2 real eigenvectors and run k-means -- cf. theorem 6.5 and
# exercise 11. Adjacency degrades first, since hub eigenvalues compete with the
# signal (over 10 seeds: accuracy about 0.77 for A against 0.83 for B).

9. Course research notes (Massoulié, Inria)

The module is taught by Laurent Massoulié, Inria senior researcher (Dragon team, Inria Paris center; he headed the joint Microsoft Research–Inria center and teaches at École Polytechnique). His career covers exactly the syllabus: epidemics and networks, rumors, stochastic block model, and distributed systems (caching, load balancing, decentralized optimization). Five axes, with the founding papers to read as a project (exercise 12).

Exercises

1. ★ From binomial to Poisson. Complete the proof of Proposition 1.2 by controlling the error terms: show that (1 - c/n)^{n-1-k} = e^{-c}\big(1 + O(1/n)\big) for fixed k (logarithm expansion); show that the variance of \mathrm{Bin}(n-1, c/n) converges to c (Refresher Statistics module, ch. 3).

2. ★ Giant component. Solve \rho = 1 - e^{-c\rho} numerically for c = 1.5, 2, 4, 10 and check by simulation (nx.gnp_random_graph, 10 repetitions); show the uniqueness of the solution in (0, 1) for c > 1 (study f(\rho) = \rho - 1 + e^{-c\rho}).

3. ★ Watts–Strogatz. Simulate the diameter and average clustering of the rewired ring for \beta \in \{10^{-4}, \dots, 1\} (log scale); reproduce the original figure; explain why \Theta(\beta n K) rewired “long” links in total, that is only \Theta(\beta K) per vertex, suffice to drop the diameter from \Theta(n/K) to \Theta(\log n) while clustering barely moves.

4. ★ Transmission-recovery race. In continuous SIR, show that on an infected edge, transmission beats recovery with probability \frac{\beta}{\beta + \delta} (independent exponential races — minimum distribution), and recompute R_0^{\text{graph}} of Theorem 3.2. Then show, by conditioning on the infectious period, that two edges leaving the same infective are both open with probability \frac{2\beta^2}{(\beta+\delta)(2\beta+\delta)}, which exceeds T^2: why does the exact coupling of Theorem 3.4 need a fixed infectious period?

5. ★ Push-pull. Show that pull alone does start from a single informed node: each of the n-1 ignorant nodes calls it with probability 1/(n-1), so one node is informed per round on average, and a round informs nobody with probability about e^{-1}.

   Write the exact recursions \mathbb{E}[k_{t+1} \mid k_t] for push alone and for pull alone. Check that both growth ratios are close to 2 while k_t = o(n), and that the push ratio is still 2 - e^{-1/2} \approx 1.39 at k_t = n/2 (Theorem 4.2).

6. ★ Power of two choices. Simulate n balls into n bins (one choice vs two); plot max load vs n on a log scale and check the two asymptotics \frac{\ln n}{\ln \ln n} and \frac{\ln \ln n}{\ln 2} (Theorem 5.1); discuss the information cost (the bin must know its load) and the passage to the dynamic model (queue arrivals/departures).

7. ★★ Triangle threshold. Complete the second moment of Theorem 1.6: compute \mathbb{E}[T(T-1)] by separating pairs of triangles that are disjoint, share a vertex, share an edge; deduce \mathrm{Var}(T) = o(\mathbb{E}[T]^2) when np \to \infty. What happens for K_4 (threshold n^{-2/3})?

8. ★★ Preferential attachment. Redo the master equation of Theorem 2.5 with the rule \Pi(i) \propto d_i + \alpha (attachment with newborns): show p_k \sim k^{-\gamma} with \gamma = 3 + \alpha/m (set up the differential equation and differentiate as in the proof).

9. ★★ Spectral threshold. Complete the proof of Theorem 3.3(i): justify the equality \sum_i x_i \sum_{j \sim i} u_j = \rho \sum_i x_i u_i (use (A u)_i = \rho u_i component by component); where do we use u > 0 (Perron–Frobenius) in the step \Phi_t \geq (\min_i u_i)\mathbf{1}_{\{\text{not extinct}\}} \ ?

   On a clique of size K with a pendant path of length L, show that \min_i u_i decays geometrically in L, so this route gives no O(\log n) bound. Then prove the componentwise bound \mathbb{E}[x(t)] \leq e^{(\beta A - \delta I)t} x(0) and deduce \mathbb{P}(\text{not extinct at } t) \leq n\, e^{-(\delta - \beta\rho)t}.

10. ★★ Submodularity. Prove the submodularity of reachability via the live-edge coupling of Theorem 4.4; show that the (1 - 1/e) bound is attained by the set-cover example; implement the CELF greedy algorithm on an SBM (1000 vertices) and compare with 20 random seeders.

11. ★★★ Non-backtracking. For a path with n vertices, compute the spectrum of A and of B (tridiagonality); for a d-regular graph, show that \rho(B) = d - 1 (walks without U-turns on a local tree).

    Implement sparse B (scipy.sparse) on an SBM with q = 2 blocks and check the Kesten–Stigum criterion of Theorem 6.3 by scanning (a, b) at fixed mean degree: plot the overlap 2\,\mathrm{acc} - 1 of Definition 6.2, which should stay near 0 below the threshold and become positive above it, up to finite-size blurring.

12. ★★★ Paper. Choose a paper from ch. 9 (Ganesh–Massoulié–Towsley 2005; Massoulié 2014; Bordenave–Lelarge–Massoulié 2015; Hall–Massoulié 2023; Even–Koloskova–Massoulié 2024), read it and present it in 10 minutes: model, main theorem, proof idea, algorithm, numerical results, limitations. Grid: one figure re-explained, one experiment reproduced in a lab, one open question.

Projects and assessment

Official assessment (last published sheet, SynapseS 2025–2026): “Written final exam of 3 hours, all documents allowed; oral resit possible at the end of the year; numerical grade out of 20; course unit earned if final grade ≥ 10.” The unit is absent from the 2026–2027 catalogue and from the LLGA lists (notes kept for reference), so no LLGA modality applies. Everything below is a proposal sized for a 36 h course: solo subjects of 15–20 h, group subjects of 25–30 h per member, a written exam in the format of the sheet, and a rubric for the projects.

The projects exercise mainly two master objectives: O4 (graph-structured data: random graphs, epidemics and communities measured on real and synthetic networks) and O2 (generative modelling theory: Erdős–Rényi, the configuration model and the SBM as generative models with sharp thresholds). The knowledge-graph subject adds O5 (Graph × LLM) through Graph ML, and the alignment subject adds O8 (privacy of pseudonymized graphs). All of them train O7: every prediction of a theorem is checked against a simulation with error bars.

Solo projects

1. [Solo · ≈ 20 h] Detectability at the Kesten–Stigum threshold: adjacency, non-backtracking and Bethe Hessian. Where does each spectral operator start to recover two planted communities in a sparse graph, and what do hubs change?
   • Implement: two balanced blocks with mean degree d = (a+b)/2 = 3 and n = 20{,}000, scanning the signal-to-noise ratio \lambda = (a-b)^2 / (2(a+b)) from 0.5 to 3; then a degree-corrected variant with a few planted hubs. Score each method by the overlap 2\,\mathrm{acc} - 1, maximized over the swap of the labels.
   • Operators: the adjacency A (Lab 3), the normalized Laplacian, the non-backtracking matrix B (Definition 6.4) and the Bethe Hessian H(r) = (r^2 - 1)I - rA + D at r = \sqrt{d}.
   • Hint: away from \pm 1, B has the same eigenvalues as the 2n \times 2n matrix below, which is much cheaper to build (Ihara–Bass): \begin{pmatrix} 0 & D - I \\ -I & A \end{pmatrix}.
   • Paper study: Krzakala, Moore, Mossel, Neeman, Sly, Zdeborová and Zhang, “Spectral redemption in clustering sparse networks”, PNAS 110(52), 2013; Saade, Krzakala and Zdeborová, “Spectral clustering of graphs with the Bethe Hessian”, NeurIPS 2014.
   • Optional link: a two-layer GCN of Graph ML, ch. 5, given 1 % of the labels, to see how far a few labels move the threshold.
   • Deliverables: code, 4–6 page report built around the overlap-versus-\lambda figure, 10-minute talk. Chapters: ch. 6, 8 (Lab 3) and Ex. 11.
   • Success criterion: over 10 seeds, the overlaps of B and of the Bethe Hessian stay near 0 for \lambda < 1 and become clearly positive above it (test runs at \lambda = 1.2 give about 0.3 for B).
   • Adjacency: without hubs it lags only near the threshold (below 0.1 at \lambda = 1.2) and catches up by \lambda = 3. With a few planted hubs it fails at every \lambda while B and the Bethe Hessian still detect; the report shows the localized eigenvectors responsible.
2. [Solo · ≈ 20 h] Power law or not? Auditing scale-free claims. Which degree tails of real networks survive a rigorous power-law test, and what does each model of ch. 2 reproduce of them?
   • Data: six SNAP networks of different kinds: ego-Facebook, ca-AstroPh (collaborations), email-Enron, soc-Epinions1, web-Stanford and roadNet-PA (a road network, as a negative control).
   • Implement: the protocol of Clauset, Shalizi and Newman (SIAM Review 51, 2009): discrete maximum-likelihood exponent, k_{\min} chosen by the Kolmogorov–Smirnov distance, goodness-of-fit p-value by semi-parametric bootstrap, and likelihood-ratio tests against log-normal, exponential and truncated power-law tails (the powerlaw package is allowed, once checked against your own code).
   • Compare: clustering, effective diameter and degree tail of each network with fitted Barabási–Albert, configuration (degree-preserving rewiring) and Watts–Strogatz models — the table at the end of ch. 2.
   • Paper study: Broido and Clauset, “Scale-free networks are rare”, Nature Communications 10, 1017, 2019 — place your six verdicts in their categories.
   • Deliverables: code, 4-page report with one verdict table, 10-minute talk. Chapters: ch. 0, 2, 8 (Lab 1).
   • Success criterion: on 100 synthetic samples of 10,000 values from a discrete power law with exponent 2.5, the estimated exponent is within 0.05 of the truth in at least 95 of them, and the bootstrap p-value exceeds 0.1 in about 90 % of the samples tested, as it should under the true model.
   • On log-normal samples, the report says how often the likelihood ratio is significant, and in which direction. Every real verdict comes with its p-value and the sign and significance of each likelihood ratio.
3. [Solo · ≈ 15 h] Random infectious periods: outbreak probability versus attack rate. At equal transmissibility T, how do the probability of a massive SIR epidemic on G(n, c/n) and its final size depend on the law of the infectious period? A paper study of Kenah and Robins, “Second look at the spread of epidemics on networks”, Physical Review E 76, 2007.
   • Implement: the directed coupling of the proof of Theorem 3.4 (one infectious period per vertex, one clock per oriented edge) for fixed, exponential and gamma infectious periods with the same T.
   • Predict: the attack rate from \rho = 1 - e^{-cT\rho}, and the outbreak probability 1 - q from the mixed Poisson branching of Theorem 3.2, solved numerically: q = \mathbb{E}\big[ \exp\big( -c\,(1 - e^{-\beta R})(1 - q) \big) \big].
   • Prove: the pair probability of Theorem 3.4 and, by Jensen’s inequality, that the outbreak probability is at most \rho.
   • Deliverables: code, 4-page report, 10-minute talk. Chapters: ch. 0, 1, 3 and Ex. 4.
   • Success criterion: for c = 4 and T = 1/2, over 1,000 runs at n = 10^4, the measured attack rate is within 0.01 of \rho \approx 0.80 for every law, and each outbreak probability matches its prediction within two binomial standard errors, about 0.03 at 1,000 runs (the predictions are about 0.80 for a fixed period and 0.64 for an exponential one).

Group projects

1. [Group of 3 · ≈ 30 h each] Cascades on a real social graph: thresholds, immunization and seeding. Do the thresholds of ch. 3 predict when a simulated contagion takes off on a real follower graph, and which interventions move them?
   • Data: the SNAP “Higgs Twitter” dataset (De Domenico, Lima, Mougel and Musolesi, “The anatomy of a scientific rumor”, Scientific Reports 3, 2013): the follower graph of about 456,000 users, with the timestamped retweets, mentions and replies around the July 2012 announcement of the Higgs boson. Work on a k-core that fits in memory.
   • Thresholds: the spectral bound 1/\rho(A), a sufficient condition for SIR to stay small (Draief, Ganesh and Massoulié, Annals of Applied Probability 18(2), 2008), against the configuration value T_c = \mathbb{E}[D] / \mathbb{E}[D(D-1)] of Theorem 3.5.
   • Implement: configuration and DC-SBM null models with the same degrees (graph-tool); discrete SIR and independent-cascade simulators; random, degree-targeted and acquaintance immunization (Cohen, Havlin and ben-Avraham, Physical Review Letters 91, 2003); CELF greedy seeding against the top-degree heuristic (Theorem 4.4).
   • Split of work: A: graph, null models and thresholds; B: simulators and immunization; C: seeding, a Hawkes fit of the real retweet times (branching ratio as an empirical R_0, ch. 3 note) and the evaluation.
   • Deliverables: repository, 6-page report, 15-minute talk. Chapters: ch. 2, 3, 4, 6, 8.
   • Success criterion: on the configuration null, the simulated SIR takeoff matches T_c within 10 % at two graph sizes; on the real graph, the report says which predicted threshold is closer and why (clustering, communities); every immunization and seeding curve has error bars over 20 runs.
2. [Group of 3 · ≈ 30 h each] Modularity versus SBM inference on an LLM-built knowledge graph. When an LLM turns paragraphs into an entity graph, are the communities found by modularity real structure, resolution-limit artefacts or the noise of a sparse graph, and which partition gives the better GraphRAG summaries?
   • Data: the paragraphs of about 1,000 questions of 2WikiMultiHopQA (Ho, Duong Nguyen, Sugawara and Aizawa, COLING 2020), whose gold evidence triples score the extraction; an open 7–8B instruct model (for example Qwen2.5-7B-Instruct) on a free GPU tier, with spaCy NER plus co-occurrence as a cheap baseline.
   • Implement: the extraction to a knowledge graph; Louvain and Leiden over a range of resolutions; graph-tool’s flat and nested SBM (Peixoto, 2014); the same partitions on degree-preserving rewired copies (ch. 7 note, items 1–2).
   • Measure: modularity and description length on the real and rewired graphs; NMI against a reference grouping (the entities of each question’s evidence); exact match of community-summary retrieval (Edge et al., “From local to global: a Graph RAG approach to query-focused summarization”, 2024) against BM25.
   • Split of work: A: extraction and knowledge-graph quality; B: partitions and null models; C: summaries and question answering.
   • Links: Graph ML, ch. 0, 9 and 10 (Louvain, the SBM, GraphRAG worked in 10.4), and the Year 1 capstone Y1.1, which reuses this knowledge graph.
   • Deliverables: repository, 6-page report, 15-minute talk. Chapters: ch. 6, 7, 8.
   • Success criterion: triple precision is measured against the gold triples; on the rewired copies, Louvain’s modularity and the number of blocks chosen by the SBM are both reported, so the spurious-community effect is quantified; the two partitions are compared on 200 questions with a paired bootstrap.
3. [Group of 2 · ≈ 25 h each] De-anonymizing correlated graphs. How much correlation, and how many seeds, does an attacker need to re-identify the users of a pseudonymized social graph? A paper study of Hall and Massoulié, “Partial recovery in the graph alignment problem”, Operations Research 71(1), 2023 (ch. 9.5).
   • Implement: correlated Erdős–Rényi pairs (a parent G(n, p), two copies that keep each edge with probability s, the second one relabelled at random) and correlated SBM pairs; seeded percolation matching (Yartseva and Grossglauser, COSN 2013); a seedless spectral aligner, GRAMPA (Fan, Mao, Wu and Xu, ICML 2020).
   • Real graph: SNAP ego-Facebook (McAuley and Leskovec, NeurIPS 2012), split into two noisy copies in the same way.
   • Optional link: fused Gromov–Wasserstein alignment from Optimal Transport, ch. 5, as a third aligner.
   • Split of work: A: generators, seeded matching and the recovery map against s and the mean degree; B: spectral and transport aligners, the real-graph study, and a one-page note on what pseudonymization under the GDPR does and does not protect (ch. 7.2, graph alignment and privacy).
   • Deliverables: repository, 5-page report, 15-minute talk. Chapters: ch. 1, 7, 9.
   • Success criterion: the recovery map shows a sharp transition, placed against the exact-recovery threshold n p s^2 \approx \ln n (Cullina and Kiyavash, SIGMETRICS 2016) and the partial-recovery conditions of Hall and Massoulié; on ego-Facebook, the report gives the number of seeds needed to re-identify half of the users at s = 0.8, with error bars over 10 splits.

Written exam (proposal)

Three hours, all documents allowed (the format of the 2025–2026 sheet), no calculator needed; four independent questions. Use the values e^{-1/2} \approx 0.61, \quad e^{-1.6} \approx 0.20, \quad \ln 2 \approx 0.69, \quad \ln 3 \approx 1.10, \quad \ln(10^6) \approx 13.8, \quad \log_2(10^6) \approx 19.9, \quad \ln\ln(10^6) \approx 2.63.

1. Question (5 points). Two symmetric blocks, with p_{\mathrm{in}} = a/n and p_{\mathrm{out}} = b/n. (a) Define detection, partial recovery and exact recovery, and say in which degree regime each is the relevant question. (b) State the Kesten–Stigum condition and decide whether detection is possible for (a, b) = (5, 1) and (4, 2). (c) Explain why spectral clustering on A fails at bounded degrees, and what the non-backtracking matrix changes.

   Expected:

   • 1. Definition 6.2, all with probability tending to 1 and up to the swap of the two labels: detection = an accuracy of at least 1/2 + \varepsilon for some fixed \varepsilon > 0 (an overlap bounded away from 0), at bounded degrees; partial recovery = an accuracy of at least a prescribed \alpha \in (1/2, 1); exact recovery = the whole partition, at degrees \Theta(\log n), with threshold \sqrt a - \sqrt b > \sqrt 2 in the \log n / n scaling.
   • 2. Detection is possible iff (a-b)^2 > 2(a+b) (Theorem 6.3): 16 > 12, so yes for (5, 1); 4 \leq 12, so no for (4, 2), where no estimator reaches an accuracy of 1/2 + \varepsilon with probability tending to 1.
   • 3. The highest degree is \Theta(\log n / \log\log n), and a star of degree \Delta has eigenvalue \sqrt\Delta, which exceeds the signal eigenvalue (a-b)/2; the top eigenvectors localize on hubs. B forbids immediate returns: its bulk lies in the disk of radius \sqrt d, and an informative eigenvalue escapes it exactly above the threshold (Theorem 6.5).

2. Question (6 points). SIR with a fixed infectious period and transmissibility T. (a) On G(n, 4/n) with T = 1/2, is a massive epidemic possible? Compute its final fraction to two decimals and the probability that it occurs. What changes for exponential infectious periods with the same T?

   2. A fraction v of the vertices, chosen uniformly at random, is vaccinated before the outbreak: find the critical v.

   3. On a configuration graph where half of the vertices have degree 2 and half degree 8, compute T_c and compare it with an Erdős–Rényi graph of the same mean degree.

   Expected:

   • 1. cT = 2 > 1: yes (Theorem 3.4). Iterating \rho = 1 - e^{-2\rho} from 0.8 gives 0.798, then 0.797, so \rho \approx 0.80. With a fixed period the outbreak probability is the survival probability of a \mathrm{Pois}(2) branching, which solves the same equation: about 0.80. With exponential periods the threshold and \rho are unchanged, but the offspring is mixed Poisson and the outbreak probability drops (about 0.64).
   • 2. The unvaccinated vertices form G(n(1-v), c/n), of mean degree c(1-v); the threshold c(1-v)T = 1 gives v_c = 1 - 1/(cT) = 1/2.
   • 3. \mathbb{E}[D] = 5 and \mathbb{E}[D(D-1)] = (2 + 56)/2 = 29, so T_c = 5/29 \approx 0.17. For G(n, 5/n), \mathbb{E}[D(D-1)] = 25 and T_c = 0.20: degree heterogeneity lowers the threshold (Theorem 3.5).

3. Question (5 points). Let X be the number of isolated vertices of G(n, p). (a) Prove that \mathrm{Var}(X) = \mathbb{E}[X] + \mathbb{E}[X]^2\, \frac{p - 1/n}{1 - p}.

   2. Deduce that if np = \ln n - t_n with t_n \to \infty, then G(n, p) has an isolated vertex with high probability. (c) Show that if np = \ln n + t_n there is none with high probability, and say why this does not yet prove connectivity.

   Expected:

   • 1. Write X as a sum of indicators: \mathbb{E}[X] = n(1-p)^{n-1}, and two distinct vertices are both isolated with probability (1-p)^{2n-3}, since they share one potential edge. Then \mathrm{Var}(X) = \mathbb{E}[X] + n(n-1)(1-p)^{2n-3} - \mathbb{E}[X]^2, and factoring \mathbb{E}[X]^2 gives the formula.
   • 2. Here p \to 0 and \mathbb{E}[X] = e^{t_n + o(1)} \to \infty, so \mathrm{Var}(X) / \mathbb{E}[X]^2 \to 0, and Chebyshev (Proposition 0.3) gives \mathbb{P}(X = 0) \to 0.
   • 3. \mathbb{E}[X] \approx e^{-t_n} \to 0 and Markov concludes. A disconnected graph may have no isolated vertex: one must still exclude components of every size from 2 to n/2, by the spanning-tree first moment of Theorem 1.4.

4. Question (4 points). Orders of magnitude for n = 10^6. (a) Write \mathbb{E}[k_{t+1} \mid k_t] for push on K_n and evaluate the growth ratio k_{t+1}/k_t when k_t = o(n) and when k_t = n/2. (b) Give the leading terms of the number of rounds of push and of push-pull (Theorem 4.2). (c) Give the leading terms of the maximum load with one and with two choices (Theorem 5.1), and say what the second choice buys.

   Expected:

   • 1. An ignorant node stays ignorant if none of the k_t informed nodes calls it, so \mathbb{E}[k_{t+1} \mid k_t] = k_t + (n - k_t)\Big( 1 - \big(1 - \tfrac{1}{n-1}\big)^{k_t} \Big). The ratio tends to 2 when k_t = o(n), and is about 2 - e^{-1/2} \approx 1.39 at n/2.
   • 2. Push: \log_2 n + \ln n \approx 19.9 + 13.8 \approx 34 rounds. Push-pull: \log_3 n \approx 12.6 rounds, plus O(\log\log n), a few rounds.
   • 3. One choice: \ln n / \ln\ln n \approx 13.8 / 2.63 \approx 5.3. Two choices: \ln\ln n / \ln 2 \approx 3.8, plus O(1). The gain is modest at 10^6 but exponential in the asymptotics, for one extra probe per ball.

Total: 5 + 6 + 5 + 4 = 20 points.

Grading rubric (proposal)

References

• M. E. J. Newman, Networks, 2nd edition, Oxford University Press, 2018 — the module’s textbook: chapters on random graphs, epidemics, communities.
• R. van der Hofstad, Random Graphs and Complex Networks, Vol. 1, Cambridge University Press, 2017 — free on arXiv: the rigorous reference for ch. 1 (thresholds, Gumbel, percolation).
• B. Bollobás, Random Graphs, 2nd edition, Cambridge University Press, 2001 — the classic; the 1959-60 results of Erdős and Rényi put in shape.
• P. Erdős, A. Rényi, On Random Graphs I, Publicationes Mathematicae Debrecen 6, 1959 — the founding paper (connectivity threshold).
• D. Easley, J. Kleinberg, Networks, Crowds, and Markets, Cambridge University Press, 2010 — free online: the economics/society reading (small-world, network effects).
• M. O. Jackson, Social and Economic Networks, Princeton University Press, 2008 — the social sciences viewpoint.
• M. Molloy, B. Reed, A Critical Point for Random Graphs with a Given Degree Sequence, Random Structures & Algorithms 6, 1995 — the configuration model (ch. 2).
• D. J. Watts, S. H. Strogatz, Collective Dynamics of ‘Small-World’ Networks, Nature 393, 1998 — the small world (ch. 2).
• A.-L. Barabási, R. Albert, Emergence of Scaling in Random Networks, Science 286, 1999 — preferential attachment (Theorem 2.5).
• A. Clauset, C. R. Shalizi, M. E. J. Newman, Power-law Distributions in Empirical Data, SIAM Review 51, 2009 — the estimation protocol for power laws.
• R. Pastor-Satorras, A. Vespignani, Epidemic Spreading in Scale-Free Networks, Physical Review Letters 86, 2001 — the vanishing threshold (Theorem 3.5).
• R. Pastor-Satorras, C. Castellano, P. Van Mieghem, A. Vespignani, Epidemic Processes in Complex Networks, Reviews of Modern Physics 87, 2015 — the big survey of epidemics on graphs.
• A. Ganesh, L. Massoulié, D. Towsley, The Effect of Network Topology on the Spread of Epidemics, IEEE INFOCOM 2005 — the spectral threshold (Theorem 3.3; team, ch. 9.1).
• R. Karp, C. Schindelhauer, S. Shenker, B. Vöcking, Randomized Rumor Spreading, FOCS 2000 — push-pull (Theorem 4.2).
• B. Pittel, On Spreading a Rumor, SIAM Journal on Applied Mathematics 47, 1987 — the \log_2 n + \ln n of push (Theorem 4.2).
• U. Feige, D. Peleg, P. Raghavan, E. Upfal, Randomized Broadcast in Networks, Random Structures & Algorithms 1, 1990 — push on general graphs (ch. 4).
• D. Kempe, J. Kleinberg, É. Tardos, Maximizing the Spread of Influence through a Social Network, KDD 2003 — influence maximization (Theorem 4.4).
• G. L. Nemhauser, L. A. Wolsey, M. L. Fisher, An Analysis of Approximations for Maximizing Submodular Set Functions—I, Mathematical Programming 14, 1978 — the 1 - 1/e bound.
• M. E. J. Newman, Spread of Epidemic Disease on Networks, Physical Review E 66, 016128, 2002 — SIR as bond percolation on the configuration model (Theorems 3.4–3.5).
• E. Kenah, J. M. Robins, Second Look at the Spread of Epidemics on Networks, Physical Review E 76, 036113, 2007 — random infectious periods and directed percolation (Theorem 3.4).
• M.-A. Rizoiu, Y. Lee, S. Mishra, L. Xie, A Tutorial on Hawkes Processes for Events in Social Media, 2017 — Hawkes models of cascades (ch. 3 note).
• P. W. Holland, K. B. Laskey, S. Leinhardt, Stochastic Blockmodels: First Steps, Social Networks 5, 1983 — the birth of the SBM.
• B. Karrer, M. E. J. Newman, Stochastic Blockmodels and Community Structure in Networks, Physical Review E 83, 2011 — the DC-SBM.
• A. Decelle, F. Krzakala, C. Moore, L. Zdeborová, Inference and Phase Transitions in the Detection of Modules in Sparse Networks, Physical Review Letters 107, 2011 — the threshold conjecture (ch. 6).
• L. Massoulié, Community Detection Thresholds and the Weak Ramanujan Property, STOC 2014 — the feasibility threshold (Theorem 6.3; team, ch. 9.2).
• C. Bordenave, M. Lelarge, L. Massoulié, Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs, FOCS 2015; Annals of Probability 46(1), 2018 — the non-backtracking spectrum (Theorem 6.5; team, ch. 9.3).
• E. Abbe, Community Detection and Stochastic Block Models: Recent Developments, JMLR 18(177), 2018 — the big SBM survey.
• M. Girvan, M. E. J. Newman, Community Structure in Social and Biological Networks, PNAS 99, 2002 — the edge-betweenness divisive algorithm; modularity itself comes two years later (next entry).
• M. E. J. Newman, M. Girvan, Finding and Evaluating Community Structure in Networks, Physical Review E 69, 026113, 2004 — modularity (Definition 7.1).
• V. D. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefebvre, Fast Unfolding of Communities in Large Networks, Journal of Statistical Mechanics, 2008 — Louvain.
• S. Fortunato, M. Barthélemy, Resolution Limit in Community Detection, PNAS 104, 2007 — the resolution limit.
• T. P. Peixoto, Parsimonious Module Inference in Large Networks, Physical Review Letters 110, 148701, 2013; Hierarchical Block Structures and High-Resolution Model Selection in Large Networks, Physical Review X 4, 011047, 2014 — Bayesian and nested SBM inference (ch. 7).
• J. Leskovec, K. J. Lang, A. Dasgupta, M. W. Mahoney, Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters, Internet Mathematics 6, 2009.
• Y. Azar, A. Z. Broder, A. R. Karlin, E. Upfal, Balanced Allocations, SIAM Journal on Computing 29(1), 1999 — power of two choices (Theorem 5.1).
• M. Mitzenmacher, A. Richa, R. Sitaraman, The Power of Two Random Choices: A Survey of Techniques and Results, 2001 — the synthesis.
• M. Mitzenmacher, E. Upfal, Probability and Computing, 2nd edition, Cambridge University Press, 2017 — the coupon collector (ch. 2), Chernoff bounds (ch. 4), balls into bins and random graphs (ch. 5).
• F. Kelly, Charging and Rate Control for Elastic Traffic, European Transactions on Telecommunications 8(1), 1997 — proportional fairness (5.3).
• F. P. Kelly, A. K. Maulloo, D. K. H. Tan, Rate Control for Communication Networks: Shadow Prices, Proportional Fairness and Stability, Journal of the Operational Research Society 49(3), 1998 — decentralized convergence to proportional fairness (5.3).
• L. Massoulié, J. Roberts, Bandwidth Sharing: Objectives and Algorithms, INFOCOM 1999; IEEE/ACM Transactions on Networking 10(3), 2002 — minimum-potential-delay fairness and the realization of \alpha-fair sharing (5.3; team, ch. 9.4).
• S. Ioannidis, L. Massoulié, A. Chaintreau, Distributed Caching over Heterogeneous Mobile Networks, SIGMETRICS 2010; Queueing Systems 72, 2012 — decentralized caching (team, ch. 9.4).
• G. Hall, L. Massoulié, Partial Recovery in the Graph Alignment Problem, Operations Research 71(1), 2023 — graph alignment (team, ch. 9.5).
• M. Even, A. Koloskova, L. Massoulié, Asynchronous SGD on Graphs: A Unified Framework for Asynchronous Decentralized and Federated Optimization, AISTATS 2024 — distributed learning (team, ch. 9.5).
• R. Cosson, L. Massoulié, Collective Tree Exploration via Potential Function Method, ITCS 2024 — collective exploration (team, ch. 9.5).
• Tools: networkx (the lab simulations); graph-tool (Bayesian SBM); EoN (epidemics).