Edge Lists, Adjacency Matrices, and Sparse Storage
A graph is an abstract data model; an edge list or adjacency matrix is a storage representation. Choosing storage should follow the operations, scale, and semantics you need—not change them accidentally.
Prerequisites
Complete directed, weighted, and multigraphs. Basic matrix indexing from linear algebra is helpful.
Learning goals
- Distinguish a graph's meaning from its storage representation.
- Fix node ordering before interpreting matrix rows and columns.
- Explain how parallel edges and self-loops populate a weighted adjacency matrix.
- Compare the space costs of edge lists, dense matrices, and sparse matrices.
Three representations
An edge list stores one record per edge and naturally retains edge attributes and identifiers. A dense adjacency matrix for (n) nodes stores (n^2) entries; row (i), column (j) represents the edge from the (i)-th node to the (j)-th node under a declared order. A sparse array stores only nonzero positions plus indexing structures and is usually more appropriate when the number of edges is far below (n^2).
For this directed multigraph, converting to a weighted matrix requires parallel-edge aggregation. NetworkX's to_scipy_sparse_array sums parallel weights. It puts the self-loop weight on the diagonal once. Those are documented conventions, not universal mathematical laws.
| Representation | Strength | Cost or risk |
|---|---|---|
| edge list | event-level attributes and streaming | neighbor lookup may require an index |
| dense matrix | simple algebra and constant-position lookup | quadratic storage, even for absent edges |
| sparse matrix | algebra on sparse graphs | edge identity and rich attributes need side data |
Worked example
import csv
from pathlib import Path
import networkx as nx
fixture = Path("tests/fixtures/graph-data-science")
graph = nx.MultiDiGraph()
with (fixture / "interaction-nodes.csv").open(encoding="utf-8") as handle:
graph.add_nodes_from(row["node_id"] for row in csv.DictReader(handle))
with (fixture / "interaction-relationships.csv").open(encoding="utf-8") as handle:
for row in csv.DictReader(handle):
if row["record_status"] == "valid":
graph.add_edge(
row["source"], row["target"],
key=row["relationship_id"], weight=float(row["weight"]),
)
order = sorted(graph.nodes)
adjacency = nx.to_scipy_sparse_array(graph, nodelist=order, weight="weight", format="csr")
ada, ben, gia = (order.index(name) for name in ("ada", "ben", "gia"))
print(f"shape={adjacency.shape} nnz={adjacency.nnz}")
print(f"ada_to_ben={adjacency[ada, ben]:.1f} gia_out={adjacency[gia].sum():.1f}")
Expected output:
shape=(7, 7) nnz=9
ada_to_ben=3.0 gia_out=0.0
Ten valid event edges become nine nonzero matrix cells because the two Ada-to-Ben weights are summed. Gia remains a row and column only because nodes were declared before conversion.
Limitations
- A zero matrix entry means “not represented under this construction,” not a measured negative relationship.
- Matrix order is external metadata. Reordering nodes changes coordinates without changing the graph.
- Sparse storage improves memory only when the graph is sparse enough and the chosen operation supports sparse input.
- Aggregation loses event identity, timestamps, and interaction type unless they are stored separately.
Practice
Write the (3 \times 3) weighted adjacency matrix for two Ada-to-Ben events with weights 2 and 1 plus one Ben-to-Ada event of weight 4. Label row and column order and explain why the matrix is not symmetric.
Next steps
Next, build and inspect the same fixture by working with NetworkX.
Primary sources
Checked 2026-10-18: NetworkX, to_scipy_sparse_array; SciPy, sparse arrays; NetworkX, conversion reference.