incidence

Graph incidence matrix

Syntax

I = incidence(G)

Description

I = incidence(G) returns the sparse incidence matrix for graph G. If s and t are the node IDs of the source and target nodes of the jth edge in G, then I(s,j) = -1 and I(t,j) = 1. That is, each column of I indicates the source and target nodes for a single edge in G.

Examples

Graph Incidence Matrix

Create a graph using an edge list, and then calculate the graph incidence matrix.

s = [1 1 1 1 1];
t = [2 3 4 5 6];
G = graph(s,t);
I = incidence(G)

I = 
   (1,1)       -1
   (2,1)        1
   (1,2)       -1
   (3,2)        1
   (1,3)       -1
   (4,3)        1
   (1,4)       -1
   (5,4)        1
   (1,5)       -1
   (6,5)        1

Each column in I contains two nonzero entries, which indicate the end nodes of a single edge in G.

Calculate the graph Laplacian matrix, L, and confirm the relation L = I*I' for undirected graphs.

L = laplacian(G);
L - I*I'

ans = 
   All zero sparse: 6x6

Incidence Matrix of Directed Graph

Create a directed graph using an edge list, and then calculate the incidence matrix.

s = [1 2 1 3 2 3 3 3];
t = [2 1 3 1 3 4 5 6];
G = digraph(s,t)

G = 
  digraph with properties:

    Edges: [8x1 table]
    Nodes: [6x0 table]

I = incidence(G)

I = 
   (1,1)       -1
   (2,1)        1
   (1,2)       -1
   (3,2)        1
   (1,3)        1
   (2,3)       -1
   (2,4)       -1
   (3,4)        1
   (1,5)        1
   (3,5)       -1
   (3,6)       -1
   (4,6)        1
   (3,7)       -1
   (5,7)        1
   (3,8)       -1
   (6,8)        1

Each column in I represents the source and target nodes of a single edge in G.

Input Arguments

G — Input graph

graph object | digraph object

Input graph, specified as either a graph or digraph object. Use graph to create an undirected graph or digraph to create a directed graph.

Example: G = graph(1,2)

Example: G = digraph([1 2],[2 3])

Output Arguments

I — Incidence matrix

sparse matrix

Incidence matrix, returned as a sparse matrix. The size of I is numnodes(G)-by-numedges(G). The graph incidence matrix is undefined for graphs with self-loops.

Tips

• The incidence function calculates the variety of incidence matrix commonly known as a signed or oriented incidence matrix. The signed incidence matrix of an undirected graph, I, is related to the graph Laplacian matrix, L, such that L == I*I'.