Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Random graph ensembles
View through CrossRef
This chapter presents some theoretical tools for defining random graph ensembles systematically via soft or hard topological constraints including working through some properties of the Erdös-Rényi random graph ensemble, which is the simplest non-trivial random graph ensemble where links appear between two nodes with a fixed probability p. The chapter sets out the central representation of graph generation as the result of a discrete-time Markovian stochastic process. This unites the two flavours of graph generation approaches – because they can be viewed as simply moving forwards or backwards through this representation. It is possible to define a random graph by an algorithm, and then calculate the associated stationary probability. The alternative approach is to specify sampling weights and then to construct an algorithm that will have these weights as the stationary probabilities upon convergence.
Title: Random graph ensembles
Description:
This chapter presents some theoretical tools for defining random graph ensembles systematically via soft or hard topological constraints including working through some properties of the Erdös-Rényi random graph ensemble, which is the simplest non-trivial random graph ensemble where links appear between two nodes with a fixed probability p.
The chapter sets out the central representation of graph generation as the result of a discrete-time Markovian stochastic process.
This unites the two flavours of graph generation approaches – because they can be viewed as simply moving forwards or backwards through this representation.
It is possible to define a random graph by an algorithm, and then calculate the associated stationary probability.
The alternative approach is to specify sampling weights and then to construct an algorithm that will have these weights as the stationary probabilities upon convergence.
Related Results
Ensembles with hard constraints
Ensembles with hard constraints
This chapter introduces random graph ensembles involving hard constraints such as setting a fixed total number of links or fixed degree sequence, including properties of the partit...
Introduction
Introduction
This introductory chapter sets the scene for the material which follows by briefly introducing the study of networks and describing their wide scope of application. It discusses th...
Topics in Algorithmic Graph Theory
Topics in Algorithmic Graph Theory
Algorithmic graph theory has been expanding at an extremely rapid rate since the middle of the twentieth century, in parallel with the growth of computer science and the accompanyi...
Applications of random graphs
Applications of random graphs
This chapter reviews graph generation techniques in the context of applications. The first case study is power grids, where proposed strategies to prevent blackouts have been teste...
Topics in Chromatic Graph Theory
Topics in Chromatic Graph Theory
Chromatic graph theory is a thriving area that uses various ideas of 'colouring' (of vertices, edges, and so on) to explore aspects of graph theory. It has links with other areas o...
American Theatre Ensembles
American Theatre Ensembles
In this volume, Mike Vanden Heuvel and contributors present the history, processes and achievements of American theatre companies renowned for their use of collective and/or ensemb...
Exchange In Oceania
Exchange In Oceania
Abstract
In their previous book, Structural Models in Anthropology, anthropologist Per Hage and mathematician Frank Harary used graph theory, a branch of pure mathem...
Topics in Topological Graph Theory
Topics in Topological Graph Theory
The use of topological ideas to explore various aspects of graph theory, and vice versa, is a fruitful area of research. There are links with other areas of mathematics, such as de...