Network and Graph Analytics

Network & Graph Analytics

Overview

Network (graph) analytics models data as nodes (vertices) connected by edges (links) and measures the resulting structure to answer questions that row/column tables cannot: who is influential, what clusters exist, what is the shortest path, what links are likely to form. It is the analytics counterpart to graph theory — the goal is insight from relationships, not just storing them.

Use a graph framing when the connections carry the signal: social networks, fraud rings, supply chains, citation/co-authorship, recommendation, knowledge graphs, dependency graphs, transaction flows. If the question is answerable with a GROUP BY, you probably do not need a graph.

This skill is the network/graph node of the data-analytics curriculum (da-1 onward).

Core Concepts

1. Graph representations

• Directed vs undirected: edges with vs without a direction (following vs friendship). Weighted vs unweighted: edges carry a cost/strength.
• Adjacency matrix: V×V matrix, O(V²) space, O(1) edge lookup — good for dense graphs and linear-algebra ops (PageRank, spectral methods).
• Adjacency list: per-node neighbor lists, O(V+E) space — the default for sparse real-world graphs; faster traversal.
• Bipartite graph: two disjoint node sets with edges only across sets (users↔products, authors↔papers).
• Ego network: the subgraph of one focal node (“ego”), its direct neighbors (“alters”), and edges among them — the unit of local social-structure analysis.
• Multigraph / multi-relational: parallel edges or typed edges (knowledge graphs).

2. Connectivity & paths

• Connected components: maximal sets of mutually reachable nodes. In directed graphs distinguish weakly (ignore direction) vs strongly connected components.
• Shortest paths: BFS for unweighted; Dijkstra for non-negative weights (O(E log V) with a heap on an adjacency list); Bellman-Ford when negative-weight edges exist (Dijkstra fails on negatives). All-pairs via repeated Dijkstra or Floyd-Warshall.
• Diameter / eccentricity / average path length: global reachability measures (expensive on large graphs — sample).

3. Centrality (who matters)

• Degree centrality: number of edges (in/out for directed) — local popularity, cheap.
• Betweenness centrality: fraction of shortest paths passing through a node — bridges/brokers/bottlenecks. Expensive (Brandes ≈ O(VE)); approximate via sampling on big graphs.
• Closeness centrality: inverse of mean shortest-path distance to all others.
• Eigenvector centrality: recursive importance — you matter if connected to nodes that matter. Can fail to converge on some directed graphs.
• PageRank: eigenvector centrality with a damping factor (~0.85) modeling a teleporting random surfer. Handles directed graphs reliably; the production default for influence ranking.

4. Community detection (what clusters)

• Modularity (Q): edges-inside-communities vs expected at random, range roughly −1..1; higher = stronger structure.
• Louvain (Blondel et al., 2008): fast greedy modularity maximization. Ubiquitous but suffers the resolution limit (merges small real communities) and can produce badly/disconnected communities.
• Leiden (Traag, Van Eck & Waltman, 2019): adds a refinement phase; guarantees communities are connected and well-separated, faster and higher-quality — the recommended default.
• Label propagation: near-linear, no objective — fast but unstable/non-deterministic.
• CPM (constant Potts model) and resolution parameters address the resolution limit.

5. Link prediction (what edges will form)

Local proximity scores for non-adjacent pairs x,y (Γ = neighbor set):

• Common Neighbors: |Γ(x) ∩ Γ(y)|.
• Jaccard Coefficient: |Γ(x) ∩ Γ(y)| / |Γ(x) ∪ Γ(y)|.
• Adamic-Adar: sum of 1/log(degree) over shared neighbors — rare shared neighbors count more.
• Preferential Attachment: deg(x)·deg(y) — “rich get richer.” Embedding/GNN methods are the supervised upgrade.

6. Network motifs & bipartite projection

• Motifs: statistically over-represented subgraphs (feed-forward loops, triangles). Compare against a degree-preserving null model.
• Bipartite (one-mode) projection: collapse a two-set graph onto one set (two authors linked if they co-wrote a paper). Loses information — weight edges by shared-neighbor count / Newman weighting to avoid hub-dominated dense graphs.

7. Graph embeddings (nodes → vectors)

• DeepWalk (Perozzi et al., 2014): uniform random walks → skip-gram (Word2Vec) node vectors.
• node2vec (Grover & Leskovec, 2016): biased walks with return parameter p and in-out parameter q interpolating BFS-like (structural roles) vs DFS-like (community) exploration. Outperforms DeepWalk/LINE on classification and link prediction. Vectors feed downstream ML.

8. GNN basics for analytics

• GCN (Kipf & Welling, 2017): neighborhood aggregation via normalized adjacency; transductive — needs the whole graph, retrain on new nodes.
• GraphSAGE (Hamilton, Ying & Leskovec, NeurIPS 2017): learns aggregator functions over a sampled neighborhood → inductive, generalizes to unseen nodes, scales to large/dynamic graphs. Use GNNs when you have rich node features + a supervised target; use node2vec when you only have structure.

Tools / Frameworks

