ML p(r)ior | New classes of degree sequences with fast mixing swap Markov chain sampling

New classes of degree sequences with fast mixing swap Markov chain sampling

2016-01-29
In network modeling of complex systems one is often required to sample random realizations of networks that obey a given set of constraints, usually in form of graph measures. A much studied class of problems targets uniform sampling of simple graphs with given degree sequence or also with given degree correlations expressed in the form of a joint degree matrix. One approach is to use Markov chains based on edge switches (swaps) that preserve the constraints, are irreducible (ergodic) and fast mixing. In 1999, Kannan, Tetali and Vempala (KTV) proposed a simple swap Markov chain for sampling graphs with given degree sequence and conjectured that it mixes rapidly (in poly-time) for arbitrary degree sequences. While the conjecture is still open, it was proven for special degree sequences, in particular, for those of undirected and directed regular simple graphs, of half-regular bipartite graphs, and of graphs with certain bounded maximum degrees. Here we prove the fast mixing KTV conjecture for novel, exponentially large classes of irregular degree sequences. Our method is based on a canonical decomposition of degree sequences into split graph degree sequences, a structural theorem for the space of graph realizations and on a factorization theorem for Markov chains. After introducing bipartite splitted degree sequences, we also generalize the canonical split graph decomposition for bipartite and directed graphs.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2019-05-08

We show that the graph transformation problem of turning a simple graph into an Eulerian one by a mi… show more
PDF

Highlights - Most important sentences from the article

2019-01-28

We investigate a covering problem in $3$-uniform hypergraphs ($3$-graphs): given a $3$-graph $F$, wh… show more
PDF

Highlights - Most important sentences from the article

2019-03-15

Since 1997 a considerable effort has been spent to study the mixing time of \textbf{swap} (switch) M… show more
PDF

Highlights - Most important sentences from the article

2019-01-07

For every fixed integer $k \geq 1$, we prove that $k$-Edge Colouring is fixed-parameter-tractable wh… show more
PDF

Highlights - Most important sentences from the article

2014-06-10

This research establishes that many real-world networks exhibit bounded expansion, a strong notion o… show more
PDF

Highlights - Most important sentences from the article

2018-09-08

We consider the problem of determining the maximal $\alpha \in (0,1]$ such that every matching $M$ o… show more
PDF

Highlights - Most important sentences from the article

2018-12-07

We show that a simple Markov chain, the Glauber dynamics, can efficiently sample independent sets al… show more
PDF

Highlights - Most important sentences from the article

2018-02-11

We study a restricted form of list colouring, for which every pair of lists that correspond to adjac… show more
PDF

Highlights - Most important sentences from the article

2019-04-26
1904.11861 | math.PR

We study the following preferential attachment variant of the classical Erdos-Renyi random graph pro… show more
PDF

Highlights - Most important sentences from the article

2018-03-04
1803.01338 | cs.DM

The switch Markov chain has been extensively studied as the most natural Markov Chain Monte Carlo ap… show more
PDF

Highlights - Most important sentences from the article

2018-07-12
1807.04803 | math.CO

A maximal $\varepsilon$-near perfect matching is a maximal matching which covers at least $(1-\varep… show more
PDF

Highlights - Most important sentences from the article

2018-09-14
1809.05443 | cs.DM

A graph $G$ realizes the degree sequence $S$ if the degrees of its vertices is $S$. Hakimi gave a ne… show more
PDF

Highlights - Most important sentences from the article

2018-08-07

Any triangle-free graph on $n$ vertices with minimum degree at least $d$ contains a bipartite induce… show more
PDF

Highlights - Most important sentences from the article

2019-03-04
1903.01342 | math.PR

We establish and generalise several bounds for various random walk quantities including the mixing t… show more
PDF

Highlights - Most important sentences from the article

2017-06-13

We introduce and study the problem of optimizing arbitrary functions over degree sequences of hyperg… show more
PDF

Highlights - Most important sentences from the article

2016-09-16

The switching model is a Markov chain approach to sample graphs with fixed degree sequence uniformly… show more
PDF

Highlights - Most important sentences from the article