Multigraph adjacency - Ciallo Wiki

1 Basic concepts of multigraph adjacency

1.1 Multigraphs and edge multiplicity

A multigraph is a graph model in which two vertices can be connected by more than one edge. The defining feature is edge multiplicity: for each ordered or unordered vertex pair (depending on whether the graph is directed), the representation must record how many parallel connections exist.

Adjacency-based descriptions are therefore richer than in simple graphs. In a simple graph, adjacency is binary—either an edge exists or it does not. In a multigraph, adjacency typically encodes counts or weights that reflect the number of parallel edges (or their aggregate weight).

1.2 Adjacency notions for vertices and edges

Adjacency can be defined at the vertex level: a vertex is adjacent to other vertices according to the edges incident to it. For multigraphs, the adjacency relation is not merely a set of neighbors; it is often a multiset in which repeated neighbors correspond to multiple edges.

In addition, adjacency can be approached from an edge-oriented viewpoint. Here, the representation is concerned with how edges connect vertex endpoints, and multiplicity emerges from repeated endpoint pairs.

1.3 Loops and how they are treated in adjacency

A loop is an edge that starts and ends at the same vertex. In adjacency matrices, loops affect entries on the diagonal. However, different conventions exist for how loop contributions should be interpreted, particularly when converting adjacency data into degrees.

Commonly:

For undirected adjacency matrices, the diagonal entry stores the number of loops at the vertex (or the total loop multiplicity/weight).
For directed adjacency matrices, diagonal entries store the number of directed loops from a vertex to itself.

When degrees are computed, loops are typically counted twice in undirected degree conventions because a loop contributes two incidences at the same vertex, even though it begins and ends there.

2 Adjacency matrix for multigraphs

2.1 Definition and entry interpretation

An adjacency matrix translates the multigraph’s edge structure into a matrix form. The key issue is interpreting what each entry means when parallel edges are present.

2.1.1 Undirected multigraph adjacency matrix

For an undirected multigraph with vertex set \(\{1,\dots,n\}\), the adjacency matrix \(A\) is usually defined so that

\(A_{ij}\) equals the number of edges between vertices \(i\) and \(j\) for \(i\neq j\),
\(A_{ii}\) equals the number of loops at vertex \(i\).

Parallel edges increase the corresponding entry values rather than merely toggling an existence flag.

2.1.1.1 Symmetry and diagonal behavior

Because the graph is undirected, the matrix is typically symmetric: \(A_{ij}=A_{ji}\). The diagonal behavior captures loops. Since loops connect a vertex to itself, their count is concentrated in \(A_{ii}\). The diagonal does not represent adjacency to a different vertex; it represents self-connection multiplicity.

2.1.2 Directed multigraph adjacency matrix

For a directed multigraph, ordered pairs matter. The adjacency matrix \(A\) is often defined so that

\(A_{ij}\) equals the number of directed edges from vertex \(i\) to vertex \(j\),
\(A_{ii}\) equals the number of directed loops at \(i\).

Parallel directed edges from \(i\) to \(j\) increase \(A_{ij}\) by their multiplicity.

2.1.2.1 In/out multiplicities in entries

The entry \(A_{ij}\) simultaneously participates in two degree-like notions:

It contributes to the out-degree of \(i\) (edges leaving \(i\)),
It contributes to the in-degree of \(j\) (edges entering \(j\)).

Diagonal entries \(A_{ii}\) represent loops that contribute to both in- and out-counts, depending on the convention used for degree definitions.

2.2 Matrix conventions and normalization options

Some sources normalize adjacency data, such as scaling entries by a factor (e.g., dividing by maximum multiplicity, or using probabilities derived from multiplicities). Others may store weights directly rather than counts. In these alternatives, the adjacency matrix entries are no longer purely integer counts but still encode the underlying connection strength or frequency.

Normalization also appears in derived matrices (like normalized Laplacians). Those are built from degree and adjacency matrices, so the initial convention for what \(A_{ij}\) represents must align with the subsequent formulas.

2.3 Relation to the incidence structure

2.3.1 Edge-indexed viewpoints

While adjacency aggregates edge information into vertex pairs, incidence representations keep track of which edges touch which endpoints. In multigraphs, an edge-indexed incidence view can distinguish distinct edges even when they share endpoints. Adjacency “forgets” identity of individual parallel edges unless weights or tensorial refinements preserve type information.

