Skip to content

Incidence representation

annnet uses a sparse incidence matrix because it can represent ordinary edges, hyperedges, parallel edges, and edge-entities without switching data structures.

Basic idea

  • Let V be the set of entities and E the set of edges.
  • The incidence matrix is B ∈ R^{|V|×|E|}.
  • Each column is one edge.
  • Each row is one entity. In annnet, entities include both ordinary nodes and edge-entities.

Sign convention:

  • Directed edge e: for each head or source endpoint u, set B[u,e] = +w.
  • Directed edge e: for each tail or target endpoint v, set B[v,e] = -w.
  • Undirected edge e: for each endpoint u, set B[u,e] = +w.

A self-loop and a one-sided edge

A column records one entry per role, not one per entity. An entity that takes two roles in one edge therefore appears twice in that column.

This matters for two shapes that would otherwise look identical:

  • A self-loop a -> a with weight w contributes +w for the source role and -w for the target role, both on row a. The two entries sum, so the column of a directed self-loop is zero in B and in S. The loop is still in the graph: G.A gives it a diagonal entry, and degree counts it twice, once per role.
  • A one-sided or boundary edge, which drains or feeds a node with no other side, contributes a single entry.

This changed. Before the core refactor, a directed self-loop wrote +w and then -w into the same cell, so the second overwrote the first and the column held one entry of -w. That was indistinguishable from a sink boundary edge on the same node, and the fact that the edge was a loop survived only outside the matrix.

If you relied on the old shape, the migration is:

You want Before Now
Is this edge a self-loop inspect the endpoints the column sums to zero, or ask G.A for the diagonal
The weight of a self-loop read the single entry read G.A[a, a], or the edge weight
A boundary edge one entry, ambiguous one entry, and no other shape produces one

What this makes possible

  • Hyperedges become columns with more than two non-zero entries.
  • Parallel edges become additional columns with the same endpoint set but different edge IDs.
  • Node-to-edge and edge-to-edge relations work because edge-entities live in the same row space as ordinary nodes.
  • Stoichiometric coefficients can be written directly into the corresponding incidence column.

Example

Entities (rows):   a,  b,  c,  d
Edges (columns):  e1, e2, e3

B =
      e1  e2  e3
 a   +2   0  +1
 b   -2  +1  +1
 c    0  +1  +1
 d    0  -2  +1
  • e1: directed a → b with weight 2
  • e2: directed edge with positive membership on b and negative membership on d
  • e3: undirected hyperedge over {a, b, c, d}

Hyperedges

  • Undirected hyperedge over members M: put +w in every row for v ∈ M.
  • Directed hyperedge with head H and tail T: put +w in rows for H and -w in rows for T.
  • SBML-style stoichiometric coefficients can be stored directly as endpoint-specific values in the same column.

There is no need to reify hyperedges into auxiliary nodes unless you export to a format that requires that shape.

Edge-entities

AnnNet can represent node→edge and edge→edge relations because edges can themselves appear in the entity row space.

G.add_edges(edge_id='e_meta', as_entity=True, description='signal')
G.add_edges('e_meta', 'C', as_entity=True, directed=True)

An edge-entity may exist either as a structural edge that is also connectable, or as a placeholder edge-entity with a row but no incidence column yet. In both cases, once it has an entity row it can act as an endpoint like any other entity.

Parallel edges and weights

  • Parallel edges are separate columns with distinct IDs.
  • Edge weights scale the relevant column.
  • Hyperedges can carry endpoint-specific coefficients.
  • Slice-specific overrides can change the effective weight in a given slice without changing the base structure.

If you later ask for a simple backend graph, those parallel edges may be collapsed during conversion, but they remain distinct in annnet itself.

Operators

Let W = diag(w_e) be a diagonal matrix of edge weights.

  • Undirected Laplacian: L = B W Bᵀ
  • Directed adjacency:
  • B⁺ = max(B,0)
  • B⁻ = max(-B,0)
  • A = B⁺ W (B⁻)ᵀ
  • Row-stochastic transition: P = D⁻¹ A, with D = diag(A 1)

Other directed operators are possible, but these constructions capture the main idea used throughout annnet.

Multilayer extension

For multilayer graphs, the same logic is applied to the supra incidence matrix over (node, layer) pairs. See Multilayer and multi-aspect graphs.