Counting subgraphs in multiplex networks

Abstract

Beyond isolated nodes, subgraphs are fundamental components of networks, with enormous potential to provide a detailed characterization of the underlying systems. Computing subgraph frequencies is therefore a core task indispensable to several other important network metrics. Yet, quantifying these small pieces is computationally challenging, with no known general polynomial-time solution, driving the search for efficient methodologies. Previous counting methods mainly focused on simple classic networks, consisting of a single layer of connectivity. In the last decade, there has been growing interest in multilayer networks, which provide a more realistic representation of complex systems by incorporating layers. With this integration, fundamental concepts were meanwhile presented in a consolidated manner, forming the basis for the development of our proposed strategy. Seeking to contribute to the advancement of multilayer network analysis, but considering the scarcity of available solutions, we focus on a specific and more limited problem before progressing to the more general case. Here, we focus precisely on providing a subgraph counting methodology by computing the frequency of all subgraphs of a specified size in the multiplex case, which is the most widely used type of multilayer networks. Our MPCount implementation builds on the FaSE algorithm, extending it to accommodate multiplex networks by adapting its efficient enumeration and isomorphism identification process to address the introduced layers. This adaptation preserves accuracy, making it an available practical tool for counting subgraphs in multiplex networks, with proof of its performance, supported by experimental results that validate its effectiveness in both synthetic and real world datasets.