The incidence structure therefore serves as a more granular base from which adjacency can be computed by summing over edge endpoints with multiplicity.

2.3.2 From edge lists to matrix form

Given an edge list with multiplicities (explicit counts or repeated edge records), adjacency matrices are constructed by:

Initializing all entries to zero,
For each edge (or edge group), incrementing the appropriate entry(s) based on its endpoints and direction,
Handling loops by incrementing diagonal entries.

When edges are provided as a list with repetitions, the same procedure applies; multiplicity naturally accumulates from repeated items.

3 Adjacency tensor extensions (for higher structure)

3.1 When tensors are used instead of matrices

Tensors generalize matrices to represent multiway relationships. For multigraphs, tensor methods appear when adjacency must capture more than just endpoint pairs—such as multiple edge attributes that matter structurally.

A tensor adjacency might, for example, distinguish edge categories by using an extra index for edge type, while still encoding connections between vertex pairs.

3.2 Accounting for edge types or colors

If edges come in labeled classes (often described as colors or types), a tensor can store separate adjacency layers per type. In the simplest tensor extension:

each vertex pair \((i,j)\) indexes a connection,
a third index indexes the edge type,
the tensor entry stores the multiplicity of type-specific edges from \(i\) to \(j\) (or between them in an undirected setting).

This preserves information that would otherwise be collapsed by summing counts across types.

3.3 Aggregation back to matrix adjacency

Often, only aggregated behavior is needed. The tensor can be collapsed by summing over the type index, producing a conventional adjacency matrix whose entries equal total multiplicity across all edge types. Alternatively, aggregation may involve weighted sums if types carry different importances.

4 Degrees and derived quantities from adjacency

4.1 Degree in multigraphs using multiplicity

Degrees count how many edge incidences meet at a vertex, but in multigraphs multiplicities directly increase those counts. For undirected graphs, the degree of a vertex \(i\) is commonly computed by adding all adjacency entries in row \(i\), with a careful treatment of loops:

edges to distinct neighbors contribute once,
each loop contributes twice (because it provides two incidences at the same vertex).

For directed multigraphs, in-degree and out-degree separate contributions:

out-degree counts entries leaving \(i\),
in-degree counts entries entering \(i\),
loops contribute to both in- and out-degree counts.

4.2 Weighted degrees and loop contributions

If adjacency entries represent weights rather than literal edge counts, degrees become weighted degrees. The same structural principles remain:

for undirected graphs, loops typically contribute a doubled amount to the weighted degree,
for directed graphs, a loop contributes both to the in-weight and out-weight at that vertex.

This ensures compatibility with formulas for walks, spectral calculations, and conservation properties.

4.3 Neighborhood multiset interpretation

A vertex’s neighborhood in a multigraph is naturally a multiset. The multiplicity of a neighbor \(j\) inside the neighborhood of \(i\) corresponds to \(A_{ij}\) (or the appropriate directed entry). This multiset view clarifies that adjacency counts determine how many distinct edge choices lead from one vertex to another.

4.4 Computing edge counts from adjacency data

Global counts can be derived from adjacency matrices:

In undirected multigraphs without loops, summing over all off-diagonal entries and dividing by two yields the total number of edges, accounting for symmetry.
Loops require correction because diagonal entries represent self-edges but are not paired across off-diagonal symmetric positions.

For directed multigraphs, total edge count is often the sum of all matrix entries, since each directed edge contributes to exactly one ordered pair entry.

5 Walks, paths, and counting with adjacency

5.1 Walk counting via matrix powers

A standard property of adjacency matrices extends to multigraphs: the \((i,j)\) entry of \(A^k\) counts the number of length-\(k\) walks from \(i\) to \(j\), provided \(A\) encodes edge multiplicities (or corresponding weights with an appropriate interpretation).

Because multiple parallel edges multiply the number of choices at each step, walk counts scale accordingly, reflecting the combinatorial richness of multigraphs.

5.2 Paths vs walks in the multigraph setting

A walk permits revisiting vertices and edges. A path usually implies constraints such as distinct vertices (for simple path definitions). In multigraphs, the difference between paths and walks is especially important because parallel edges can create multiple walks that follow the “same” vertex sequence but use different edge instances.

