04. Graph Algorithms

Structural analysis on Facebook.

Three algorithms, one dataset, and a question: what does a social graph reveal about itself? Starting from a 22,000-node Facebook friendship graph, these demos trace a path from descriptive statistics through structural decomposition to exact reliability under random edge failure. Each demo runs entirely in your browser, with no server involved.

Social Network Analytics

PageRank, triangle counting, connected components, and degree analysis on the MUSAE Facebook dataset. Upload your own edge list or use the bundled 171k-edge graph. The top-5 nodes per metric are shown alongside a sigma.js visualization. PageRank runs in a Web Worker to keep the interface responsive.

social-network-graph-analytics

MUSAE Facebook dataset, 22,470 nodes and 171,002 edges. PageRank damping 0.85, 50 iterations.

K-Core Decomposition

Iterative peeling reveals the nested shell structure of a graph. Vertices with degree below k are removed one round at a time until the remaining subgraph is a k-core. The animation shows each layer stripped away with a 200ms delay.

graph-kcore-decomposition

Paste an adjacency matrix or pick a sample graph. Set k and watch the peeling unfold.

Network Reliability Polynomial

For a graph with E edges, there are 2^E possible failure scenarios. This demo enumerates them all, computes the fraction of scenarios where the source and target remain connected weighted by the edge-survival probability p, and plots the reliability polynomial. Edit the graph interactively and the chart updates immediately.

network-reliability-polynomial

Exact exhaustive enumeration. Practical up to about 20 edges. The default 7-vertex graph from the original assignment has 10 edges, completing in under 1 ms.