Back to Search
Start Over
Construction and Random Generation of Hypergraphs with Prescribed Degree and Dimension Sequences
- 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
- Subjects :
- FOS: Computer and information sciences
050101 languages & linguistics
Hypergraph
Computer science
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
02 engineering and technology
Statistics - Applications
Matrix (mathematics)
symbols.namesake
Computer Science - Data Structures and Algorithms
FOS: Mathematics
0202 electrical engineering, electronic engineering, information engineering
Mathematics - Combinatorics
Leverage (statistics)
Data Structures and Algorithms (cs.DS)
Applications (stat.AP)
0501 psychology and cognitive sciences
Clustering coefficient
Social and Information Networks (cs.SI)
Discrete mathematics
[INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB]
05 social sciences
Estimator
Computer Science - Social and Information Networks
Markov chain Monte Carlo
[MATH.MATH-PR]Mathematics [math]/Probability [math.PR]
symbols
020201 artificial intelligence & image processing
Combinatorics (math.CO)
Importance sampling
Subjects
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