Network and Graph Analytics

Parent: data analysis · researched 2026-05-30T22:23:24.945Z· 16 sources · 9 concepts · skill da-27-network-graph-analytics

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 cl

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. [source]
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. [source]
This skill is the network/graph node of the data-analytics curriculum (da-1 onward). [source]

1. Graph representations

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

2. Connectivity & paths

Connected components: maximal sets of mutually reachable nodes. In directed graphs distinguish weakly (ignore direction) vs strongly connected components. [source]
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. [source]
Diameter / eccentricity / average path length: global reachability measures (expensive on large graphs - sample). [source]

3. Centrality (who matters)

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

4. Community detection (what clusters)

Modularity (Q): edges-inside-communities vs expected at random, range roughly −1..1; higher = stronger structure. [source]
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. [source]
Leiden (Traag, Van Eck & Waltman, 2019): adds a refinement phase; guarantees communities are connected and well-separated, faster and higher-quality - the recommended default. [source]
Label propagation: near-linear, no objective - fast but unstable/non-deterministic. [source]
CPM (constant Potts model) and resolution parameters address the resolution limit. [source]

5. Link prediction (what edges will form)

Local proximity scores for non-adjacent pairs x,y (Γ = neighbor set): [source]
Common Neighbors: |Γ(x) ∩ Γ(y)|. [source]
Jaccard Coefficient: |Γ(x) ∩ Γ(y)| / |Γ(x) ∪ Γ(y)|. [source]
Adamic-Adar: sum of 1/log(degree) over shared neighbors - rare shared neighbors count more. [source]
Preferential Attachment: deg(x)·deg(y) - "rich get richer." [source]
Embedding/GNN methods are the supervised upgrade. [source]

6. Network motifs & bipartite projection

Motifs: statistically over-represented subgraphs (feed-forward loops, triangles). Compare against a degree-preserving null model. [source]
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. [source]

7. Graph embeddings (nodes → vectors)

DeepWalk (Perozzi et al., 2014): uniform random walks → skip-gram (Word2Vec) node vectors. [source]
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. [source]

8. GNN basics for analytics

GCN (Kipf & Welling, 2017): neighborhood aggregation via normalized adjacency; transductive - needs the whole graph, retrain on new nodes. [source]
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. [source]

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. [source]

Methodology

Frame the question as a graph - define node, edge, direction, weight. Wrong definition dooms everything downstream. [source]
Build & sanity-check - node/edge counts, degree distribution (expect heavy tails), components, density. Restrict to the giant component when appropriate. [source]
Match analytic to question: influence → centrality (PageRank default); clusters → community detection (Leiden default); reachability → components/shortest paths; missing links → link prediction or embeddings. [source]
Scale-match the tool before running O(VE) measures. [source]
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. [source]
Communicate - layouts for small graphs only (<~1k nodes); for large graphs report metrics, ranked tables, community summaries - not hairball plots. [source]

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. [source]
Leiden over Louvain unless you have a hard dependency on Louvain output. [source]
node2vec for structure-only data, GraphSAGE for feature-rich + supervised targets needing inductive generalization. [source]
Work on the giant connected component - isolates distort global metrics. [source]
Approximate expensive centralities (sampled betweenness/closeness) over ~10⁵ nodes. [source]
Weight bipartite projections rather than using raw co-occurrence. [source]
Tune node2vec p/q deliberately: low q → community-flavored; high q (low p) → structural-role embeddings. [source]

Anti-Patterns

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

Troubleshooting

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

References

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

Children

Graph representations (adjacency matrix/list, directed/weighted, bipartite, ego networks) (frontier)
Connectivity and shortest paths (connected components, BFS, Dijkstra, Bellman-Ford) (frontier)
Centrality measures (degree, betweenness, closeness, eigenvector, PageRank) (frontier)
Community detection (Louvain, Leiden, label propagation, modularity, resolution limit) (frontier)
Link prediction (common neighbors, Jaccard, Adamic-Adar, preferential attachment) (frontier)
Network motifs and bipartite projection (frontier)
Graph embeddings (node2vec, DeepWalk) (frontier)
Graph neural networks for analytics (GCN, GraphSAGE) (frontier)
Graph analytics tooling (NetworkX, igraph, graph-tool, cuGraph, Neo4j GDS) (frontier)

Frontier under this node: Centrality measures (degree, betweenness, closeness, eigenvector, PageRank), Community detection (Louvain, Leiden, label propagation, modularity, resolution limit), Connectivity and shortest paths (connected components, BFS, Dijkstra, Bellman-Ford), Graph analytics tooling (NetworkX, igraph, graph-tool, cuGraph, Neo4j GDS), Graph embeddings (node2vec, DeepWalk), Graph neural networks for analytics (GCN, GraphSAGE), Graph representations (adjacency matrix/list, directed/weighted, bipartite, ego networks), Link prediction (common neighbors, Jaccard, Adamic-Adar, preferential attachment), Network motifs and bipartite projection

← the whole tree · 3D view· how to read this page