Adjacency powers count walks at the edge-choice level; distinguishing paths requires additional constraints beyond adjacency matrix multiplication.

5.3 Effects of parallel edges on counting

Parallel edges increase the branching factor in traversal. Even if two vertices are connected by the same endpoint pair, multiplicity implies more than one distinct edge can be chosen at each occurrence of that connection. Thus:

walk counts rise proportionally with multiplicity,
short-walk statistics (like counts of length-2 walks) are directly influenced by products of adjacency entries.

5.4 Special cases: loops and short walks

Loops create immediate short walks:

A loop at vertex \(i\) increases the number of length-1 walks from \(i\) back to \(i\).
It also increases length-2 walks that begin or end at \(i\) through repeated self-visits.

When counting using \(A^k\), these contributions appear naturally via diagonal entries and their propagation through matrix multiplication.

6 Graph properties influenced by multigraph adjacency

6.1 Connectivity considerations

Connectivity notions extend naturally to multigraphs. The adjacency representation affects how one interprets reachability: if there is at least one edge (with any multiplicity) between relevant vertices, reachability is established. Multiplicity typically does not change whether vertices are connected, but it can alter the number of distinct connecting walks and affect probabilistic processes on the graph.

6.2 Bipartiteness and parity constraints

Bipartiteness depends primarily on whether cycles of odd length exist in the underlying graph. In multigraphs, parallel edges can create cycles of length 2 (when two distinct vertices share multiple edges), but whether such structures count as “odd cycles” depends on the precise cycle definition used. Generally:

multiplicity can introduce additional even-length cycles,
odd-length cycles are still tied to the existence of vertex sequences with odd length that respect adjacency.

Adjacency multiplicities influence how many cycles exist, even if the yes/no bipartite classification remains governed by the presence or absence of odd cycles.

6.3 Cycles and multiedge-induced cycle multiplicity

With parallel edges, a cycle template can exist in many edge-distinct ways. For example, two vertices connected by multiple parallel edges permit multiple distinct 2-cycles (in directed formulations or via appropriate undirected cycle conventions). As a result, cycle counting becomes sensitive not only to whether a cycle exists but also to how many distinct edge instances realize it.

Adjacency matrices capture these multiplicities through combinatorial multiplication in counting methods.

6.4 Spectral viewpoint (eigenvalues and multiplicity)

Spectral properties rely on the adjacency matrix and its eigenvalues. In multigraphs, increased multiplicity changes entries and therefore shifts eigenvalues and eigenvalue multiplicities. This influences spectral clustering heuristics, diffusion interpretations, and robustness measures derived from eigen-structure.

Because adjacency powers count walks, spectral methods indirectly capture counts aggregated across path lengths, connecting multiplicity to long-range behavior.

7 Algorithmic construction and verification

7.1 Building adjacency matrices from input data

Common input sources include:

explicit edge lists with possible repetition,
edge lists with multiplicity fields,
adjacency-like inputs that already store counts.

Construction typically involves summing multiplicities into the correct matrix entry based on endpoints and direction. For undirected graphs, careful handling is required to avoid double-counting when aggregating from edge lists that may already list each connection once.

7.2 Efficient storage strategies (sparse matrices)

Adjacency matrices for large, sparse multigraphs are often too large to store densely. Sparse matrix representations store only nonzero entries, which correspond to vertex pairs with nonzero edge multiplicity. In multigraph contexts, the number of nonzero entries may still be manageable even when parallel edges are present, because multiplicity increases values but does not necessarily increase the count of nonzero locations.

For tensor extensions, sparse tensor formats may be used similarly, storing only present type-specific connections.

7.3 Validating matrix properties and conventions

Verification includes:

checking symmetry for undirected adjacency matrices,
checking index conventions (row vs column meaning for directed edges),
ensuring diagonal entries correspond to loop multiplicities,
confirming that derived degree computations match the intended loop convention.

Matrix validation often requires comparing reconstructed totals (e.g., total number of edges inferred from the adjacency) against the input data.

7.4 Complexity considerations for large multigraphs

Key computational tasks include:

matrix construction complexity (typically proportional to input edges or distinct endpoint pairs),
multiplication or exponentiation (walk counting via \(A^k\) is costly for large \(k\)),
spectral computations (often iterative methods that depend on sparsity and matrix size).

