Catalogue Search | MBRL
Are you sure you want to remove the book from the shelf?
{{itemTitle}}
5,863
result(s) for
"Random graphs"
Sort by:
ESTIMATING AND UNDERSTANDING EXPONENTIAL RANDOM GRAPH MODELS
We introduce a method for the theoretical analysis of exponential random graph models. The method is based on a large-deviations approximation to the normalizing constant shown to be consistent using theory developed by Chatterjee and Varadhan [European J. Combin. 32 (2011) 1000—1017]. The theory explains a host of difficulties encountered by applied workers: many distinct models have essentially the same MLE, rendering the problems \"practically\" ill-posed. We give the first rigorous proofs of \"degeneracy\" observed in these models. Here, almost all graphs have essentially no edges or are essentially complete. We supplement recent work of Bhamidi, Bresler and Sly [2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2008) 803—812 IEEE] showing that for many models, the extra sufficient statistics are useless: most realizations look like the results of a simple Erdős—Rényi model. We also find classes of models where the limiting graphs differ from Erdős—Rényi graphs. A limitation of our approach, inherited from the limitation of graph limit theory, is that it works only for dense graphs.
Journal Article
Graph theoretic methods in multiagent networks
This accessible book provides an introduction to the analysis and design of dynamic multiagent networks. Such networks are of great interest in a wide range of areas in science and engineering, including: mobile sensor networks, distributed robotics such as formation flying and swarming, quantum networks, networked economics, biological synchronization, and social networks. Focusing on graph theoretic methods for the analysis and synthesis of dynamic multiagent networks, the book presents a powerful new formalism and set of tools for networked systems.
The book's three sections look at foundations, multiagent networks, and networks as systems. The authors give an overview of important ideas from graph theory, followed by a detailed account of the agreement protocol and its various extensions, including the behavior of the protocol over undirected, directed, switching, and random networks. They cover topics such as formation control, coverage, distributed estimation, social networks, and games over networks. And they explore intriguing aspects of viewing networks as systems, by making these networks amenable to control-theoretic analysis and automatic synthesis, by monitoring their dynamic evolution, and by examining higher-order interaction models in terms of simplicial complexes and their applications.
The book will interest graduate students working in systems and control, as well as in computer science and robotics. It will be a standard reference for researchers seeking a self-contained account of system-theoretic aspects of multiagent networks and their wide-ranging applications.
This book has been adopted as a textbook at the following universities:
University of Stuttgart, GermanyRoyal Institute of Technology, SwedenJohannes Kepler University, AustriaGeorgia Tech, USAUniversity of Washington, USAOhio University, USA
eBook
separable model for dynamic networks
Models of dynamic networks—networks that evolve over time—have manifold applications. We develop a discrete time generative model for social network evolution that inherits the richness and flexibility of the class of exponential family random‐graph models. The model—a separable temporal exponential family random‐graph model—facilitates separable modelling of the tie duration distributions and the structural dynamics of tie formation. We develop likelihood‐based inference for the model and provide computational algorithms for maximum likelihood estimation. We illustrate the interpretability of the model in analysing a longitudinal network of friendship ties within a school.
Journal Article
The front of the epidemic spread and first passage percolation
We establish a connection between epidemic models on random networks with general infection times considered in Barbour and Reinert (2013) and first passage percolation. Using techniques developed in Bhamidi, van der Hofstad and Hooghiemstra (2012), when each vertex has infinite contagious periods, we extend results on the epidemic curve in Barbour and Reinert (2013) from bounded degree graphs to general sparse random graphs with degrees having finite second moments as n → ∞, with an appropriate X
2log+
X condition. We also study the epidemic trail between the source and typical vertices in the graph.
Journal Article
Cliques in rank-1 random graphs
We study the asymptotic behavior of the clique number in rank-1 inhomogeneous random graphs, where edge probabilities between vertices are roughly proportional to the product of their vertex weights. We show that the clique number is concentrated on at most two consecutive integers, for which we provide an expression. Interestingly, the order of the clique number is primarily determined by the overall edge density, with the inhomogeneity only affecting multiplicative constants or adding at most a log log (n) multiplicative factor. For sparse enough graphs the clique number is always bounded and the effect of inhomogeneity completely vanishes.
Journal Article
LIMITS OF SPARSE CONFIGURATION MODELS AND BEYOND
We investigate structural properties of large, sparse random graphs through the lens of sampling convergence (Borgs et al. (Ann. Probab. 47 (2019) 2754–2800). Sampling convergence generalizes left convergence to sparse graphs, and describes the limit in terms of a graphex. We introduce a notion of sampling convergence for sequences of multigraphs, and establish the graphex limit for the configuration model, a preferential attachment model, the generalized random graph and a bipartite variant of the configuration model. The results for the configuration model, preferential attachment model and bipartite configurationmodel provide necessary and sufficient conditions for these random graph models to converge. The limit for the configuration model and the preferential attachment model is an augmented version of an exchangeable random graph model introduced by Caron and Fox (J. R. Stat. Soc. Ser. B. Stat. Methodol. 79 (2017) 1295–1366).
Journal Article
A large-deviations principle for all the components in a sparse inhomogeneous random graph
We study an inhomogeneous sparse random graph, GN, on [N]={1,⋯,N} as introduced in a seminal paper by Bollobás et al. (Random Struct Algorithms 31(1):3–122, 2007): vertices have a type (here in a compact metric space S), and edges between different vertices occur randomly and independently over all vertex pairs, with a probability depending on the two vertex types. In the limit N→∞, we consider the sparse regime, where the average degree is O(1). We prove a large-deviations principle with explicit rate function for the statistics of the collection of all the connected components, registered according to their vertex type sets, and distinguished according to being microscopic (of finite size) or macroscopic (of size ≍N). In doing so, we derive explicit logarithmic asymptotics for the probability that GN is connected. We present a full analysis of the rate function including its minimizers. From this analysis we deduce a number of limit laws, conditional and unconditional, which provide comprehensive information about all the microscopic and macroscopic components of GN. In particular, we recover the criterion for the existence of the phase transition given in Bollobás et al. (2007).
Journal Article
COMMUNITY DETECTION IN DENSE RANDOM NETWORKS
We formalize the problem of detecting a community in a network into testing whether in a given (random) graph there is a subgraph that is unusually dense. Specifically, we observe an undirected and unweighted graph on N nodes. Under the null hypothesis, the graph is a realization of an Erdős-Rényi graph with probability p₀. Under the (composite) alternative, there is an unknown subgraph of n nodes where the probability of connection is p₁ > p₀. We derive a detection lower bound for detecting such a subgraph in terms of N, n, p₀, p₁ and exhibit a test that achieves that lower bound. We do this both when p₀ is known and unknown. We also consider the problem of testing in polynomial-time. As an aside, we consider the problem of detecting a clique, which is intimately related to the planted clique problem. Our focus in this paper is in the quasi-normal regime where np₀ is either bounded away from zero, or tends to zero slowly.
Journal Article
Random networks, graphical models and exchangeability
We study conditional independence relationships for random networks and their interplay with exchangeability. We show that, for finitely exchangeable network models, the empirical subgraph densities are maximum likelihood estimates of their theoretical counterparts. We then characterize all possible Markov structures for finitely exchangeable random graphs, thereby identifying a new class of Markov network models corresponding to bidirected Kneser graphs. In particular, we demonstrate that the fundamental property of dissociatedness corresponds to a Markov property for exchangeable networks described by bidirected line graphs. Finally we study those exchangeable models that are also summarized in the sense that the probability of a network depends only on the degree distribution, and we identify a class of models that is dual to the Markov graphs of Frank and Strauss. Particular emphasis is placed on studying consistency properties of network models under the process of forming subnetworks and we show that the only consistent systems of Markov properties correspond to the empty graph, the bidirected line graph of the complete graph and the complete graph.
Journal Article