Subnetwork enumeration algorithms for multilayer networks

Tarmo Nurmi*, Mikko Kivela

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)5803-5817
Number of pages15
JournalIEEE Transactions on Network Science and Engineering
Volume11
Issue number6
Early online date2 Sept 2024
DOIs
Publication statusPublished - 2024
MoE publication typeA1 Journal article-refereed

Keywords

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

Fingerprint

Dive into the research topics of 'Subnetwork enumeration algorithms for multilayer networks'. Together they form a unique fingerprint.

Cite this