Function Repository Resource:

AdjacencyTensor

Source Notebook

Compute the adjacency tensor of an arbitrary hypergraph

Contributed by: Jonathan Gorard

ResourceFunction["AdjacencyTensor"][h]

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

Details and Options

An adjacency tensor is a generalization of the concept of an adjacency matrix from graphs to hypergraphs, in which hyperedges may be of arbitrary arity.
The rank of the adjacency tensor is equal to the arity of the hyperedges in the hypergraph.
The adjacency tensor for a hypergraph will have dimensions n×n××n, where n is the number of vertices.
ResourceFunction["AdjacencyTensor"] returns a SparseArray object, which can be converted into ordinary nested lists using Normal.
Each entry aij…k of the adjacency tensor represents the number of hyperedges of the form {vi,vj,,vk}.
The diagonal entries aii…i count the number of self-loops for each vertex vi.
ResourceFunction["AdjacencyTensor"] has the following option:
"OrderedHyperedges"Falsewhether to treat hyperedges as being ordered (directed)
When all hyperedges are of arity 2, the output of ResourceFunction["AdjacencyTensor"] is identical to that of AdjacencyMatrix.

Examples

Basic Examples (3) 

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

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

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

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

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

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

Scope (6) 

AdjacencyTensor supports multihypergraphs, in which case the tensor entries represent hyperedge multiplicities:

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

When the arity of hyperedges is equal to 2, the output of AdjacencyTensor is identical to the output of AdjacencyMatrix:

In[8]:=
tensor = ResourceFunction[
  "AdjacencyTensor"][{{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}]
Out[8]=
In[9]:=
matrix = AdjacencyMatrix[
  Graph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 4, 3 \[UndirectedEdge] 4}]]
Out[9]=
In[10]:=
tensor === matrix
Out[10]=

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

In[11]:=
tensor = ResourceFunction[
  "AdjacencyTensor"][{{1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5, 6}, {5, 6, 1}}]
Out[11]=
In[12]:=
tensor[[1, 2, 3]] == tensor[[1, 3, 2]]
Out[12]=

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

In[13]:=
tensor = ResourceFunction[
  "AdjacencyTensor"][{{1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5, 6}, {5, 6, 1}}, "OrderedHyperedges" -> True]
Out[13]=
In[14]:=
tensor[[1, 2, 3]] == tensor[[1, 3, 2]]
Out[14]=

The adjacency tensor of a hypergraph with self-loops has diagonal entries:

In[15]:=
tensor = ResourceFunction[
  "AdjacencyTensor"][{{1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5, 1}, {2, 2, 2}, {3, 3, 3}}]
Out[15]=
In[16]:=
Normal[tensor]
Out[16]=
In[17]:=
tensor[[2, 2, 2]]
Out[17]=

Hyperedges can be of arbitrary arity:

In[18]:=
ResourceFunction[
 "AdjacencyTensor"][{{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[18]=

Options (2) 

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

In[19]:=
tensor = ResourceFunction[
  "AdjacencyTensor"][{{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}]
Out[19]=
In[20]:=
MatrixForm[tensor]
Out[20]=

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

In[21]:=
tensor2 = ResourceFunction[
  "AdjacencyTensor"][{{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}, "OrderedHyperedges" -> True]
Out[21]=
In[22]:=
MatrixForm[tensor2]
Out[22]=

Publisher

Jonathan Gorard

Version History

  • 1.0.0 – 17 March 2021

Related Resources

License Information