Graph

Graph analytics treats data as nodes and edges. Operator applications: link analysis on captured comms, lateral-movement maps, dependency / call graphs, recommendation, fraud rings, knowledge graphs. The algorithm catalog is finite and the properties are well-understood; once the data is in the right structure, the methods compose.

Representations

Representation	Use
Edge list	The default ingestion format. (src, dst, weight, attrs) rows. Cheap to store, cheap to stream.
Adjacency list	{node: [neighbors]}. Right for sparse graphs in memory.
Adjacency matrix	n × n matrix of edge weights. Right for dense graphs and matrix-formulated algorithms.
CSR / CSC (Compressed Sparse Row / Column)	Memory-efficient sparse matrix layout. The standard for large-scale numerical graph code.
Property graph	Nodes and edges with arbitrary key-value attributes. Native to Neo4j, JanusGraph, Memgraph.
RDF triples	(subject, predicate, object). Knowledge graphs and SPARQL.

Traversal

Algorithm	Use
BFS	Shortest path by edge count; layered exploration. O(V + E).
DFS	Topological sort, cycle detection, articulation points, strongly connected components.
Dijkstra	Shortest path with non-negative weights.
A*	Heuristic-guided shortest path. Faster than Dijkstra with a good admissible heuristic.
Bellman-Ford	Shortest path with negative weights; detects negative cycles.
Floyd-Warshall	All-pairs shortest paths on small graphs. O(V^3).

Centrality

Who matters in the network.

Centrality	Meaning
Degree	Number of neighbors. Quick popularity proxy.
Closeness	Inverse of mean distance to all other nodes. Center of the network by hop distance.
Betweenness	Fraction of shortest paths passing through a node. Bridges and bottlenecks.
Eigenvector	Recursive: important nodes are connected to important nodes.
PageRank	Damped eigenvector centrality. The Google original; widely used outside web search.
Katz	PageRank’s older cousin; weighted by distance.
HITS	Hubs and authorities; bipartite-flavoured centrality.

Community detection

Algorithm	Detail
Louvain	Greedy modularity optimization. Fast, the default for medium graphs.
Leiden	Refinement of Louvain that avoids disconnected communities.
Label propagation	Each node adopts the most common label among neighbors; iterate to fixed point. Cheap, less accurate.
Girvan-Newman	Iteratively remove edges of highest betweenness; classic but expensive.
Spectral clustering	Eigenvectors of the graph Laplacian; k-cluster the projection.
Stochastic block models	Probabilistic generative model of community structure.

Link analysis

Concept	Detail
Connected components	Subgraphs reachable from each other. O(V + E).
Strongly connected components	Directed-graph equivalent. Tarjan’s or Kosaraju’s algorithm.
Triangle counting / clustering coefficient	Local density. Triangles indicate tight-knit substructure.
Motif counting	Counting small subgraphs (k-cliques, fan-outs). Used in fraud and network-biology analysis.
Bridge / articulation point	Edges / nodes whose removal disconnects the graph. Critical infrastructure.

Link prediction

Given the current graph, predict edges that should or will exist.

Score	Detail
Common neighbors	Number of shared neighbors; the simplest baseline.
Jaccard / Adamic-Adar / Resource Allocation	Weighted variants of common-neighbors.
Preferential attachment	Product of degrees. Rich-get-richer model.
Embedding-based (node2vec, DeepWalk)	Learn node vectors; predict from vector similarity.
Graph neural networks	Message-passing over the graph. State-of-the-art on most link-prediction benchmarks.

Embeddings

Compress nodes (or graphs) into vectors so downstream models can use them.

Method	Detail
node2vec / DeepWalk	Random walks plus skip-gram (word2vec maths). Embed by neighbourhood structure.
LINE	Preserves first- and second-order proximity directly.
GraphSAGE	Inductive: handles unseen nodes by aggregating neighbor features.
GCN	Graph Convolutional Network. Spectral message-passing.
GAT	Graph Attention Network. Attention-weighted neighbor aggregation.

Once the embeddings exist, every method from Search (kNN, cosine similarity, ANN indexes) applies.

Implementations

Tool	Detail
NetworkX	Python; canonical reference; slow at scale.
igraph	C-backed; faster than NetworkX; Python and R bindings.
graph-tool	C++/Python; very fast on dense graphs and inference.
cuGraph	GPU-accelerated; NVIDIA RAPIDS.
Neo4j / Memgraph / JanusGraph	Property-graph databases with built-in algorithm libraries.
PyG (PyTorch Geometric)	GNN training in PyTorch.
DGL	Deep Graph Library; alternative GNN framework.
Apache Spark GraphFrames / GraphX	Distributed graph compute.

Pitfalls

• Scale: many algorithms are super-linear in nodes / edges. PageRank, BFS, connected components scale linearly; betweenness centrality does not.

• Directionality: algorithms behave differently on directed vs undirected graphs. Many implementations default to one; check.

• Sampling biases: subgraph extracts can warp centrality and community results. Sample by random walks rather than by attribute when possible.

• Weight scales: edge-weighted algorithms (Dijkstra, weighted PageRank) are sensitive to scale; normalize or take logs first.

References

• Search for embedding-based retrieval over graph embeddings.

• Statistics for the distributional reasoning underneath null models.

• NetworkX

• Stanford CS224W: Machine Learning with Graphs

• Networks, Crowds, and Markets (Easley & Kleinberg)