Source author record

Jennifer T. Chayes

Jennifer T. Chayes appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.PR math-ph math.CO math.MP math.ST Statistics Theory Cryptography and Security Data Structures and Algorithms Discrete Mathematics

Catalog footprint

What is connected

6works

9topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Sampling perspectives on sparse exchangeable graphs

Recent work has introduced sparse exchangeable graphs and the associated graphex framework, as a generalization of dense exchangeable graphs and the associated graphon framework. The development of this subject involves the interplay between the statistical modeling of network data, the theory of large graph limits, exchangeability, and network sampling. The purpose of the present paper is to clarify the relationships between these subjects by explaining each in terms of a certain natural sampling scheme associated with the graphex model. The first main technical contribution is the introduction of sampling convergence, a new notion of graph limit that generalizes left convergence so that it becomes meaningful for the sparse graph regime. The second main technical contribution is the demonstration that the (somewhat cryptic) notion of exchangeability underpinning the graphex framework is equivalent to a more natural probabilistic invariance expressed in terms of the sampling scheme.

preprint2016arXiv

Consistent nonparametric estimation for heavy-tailed sparse graphs

We study graphons as a non-parametric generalization of stochastic block models, and show how to obtain compactly represented estimators for sparse networks in this framework. Our algorithms and analysis go beyond previous work in several ways. First, we relax the usual boundedness assumption for the generating graphon and instead treat arbitrary integrable graphons, so that we can handle networks with long tails in their degree distributions. Second, again motivated by real-world applications, we relax the usual assumption that the graphon is defined on the unit interval, to allow latent position graphs where the latent positions live in a more general space, and we characterize identifiability for these graphons and their underlying position spaces. We analyze three algorithms. The first is a least squares algorithm, which gives an approximation we prove to be consistent for all square-integrable graphons, with errors expressed in terms of the best possible stochastic block model approximation to the generating graphon. Next, we analyze a generalization based on the cut norm, which works for any integrable graphon (not necessarily square-integrable). Finally, we show that clustering based on degrees works whenever the underlying degree distribution is atomless. Unlike the previous two algorithms, this third one runs in polynomial time.

preprint2015arXiv

Private Graphon Estimation for Sparse Graphs

We design algorithms for fitting a high-dimensional statistical model to a large, sparse network without revealing sensitive information of individual members. Given a sparse input graph $G$, our algorithms output a node-differentially-private nonparametric block model approximation. By node-differentially-private, we mean that our output hides the insertion or removal of a vertex and all its adjacent edges. If $G$ is an instance of the network obtained from a generative nonparametric model defined in terms of a graphon $W$, our model guarantees consistency, in the sense that as the number of vertices tends to infinity, the output of our algorithm converges to $W$ in an appropriate version of the $L_2$ norm. In particular, this means we can estimate the sizes of all multi-way cuts in $G$. Our results hold as long as $W$ is bounded, the average degree of $G$ grows at least like the log of the number of vertices, and the number of blocks goes to infinity at an appropriate rate. We give explicit error bounds in terms of the parameters of the model; in several settings, our bounds improve on or match known nonprivate results.

preprint2014arXiv

Asymptotic behavior and distributional limits of preferential attachment graphs

We give an explicit construction of the weak local limit of a class of preferential attachment graphs. This limit contains all local information and allows several computations that are otherwise hard, for example, joint degree distributions and, more generally, the limiting distribution of subgraphs in balls of any given radius $k$ around a random vertex in the preferential attachment graph. We also establish the finite-volume corrections which give the approach to the limit.

preprint2010arXiv

Tight Bounds for Mixing of the Swendsen-Wang Algorithm at the Potts Transition Point

We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice Z^d - heat bath dynamics and the Swendsen-Wang algorithm - and prove that, under certain circumstances, the mixing in these algorithms is torpid or slow. In particular, we show that for heat bath dynamics throughout the region of phase coexistence, and for the Swendsen-Wang algorithm at the transition point, the mixing time in a box of side length L with periodic boundary conditions has upper and lower bounds which are exponential in L^{d-1}. This work provides the first upper bound of this form for the Swendsen-Wang algorithm, and gives lower bounds for both algorithms which significantly improve the previous lower bounds that were exponential in L/(log L)^2.

preprint2001arXiv

The Scaling Window of the 2-SAT Transition

We consider the random 2-satisfiability problem, in which each instance is a formula that is the conjunction of m clauses of the form (x or y), chosen uniformly at random from among all 2-clauses on n Boolean variables and their negations. As m and n tend to infinity in the ratio m/n --> alpha, the problem is known to have a phase transition at alpha_c = 1, below which the probability that the formula is satisfiable tends to one and above which it tends to zero. We determine the finite-size scaling about this transition, namely the scaling of the maximal window W(n,delta) = (alpha_-(n,delta),alpha_+(n,delta)) such that the probability of satisfiability is greater than 1-delta for alpha < alpha_- and is less than delta for alpha > alpha_+. We show that W(n,delta)=(1-Theta(n^{-1/3}),1+Theta(n^{-1/3})), where the constants implicit in Theta depend on delta. We also determine the rates at which the probability of satisfiability approaches one and zero at the boundaries of the window. Namely, for m=(1+epsilon)n, where epsilon may depend on n as long as |epsilon| is sufficiently small and |epsilon|*n^(1/3) is sufficiently large, we show that the probability of satisfiability decays like exp(-Theta(n*epsilon^3)) above the window, and goes to one like 1-Theta(1/(n*|epsilon|^3)) below the window. We prove these results by defining an order parameter for the transition and establishing its scaling behavior in n both inside and outside the window. Using this order parameter, we prove that the 2-SAT phase transition is continuous with an order parameter critical exponent of 1. We also determine the values of two other critical exponents, showing that the exponents of 2-SAT are identical to those of the random graph.