Multiplicity values affect arithmetic cost but usually do not change asymptotic complexity relative to the number of nonzero entries.

8 Example-driven representations

8.1 Small illustrative multigraph examples

Consider a multigraph with three vertices where vertices 1 and 2 are connected by two parallel undirected edges, and vertex 2 has one loop. The adjacency matrix reflects these facts:

\(A_{12}=A_{21}=2\),
\(A_{22}=1\),
other off-diagonal entries are zero.

This example illustrates how multiplicity becomes numerical entry values.

8.2 Worked adjacency matrix computations

Given a directed multigraph on vertices \(\{1,2,3\}\) with edges:

two edges from 1 to 3,
one edge from 3 to 2,
one loop at 2.

The directed adjacency matrix has:

\(A_{13}=2\),
\(A_{32}=1\),
\(A_{22}=1\),

with all remaining entries equal to zero.

From this matrix, in-degrees and out-degrees can be computed by summing columns and rows (respecting the directed convention).

8.3 Directed vs undirected comparison examples

If the directed example above is treated as undirected by replacing each directed edge with an undirected connection (and handling loops as loops), then the adjacency matrix changes:

entries corresponding to undirected neighbor relationships become symmetric,
the multiplicity for a pair may reflect total edges between the pair regardless of direction, depending on the conversion rule.

This comparison highlights that adjacency matrices encode whether order matters.

8.4 Loop-containing examples and checks

In an undirected multigraph with a single vertex \(1\) and three loops, the adjacency matrix is \([3]\). The diagonal entry is 3, but the degree of vertex 1 under the common undirected convention is typically \(2\times 3=6\). Checking such consistency helps confirm that loop contributions are treated correctly in degree formulas.

9 Alternative adjacency representations

9.1 Weighted adjacency as multiplicity counts

A weighted adjacency matrix can represent multiplicities directly by setting weights equal to edge counts. In that setting, most algebraic methods still apply, but interpretation shifts:

matrix entries are no longer purely combinatorial counts if weights are non-integer,
walk “counts” become weighted totals unless weights have a probabilistic meaning.

When weights are literal multiplicities, the weighted framework coincides with the multigraph adjacency framework.

9.2 Adjacency via multiset neighbor lists

Instead of matrices, one can store for each vertex a multiset (or list with repeats) of neighbors. In such a structure:

if vertex \(i\) has \(m\) parallel edges to vertex \(j\), then \(j\) appears \(m\) times in \(i\)’s neighbor multiset.

This representation is often convenient for algorithms that traverse adjacency lists directly, especially when matrices are impractical.

9.3 Edge-pair multiplicity maps (hash/dictionary form)

Another alternative is a dictionary keyed by vertex pairs \((i,j)\) storing multiplicities. For directed graphs, ordered pairs serve as keys; for undirected graphs, one may enforce an ordering such as storing only \((\min(i,j),\max(i,j))\).

This approach supports fast lookup and sparse storage, while enabling on-demand conversion to matrix form for computations requiring linear algebra operations.

10 Conventions and common pitfalls

10.1 Off-by-one errors in loop handling

Loop handling is a frequent source of error. For adjacency matrices, the diagonal entry should equal the loop multiplicity under typical conventions. However, when degrees are computed, undirected loop contributions often must be doubled. Confusing these two interpretations leads to systematic degree mismatches.

10.2 Confusing directed entries with undirected symmetry

In directed multigraphs, adjacency matrices are generally not symmetric. A common pitfall is to enforce symmetry inadvertently, which effectively collapses direction information. Correct validation includes confirming that \(A_{ij}\) is interpreted as edges from \(i\) to \(j\), not vice versa.

10.3 Misinterpreting adjacency counts as boolean edges

When adjacency entries store multiplicity counts, interpreting any nonzero entry as a single edge loses information. Algorithms based on boolean adjacency may undercount walks, paths, or spectral quantities that depend on multiplicity-sensitive structure.

10.4 Inconsistent normalization across sources

Comparing adjacency matrices from different sources can be problematic if one uses normalization (e.g., scaling by degrees or transforming into transition probabilities) while another uses raw multiplicities. Derived computations—like random-walk interpretations, Laplacians, or degree-based normalizations—must align with the input convention to avoid incorrect conclusions.