Back to Search Start Over

Construction and Random Generation of Hypergraphs with Prescribed Degree and Dimension Sequences

Authors :
Laurent Decreusefond
Stéphane Bressan
Debabrota Basu
Naheed Anjum Arafat
National University of Singapore (NUS)
Chalmers University of Technology [Göteborg]
Département Informatique et Réseaux (INFRES)
Télécom ParisTech
Laboratoire Traitement et Communication de l'Information (LTCI)
Institut Mines-Télécom [Paris] (IMT)-Télécom Paris
Data, Intelligence and Graphs (DIG)
Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris
ANR-17-CE40-0017,ASPAG,Analyse et Simulation Probabilistes des Algorithmes Géométriques(2017)
Source :
Lecture Notes in Computer Science ISBN: 9783030590505, DEXA (2), DEXA, DEXA, 2020, Bratislava, Slovenia
Publication Year :
2020
Publisher :
Springer International Publishing, 2020.

Abstract

We propose algorithms for construction and random generation of hypergraphs without loops and with prescribed degree and dimension sequences. The objective is to provide a starting point for as well as an alternative to Markov chain Monte Carlo approaches. Our algorithms leverage the transposition of properties and algorithms devised for matrices constituted of zeros and ones with prescribed row- and column-sums to hypergraphs. The construction algorithm extends the applicability of Markov chain Monte Carlo approaches when the initial hypergraph is not provided. The random generation algorithm allows the development of a self-normalised importance sampling estimator for hypergraph properties such as the average clustering coefficient.We prove the correctness of the proposed algorithms. We also prove that the random generation algorithm generates any hypergraph following the prescribed degree and dimension sequences with a non-zero probability. We empirically and comparatively evaluate the effectiveness and efficiency of the random generation algorithm. Experiments show that the random generation algorithm provides stable and accurate estimates of average clustering coefficient, and also demonstrates a better effective sample size in comparison with the Markov chain Monte Carlo approaches.<br />Comment: 21 pages, 3 figures

Details

ISBN :
978-3-030-59050-5
ISBNs :
9783030590505
Database :
OpenAIRE
Journal :
Lecture Notes in Computer Science ISBN: 9783030590505, DEXA (2), DEXA, DEXA, 2020, Bratislava, Slovenia
Accession number :
edsair.doi.dedup.....85e8417da0d6f8e7e7dfee43ae99841b
Full Text :
https://doi.org/10.1007/978-3-030-59051-2_9