Generating random graphs with prescribed graphlet frequency bounds derived from probabilistic networks
PLOS One · 2025
DOI: 10.1371/journal.pone.0328639 ↗Kurz gefasst
Fachartikel in der Zeitschrift PLOS One, 2025. Verfasst von Bram Mornie und 3 weiteren Autor:innen. Beteiligte Einrichtung: IDLab, Department of Information Technology, Ghent University - imec, Ghent, Belgium. Hauptthemen laut MEDLINE: Algorithms, Computational Biology, Models, Statistical. Die Arbeit nennt 51 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Bijzonder Onderzoeksfonds UGent.
Abstract (Originalsprache)
Testing or benchmarking network algorithms in bioinformatics requires a diverse set of networks with realistic properties. Real networks are often supplemented by randomly generated synthetic ones, but most graph generative models do not take into account the distribution of subgraph patterns, i.e. motifs or graphlets . Moreover, in many cases, biological interactions are uncertain events and must be modeled by probabilistic graph edges. The uncertainty is often ignored in practice, which can lead to incorrect conclusions about the properties of biological networks. In this work, we instead derive bounds on the graphlet counts and degree distribution of a probabilistic target network and use this information as input to a novel random graph generation algorithm. The algorithm grows graphs incrementally by making small modifications in every step, which allows for an efficient graphlet counting method. Using this method, we can update graphlet counts after each iteration in a time independent of the total node number on sparse graphs. We evaluate our model on synthetic and real networks of different sizes and with different degrees of uncertainty. Although computation times strongly depend on the size of graphlets taken into account, our experiments demonstrate that graphs with over 10 000 edges and well-controlled frequencies of all three- and four-node graphlets can be generated in under an hour.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- IDLab, Department of Information Technology, Ghent University - imec, Ghent, Belgium.
ORCID-Profile: Bram Mornie
Förderung
- Bijzonder Onderzoeksfonds UGent
Zitieren
APA
Mornie, B., Colle, D., Audenaert, P., & Pickavet, M. (2025). Generating random graphs with prescribed graphlet frequency bounds derived from probabilistic networks. PLOS One. https://doi.org/10.1371/journal.pone.0328639
Vancouver
Mornie B, Colle D, Audenaert P, Pickavet M. Generating random graphs with prescribed graphlet frequency bounds derived from probabilistic networks. PLOS One. 2025. doi:10.1371/journal.pone.0328639
BibTeX
@article{Mornie2025,
author = {Mornie, Bram and Colle, Didier and Audenaert, Pieter and Pickavet, Mario},
title = {Generating random graphs with prescribed graphlet frequency bounds derived from probabilistic networks},
journal = {PLOS One},
year = {2025},
doi = {10.1371/journal.pone.0328639}
}
EUVIMED