TY - JOUR

T1 - Isomorphisms in Multilayer Networks

AU - Kivela, Mikko

AU - Porter, Mason A.

PY - 2017/9/16

Y1 - 2017/9/16

N2 - We extend the concept of graph isomorphisms to multilayer networks with any number of "aspects" (i.e., types of layering). In developing this generalization, we identify multiple types of isomorphisms. For example, in multilayer networks with a single aspect, permuting vertex labels, layer labels, and both vertex labels and layer labels each yield different isomorphism relations between multilayer networks. Multilayer network isomorphisms lead naturally to defining isomorphisms in any of the numerous types of networks that can be represented as a multilayer network, and we thereby obtain isomorphisms for multiplex networks, temporal networks, networks with both of these features, and more. We reduce each of the multilayer network isomorphism problems to a graph isomorphism problem, where the size of the graph isomorphism problem grows linearly with the size of the multilayer network isomorphism problem. One can thus use software that has been developed to solve graph isomorphism problems as a practical means for solving multilayer network isomorphism problems. Our theory lays a foundation for extending many network analysis methods - including motifs, graphlets, structural roles, and network alignment - to any multilayer network.

AB - We extend the concept of graph isomorphisms to multilayer networks with any number of "aspects" (i.e., types of layering). In developing this generalization, we identify multiple types of isomorphisms. For example, in multilayer networks with a single aspect, permuting vertex labels, layer labels, and both vertex labels and layer labels each yield different isomorphism relations between multilayer networks. Multilayer network isomorphisms lead naturally to defining isomorphisms in any of the numerous types of networks that can be represented as a multilayer network, and we thereby obtain isomorphisms for multiplex networks, temporal networks, networks with both of these features, and more. We reduce each of the multilayer network isomorphism problems to a graph isomorphism problem, where the size of the graph isomorphism problem grows linearly with the size of the multilayer network isomorphism problem. One can thus use software that has been developed to solve graph isomorphism problems as a practical means for solving multilayer network isomorphism problems. Our theory lays a foundation for extending many network analysis methods - including motifs, graphlets, structural roles, and network alignment - to any multilayer network.

KW - Complex networks

KW - Computer science

KW - Mathematics

KW - Multiplexing

KW - Nonhomogeneous media

KW - Software

KW - Terminology

KW - Tools

UR - http://www.scopus.com/inward/record.url?scp=85030656151&partnerID=8YFLogxK

U2 - 10.1109/TNSE.2017.2753963

DO - 10.1109/TNSE.2017.2753963

M3 - Article

AN - SCOPUS:85030656151

JO - IEEE Transactions on Network Science and Engineering

JF - IEEE Transactions on Network Science and Engineering

SN - 2327-4697

ER -