11_social_network

Example 11 — Social network analytics

What it demonstrates

An end-to-end social-network workload over a labelled property graph (LPG): four analytics run over one seeded social graph — PageRank influence ranking (search/centrality.PageRank), Leiden community detection (search/community.Leiden), a manual friend-of-friend recommendation walk over the live adjacency list, and a structural-analytics pass over the search package: k-core decomposition (search.KCore), the global triangle count and clustering coefficient (search.CountTriangles), the diameter (search.Diameter), and the reachable set from the seed user (search.TransitiveClosure). The graph is frozen into an immutable CSR snapshot for the centrality, community, and structural algorithms, while the recommendation walk reads the mutable adjacency list directly.

Domain / scenario

A friendship network generated by per-community Barabási–Albert (BA) blocks joined by a sparse bridge layer — the model the project's graph-theory-expert recommended so that one graph serves all three analytics meaningfully:

• Heavy-tailed degree within each community (BA preferential attachment, exponent γ = 3) gives PageRank a small, clearly separated set of influencers rather than all-equal scores.
• Assortative community structure (separate BA blocks + few inter-community bridges) gives Leiden real, well-separated communities with a healthy modularity.
• Triangle-rich neighbourhoods give the friend-of-friend walk a non-trivial, intra-community recommendation set.

Each User node carries an id, a realistic name, and its planted community label. Friendships are undirected, unweighted FRIEND edges. The fixed friend-of-friend seed user is node u0000000 (the first-born hub of community 0); the bridge layer is laid down so neither it nor its direct friends is a bridge endpoint, which makes "every recommendation is in the seed user's community" a theorem of the construction, not a coincidence.

Fixing -seed fixes the generated graph — and therefore every deterministic fact — exactly.

How to run

go run ./examples/11_social_network                                  # small deterministic default
go run ./examples/11_social_network -users 1000000 -communities 50 -m 4 -seed 7   # observable-scale run

Scale and flags

validate() enforces the graph-theory-expert's parameter regime: K ≥ 3 (so the modularity ceiling 1 − 1/K can exceed 0.5); each BA block connected by construction (m ≥ 1, smallest block ≥ m+1); a spanning bridge set so the whole graph is connected (B ≥ K−1); and a bridge cap (B ≤ 5 % of intra edges) so communities stay distinct and modularity lands in roughly [0.4, 0.7].

Expected output

Deterministic fact lines at the default config (reproducible for a fixed -seed, across machines):

config.users=256
config.communities=4
config.m=2
config.bridges=8
config.top_k=4
config.seed=1
nodes.users=256
edges.friend=504
influence.rank.1=u0000193
influence.rank.2=u0000001
influence.rank.3=u0000065
influence.rank.4=u0000005
influence.communities_spanned=3
communities.found=4
communities.modularity=0.72
fof.seed_user=u0000000
fof.candidates=44
fof.all_same_community=true
fof.top=u0000006
fof.top_shared=2
core.degeneracy=3
core.size=69
triangles.total=92
triangles.triples=3321
triangles.clustering=0.08
diameter.lo=12
diameter.hi=12
diameter.exact=true
reach.from_seed=256
reach.fully_connected=true

Interleaved with the facts are volatile telemetry lines, prefixed with # , that vary per run and per machine and are never pinned by the test:

# build.elapsed=830µs
# influence.pagerank.elapsed=186µs
# influence.pagerank.iterations=34
# communities.leiden.elapsed=332µs
# communities.modularity_exact=0.724035
# fof.walk.elapsed=32µs
# mem.heap_alloc=488.67 KiB

The exact PageRank float scores and the modularity to six decimals are emitted as telemetry, not facts: they are stable for a fixed seed on one machine but may drift in the last digits across architectures, so the test pins the influencer identities, the community-count band, and a modularity lower bound instead.

Evidence it collects

From the centrality/community row of the evidence taxonomy:

• Per-stage wall-clock — build.elapsed, influence.pagerank.elapsed, communities.leiden.elapsed, fof.walk.elapsed, and the structural analytics (core.kcore.elapsed, triangles.count.elapsed, diameter.elapsed, reach.tc.elapsed).
• Convergence — influence.pagerank.iterations.
• Transient allocations — core.kcore.allocs, triangles.count.allocs, diameter.allocs, reach.tc.allocs (mallocs delta per analysis; note the TransitiveClosure bit-matrix is O(V²) and dominates on dense graphs).
• Live heap — mem.heap_alloc and mem.heap_growth (after a forced GC, so they reflect reachable bytes).
• Result separation — the influencer scores (influence.rank.N.score) show how cleanly the BA hubs separate from the tail.
• Structure — core.degeneracy/core.size (the dense k-core), triangles.total/triangles.clustering (transitivity), diameter.exact (the small-world diameter), and reach.from_seed (reachable-set size) characterise the graph's shape.

When scaling up, watch how PageRank's iteration count and wall-clock grow with -users, how the recovered community count tracks -communities, how the TransitiveClosure allocation grows with V², and how mem.heap_alloc grows with the edge count (≈ users × m).

Key APIs

• graph/lpg.New / Graph.AddNode / Graph.SetNodeLabel / Graph.SetNodeProperty — build the labelled property graph (User nodes with id, name, community).
• graph/lpg.Graph.AddEdge — add the undirected, unweighted FRIEND edges (mirrored internally).
• graph/adjlist.AdjList.Compact — right-size the adjacency arrays after the bulk build, before the read phase.
• graph/csr.BuildFromAdjList — freeze the live adjacency list into an immutable CSR snapshot for the analytics.
• search/centrality.PageRankCtx / DefaultPageRankOptions — rank users by influence; context-aware, NodeID-indexed result.
• search/community.LeidenCtx / DefaultLeidenOptions — detect communities; the result's Community slice maps each NodeID to a cluster id.
• graph/adjlist.AdjList.Mapper (Resolve, Lookup) / AdjList.Neighbours — translate NodeIDs back to ids and walk the live adjacency list for the friend-of-friend recommendation.
• search.KCoreCtx — k-core decomposition; the graph degeneracy and the size of the densest core.
• search.CountTrianglesCtx — the global triangle total, from which the clustering coefficient (transitivity) is derived.
• search.DiameterCtx — the exact diameter (2-sweep lower bound + iFUB upper bound) that underwrites the small-world claim.
• search.TransitiveClosureCtx — the set of users reachable from the seed, cross-checked against a BFS reach.

Further reading

• search/centrality — PageRank and other centrality measures
• search/community — Leiden and community-detection algorithms
• graph/lpg — the labelled property-graph builder used here
• Example 08 — PageRank — Price-model scale-free web, PageRank in isolation
• Example 09 — Leiden — planted-partition SBM, community detection in isolation
• Example 26 — Social-scale benchmark — the reference end state for the examples standard
• docs/examples-standard.md — the standard every example follows