Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 KirchhoffTensor

Source Notebook

Compute the Kirchhoff tensor (Laplacian) of an arbitrary hypergraph

Contributed by: Jonathan Gorard

ResourceFunction["KirchhoffTensor"][h]

gives the Kirchhoff tensor of the (ordered or orderless) hypergraph h.

Details and Options

A Kirchhoff tensor (hypergraph Laplacian) is a generalization of the concept of a Kirchhoff matrix (graph Laplacian) from graphs to hypergraphs, in which hyperedges may be of arbitrary arity.
The rank of the Kirchhoff tensor is equal to the arity of the hyperedges of the hypergraph.
The Kirchhoff tensor for a hypergraph will have dimensions n×n×…×n, where n is the number of vertices.
ResourceFunction["KirchhoffTensor"] returns a SparseArray object, which can be converted into ordinary nested lists using Normal.
The diagonal entries aii…i represent the degrees for each vertex vi.
An off-diagonal entry aij…k is equal to -1 if vertices vi,vj,…,vk are adjacent (or, in the case of multihypergraphs, -aij…k is equal to the number of hyperedges of the form {vi,vj,…,vk}).
ResourceFunction["KirchhoffTensor"] has the following options:
"OrderedHyperedges"Falsewhether to treat hyperedges as being ordered (directed)
"OrderedHyperedgeDegree""InOutDegree"which notion of vertex degree to use for ordered (directed) hypergraphs
The following settings for "OrderedHyperedgeDegree" can be used in ResourceFunction["KirchhoffTensor"]:
"InOutDegree"treat the degree of a vertex in an ordered (directed) hypergraph as the sum of its in- and out-degrees
"InDegree"treat the degree of a vertex in an ordered (directed) hypergraph as its in-degree
"OutDegree"treat the degree of a vertex in an ordered (directed) hypergraph as its out-degree
When all hyperedges are of arity 2, the output of ResourceFunction["KirchhoffTensor"] is identical to that of KirchhoffMatrix.

Examples

Basic Examples (3) 

The Kirchhoff tensor of an orderless hypergraph, with hyperedges of arity 3:

In[1]:=
tensor = ResourceFunction[ "KirchhoffTensor"][{{1, 2, 3}, {2, 3, 4}, {3, 4, 1}}]
Out[1]=
In[2]:=
Normal[tensor]
Out[2]=

The Kirchhoff tensor of an ordered hypergraph, with hyperedges of arity 3:

In[3]:=
tensor = ResourceFunction[ "KirchhoffTensor"][{{1, 2, 3}, {2, 3, 4}, {3, 4, 1}}, "OrderedHyperedges" -> True]
Out[3]=
In[4]:=
Normal[tensor]
Out[4]=

Use only vertex in-degrees along the main diagonal:

In[5]:=
tensor2 = ResourceFunction[ "KirchhoffTensor"][{{1, 2, 3}, {2, 3, 4}, {3, 4, 1}}, "OrderedHyperedges" -> True, "OrderedHyperedgeDegree" -> "InDegree"]
Out[5]=
In[6]:=
Normal[tensor2]
Out[6]=

The Kirchhoff tensor of an orderless hypergraph, with hyperedges of arity 5:

In[7]:=
tensor = ResourceFunction[ "KirchhoffTensor"][{{1, 2, 3, 4, 5}, {6, 2, 8, 9, 7}, {10, 9, 3, 5, 1}, {9, 8, 5, 3, 2}}]
Out[7]=

Scope (6) 

KirchhoffTensor supports multihypergraphs, in which case the off-diagonal tensor entries represent hyperedge multiplicities:

In[8]:=
tensor = ResourceFunction[ "KirchhoffTensor"][{{1, 2, 3}, {2, 3, 4}, {2, 3, 4}, {3, 4, 1}, {3, 4, 1}, {3, 4, 1}}]
Out[8]=
In[9]:=
Normal[tensor]
Out[9]=

