Skip to main content

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.

RepresentationStrengthCost or risk
edge listevent-level attributes and streamingneighbor lookup may require an index
dense matrixsimple algebra and constant-position lookupquadratic storage, even for absent edges
sparse matrixalgebra on sparse graphsedge 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.