Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConstruction and Random Generation of Hypergraphs with Prescribed Degree and Dimension Sequences
206
0
0.0
(
0
)
Added by
Debabrota Basu
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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.
rate research
Read More
We study the realizability of simplicial complexes with a given pair of integer sequences, representing the node degree distribution and facet size distribution, respectively. While the $s$-uniform variant of the problem is $mathsf{NP}$-complete when $s geq 3$, we identify two populations of input sequences, most of which can be solved in polynomial time using a recursive algorithm that we contribute. Combining with a sampler for the simplicial configuration model [Young $textit{et al.}$, Phys. Rev. E $textbf{96}$, 032312 (2017)], we facilitate efficient sampling of simplicial ensembles from arbitrary degree and size distributions. We find that, contrary to expectations based on dyadic networks, increasing nodes degrees reduces the number of loops in simplicial complexes. Our work unveils a fundamental constraint on the degree-size sequences and sheds light on further analysis of higher-order phenomena based on local structures.
We find an asymptotic enumeration formula for the number of simple $r$-uniform hypergraphs with a given degree sequence, when the number of edges is sufficiently large. The formula is given in terms of the solution of a system of equations. We give sufficient conditions on the degree sequence which guarantee existence of a solution to this system. Furthermore, we solve the system and give an explicit asymptotic formula when the degree sequence is close to regular. This allows us to establish several properties of the degree sequence of a random $r$-uniform hypergraph with a given number of edges. More specifically, we compare the degree sequence of a random $r$-uniform hypergraph with a given number edges to certain models involving sequences of binomial or hypergeometric random variables conditioned on their sum.
Random graph null models have found widespread application in diverse research communities analyzing network datasets, including social, information, and economic networks, as well as food webs, protein-protein interactions, and neuronal networks. The most popular family of random graph null models, called configuration models, are defined as uniform distributions over a space of graphs with a fixed degree sequence. Commonly, properties of an empirical network are compared to properties of an ensemble of graphs from a configuration model in order to quantify whether empirical network properties are meaningful or whether they are instead a common consequence of the particular degree sequence. In this work we study the subtle but important decisions underlying the specification of a configuration model, and investigate the role these choices play in graph sampling procedures and a suite of applications. We place particular emphasis on the importance of specifying the appropriate graph labeling (stub-labeled or vertex-labeled) under which to consider a null model, a choice that closely connects the study of random graphs to the study of random contingency tables. We show that the choice of graph labeling is inconsequential for studies of simple graphs, but can have a significant impact on analyses of multigraphs or graphs with self-loops. The importance of these choices is demonstrated through a series of three vignettes, analyzing network datasets under many different configuration models and observing substantial differences in study conclusions under different models. We argue that in each case, only one of the possible configuration models is appropriate. While our work focuses on undirected static networks, it aims to guide the study of directed networks, dynamic networks, and all other network contexts that are suitably studied through the lens of random graph null models.
Many complex systems involve direct interactions among more than two entities and can be represented by hypergraphs, in which hyperedges encode higher-order interactions among an arbitrary number of nodes. To analyze structures and dynamics of given hypergraphs, a solid practice is to compare them with those for randomized hypergraphs that preserve some specific properties of the original hypergraphs. In the present study, we propose a family of such reference models for hypergraphs, called the hyper dK-series, by extending the so-called dK-series for dyadic networks to the case of hypergraphs. The hyper dK-series preserves up to the individual nodes degree, nodes degree correlation, nodes redundancy coefficient, and/or the hyperedges size depending on the parameter values. We also apply the hyper dK-series to numerical simulations of epidemic spreading and evolutionary game dynamics on empirical hypergraphs.
Let mu be a computable ergodic shift-invariant measure over the Cantor space. Providing a constructive proof of Shannon-McMillan-Breiman theorem, Vyugin proved that if a sequence x is Martin-Lof random w.r.t. mu then the strong effective dimension Dim(x) of x equals the entropy of mu. Whether its effective dimension dim(x) also equals the entropy was left as an problem question. In this paper we settle this problem, providing a positive answer. A key step in the proof consists in extending recent results on Birkhoffs ergodic theorem for Martin-Lof random sequences.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
