Advanced14 min read

Influence and link prediction

How ideas spread through a network — independent cascade and linear threshold — and how the same graph structure predicts which missing links will form.

Networks are not static. Information, rumours, purchases and behaviours flow along their edges, and edges themselves appear and disappear as people meet and drift apart. Two classic questions follow. If you could persuade a handful of seed users, who should they be to maximise the spread? And given today's graph, which pairs are most likely to become connected tomorrow?

Both reduce to structure. Influence spreads through adjacency; missing links leave structural fingerprints.

Cascade, then prediction

In a cascade, an active node tries to activate its neighbours with some probability, and activation repeats from each newly active node. In link prediction, two nodes with many common neighbours are likely to know each other. The first simulates a process over edges; the second scores edges that are not there yet.

Seed the graph and step the cascade forward edge by edge.

Pick seed nodes, set the transmission probability, then step the independent cascade forward. Highlighted edges are the successful transmissions.

probability p0.40

seeds: A
round: 0 / 0
active: 1 / 6
future spread: 1 last-round nodes

Click a node to add or remove it as a seed. Yellow rings are seeds; the cascade recolours nodes as they activate.

A genuine independent-cascade process with seeded pseudo-random coin flips. Finding the seed set that maximises expected spread is NP-hard; Kempe–Kleinberg–Tardos greedy gives a (1 − 1/e) approximation, which is what real influence-maximisation uses.

Two diffusion models

Independent cascade (IC). Given a seed set, each newly activated node gets one independent chance to activate each currently inactive neighbour with probability $p$ . The chance is independent across edges and attempts. The process runs until no new activations.

Linear threshold (LT). Each node $v$ has a threshold $\theta_v$ , and each edge $u \to v$ a weight $w_{uv}$ with $\sum_u w_{uv} \le 1$ . Node $v$ activates when the total weight of its active neighbours reaches $\theta_v$ :

\sum_{u \text{ active}} w_{uv} \;\ge\; \theta_v .

IC is probabilistic and edge-local; LT is deterministic given thresholds and captures the "enough of my friends are doing it" effect.

Influence maximisation and submodularity

The optimisation problem is: choose $k$ seeds to maximise the expected number of activated nodes. It is NP-hard for both models, but the expected spread is a monotone submodular function of the seed set — adding a seed helps less when you already have many. That gives the greedy algorithm a $(1 - 1/e)$ approximation guarantee: repeatedly add the node with the largest marginal gain, estimating spreads by Monte-Carlo simulation. In practice this is accelerated with sketches such as Reverse Influence Sampling.

Link prediction from structure

Given a target pair $(u, v)$ that is not yet connected, score it with:

Common neighbours: $|\Gamma(u) \cap \Gamma(v)|$ .
Jaccard: $|\Gamma(u) \cap \Gamma(v)| / |\Gamma(u) \cup \Gamma(v)|$ — normalises for degree so hubs do not dominate.
Adamic–Adar: $\sum_{w \in \Gamma(u) \cap \Gamma(v)} 1 / \log |\Gamma(w)|$ , down-weighting shared neighbours that are themselves hubs.
Preferential attachment: $|\Gamma(u)|\,|\Gamma(v)|$ — purely degree-based.
Katz: a weighted count of all paths between them, decaying with length.

Predictions are usually evaluated as a ranking problem: hide a fraction of edges, score the withheld pairs, and report ROC-AUC or precision@k.

Correlation is not diffusion

Structural overlap predicts links because networks form by homophily, triadic closure and shared context — not because similarity causes connection. Likewise a simulated cascade is a model, not a measurement: estimated probabilities from real social data are confounded by exposure, recommendation and selection. Treat both as hypotheses about mechanism.

Illustrative vs real

The widget runs a genuine independent cascade with seeded coin flips on six nodes. Real influence studies estimate $p$ or thresholds from logs, simulate the spread of an item through a much larger graph, and validate with held-out diffusion traces; link-prediction papers report AUC on collaboration, co-authorship and social graphs. The algorithms and the approximation guarantee are exactly as stated; the scale is not.

Check yourself

Eduspheria wiki · Applied AI, Social network analysis

0 / 5 answered

1Nodes u and v have 3 common neighbours; u has 8 neighbours and v has 7, with the union counting 12. What is the Jaccard score?
Numeric answer
2Which property of the influence-spread function makes the greedy algorithm provably near-optimal?
Multiple choice
3In the independent cascade model, each newly active node tries once to activate each inactive neighbour, independently.
True / false
4Which link-prediction score sums 1/log(degree) over shared neighbours, penalising hubs?
Short answer
5In linear threshold with a single active neighbour of weight 0.6 and threshold 0.5, does the node activate? Enter 1 for yes, 0 for no.
Numeric answer

From the exam paper

Modeled on NITJ AI-603, End-Sem May 2025

0 / 6 answered

1An independent cascade starts from A with edge probabilities A→B = 0.4, B→C = 0.3 and C→D = 0.5. What is the expected number of activations of B at step 1?
Numeric answer
2Continuing the cascade, what is the expected number of activations of C at step 2?
Numeric answer
3What is the total expected number of activations up to two steps, including the seed A?
Numeric answer
4Link prediction scores three candidate pairs. X–Y has common neighbours 3, Jaccard 0.5 and Adamic–Adar 2.1; X–Z has 1, 0.2 and 0.7; Y–Z has 2, 0.4 and 1.3. Which pair should be recommended?
Multiple choice
5Which diffusion model gives each newly activated node one independent chance to activate each currently inactive neighbour?
Short answer
6In this example the C→D attempt would occur at step 3, so it is correctly excluded from a two-step expected count.
True / false

Where next: networks of people generalise to networks of facts — the semantic web's triples, ontologies and reasoning.

Two diffusion models #

Influence maximisation and submodularity #

Link prediction from structure #

Two diffusion models

Influence maximisation and submodularity

Link prediction from structure