Rule of thumb: prototype in NetworkX, move to igraph/graph-tool when slow, cuGraph when huge, Neo4j GDS when the graph already lives in Neo4j.

Methodology

1. Frame the question as a graph — define node, edge, direction, weight. Wrong definition dooms everything downstream.
2. Build & sanity-check — node/edge counts, degree distribution (expect heavy tails), components, density. Restrict to the giant component when appropriate.
3. Match analytic to question: influence → centrality (PageRank default); clusters → community detection (Leiden default); reachability → components/shortest paths; missing links → link prediction or embeddings.
4. Scale-match the tool before running O(VE) measures.
5. Validate — compare against a null model; check modularity and stability across seeds; for link prediction use a temporal train/test split and AUC/precision@k.
6. Communicate — layouts for small graphs only (<~1k nodes); for large graphs report metrics, ranked tables, community summaries — not hairball plots.

Practical Patterns

• PageRank as the default influence score on directed graphs: degree is cheap but naive; betweenness is informative but slow; PageRank is the reliable middle ground.
• Leiden over Louvain unless you have a hard dependency on Louvain output.
• node2vec for structure-only data, GraphSAGE for feature-rich + supervised targets needing inductive generalization.
• Work on the giant connected component — isolates distort global metrics.
• Approximate expensive centralities (sampled betweenness/closeness) over ~10⁵ nodes.
• Weight bipartite projections rather than using raw co-occurrence.
• Tune node2vec p/q deliberately: low q → community-flavored; high q (low p) → structural-role embeddings.

Anti-Patterns

• Treating any join table as a graph. If a GROUP BY answers it, a graph adds cost, not insight.
• Trusting Louvain communities as connected. Up to ~25% badly connected in the original study. Use Leiden or verify.
• Ignoring the modularity resolution limit — don’t over-interpret community count without a resolution sweep.
• Exact betweenness on million-node graphs in NetworkX — won’t finish; sample or use graph-tool/cuGraph.
• Adjacency matrix for sparse graphs — O(V²) memory blows up; use adjacency lists.
• Dijkstra with negative weights — silently wrong; use Bellman-Ford.
• Plotting a 100k-node hairball — summarize with metrics and community-level rollups.
• Comparing motif/community counts without a null model.
• Using transductive GCN on a growing graph — use GraphSAGE.

Troubleshooting

• Eigenvector centrality won’t converge → directed graph with sinks; use PageRank or eigenvector_centrality_numpy.
• Everything is one giant community → resolution limit; lower the resolution parameter, switch to Leiden/CPM.
• Community results change every run → expected for Louvain/label propagation; fix the seed, take consensus, or use Leiden.
• Centrality job never finishes → O(VE)-class; sample, restrict to giant component, or move to C/GPU backend.
• Link prediction AUC ≈ 0.5 → no temporal split (leakage) or too sparse; try embedding features.
• node2vec embeddings look random → walks too short/few, or p/q untuned.
• Out of memory building the graph → dense matrix; switch to edge list / sparse (CSR) or igraph/cuGraph.

References

• NetworkX docs — centrality, components, shortest paths, link prediction. https://networkx.org/documentation/stable/ (2024)
• Brandes. “A Faster Algorithm for Betweenness Centrality.” J. Math. Sociology (2001).
• Page, Brin et al. “The PageRank Citation Ranking.” Stanford (1999).
• Blondel et al. “Fast unfolding of communities in large networks” (Louvain). (2008). https://arxiv.org/abs/0803.0476
• Fortunato & Barthélemy. “Resolution limit in community detection.” PNAS (2007). https://arxiv.org/abs/physics/0607100
• Traag, Van Eck & Waltman. “From Louvain to Leiden.” Scientific Reports (2019). https://arxiv.org/abs/1810.08473
• Liben-Nowell & Kleinberg. “The Link Prediction Problem for Social Networks.” (2007). https://www.cs.cornell.edu/home/kleinber/link-pred.pdf
• Arthur. “Modularity and Projection of Bipartite Networks” (2019). https://arxiv.org/pdf/1908.02520
• Perozzi, Al-Rfou & Skiena. “DeepWalk.” KDD (2014).
• Grover & Leskovec. “node2vec: Scalable Feature Learning for Networks.” KDD (2016). https://cs.stanford.edu/~jure/pubs/node2vec-kdd16.pdf
• Kipf & Welling. “Semi-Supervised Classification with GCNs.” ICLR (2017).
• Hamilton, Ying & Leskovec. “Inductive Representation Learning on Large Graphs” (GraphSAGE). NeurIPS (2017). https://cs.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
• Neo4j Graph Data Science docs. https://neo4j.com/docs/graph-data-science/current/ (2024)
• igraph documentation. https://igraph.org/ (2024)
• graph-tool performance. https://graph-tool.skewed.de/performance.html (2024)
• RAPIDS cuGraph. https://docs.rapids.ai/api/cugraph/stable/ (2024)
• Benchmark of popular graph/network packages. https://www.timlrx.com/blog/benchmark-of-popular-graph-network-packages-v2/ (2020)