Isomorphisms and automorphisms

Requirements

pymnet uses third-party software to solve graph-isomorphism problems, i.e., some of its functionality depends on having this software installed. Some of the functionality is redundant in a way that optional software packages can be used to solve the same problem, and only one of them is needed to be installed to gain access to that functionality.

• networkx: Available through pip. Allows the usage of the following functions: is_isomorphic, get_isomorphism.

• bliss-blind: Installed as a dependency on MacOS, X64 Windows and X64 Linux machines, has to be manually compiled and installed on other system using the command python -m pip install bliss-bind. Allows the usage of the following functions: is_isomorphic, get_isomorphism, get_automorphism_generators, get_complete_invariant.

Setup

pymnet can deal with generalized graph isomorphisms introduced in this article. This tutorial introduces the basic multilayer-network isomorphism functionality available in pymnet.

Let’s start by creating a multilayer social network:

from pymnet import *
net_social = MultiplexNetwork(couplings="categorical", fullyInterconnected=False)
net_social["Alice", "Bob", "Friends"] = 1
net_social["Alice", "Carol", "Friends"] = 1
net_social["Bob", "Carol", "Friends"] = 1
net_social["Alice", "Bob", "Married"] = 1
fig_social = draw(net_social, layout="circular", layerPadding=0.2, defaultLayerLabelLoc=(0.9,0.9))

We want to compare networks, so let’s create another network. A transportation network this time:

net_transport = MultiplexNetwork(couplings="categorical", fullyInterconnected=False)
net_transport["Helsinki", "Turku", "Train"] = 1
net_transport["Helsinki", "Tampere", "Train"] = 1
net_transport["Turku", "Tampere", "Train"] = 1
net_transport["Helsinki", "Turku", "Ferry"] = 1
fig_transport = draw(net_transport, layout="circular", layerPadding=0.2, defaultLayerLabelLoc=(0.9,0.9))

Isomorphisms

Clearly, the two above networks have the same structure but different labels of nodes and layers. In terms of multilayer network isomorphisms, this means that the two networks are node-layer isomorphic (but not node isomorphic or layer isomorphic). This can be confirmed using the is_isomorphic function as follows:

print(is_isomorphic(net_social, net_transport, allowed_aspects=[0]))  # node isomorphism

False

print(is_isomorphic(net_social, net_transport, allowed_aspects=[1]))  # layer isomorphism

False

print(is_isomorphic(net_social, net_transport, allowed_aspects=[0, 1]))  # node-layer isomorphism

True

In the above example, the different isomorphism types are specified using the allowed_aspects parameter, which takes a list of integers each corresponding to one aspect that can be permuted. The node aspect is the 0th aspect by convention as usual.

We can also recover the isomorphic map from the social network node and layer labels to the transportation network node and layer labels using the get_isomorphism function:

print(get_isomorphism(net_social, net_transport))

[{'Alice': 'Helsinki', 'Bob': 'Turku', 'Carol': 'Tampere'}, {'Friends': 'Train', 'Married': 'Ferry'}]

Note that you might want to use the function get_complete_invariant if you are doing multiple isomorphism comparisons. The function returns an object that can be directly compared to another complete invariant object to determine if two networks are isomorphic, and there is no need to rerun the expensive graph-isomorphism algorithms.

Automorphisms

Automorphisms are isomorphisms with the network itself. One can calculate automorphism groups using this library. As automorphisms are isomorphisms, one needs to specify the type of the automorphism exactly in the same way as one does the type of isomorphisms. For example, in the above social network, one can find the only (non-trivial) automorphism where Bob and Alice change labels:

print(get_automorphism_generators(net_social, allowed_aspects=[0])) #node isomorphism

[[{'Alice': 'Bob', 'Bob': 'Alice'}, {}]]

print(get_automorphism_generators(net_social, allowed_aspects=[1])) #layer isomorphism

[]

print(get_automorphism_generators(net_social, allowed_aspects=[0, 1])) #node-layer isomorphism

[[{'Alice': 'Bob', 'Bob': 'Alice'}, {}]]

The function get_automorphism_generators returns a list of automorphisms that can be used to generate all possible automorphisms by combining the permutation operations. That is, the list of automorphisms returned form a generating set of the automorphism group.

Note that in the above example, the automorphism group given by node isomorphism is the same as the one given by node-layer isomorphism. The node-layer isomorphisms are not always unions of node isomorphisms and layer isomorphisms. To illustrate this, we generate a network that has a slightly more interesting automorphism-group structure:

net = MultilayerNetwork(aspects=1)
net[1, "A"][2, "A"] = 1
net[2, "A"][3, "A"] = 1
net[3, "B"][2, "B"] = 1
net[2, "B"][1, "B"] = 1
net[3, "A"][1, "B"] = 1
fig = draw(net, layerPadding=0.2)

For this network, there are no (nontrivial) node automorphisms or layer isomorphisms, but there is a node-layer isomorphism:

print(get_automorphism_generators(net, allowed_aspects=[0]))

[]

print(get_automorphism_generators(net, allowed_aspects=[1]))

[]

print(get_automorphism_generators(net, allowed_aspects=[0, 1]))

[[{1: 3, 3: 1}, {'B': 'A', 'A': 'B'}]]