Automorphisms

[camillerievan]

Once I build the hypergraph is it possible to get a list of Automorphisms in the hypergraph?

[brendapraggastis]

@camillerievan That is an interesting idea. Could you give an explicit example and I will see what we have in the library that might apply to it.

[camillerievan]

Example Vertices: {1, 2, 3, 4, 5} Hyperedges: {1, 2, 3}, {3, 4, 5}, {1, 5}

Besides the identity authmorphism which does not interest me, one can consider a permutation where vertex 1 and 5 are swapped, and 3 and 4 are swapped. This preserves the hyperedge structure. So, (1 → 5, 3 → 4).

For a normal graph python-graph provides the solution to find authmorphism of a graph (see code below). Till now I did not find a library to give me the authmorphisms of a hypergraph. Since my study requires that I study hundreds of hypergraphs it will not be possible to find these by hand!

Code for authmorphism of a normal graph

import networkx as nx
from igraph import Graph as IGraph
import matplotlib.pyplot as plt

# Function to convert a NetworkX graph to an igraph graph
def convert_networkx_to_igraph(nx_graph):
    mapping = {node: idx for idx, node in enumerate(nx_graph.nodes())}
    g = IGraph(len(nx_graph))
    g.add_edges([(mapping[u], mapping[v]) for u, v in nx_graph.edges()])
    return g, mapping

# Create a NetworkX graph (Example: a triangle graph)
#nx_graph = nx.Graph([(1, 2), (2, 3), (3, 1)])
#nx_graph = nx.Graph([(1, 2), (2, 3), (3, 4), (2, 4), (4, 5)])
nx_graph = nx.Graph([(1, 2), (2, 3), (3, 4), (4, 1)])

# Convert the NetworkX graph to an igraph graph
igraph_graph, mapping = convert_networkx_to_igraph(nx_graph)

# Find automorphisms
automorphisms = igraph_graph.get_isomorphisms_vf2(igraph_graph)

# Convert automorphisms back to the original node labels
automorphisms_labels = [[list(mapping.keys())[list(mapping.values()).index(i)] for i in automorphism] for automorphism in automorphisms]

# Print the automorphisms
print("Automorphisms (in terms of original node labels):")
for automorphism in automorphisms_labels:
    print(automorphism)

# Display the graph using matplotlib
plt.figure(figsize=(8, 6))
nx.draw(nx_graph, with_labels=True, font_weight='bold', node_color='skyblue', node_size=700, font_size=18)
plt.title('NetworkX Graph Visualization')
plt.show()

Thanks

[brendapraggastis]

@camillerievan A hypergraph's structure is completely described by its incidence matrix. Two hypergraphs are isomorphic if and only if their incidence matrices are equivalent up to a row permutation. If you use the indices of the rows as names for your nodes you can quickly generate all of the isomorphic hypergraphs by permuting the rows and generating the hypergraph from the incidence matrices:

import hypernetx as hnx
import itertools as it

H = hnx.Hypergraph([[1,2,3],[3,4,5],[1,5]])
M = H.incidence_matrix()
R = [list(x) for x in it.permutations(range(5))]
listOfIsomorphicHypergraphs = [hnx.Hypergraph.from_incidence_matrix(M[r].todense()) for r in R]

If you wish to permute them preserving different names then you can do something similar by permuting the rows of the associated incidence dataframe or use dictionaries:

def permute(H,d):
    newd = dict()
    for e,v in H.incidence_dict.items():
        newd[e] = [d.get(vv,vv) for vv in v]
    return hnx.Hypergraph(newd)
H = hnx.Hypergraph([[1,2,3],[3,4,5],[1,5]])
d = {1:5, 5:1, 3:4, 4:3} 
permute(H,d).incidence_dict

You can also generate the dictionaries by permuting the names:

Ha = hnx.Hypergraph([['A', 'B', 'C'], ['C', 'D', 'E'], ['A', 'E']])
names = ['A', 'B', 'C', 'D', 'E']
R = list(it.permutations(names))

## make a dictionary to permute the names
d = {idx:dict(zip(names,R[3])) for idx in range(len(R))}
Hd = {idx: permute(Ha,d[idx]) for idx in range(len(R))}

## Look at some of the new hypergraphs:
fig,ax = plt.subplots(5,5,figsize=(15,15))
for idx in range(25):
     thisax = ax[idx//5,idx%5]
     hnx.draw(Hd[idx],ax=thisax)

[brendapraggastis]

@camillerievan A colleague pointed out you were asking for automorphisms not isomorphisms or relabelings. He provided the following answer, which I think is more of what you want:

"Nauty (No AUTomorphisms, Yes?) has for long been my go to reference on graph isomorphism stuff. It was started by Brendan McKay who is a world leader on this topic. Probably anything you’d ever want to compute regarding graph isomorphism is covered by this package, though the documentation is hit or miss -- here is a PDF listing its capabilities:

https://users.cecs.anu.edu.au/~bdm/nauty/nug28.pdf

and here is a Python implementation: https://pypi.org/project/pynauty/

The key thing this user probably doesn’t realize is that they can use tools for graph isomorphism for hypergraphs by just treating the hypergraph as a bicolored graph. For instance, on pg. 97-98 of the Nauty documentation, there is a function called genbg that will find all bicolored graphs with specified parameters (n1=#nodes, n2=#hyperedges, connected or not, etc). Anyway, looking at the notebook the user submitted, they are using this function from igraph:

https://igraph.org/python/doc/api/igraph._igraph.GraphBase.html#count_isomorphisms_vf2

which has optional parameters for specifying the color classes of vertices. So I don’t even think they need to use nauty if they want to stick with igraph – I think it suffices to just convert the hypergraph to a bicolored one and plug in the color classes for nodes and hyperedges to this function."

Hope this helps!!