Projects per year
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 language | English |
---|---|
Pages (from-to) | 5803-5817 |
Number of pages | 15 |
Journal | IEEE Transactions on Network Science and Engineering |
Volume | 11 |
Issue number | 6 |
Early online date | 2 Sept 2024 |
DOIs | |
Publication status | Published - 2024 |
MoE publication type | A1 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.Projects
- 1 Active
-
Kivelä Mikko / AoF Fellow Salary: Generalized network representation methods for understanding polarization and group formation
Kivelä, M. (Principal investigator), Yuan, Y. (Project Member) & Urena Carrion, J. (Project Member)
01/09/2022 → 31/08/2027
Project: Academy of Finland: Other research funding