EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Generating random graphs with prescribed graphlet frequency bounds derived from probabilistic networks

Bram Mornie iD, Didier Colle, Pieter Audenaert, Mario Pickavet

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

AlgorithmsComputational BiologyModels, StatisticalProbabilityComputer Simulation

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}
}
Kostenlos starten →