# Network and 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 Parent: [Data Analysis](https://llms-explorer.com/tree/data-analysis/) · 19 facets · 96 facts · page: https://llms-explorer.com/tree/network-and-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. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#overview) - 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](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#overview) - This skill is the network/graph node of the data-analytics curriculum (da-1 onward). — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#overview) ## 1. Graph representations - Directed vs undirected: edges with vs without a direction (following vs friendship). Weighted vs unweighted: edges carry a cost/strength. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#1-graph-representations) - Adjacency matrix: V×V matrix, O(V²) space, O(1) edge lookup - good for dense graphs and linear-algebra ops (PageRank, spectral methods). — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#1-graph-representations) - Adjacency list: per-node neighbor lists, O(V+E) space - the default for sparse real-world graphs; faster traversal. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#1-graph-representations) - Bipartite graph: two disjoint node sets with edges only across sets (users↔products, authors↔papers). — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#1-graph-representations) - 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](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#1-graph-representations) - Multigraph / multi-relational: parallel edges or typed edges (knowledge graphs). — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#1-graph-representations) ## 2. Connectivity & paths - Connected components: maximal sets of mutually reachable nodes. In directed graphs distinguish weakly (ignore direction) vs strongly connected components. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#2-connectivity-paths) - 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](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#2-connectivity-paths) - Diameter / eccentricity / average path length: global reachability measures (expensive on large graphs - sample). — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#2-connectivity-paths) ## 3. Centrality (who matters) - Degree centrality: number of edges (in/out for directed) - local popularity, cheap. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#3-centrality-who-matters) - Betweenness centrality: fraction of shortest paths passing through a node - bridges/brokers/bottlenecks. Expensive (Brandes ≈ O(VE)); approximate via sampling on big graphs. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#3-centrality-who-matters) - Closeness centrality: inverse of mean shortest-path distance to all others. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#3-centrality-who-matters) - Eigenvector centrality: recursive importance - you matter if connected to nodes that matter. Can fail to converge on some directed graphs. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#3-centrality-who-matters) - 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](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#3-centrality-who-matters) ## 4. Community detection (what clusters) - Modularity (Q): edges-inside-communities vs expected at random, range roughly −1..1; higher = stronger structure. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#4-community-detection-what-clusters) - 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](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#4-community-detection-what-clusters) - 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](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#4-community-detection-what-clusters) - Label propagation: near-linear, no objective - fast but unstable/non-deterministic. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#4-community-detection-what-clusters) - CPM (constant Potts model) and resolution parameters address the resolution limit. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#4-community-detection-what-clusters) ## 5. Link prediction (what edges will form) - Local proximity scores for non-adjacent pairs x,y (Γ = neighbor set): — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#5-link-prediction-what-edges-will-form) - Common Neighbors: |Γ(x) ∩ Γ(y)|. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#5-link-prediction-what-edges-will-form) - Jaccard Coefficient: |Γ(x) ∩ Γ(y)| / |Γ(x) ∪ Γ(y)|. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#5-link-prediction-what-edges-will-form) - Adamic-Adar: sum of 1/log(degree) over shared neighbors - rare shared neighbors count more. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#5-link-prediction-what-edges-will-form) - Preferential Attachment: deg(x)·deg(y) - "rich get richer." Embedding/GNN methods are the supervised upgrade. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#5-link-prediction-what-edges-will-form) ## 6. Network motifs & bipartite projection - Motifs: statistically over-represented subgraphs (feed-forward loops, triangles). Compare against a degree-preserving null model. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#6-network-motifs-bipartite-projection) - 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](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#6-network-motifs-bipartite-projection) ## 7. Graph embeddings (nodes → vectors) - DeepWalk (Perozzi et al., 2014): uniform random walks → skip-gram (Word2Vec) node vectors. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#7-graph-embeddings-nodes-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. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#7-graph-embeddings-nodes-vectors) ## 8. GNN basics for analytics - GCN (Kipf & Welling, 2017): neighborhood aggregation via normalized adjacency; transductive - needs the whole graph, retrain on new nodes. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#8-gnn-basics-for-analytics) - 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](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#8-gnn-basics-for-analytics) ## 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](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#tools-frameworks) ## Methodology - Frame the question as a graph - define node, edge, direction, weight. Wrong definition dooms everything downstream. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#methodology) - Build & sanity-check - node/edge counts, degree distribution (expect heavy tails), components, density. Restrict to the giant component when appropriate. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#methodology) - Match analytic to question: influence → centrality (PageRank default); clusters → community detection (Leiden default); reachability → components/shortest paths; missing links → link prediction or embeddings. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#methodology) - Scale-match the tool before running O(VE) measures. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#methodology) - 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](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#methodology) - Communicate - layouts for small graphs only (<~1k nodes); for large graphs report metrics, ranked tables, community summaries - not hairball plots. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#methodology) ## 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](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#practical-patterns) - Leiden over Louvain unless you have a hard dependency on Louvain output. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#practical-patterns) - node2vec for structure-only data, GraphSAGE for feature-rich + supervised targets needing inductive generalization. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#practical-patterns) - Work on the giant connected component - isolates distort global metrics. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#practical-patterns) - Approximate expensive centralities (sampled betweenness/closeness) over ~10⁵ nodes. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#practical-patterns) - Weight bipartite projections rather than using raw co-occurrence. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#practical-patterns) - Tune node2vec p/q deliberately: low q → community-flavored; high q (low p) → structural-role embeddings. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#practical-patterns) ## Anti-Patterns - Treating any join table as a graph. If a GROUP BY answers it, a graph adds cost, not insight. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#anti-patterns) - Trusting Louvain communities as connected. Up to ~25% badly connected in the original study. Use Leiden or verify. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#anti-patterns) - Ignoring the modularity resolution limit - don't over-interpret community count without a resolution sweep. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#anti-patterns) - Exact betweenness on million-node graphs in NetworkX - won't finish; sample or use graph-tool/cuGraph. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#anti-patterns) - Adjacency matrix for sparse graphs - O(V²) memory blows up; use adjacency lists. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#anti-patterns) - Dijkstra with negative weights - silently wrong; use Bellman-Ford. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#anti-patterns) - Plotting a 100k-node hairball - summarize with metrics and community-level rollups. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#anti-patterns) - Comparing motif/community counts without a null model. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#anti-patterns) - Using transductive GCN on a growing graph - use GraphSAGE. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#anti-patterns) ## Troubleshooting - Eigenvector centrality won't converge → directed graph with sinks; use PageRank or eigenvector_centrality_numpy. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#troubleshooting) - Everything is one giant community → resolution limit; lower the resolution parameter, switch to Leiden/CPM. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#troubleshooting) - Community results change every run → expected for Louvain/label propagation; fix the seed, take consensus, or use Leiden. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#troubleshooting) - Centrality job never finishes → O(VE)-class; sample, restrict to giant component, or move to C/GPU backend. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#troubleshooting) - Link prediction AUC ≈ 0.5 → no temporal split (leakage) or too sparse; try embedding features. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#troubleshooting) - node2vec embeddings look random → walks too short/few, or p/q untuned. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#troubleshooting) - Out of memory building the graph → dense matrix; switch to edge list / sparse (CSR) or igraph/cuGraph. — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#troubleshooting) ## References - NetworkX docs - centrality, components, shortest paths, link prediction. https://networkx.org/documentation/stable/ (2024) — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - Brandes. "A Faster Algorithm for Betweenness Centrality." J. Math. Sociology (2001). — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - Page, Brin et al. "The PageRank Citation Ranking." Stanford (1999). — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - Blondel et al. "Fast unfolding of communities in large networks" (Louvain). (2008). https://arxiv.org/abs/0803.0476 — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - Fortunato & Barthélemy. "Resolution limit in community detection." PNAS (2007). https://arxiv.org/abs/physics/0607100 — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - Traag, Van Eck & Waltman. "From Louvain to Leiden." Scientific Reports (2019). https://arxiv.org/abs/1810.08473 — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - Liben-Nowell & Kleinberg. "The Link Prediction Problem for Social Networks." (2007). https://www.cs.cornell.edu/home/kleinber/link-pred.pdf — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - Arthur. "Modularity and Projection of Bipartite Networks" (2019). https://arxiv.org/pdf/1908.02520 — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - Perozzi, Al-Rfou & Skiena. "DeepWalk." KDD (2014). — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - Grover & Leskovec. "node2vec: Scalable Feature Learning for Networks." KDD (2016). https://cs.stanford.edu/~jure/pubs/node2vec-kdd16.pdf — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - Kipf & Welling. "Semi-Supervised Classification with GCNs." ICLR (2017). — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - Hamilton, Ying & Leskovec. "Inductive Representation Learning on Large Graphs" (GraphSAGE). NeurIPS (2017). https://cs.stanford.edu/people/jure/pubs/graphsage-nips17.pdf — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - Neo4j Graph Data Science docs. https://neo4j.com/docs/graph-data-science/current/ (2024) — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - igraph documentation. https://igraph.org/ (2024) — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - graph-tool performance. https://graph-tool.skewed.de/performance.html (2024) — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - RAPIDS cuGraph. https://docs.rapids.ai/api/cugraph/stable/ (2024) — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) - Benchmark of popular graph/network packages. https://www.timlrx.com/blog/benchmark-of-popular-graph-network-packages-v2/ (2020) — [source](https://llms-explorer.com/sources/mdb-context-hub/da-27-network-graph-analytics/#references) ## Where this helps - Ranking influence or importance in a directed network, such as social media accounts, web pages, or citation graphs, where PageRank is the reliable default over cheap-but-naive degree or slow-but-informative betweenness. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* - Finding fraud rings, organizational clusters, or communities of interest in a network, using Leiden community detection instead of Louvain when connectivity guarantees matter. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* - Predicting which new edges are likely to form, such as friend or connection suggestions, or missing links in a knowledge graph, using Common Neighbors, Jaccard, or Adamic-Adar as a baseline before reaching for a GNN. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* - Deciding whether a problem is a graph problem at all: if a GROUP BY answers the question, the connections aren't carrying the signal and a graph framing adds cost without insight. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* ## Project ideas - Build a fraud-ring or anomaly detector using community detection (Leiden) plus centrality (betweenness or PageRank) to surface accounts that bridge otherwise-separate clusters. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* - Build a link-prediction pipeline that starts with Jaccard/Adamic-Adar baselines, validates with a temporal train/test split and AUC/precision@k, and only escalates to node2vec or GraphSAGE embeddings if the simple scores underperform. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* - Build a recommendation feature from a bipartite user-item graph, projecting it to a weighted one-mode graph with Newman weighting rather than raw co-occurrence, then rank candidates by shared-neighbor strength. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* - Prototype a knowledge-graph embedding pipeline with node2vec, tuning the walk parameters p and q deliberately (low q for community structure, high q/low p for structural roles) before scaling to a GraphSAGE model for inductive generalization to new nodes. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* ## Common mistakes - Reaching for a graph framing when a GROUP BY would answer the question: if the connections between rows don't carry the signal, a graph adds cost without insight. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* - Trusting Louvain's output communities as internally connected without checking: the original study found up to roughly 25% badly connected communities, and Leiden guarantees connectivity where Louvain doesn't. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* - Running exact betweenness centrality on a million-node graph in NetworkX and expecting it to finish: it's an O(VE)-class computation that needs sampling or a C/GPU backend such as graph-tool or cuGraph at that scale. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* - Using Dijkstra's algorithm on a graph with negative edge weights: it silently produces wrong answers there, and Bellman-Ford is required instead. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* ## Known issues - Eigenvector centrality can fail to converge on directed graphs with sinks; PageRank's damping factor exists specifically to handle this case reliably. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* - The modularity resolution limit means Louvain and similar algorithms can merge small real communities into larger ones without any signal that this happened, unless the resolution parameter is swept. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* - Community-detection results from Louvain or label propagation can change between runs on the same graph: this is expected non-determinism, not a bug, and needs a fixed seed or consensus clustering to stabilize. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* - A transductive GNN like GCN needs the whole graph and must be retrained to incorporate new nodes; GraphSAGE's inductive design is required for a graph that keeps growing. — [source](https://llms-explorer.com/tree/network-and-graph-analytics/) *(AI-suggested, synthesized from this pack's existing facts — not extracted from a source document.)* ## Context files - [Network and Graph Analytics](https://llms-explorer.com/downloads/sources/mdb-context-hub/da-27-network-graph-analytics.md)