Combinatorial Complexes#
In this tutorial, you will learn about combinatorial complexes in TopoNetX
, which are mathematical structures that can be depicted like this:
[ ]:
from IPython.display import Image
import toponetx as tnx
Image("ccc.png")
Setup#
[2]:
Combinatorial Complex#
A combinatorial complex, CCC, combines features of both hypergraphs and of cell complexes
CCCs are both hierarchical
A CCC is made up of cells, each cell has a specific rank
Defintion of Combinatorial Complex#
(i)
(ii) for all
Example of a Combinatorial Complex#
This is an example of a combinatorial complex (CCC), this example has six cells of rank 0, three cells of rank 1 and two cells of rank 2. As we can see this is different to a cell complexes (CC) as cells of rank 2 can contain cells of rank 0 without needing cells of rank 0 also.
To express this example as code we may use the add_cell
function. Examples of this can be seen below.
[ ]:
example = tnx.CombinatorialComplex()
example.add_cell([1, 2], rank=1)
print(example)
example.add_cell([1, 3], rank=1)
print(example)
example.add_cell([1, 2, 4, 3], rank=2)
print(example)
example.add_cell([2, 5], rank=1)
print(example)
example.add_cell([2, 6, 4], rank=2)
print(example)
Combinatorial Complex with 2 nodes and cells with ranks [0, 1] and sizes (2, 1)
Combinatorial Complex with 3 nodes and cells with ranks [0, 1] and sizes (3, 2)
Combinatorial Complex with 4 nodes and cells with ranks [0, 1, 2] and sizes (4, 2, 1)
Combinatorial Complex with 5 nodes and cells with ranks [0, 1, 2] and sizes (5, 3, 1)
Combinatorial Complex with 6 nodes and cells with ranks [0, 1, 2] and sizes (6, 3, 2)
The output of this code clearly demonstrates how the CCC builds up. The first line of the output comes from adding the 1-cell
Each further line of input is adding another cell of varying rank. Finally, the last line of output is telling us that we have cells of rank 0, 1 and 2 and that they respectively have sizes of 6, 3 and 2. This is such that we have six 0-cells, three 1-cells and two 2-cells, just like our example figure does.
Helpful Code Output#
If you ever need the list of 0-cells, 1-cells or 2-cells the code below is useful for that. This utilises something called an incidence matrix which is explained later in the tutorial. Knowing the order that cells of each rank is listed in is very important when it comes to understanding the output of adjacency and incidence matrices, using this code allows you to access that information at any time.
[4]:
row, column, B1 = example.incidence_matrix(0, 1, index=True)
row1, column1, B2 = example.incidence_matrix(1, 2, index=True)
print("rank 0:")
print(row)
print("rank 1:")
print(column)
print("rank 2:")
print(column1)
rank 0:
OrderedDict({frozenset({1}): 0, frozenset({2}): 1, frozenset({3}): 2, frozenset({4}): 3, frozenset({5}): 4, frozenset({6}): 5})
rank 1:
OrderedDict({frozenset({1, 2}): 0, frozenset({1, 3}): 1, frozenset({2, 5}): 2})
rank 2:
OrderedDict({frozenset({1, 2, 3, 4}): 0, frozenset({2, 4, 6}): 1})
Although at first glance this may appear confusing, once you understand the output format it is quite simple. This output is telling us that:
In the 0-cells, the
In the 1-cells, the
In the 2-cells, the
Comparing this information to the diagram of our example, we see that all the cells of each rank are listed, and now we also know their order.
Adjacency#
Adjacency Matrix#
An adjacency matrix, is a square matrix that compares a class of objects to themselves (hence being square). Entries in an adjacency matrix are zero if they are not adjacent, and non-zero if they are adjacent
$AXY(i,j) =
$
Where
In our example there are 3 ranks, this means the number of adjacency matrices that we can make is 3; A01, A02, A12. Any other combination would be impossible as cells can only be adjacent via a cell of a higher rank.
[5]:
A01 = example.adjacency_matrix(0, 1).todense()
print(A01)
[[0 1 1 0 0 0]
[1 0 0 0 1 0]
[1 0 0 0 0 0]
[0 0 0 0 0 0]
[0 1 0 0 0 0]
[0 0 0 0 0 0]]
C:\Users\kkgg3\AppData\Roaming\Python\Python312\site-packages\scipy\sparse\_index.py:143: SparseEfficiencyWarning: Changing the sparsity structure of a csc_matrix is expensive. lil_matrix is more efficient.
self._set_arrayXarray(i, j, x)
As this is A01 matrix, it is comparing if 0-cells are related to other 0-cells via any 1-cells. The matrix is square, due to the fact it is comparing each 0-cell to every other 0-cell - it is not important which 1-cell they are adjacent by. Here we can see that the matrix is symmetric, this is due to the fact that the CCC is not directed.
To remind ourselves,
rank-0: 0: {1}, 1: {2}, 2: {3}, 3: {4}, 4: {5}, 5: {6}
rank-1: 0: {1,2}, 1: {1,3}, 2: {2,5}.
Looking at the output, the
The
[6]:
A02 = example.adjacency_matrix(0, 2).todense()
print(A02)
[[0 1 1 1 0 0]
[1 0 1 2 0 1]
[1 1 0 1 0 0]
[1 2 1 0 0 1]
[0 0 0 0 0 0]
[0 1 0 1 0 0]]
This is the A02 matrix, this is comparing which 0-cells are adjacent via 2-cells.
To remind ourselves,
rank-0: 0: {1}, 1: {2}, 2: {3}, 3: {4}, 4: {5}, 5: {6}
rank-2: 0: {1,2,3,4}, 1: {2,4,6}.
Looking at the output, the
The
[7]:
A12 = example.adjacency_matrix(1, 2).todense()
print(A12)
[[0 1 0]
[1 0 0]
[0 0 0]]
This is the A12 matrix, this is comparing which 1-cells are adjacent to each other via a 2-cell.
To remind ourselves,
rank-1: 0: {1,2}, 1: {1,3}, 2: {2,5}
rank-2: 0: {1,2,3,4}, 1: {2,4,6}.
As there are three 1-cells, this matrix is a 3x3 square matrix.
The output here can be explained in the same way. The
The
The
Co-Adjacency Matrix#
A co-adjacency matrix is a matrix that compares a class of objects to themselves, by seeing if they are coadjacent via some cell of a lower rank.
That is, do the two cells in the class being compared, both fully contain the same member of a lower class? Below is two examples that might make this concept clearer.
Here are two examples, made up of 0-cells (orange), 1-cells (pink) and 2-cells (blue).
The example on the left has that the two 1-cells {1,2} and {2,3} are coadjacent via a 0-cell, which in this case is {2}. This is because both of the 1-cells contain the 0-cell {2}, thus making the 1-cells coadjacent.
The example on the right has two 2-cells {1,2,3} and {2,3,4}, three 1-cells {1,2}, {2,3} and {3,4}, and four 0-cells {1}, {2}, {3}, {4}. The 2-cells are coadjacent via the 1-cell {2,3} and also the two 0-cells {2}, {3}; both of the 2-cells fully contain these lower rank cells. {1,2} and {2,3} are coadjacent via {2}, also {2,3} and {3,4} are coadjacent via {3}.
Now let’s compute the coadjaceny matrices, CA10, CA20 and CA21, for our original example.
[8]:
CA10 = example.coadjacency_matrix(1, 0).todense()
print(CA10)
[[0 1 1]
[1 0 0]
[1 0 0]]
The CA10 matrix, sees if 1-cells are coadjacent via any shared 0-cells.
To remind ourselves,
rank-0: 0: {1}, 1: {2}, 2: {3}, 3: {4}, 4: {5}, 5: {6}
rank-1: 0: {1,2}, 1: {1,3}, 2: {2,5}.
The matrix’s
[9]:
CA20 = example.coadjacency_matrix(2, 0).todense()
print(CA20)
[[0 2]
[2 0]]
The CA20 matrix sees if any 2-cells are coadjacent via any shared 0-cells.
To remind ourselves,
rank-0: 0: {1}, 1: {2}, 2: {3}, 3: {4}, 4: {5}, 5: {6}
rank-2: 0: {1,2,3,4}, 1: {2,4,6}.
CA20’s
This information is then repeated in the mirrored direction in the
[10]:
CA21 = example.coadjacency_matrix(2, 1).todense()
print(CA21)
[[0 0]
[0 0]]
The CA21 matrix compares if any 2-cells are coadjacent via a 1-cell.
All of the entries in this matrix are zero, which tells us that no 2-cells are coadjacent via a 1-cell.
To remind ourselves,
rank-1: 0: {1,2}, 1: {1,3}, 2: {2,5}
rank-2: 0: {1,2,3,4}, 1: {2,4,6}.
Looking at these cells it is clear that both 2-cells do not share any 1-cells, given that {2,4,6} does not fully contain a 1-cell this is inevitable.
Incidence#
Incidence Matrix#
An incidence matrix is a matrix that shows the relationship between two classes of objects. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related (called incident in this context) and 0 if they are not
$BXY(i,j) =
$
For combinatorial complexes, we compare cells of a rank to cells of a higher rank. So for our example, as we only have three ranks we have three possible incidence matrices: B01, B02 and B12.
[11]:
B01 = example.incidence_matrix(0, 1).todense()
print(B01)
[[1 1 0]
[1 0 1]
[0 1 0]
[0 0 0]
[0 0 1]
[0 0 0]]
B01 is the incidence matrix portraying which 0-cells are incident to which 1-cells.
To remind ourselves,
rank-0: 0: {1}, 1: {2}, 2: {3}, 3: {4}, 4: {5}, 5: {6}
rank-1: 0: {1,2}, 1: {1,3}, 2: {2,5}.
So in this matrix, each row represents one of the six 0-cells, and each column represents one of the three 1-cells.
The 0
The 3
[12]:
B02 = example.incidence_matrix(0, 2).todense()
print(B02)
[[1 0]
[1 1]
[1 0]
[1 1]
[0 0]
[0 1]]
B02 is the incidence matrix demonstrating which 0-cells are incident to which 2-cells.
To remind ourselves,
rank-0: 0: {1}, 1: {2}, 2: {3}, 3: {4}, 4: {5}, 5: {6}
rank-2: 0: {1,2,3,4}, 1: {2,4,6}.
In this marix, each row represents one of the six 0-cells, and each column represents one of the two 2-cells.
The
[13]:
B12 = example.incidence_matrix(1, 2).todense()
print(B12)
[[1 0]
[1 0]
[0 0]]
B12 is the incidence matrix demonstrating which 1-cells are incident to which 2-cells.
To remind ourselves,
rank-1: 0: {1,2}, 1: {1,3}, 2: {2,5}
rank-2: 0: {1,2,3,4}, 1: {2,4,6}.
The
References#