Week 10 — Social Network Analytics¶
Who matters, who belongs together, and how does information spread?¶
SENG 42293 Big Data Analytics · LO3, LO4
Relationships are data too. A social network is a graph: nodes (travellers) and edges (who follows whom). Network analytics asks questions a table cannot: who is influential, which groups exist, how fast would a recommendation spread?
In this notebook: graph basics · degree and the long tail · centrality (degree, betweenness, PageRank) · community detection (Louvain) checked against known interests · PageRank by hand on Spark RDDs · information diffusion simulation.
Data: follows.csv (directed follower → followed) and traveller_profiles.csv (each traveller's main interest).
The network is synthetic, generated with four interest-based communities plus a few popular hubs, so we know the "right answer" for community detection.
In [1]:
import os, json, warnings
import numpy as np, pandas as pd
import matplotlib.pyplot as plt
warnings.filterwarnings("ignore")
os.makedirs("figures", exist_ok=True); os.makedirs("results", exist_ok=True)
ACC, ACCL, CH, GREY = "#8b7355", "#c4b5a0", "#2a2a2a", "#999999"
plt.rcParams.update({"figure.dpi": 110, "axes.spines.top": False, "axes.spines.right": False,
"axes.prop_cycle": plt.cycler(color=[ACC, "#2a2a2a", ACCL, "#b5651d", "#6b8e8e", GREY]),
"font.size": 10, "axes.titlesize": 11, "axes.titleweight": "bold"})
RES = {} # key numbers, reused in the slides and notes
def save(name):
plt.tight_layout(); plt.savefig(f"figures/{name}.png", dpi=130); plt.show()
In [2]:
import networkx as nx
E = pd.read_csv("data/follows.csv"); P = pd.read_csv("data/traveller_profiles.csv")
G = nx.from_pandas_edgelist(E, "follower", "followed", create_using=nx.DiGraph)
G.add_nodes_from(P.user_id)
interest = P.set_index("user_id").interest.to_dict(); nx.set_node_attributes(G, interest, "interest")
n, m = G.number_of_nodes(), G.number_of_edges()
print(f"nodes = {n}, edges = {m}, density = {nx.density(G):.4f}, reciprocal edges = {sum(1 for u,v in G.edges if G.has_edge(v,u))//2}")
print("interests:", P.interest.value_counts().to_dict())
RES["graph"] = {"nodes": n, "edges": m, "density": round(nx.density(G), 5)}
nodes = 600, edges = 3167, density = 0.0088, reciprocal edges = 47
interests: {'hill-country': 150, 'beach': 150, 'culture': 150, 'budget': 150}
1. Degree: who has many connections?¶
In-degree = followers, out-degree = accounts followed. Real social networks have a long tail: most people have few followers, a few have very many.
In [3]:
indeg = pd.Series(dict(G.in_degree())); outdeg = pd.Series(dict(G.out_degree()))
print(f"in-degree: mean {indeg.mean():.2f}, median {indeg.median():.0f}, max {indeg.max()} | out-degree: mean {outdeg.mean():.2f}, max {outdeg.max()}")
print("top 5 by followers:", indeg.sort_values(ascending=False).head(5).to_dict())
RES["deg"] = {"mean": round(float(indeg.mean()), 2), "median": float(indeg.median()), "max": int(indeg.max()), "top1_share_of_edges": round(float(indeg.max() / m), 4)}
fig, ax = plt.subplots(1, 2, figsize=(10, 3.6))
ax[0].hist(indeg, bins=range(0, int(indeg.max()) + 2, 2), color=ACC); ax[0].set_title("In-degree distribution (followers)"); ax[0].set_xlabel("followers"); ax[0].set_ylabel("travellers")
vc = indeg.value_counts().sort_index(); ax[1].loglog(np.maximum(vc.index.values, 1), vc.values, "o", color=CH, ms=4); ax[1].set_title("Same data, log-log axes"); ax[1].set_xlabel("followers"); save("w10_degree")
in-degree: mean 5.28, median 4, max 88 | out-degree: mean 5.28, max 9
top 5 by followers: {'T241': 88, 'T490': 87, 'T187': 85, 'T003': 83, 'T221': 82}
A heavy right tail means the mean misleads (compare mean with median). Averages hide the hubs that dominate how information moves.
2. Centrality: three meanings of "important"¶
| Measure | Question it answers |
|---|---|
| Degree | Who has the most direct connections? |
| Betweenness | Who sits on the shortest paths between others (a bridge/broker)? |
| PageRank | Who is followed by people who are themselves important? |
In [4]:
btw = pd.Series(nx.betweenness_centrality(G, k=200, seed=1)); pr = pd.Series(nx.pagerank(G, alpha=.85))
C = pd.DataFrame({"followers": indeg, "betweenness": btw, "pagerank": pr}); C["interest"] = pd.Series(interest)
print(C.sort_values("pagerank", ascending=False).head(8).round(4))
print("\nrank correlation (Spearman):"); display(C[["followers", "betweenness", "pagerank"]].corr("spearman").round(3))
top = {k: set(C[k].sort_values(ascending=False).head(20).index) for k in ["followers", "betweenness", "pagerank"]}
ov = len(top["followers"] & top["pagerank"]); print(f"top-20 overlap, followers vs PageRank: {ov}/20 | followers vs betweenness: {len(top['followers'] & top['betweenness'])}/20")
RES["central"] = {"overlap_deg_pr": ov, "overlap_deg_btw": len(top["followers"] & top["betweenness"]), "spearman_deg_pr": round(float(C.followers.corr(C.pagerank, method="spearman")), 3),
"top_pagerank": C.sort_values("pagerank", ascending=False).head(3).index.tolist()}
followers betweenness pagerank interest T517 80 0.0428 0.0273 beach T524 71 0.0230 0.0243 hill-country T168 60 0.0350 0.0237 hill-country T540 61 0.0314 0.0235 hill-country T241 88 0.0142 0.0234 beach T187 85 0.0775 0.0213 budget T428 68 0.0434 0.0200 hill-country T003 83 0.0847 0.0192 budget rank correlation (Spearman):
| followers | betweenness | pagerank | |
|---|---|---|---|
| followers | 1.000 | 0.595 | 0.764 |
| betweenness | 0.595 | 1.000 | 0.655 |
| pagerank | 0.764 | 0.655 | 1.000 |
top-20 overlap, followers vs PageRank: 14/20 | followers vs betweenness: 12/20
Measures overlap but are not identical. Pick the one that matches the business question: reach (degree), brokerage (betweenness), or endorsement (PageRank).
3. Community detection with Louvain¶
Louvain groups nodes to maximise modularity: more edges inside groups than expected by chance. It works on an undirected graph. We know each traveller's true interest, so we can check the algorithm.
In [5]:
U = G.to_undirected()
comms = nx.community.louvain_communities(U, seed=7); comms = sorted(comms, key=len, reverse=True)
Q = nx.community.modularity(U, comms)
lab = {u: i for i, c in enumerate(comms) for u in c}
ct = pd.crosstab(pd.Series(lab, name="community"), pd.Series(interest, name="interest")); display(ct)
purity = ct.max(axis=1).sum() / ct.values.sum()
from sklearn.metrics import adjusted_rand_score
ari = adjusted_rand_score([interest[u] for u in U.nodes], [lab[u] for u in U.nodes])
print(f"communities found = {len(comms)}, modularity = {Q:.3f}, purity vs interest = {purity:.3f}, adjusted Rand = {ari:.3f}")
RES["louvain"] = {"k": len(comms), "modularity": round(float(Q), 3), "purity": round(float(purity), 3), "ari": round(float(ari), 3), "sizes": [len(c) for c in comms]}
| interest | beach | budget | culture | hill-country |
|---|---|---|---|---|
| community | ||||
| 0 | 0 | 0 | 0 | 150 |
| 1 | 150 | 0 | 0 | 0 |
| 2 | 0 | 150 | 0 | 0 |
| 3 | 0 | 0 | 150 | 0 |
communities found = 4, modularity = 0.620, purity vs interest = 1.000, adjusted Rand = 1.000
In [6]:
pos = nx.spring_layout(U, seed=3, k=.35, iterations=80)
cmap = {i: c for i, c in enumerate(["#8b7355", "#2a2a2a", "#6b8e8e", "#b5651d", "#c4b5a0", "#999999"])}
fig, ax = plt.subplots(1, 2, figsize=(11, 5))
nx.draw_networkx_edges(U, pos, ax=ax[0], alpha=.08, width=.4); nx.draw_networkx_nodes(U, pos, ax=ax[0], node_size=10 + 4 * indeg.reindex(list(U.nodes)).values, node_color=[cmap[lab[u] % 6] for u in U.nodes]); ax[0].set_title("Colour = Louvain community (size = followers)")
ic = dict(zip(sorted(set(interest.values())), cmap.values()))
nx.draw_networkx_edges(U, pos, ax=ax[1], alpha=.08, width=.4); nx.draw_networkx_nodes(U, pos, ax=ax[1], node_size=10 + 4 * indeg.reindex(list(U.nodes)).values, node_color=[ic[interest[u]] for u in U.nodes]); ax[1].set_title("Colour = true interest (ground truth)")
for a in ax: a.axis("off")
save("w10_communities")
Communities that match the interests were found without ever seeing the interest labels: structure alone revealed the groups. Real use: segment customers, target recommendations, detect fraud rings.
4. PageRank by hand: the algorithm that scales¶
PageRank is iterative: every node shares its current rank equally among the nodes it follows, then ranks are recomputed with damping d = 0.85:
PR(v) = (1 − d)/N + d · Σ PR(u)/outdeg(u) over followers u of v (plus a share of rank from dangling nodes).
This maps neatly to join → flatMap → reduceByKey on a cluster, which is how Google-scale graphs are processed (Pregel/GraphX use the same idea). First a small NumPy version, then Spark RDDs.
In [7]:
nodes = sorted(G.nodes); ix = {u: i for i, u in enumerate(nodes)}
def pagerank_np(G, d=.85, iters=50):
N = len(nodes); r = np.full(N, 1 / N)
for _ in range(iters):
new = np.full(N, (1 - d) / N); dangling = 0
for u in nodes:
out = list(G.successors(u))
if out:
for v in out: new[ix[v]] += d * r[ix[u]] / len(out)
else: dangling += r[ix[u]]
new += d * dangling / N; r = new
return pd.Series(r, index=nodes)
pr_np = pagerank_np(G)
print("max |manual - networkx| =", float((pr_np - pr.reindex(nodes)).abs().max()))
RES["pr_manual_err"] = float((pr_np - pr.reindex(nodes)).abs().max())
max |manual - networkx| = 3.951808175208654e-05
In [8]:
import sys; os.environ["PYSPARK_PYTHON"] = sys.executable
from pyspark.sql import SparkSession
spark = SparkSession.builder.master("local[4]").config("spark.ui.enabled", "false").config("spark.default.parallelism", "4").getOrCreate(); sc = spark.sparkContext; sc.setLogLevel("ERROR")
lines = sc.textFile("data/follows.csv", 4); header = lines.first()
edges = lines.filter(lambda l: l != header).map(lambda l: tuple(l.split(",")))
links = edges.groupByKey(4).mapValues(list).cache(); links.count() # node -> accounts it follows
allnodes = edges.flatMap(lambda e: e).union(sc.parallelize(nodes, 4)).distinct(4).cache()
N = allnodes.count(); ranks = allnodes.map(lambda u: (u, 1.0 / N)); d = .85
for _ in range(15):
contribs = links.join(ranks).flatMap(lambda kv: [(v, kv[1][1] / len(kv[1][0])) for v in kv[1][0]])
dangling = ranks.subtractByKey(links).values().sum() # rank held by nodes that follow nobody
summed = contribs.reduceByKey(lambda a, b: a + b, 4)
ranks = allnodes.map(lambda u: (u, 0.0)).leftOuterJoin(summed).mapValues(lambda t: (1 - d) / N + d * ((t[1] or 0.0) + dangling / N)).cache()
ranks.count() # materialise so lineage does not grow
spark_pr = pd.Series(dict(ranks.collect()))
err = float((spark_pr.reindex(nodes) - pr_np).abs().max()); print(f"nodes = {N}; max |Spark - manual NumPy| = {err:.2e}; ranks sum to {spark_pr.sum():.4f}")
print("Spark top-3:", spark_pr.sort_values(ascending=False).head(3).round(4).to_dict()); RES["pr_spark_err"] = err
spark.stop()
Picked up JAVA_TOOL_OPTIONS: -Djavax.net.ssl.trustStore=/etc/ssl/certs/java/cacerts -Djavax.net.ssl.trustStoreType=JKS -Dhttps.proxyHost=127.0.0.1 -Dhttps.proxyPort=44265 -Dhttp.nonProxyHosts=localhost|127.0.0.1|::1|127.*|0.*|::|169.254.*|api.anthropic.com|api-staging.anthropic.com|api-pr-preview.anthropic.com|mcp-proxy.anthropic.com|mcp-proxy-staging.anthropic.com|registry.npmjs.org|jsr.io|npm.jsr.io|pypi.org|files.pythonhosted.org|index.crates.io|proxy.golang.org|host.docker.internal|10.*|172.16.*|172.17.*|172.18.*|172.19.*|172.20.*|172.21.*|172.22.*|172.23.*|172.24.*|172.25.*|172.26.*|172.27.*|172.28.*|172.29.*|172.30.*|172.31.*|192.168.*|100.64.0.0/10|*.svc.cluster.local|*.svc.cluster.local -Djdk.http.auth.tunneling.disabledSchemes= -Djdk.http.auth.proxying.disabledSchemes= Picked up JAVA_TOOL_OPTIONS: -Djavax.net.ssl.trustStore=/etc/ssl/certs/java/cacerts -Djavax.net.ssl.trustStoreType=JKS -Dhttps.proxyHost=127.0.0.1 -Dhttps.proxyPort=44265 -Dhttp.nonProxyHosts=localhost|127.0.0.1|::1|127.*|0.*|::|169.254.*|api.anthropic.com|api-staging.anthropic.com|api-pr-preview.anthropic.com|mcp-proxy.anthropic.com|mcp-proxy-staging.anthropic.com|registry.npmjs.org|jsr.io|npm.jsr.io|pypi.org|files.pythonhosted.org|index.crates.io|proxy.golang.org|host.docker.internal|10.*|172.16.*|172.17.*|172.18.*|172.19.*|172.20.*|172.21.*|172.22.*|172.23.*|172.24.*|172.25.*|172.26.*|172.27.*|172.28.*|172.29.*|172.30.*|172.31.*|192.168.*|100.64.0.0/10|*.svc.cluster.local|*.svc.cluster.local -Djdk.http.auth.tunneling.disabledSchemes= -Djdk.http.auth.proxying.disabledSchemes=
26/10/13 09:21:41 WARN Utils: Your hostname, vm resolves to a loopback address: 127.0.0.1; using 192.0.2.2 instead (on interface eth0) 26/10/13 09:21:41 WARN Utils: Set SPARK_LOCAL_IP if you need to bind to another address
Setting default log level to "WARN". To adjust logging level use sc.setLogLevel(newLevel). For SparkR, use setLogLevel(newLevel).
26/10/13 09:21:42 WARN NativeCodeLoader: Unable to load native-hadoop library for your platform... using builtin-java classes where applicable
[Stage 0:> (0 + 1) / 1]
[Stage 1:> (0 + 4) / 4]
[Stage 2:> (0 + 4) / 4] [Stage 2:=============================> (2 + 2) / 4]
[Stage 3:> (0 + 4) / 8] [Stage 3:==============> (2 + 4) / 8]
[Stage 3:=============================> (4 + 4) / 8] [Stage 3:============================================> (6 + 2) / 8]
[Stage 7:=============================> (4 + 4) / 8]
[Stage 7:====================================> (5 + 3) / 8] [Stage 7:===========================================================(8 + 0) / 8]
[Stage 11:=============================> (4 + 4) / 8]
[Stage 11:===========================================> (6 + 2) / 8]
[Stage 13:=====================> (3 + 4) / 8] [Stage 13:=============================> (4 + 4) / 8]
[Stage 13:====================================> (5 + 3) / 8]
[Stage 14:===========================================> (3 + 1) / 4]
[Stage 20:==============> (1 + 3) / 4] [Stage 20:===========================================> (3 + 1) / 4]
[Stage 26:> (0 + 4) / 4]
[Stage 26:=============================> (2 + 2) / 4]
[Stage 27:==============> (2 + 6) / 8] [Stage 27:=============================> (4 + 4) / 8]
[Stage 36:> (0 + 4) / 4] [Stage 36:===========================================> (3 + 1) / 4]
[Stage 44:==============> (1 + 3) / 4]
[Stage 45:=============================> (4 + 4) / 8] [Stage 45:====================================> (5 + 3) / 8]
[Stage 46:=============================> (2 + 2) / 4]
[Stage 56:> (0 + 4) / 4]
[Stage 66:> (0 + 4) / 4]
[Stage 67:=============================> (4 + 4) / 8]
[Stage 80:=============================> (2 + 2) / 4]
[Stage 92:==============> (1 + 3) / 4]
[Stage 93:=============================> (4 + 4) / 8]
[Stage 108:==============> (1 + 3) / 4]
[Stage 122:==============> (1 + 3) / 4]
[Stage 123:============================> (4 + 4) / 8] [Stage 123:===================================> (5 + 3) / 8]
[Stage 124:==========================================> (3 + 1) / 4]
[Stage 140:> (0 + 4) / 4] [Stage 140:==========================================> (3 + 1) / 4]
[Stage 156:==============> (1 + 3) / 4]
[Stage 156:==========================================> (3 + 1) / 4]
[Stage 157:=====================> (3 + 4) / 8] [Stage 157:============================> (4 + 4) / 8]
[Stage 176:> (0 + 4) / 4]
[Stage 194:> (0 + 4) / 4]
[Stage 195:============================> (4 + 4) / 8] [Stage 195:===================================> (5 + 3) / 8]
[Stage 216:> (0 + 4) / 4]
[Stage 236:==============> (1 + 3) / 4]
[Stage 237:============================> (4 + 4) / 8]
[Stage 260:==============> (1 + 3) / 4]
[Stage 282:> (0 + 4) / 4]
[Stage 283:============================> (4 + 4) / 8] [Stage 283:==========================================> (6 + 2) / 8]
[Stage 332:> (0 + 4) / 4] [Stage 332:============================> (2 + 2) / 4]
[Stage 333:============================> (4 + 4) / 8]
[Stage 386:> (0 + 4) / 4]
[Stage 386:==============> (1 + 3) / 4]
[Stage 387:============================> (4 + 4) / 8]
[Stage 387:=================================================> (7 + 1) / 8]
[Stage 444:> (0 + 4) / 4] [Stage 444:==========================================> (3 + 1) / 4]
[Stage 445:============================> (4 + 4) / 8]
[Stage 476:> (0 + 4) / 4]
[Stage 506:==============> (1 + 3) / 4]
[Stage 507:============================> (4 + 4) / 8]
[Stage 540:==============> (1 + 3) / 4]
[Stage 572:============================> (2 + 2) / 4]
[Stage 573:============================> (4 + 4) / 8]
[Stage 573:==========================================> (6 + 2) / 8]
nodes = 600; max |Spark - manual NumPy| = 3.95e-05; ranks sum to 1.0000
Spark top-3: {'T517': 0.0273, 'T524': 0.0243, 'T168': 0.0237}
All three implementations agree. The join/flatMap/reduceByKey loop is wide (shuffles) every iteration, so iterative graph algorithms are shuffle-heavy; this is why cache() on links matters, and why dedicated engines (GraphX, GraphFrames, Pregel) exist.
5. Information diffusion: does the seed choice matter?¶
Simulate an independent cascade: a seed traveller shares a recommendation; each follower adopts with probability p; adopters share onward. Compare seeding with a random traveller, the most-followed one, and the top PageRank one (average of 300 runs, p = 0.12).
In [9]:
rng = np.random.default_rng(5)
rev = G.reverse(copy=False) # information flows to followers: edge v -> u when u follows v
def cascade(seed, p=.12):
active, frontier = {seed}, [seed]
while frontier:
nxt = []
for v in frontier:
for u in rev.successors(v):
if u not in active and rng.random() < p: active.add(u); nxt.append(u)
frontier = nxt
return len(active)
def avg(seed_fn, runs=300): return float(np.mean([cascade(seed_fn()) for _ in range(runs)]))
nodes_l = list(G.nodes); best_deg = indeg.idxmax(); best_pr = pr.idxmax()
res = {"random traveller": avg(lambda: nodes_l[rng.integers(len(nodes_l))]), "most followed": avg(lambda: best_deg), "top PageRank": avg(lambda: best_pr)}
for k, v in res.items(): print(f"{k:18s} mean reach = {v:6.1f} travellers ({v / n:.1%})")
RES["diffusion"] = {k: round(v, 1) for k, v in res.items()}
fig, ax = plt.subplots(figsize=(6, 3.4)); ax.bar(res.keys(), res.values(), color=[GREY, ACC, CH]); ax.set_ylabel("mean travellers reached"); ax.set_title("Reach of a recommendation by seed choice (p = 0.12)"); save("w10_diffusion")
random traveller mean reach = 3.1 travellers (0.5%) most followed mean reach = 22.8 travellers (3.8%) top PageRank mean reach = 20.8 travellers (3.5%)
Seeding a well-connected node reaches more people than seeding a random one, which is the logic behind influencer marketing. But reach also depends on p: below a threshold, cascades die out regardless of the seed. Try p = 0.05 and 0.25 in the exercises.
6. Limits and ethics¶
- Sampling bias: you rarely see the whole network; metrics change when edges are missing.
- Correlation, not causation: friends are similar because of influence or because similar people connect (homophily).
- Privacy: graph structure can re-identify "anonymous" users; handle with care and consent.
- Scale: all-pairs measures (betweenness) are O(n·m); use sampling (
k=200above) or approximations.
7. Exercises¶
- Run Louvain with a different
seedorresolution=0.5. How do the number of communities and purity change? - Remove the top-5 PageRank travellers and recompute the largest connected component. How fragile is the network?
- Repeat the diffusion experiment with p = 0.05 and 0.25. Where does seeding choice matter most?
- Which traveller has high betweenness but low followers? Describe what role they play.
- Why does PageRank need
cache()and adanglingcorrection in the Spark version?
In [10]:
json.dump(RES, open("results/w10.json", "w"), indent=1); print(json.dumps(RES))
{"graph": {"nodes": 600, "edges": 3167, "density": 0.00881}, "deg": {"mean": 5.28, "median": 4.0, "max": 88, "top1_share_of_edges": 0.0278}, "central": {"overlap_deg_pr": 14, "overlap_deg_btw": 12, "spearman_deg_pr": 0.764, "top_pagerank": ["T517", "T524", "T168"]}, "louvain": {"k": 4, "modularity": 0.62, "purity": 1.0, "ari": 1.0, "sizes": [150, 150, 150, 150]}, "pr_manual_err": 3.951808175208654e-05, "pr_spark_err": 3.951808175209348e-05, "diffusion": {"random traveller": 3.1, "most followed": 22.8, "top PageRank": 20.8}}