When the arity of hyperedges is equal to 2, the output of KirchhoffTensor is identical to the output of KirchhoffMatrix:

In[10]:=
tensor = ResourceFunction[ "KirchhoffTensor"][{{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}]
Out[10]=
In[11]:=
matrix = KirchhoffMatrix[ Graph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 4, 3 \[UndirectedEdge] 4}]]
Out[11]=
In[12]:=
tensor == matrix
Out[12]=

The Kirchhoff tensor of an orderless hypergraph is always symmetric across all indices:

In[13]:=
tensor = ResourceFunction[ "KirchhoffTensor"][{{1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5, 6}, {5, 6, 1}}]
Out[13]=
In[14]:=
tensor[[1, 2, 3]] == tensor[[1, 3, 2]]
Out[14]=

The Kirchhoff tensor of an ordered hypergraph is not necessarily symmetric across all indices:

In[15]:=
tensor = ResourceFunction[ "KirchhoffTensor"][{{1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5, 6}, {5, 6, 1}}, "OrderedHyperedges" -> True]
Out[15]=
In[16]:=
tensor[[1, 2, 3]] == tensor[[1, 3, 2]]
Out[16]=

KirchhoffTensor automatically removes self-loops from a hypergraph:

In[17]:=
tensor1 = ResourceFunction[ "KirchhoffTensor"][{{1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5, 1}, {1, 1, 1}}]
Out[17]=
In[18]:=
tensor2 = ResourceFunction[ "KirchhoffTensor"][{{1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5, 1}}]
Out[18]=
In[19]:=
tensor1 == tensor2
Out[19]=

Hyperedges can be of arbitrary arity:

In[20]:=
ResourceFunction[ "KirchhoffTensor"][{{1, 2, 4, 7, 3, 5}, {5, 4, 8, 9, 12, 11}, {10, 2, 3, 6, 7, 4}, {12, 5, 2, 4, 7, 9}}]
Out[20]=

Options (5) 

Ordered/orderless hyperedges (2) 

By default, all hyperedges are treated as orderless (i.e. undirected):

In[21]:=
tensor = ResourceFunction[ "KirchhoffTensor"][{{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}]
Out[21]=
In[22]:=
MatrixForm[tensor]
Out[22]=

Use "OrderedHyperedges"→True to treat hyperedges as ordered (i.e. directed):

In[23]:=
tensor2 = ResourceFunction[ "KirchhoffTensor"][{{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}, "OrderedHyperedges" -> True]
Out[23]=
In[24]:=
MatrixForm[tensor2]
Out[24]=

Ordered hyperedge degrees (3) 

By default, the vertex degrees along the main diagonal for an ordered (i.e. directed) hypergraph are given by the sum of vertex in- and out-degrees:

In[25]:=
tensor = ResourceFunction[ "KirchhoffTensor"][{{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}, "OrderedHyperedges" -> True]
Out[25]=
In[26]:=
MatrixForm[tensor]
Out[26]=

Use "OrderedHyperedgeDegree"→"InDegree" to use the vertex in-degree instead:

In[27]:=
tensor2 = ResourceFunction[ "KirchhoffTensor"][{{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}, "OrderedHyperedges" -> True, "OrderedHyperedgeDegree" -> "InDegree"]
Out[27]=
In[28]:=
MatrixForm[tensor2]
Out[28]=

Use "OrderedHyperedgeDegree"→"OutDegree" to use the vertex out-degree instead:

In[29]:=
tensor3 = ResourceFunction[ "KirchhoffTensor"][{{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}, "OrderedHyperedges" -> True, "OrderedHyperedgeDegree" -> "OutDegree"]
Out[29]=
In[30]:=
MatrixForm[tensor3]
Out[30]=

Publisher

Jonathan Gorard

Version History

  • 1.0.0 – 17 March 2021

Related Resources

License Information