Stochastic Processes on Sparse Graphs: Hydrodynamic Limits and Markov Approximations
Kavita Ramanan (Brown University)
5929 - 5940 of 22775 Results
Format results
Large Deviation Principle for the Norm of the Adjacency Matrix and the Laplacian Matrix of Inhomogeneous Erd\H{o}s-R\'enyi Random Graphs
Frank den Hollander (Leiden University)Diamagnetic response and phase stiffness for interacting isolated narrow bands
Dan Mao Massachusetts Institute of Technology (MIT)
Two aspects of quantum information theory in relation to holography
Rene Meyer Max-Planck Gesellschaft
Longitudinal Network Models, Log-Linear Multigraph Models, and Implications to Estimation and Testing Model Fit
Sonja Petrović (Illinois Institute of Technology)Vertexons and Embedded Graphon Mean Field Games
Peter Caines (McGill University)The night sky is part of the land: the ongoing colonization in astronomy research and space exploration.
Hilding Neilson Memorial University of Newfoundland
Measuring the distribution of binary black hole spins
Javier Roulet California Institute of Technology (Caltech)
Graphon Limit and Large Independent Sets in Uniform Random Cographs
Valentin Féray (Université de Lorraine)Graphon-valued Stochastic Processes
Siva Athreya (Indian Statistical Insitute)
Stochastic Processes on Sparse Graphs: Hydrodynamic Limits and Markov Approximations
Kavita Ramanan (Brown University)Abstract We consider interacting particle systems on suitable convergent sequences of sparse (or heterogeneous graphs) and show that the limiting dynamics of the associated neighborhood empirical measure process (the so-called hydrodynamic limit) can be autonomously characterized in terms of a non-Markovian process. We then describe Markovian approximations to the latter and provide examples where they are exact. This includes joint work with G. Cocomello and A. Ganguly.Large Deviation Principle for the Norm of the Adjacency Matrix and the Laplacian Matrix of Inhomogeneous Erd\H{o}s-R\'enyi Random Graphs
Frank den Hollander (Leiden University)Abstract We consider an inhomogeneous Erd\H{o}s-R\'enyi random graph $G_N$ with vertex set $[N] = \{1,\dots,N\}$ for which the pair of vertices $i,j \in [N]$, $i\neq j$, is connected by an edge with probability $r(\tfrac{i}{N},\tfrac{j}{N})$, independently of other pairs of vertices. Here, $r\colon\,[0,1]^2 \to (0,1)$ is a symmetric function that plays the role of a reference graphon. (1) Let $\lambda_N$ be the maximal eigenvalue of the \emph{adjacency matrix} of $G_N$. It is known that $\lambda_N/N$ satisfies an LDP with rate $N$ as $N \to \infty$. The associated rate function $\psi_r$ is given by a variational formula that involves the rate function $I_r$ of a large deviation principle on graphon space. We analyse this variational formula in order to identify the basic properties of $\psi_r$, especially when the reference graphon $r$ is of rank 1. (2) Let $\hat\lambda_N$ be the maximal eigenvalue of the \emph{Laplacian matrix} of $G_N$. We show that $\hat\lambda_N/N$ satisfies a downward LDP with rate $\binom{N}{2}$ and an upward LDP with rate $N$. The associated rate functions $\hat\psi_r$ and $\hat\psi^*_r$ are those of the downward LDP and upward LDP for the maximal degree in the graph. We identify the basic properties of both $hat\psi_r$ and $\hat\psi^*_r$.Diamagnetic response and phase stiffness for interacting isolated narrow bands
Dan Mao Massachusetts Institute of Technology (MIT)
Superconductivity in electronic systems, where the non-interacting bandwidth for a set of isolated bands is small compared to the scale of the interactions, is a non-perturbative problem. Here we present a theoretical framework for computing the electromagnetic response in the limit of zero frequency and vanishing wavenumber for the interacting problem, which controls the superconducting phase stiffness, without resorting to any mean-field approximation. Importantly, the contribution to the phase stiffness arises from (i) ``integrating-out" the remote bands that couple to the microscopic current operator, and (ii) the density-density interactions projected on to the isolated bands. We also obtain the electromagnetic response directly in the limit of an infinite gap to the remote bands, using the appropriate ``projected" gauge-transformations. These results can be used to obtain a conservative upper bound on the phase stiffness, and relatedly the superconducting transition temperature, with a few assumptions. In a companion article, we apply this formalism to a host of topologically (non-)trivial ``flat-band" systems, including twisted bilayer graphene.
Zoom link: https://pitp.zoom.us/j/99631762791?pwd=dU4yaU1wKzJNTisrazJjaUF2ODlXUT09
Two aspects of quantum information theory in relation to holography
Rene Meyer Max-Planck Gesellschaft
The fact black holes carry statistical entropy proportional to their horizon area implies that quantum information concepts are geometrized in gravity. This idea obtains a particular manifestation in the AdS/CFT correspondence, where it is believed that the quantum information content in the dual field theory state can be used to reconstruct the bulk space-time geometry. The calculation of entanglement entropy from geodesics in the bulk space-time have clarified this idea to some extend.
In this talk, I will consider two aspects of quantum information theory in relation to holography: First, I will discuss a refinement of entanglement entropy for systems with conserved charges, the so-called symmetry resolved entanglement. It measures the entanglement in a sector of fixed charge. I will present how to calculate the symmetry-resolved entanglement entanglement in two-dimensional conformal field theories with Kac-Moody symmetry, and also within W_3 higher spin theory. I will also discuss the geometric realization in the dual AdS space-time, and how the independent calculation there leads to a new test of the AdS3/CFT2 correspondence.
Second, I will discuss the large N limit of Nielsen's operator complexity on the SU(N) manifold, with a particular choice of cost function based on the Laplacian on the Lie algebra, which leads to polynomial (instead of exponential) penalty factors. I will first present numerical results that hint to the existence of chaotic and hence ergodic geodesic motion on the group manifold, as well show the existence of conjugate points. I will then discuss a mapping between the Euler-Arnold equation which governs the geodesic evolution, to the Euler equation of two-dimensional idea hydrodynamics, in the strict large N limit.Longitudinal Network Models, Log-Linear Multigraph Models, and Implications to Estimation and Testing Model Fit
Sonja Petrović (Illinois Institute of Technology)Abstract Consider longitudinal networks whose edges turn on and off according to a discrete-time Markov chain with exponential-family transition probabilities. We characterize when their joint distributions are also exponential families with the same parameter, and show that the permutation-uniform subclass of these chains permit interpretation as an independent, identically distributed sequence on the same state space. We apply these ideas to temporal exponential random graph models, for which permutation uniformity is well suited, and discuss mean-parameter convergence, dyadic independence, and exchangeability. The framework facilitates applying standard tools to longitudinal-network Markov chains from either asymptotics or single-observation exponential random graph models. The latter are often in log-linear form, allowing us to frame the problem of testing model fit through an exact conditional test whose p-value can be approximated efficiently in networks of both small and moderately large sizes. An important extension of this theory is to latent-variable blockmodels, an application which will be briefly discussed. This talk is based on joint work with William K. Schwartz, Hemanshu Kaul, Despina Stasi, Elizabeth Gross, Debdeep Pati, and Vishesh Karwa.Graphon Games
Francesca Parise (Cornell University)Abstract Many of today’s most promising technological systems involve very large numbers of autonomous agents that influence each other and make strategic decisions within a network structure. Examples include opinion dynamics, targeted marketing in social networks, economic exchange and international trade, product adoption and social contagion. While traditional tools for the analysis of these systems assumed that a social planner has full knowledge of the underlying game, when we turn to very large networks two issues emerge. First, collecting data about the exact network of interactions becomes very expensive or not at all possible because of privacy concerns. Second, methods for designing optimal interventions that rely on the exact network structure typically do not scale well with the population size. To obviate these issues, in this talk I will consider a framework in which the social planner designs interventions based on probabilistic instead of exact information about agent’s interactions. I will introduce the tool of “graphon games” as a way to formally describe strategic interactions in this setting and I will illustrate how this tool can be exploited to design asymptotically optimal interventions for general classes of network games, beyond the linear quadratic setting.Vertexons and Embedded Graphon Mean Field Games
Peter Caines (McGill University)Abstract An embedded vertexon sequence is the sequence of vertex sets of a sequence of graphs in a connected compact set $M$ in $R^{m}$ together with an asymptotically dense partition hierarchy of $M$. Vertexon sequences and the associated graph sequences have subsequential limit measures in $M$ and $M^2$ respectively, independent of the partition hierarchy within a large class. The differentiation of functions on vertexon limits with open support in $M,$ and certain directional derivatives in the support of the associated graphon measure in $M^2,$ may be defined. Consequently, subject to conditions, one may seek stationary node dependent Nash values for Embedded Graphon Mean Field Games (EGMFGs). An example will be given in the case of a class of Linear Quadratic Gaussian EGMFGs.\\ Work with Rinel Foguen-Tschuendom, Shuang Gao, Minyi HuangThe night sky is part of the land: the ongoing colonization in astronomy research and space exploration.
Hilding Neilson Memorial University of Newfoundland
It has been argued astronomy and astrophysics as a research field developed with the first telescope. At the same time that Galileo observed the phases of Venus and the moons of Jupiter, European Powers will colonizing the Americas and other parts of the world. This began a relationship between astronomy and colonization that continues today in terms of astronomers and nations building giant telescopes on Indigenous lands. In the future as private actors develop a new space industry we will see the export of this colonialism to Space, to the Moon and one day even to Mars. We are already seeing this today with the development of satellite constellations, some of which are visible by the unaided eye and with the multinational Artemis Accords for lunar exploration. In this talk I will review the relation between astronomy and colonization in the past, present, and future; and I will discuss steps educators and astronomers can take to address this in the classroom and how the field of astronomy and space exploration can be inclusive of Indigenous rights and voices.
Zoom link: https://pitp.zoom.us/j/95620288526?pwd=dW9ReW5FUVp3TWFmUVUxZjV5VFhNdz09
Motif Counting via Subgraph Sampling
Sumit Mukherjee (Columbia University)Abstract Consider the subgraph sampling model, where we observe a random subgraph of a given (possibly non random) large graph $G_n$, by choosing vertices of $G_n$ independently at random with probability $p_n$. In this setting, we study the question of estimating the number of copies $N(H,G_n)$ of a fixed motif/small graph (think of $H$ as edges, two stars, triangles) in the big graph $G_n$. We derive necessary and sufficient conditions for the consistency and the asymptotic normality of a natural Horvitz-Thompson (HT) type estimator. As it turns out, the asymptotic normality of the HT estimator exhibits an interesting fourth-moment phenomenon, which asserts that the HT estimator (appropriately centered and rescaled) converges in distribution to the standard normal whenever its fourth-moment converges to 3. We apply our results to several natural graph ensembles, such as sparse graphs with bounded degree, Erdős-Renyi random graphs, random regular graphs, and dense graphons. This talk is based on joint work with Bhaswar B. Bhattacharya and Sayan Das.Measuring the distribution of binary black hole spins
Javier Roulet California Institute of Technology (Caltech)
With over a hundred detections to date, the discoveries of compact binary mergers by gravitational wave observatories LIGO and Virgo have allowed us to start characterizing the astrophysical population of binary black holes. This task requires measuring the fifteen parameters (masses, spins, location, orientation, etc...) that characterize each merger event. However, these high dimensional distributions are challenging to describe due to the presence of nonlinear correlations and multiple modes. In this seminar I will describe a series of coordinate changes that, by identifying parameter combinations that control specific observable signatures in the data, remove these degeneracies and multimodality, making parameter estimation amenable. Among the new coordinates is a spin azimuth that can be measured surprisingly well in several cases, hinting that some black hole spins are misaligned with the orbit. This is very interesting because the degree of spin-orbit alignment is a robust discriminator between isolated and dynamical formation channels, which predict spins preferentially aligned with the orbit or randomly oriented, respectively. At the same time, I will show that the observed proportion of events with spins aligned versus anti-aligned with the orbit disfavors the hypothesis that the spin distribution is isotropic.
Zoom link: https://pitp.zoom.us/j/91820222881?pwd=YW9vR0xwTlBCVXg4UlRBNWxuUFhCQT09
Graphon Limit and Large Independent Sets in Uniform Random Cographs
Valentin Féray (Université de Lorraine)Abstract Cographs are by definition $P_4$-free graphs, i.e. graphs avoiding the path $P_4$ as induced subgraph. In this talk, we will consider a uniform random cograph with $n$ vertices, for large $n$. We shall describe the (random) graphon limit of this object, which is constructed using a Brownian excursion. Motivated by some probabilistic work around Erdős-Hajnal conjecture, we also consider large independent sets in uniform cographs. For both aspects, cographs behave differently from most other $H$-free random graphs. Based on joint work with F. Bassino, M. Bouvel, M. Drmota, L. Gerin, M. Maazoun and A. Pierrot.Graphon-valued Stochastic Processes
Siva Athreya (Indian Statistical Insitute)Abstract We will present out attempts thus far to develop a theory of graphon-valued stochastic processes. We will present a brief review of theory Graphons and dynamics constructed on the space of graphons. We shall construct and analyse a natural class of such processes arising from population genetics. In conclusion we shall present the challenges in our ongoing work on constructing dynamics where the edges and vertices interact with each other. This is joint work with Frank den Hollander and Adrian Roellin