Subnetwork enumeration algorithms for multilayer networks

Thumbnail Image

Access rights

openAccess
publishedVersion

URL

Journal Title

Journal ISSN

Volume Title

A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)

Authors

Date

2024

Department

Department of Computer Science

Major/Subject

Mcode

Degree programme

Language

en

Pages

15

Series

IEEE Transactions on Network Science and Engineering, Volume 11, issue 6, pp. 5803-5817

Abstract

To understand the structure of a network, it can be useful to break it down into its constituent pieces. This is the approach taken in a multitude of successful network analysis methods, such as motif analysis. These methods require one to enumerate or sample small connected subgraphs of a network. Efficient algorithms exists for both enumeration and uniform sampling of subgraphs, and here we generalize the ESU algorithm for a very general notion of multilayer networks. We show that multilayer network subnetwork enumeration introduces nontrivial complications to the existing algorithm, and present two different generalized algorithms that preserve the desired features of unbiased sampling and scalable, communicationfree parallelization. In addition, we introduce a straightforward aggregation-disaggregation-based enumeration algorithm that leverages existing subgraph enumeration algorithms. We evaluate these algorithms in synthetic networks and with real-world data, and show that none of the algorithms is strictly more efficient but rather the choice depends on the features of the data.

Description

Publisher Copyright: © 2013 IEEE.

Keywords

Multilayer networks, multilayer motifs, subgraph enumeration, subnetwork enumeration, subnetwork sampling

Other note

DOI

10.1109/TNSE.2024.3447893

Citation

Nurmi, T & Kivela, M 2024, 'Subnetwork enumeration algorithms for multilayer networks', IEEE Transactions on Network Science and Engineering, vol. 11, no. 6, pp. 5803-5817. https://doi.org/10.1109/TNSE.2024.3447893

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202412047571

Collections

[article-cris] Perustieteiden korkeakoulu / SCI