ID: 0905.4155

Constrained Markovian dynamics of random graphs

May 26, 2009

View on ArXiv

Similar papers 2

Semi-Markov Graph Dynamics

May 11, 2011

85% Match
Marco Raberto, Fabio Rapallo, Enrico Scalas
Probability
Physics and Society

In this paper, we outline a model of graph (or network) dynamics based on two ingredients. The first ingredient is a Markov chain on the space of possible graphs. The second ingredient is a semi-Markov counting process of renewal type. The model consists in subordinating the Markov chain to the semi-Markov counting process. In simple words, this means that the chain transitions occur at random time instants called epochs. The model is quite rich and its possible connections w...

Find SimilarView on arXiv

Replica methods for loopy sparse random graphs

January 29, 2016

85% Match
A C C Coolen
Disordered Systems and Neura...
Statistical Mechanics

I report on the development of a novel statistical mechanical formalism for the analysis of random graphs with many short loops, and processes on such graphs. The graphs are defined via maximum entropy ensembles, in which both the degrees (via hard constraints) and the adjacency matrix spectrum (via a soft constraint) are prescribed. The sum over graphs can be done analytically, using a replica formalism with complex replica dimensions. All known results for tree-like graphs ...

Find SimilarView on arXiv

Uniform sampling of undirected and directed graphs with a fixed degree sequence

December 3, 2009

85% Match
Annabell Berger, Matthias Müller-Hannemann
Discrete Mathematics
Data Structures and Algorith...

Many applications in network analysis require algorithms to sample uniformly at random from the set of all graphs with a prescribed degree sequence. We present a Markov chain based approach which converges to the uniform distribution of all realizations for both the directed and undirected case. It remains an open challenge whether these Markov chains are rapidly mixing. For the case of directed graphs, we also explain in this paper that a popular switching algorithm fails ...

Find SimilarView on arXiv

Random walks on graphs: ideas, techniques and results

July 6, 2005

85% Match
R. Burioni, D. Cassi
Statistical Mechanics

Random walks on graphs are widely used in all sciences to describe a great variety of phenomena where dynamical random processes are affected by topology. In recent years, relevant mathematical results have been obtained in this field, and new ideas have been introduced, which can be fruitfully extended to different areas and disciplines. Here we aim at giving a brief but comprehensive perspective of these progresses, with a particular emphasis on physical aspects.

Find SimilarView on arXiv

Generating constrained random graphs using multiple edge switches

December 14, 2010

85% Match
Lionel Tabourier, Camille Roth, Jean-Philippe Cointet
Social and Information Netwo...
Physics and Society

The generation of random graphs using edge swaps provides a reliable method to draw uniformly random samples of sets of graphs respecting some simple constraints, e.g. degree distributions. However, in general, it is not necessarily possible to access all graphs obeying some given con- straints through a classical switching procedure calling on pairs of edges. We therefore propose to get round this issue by generalizing this classical approach through the use of higher-order ...

Find SimilarView on arXiv

Controlling edge dynamics in complex networks

December 27, 2011

85% Match
Tamás Nepusz, Tamás Vicsek
Physics and Society
Statistical Mechanics
Social and Information Netwo...

The interaction of distinct units in physical, social, biological and technological systems naturally gives rise to complex network structures. Networks have constantly been in the focus of research for the last decade, with considerable advances in the description of their structural and dynamical properties. However, much less effort has been devoted to studying the controllability of the dynamics taking place on them. Here we introduce and evaluate a dynamical process defi...

Find SimilarView on arXiv

Evolving Clustered Random Networks

August 4, 2008

85% Match
Shweta Bansal, Shashank Khandelwal, Lauren Ancel Meyers
Discrete Mathematics
Physics and Society

We propose a Markov chain simulation method to generate simple connected random graphs with a specified degree sequence and level of clustering. The networks generated by our algorithm are random in all other respects and can thus serve as generic models for studying the impacts of degree distributions and clustering on dynamical processes as well as null models for detecting other structural properties in empirical networks.

Find SimilarView on arXiv

Kinetic Theory of Random Graphs

March 17, 2005

85% Match
E. Ben-Naim, P. L. Krapivsky
Statistical Mechanics
Disordered Systems and Neura...

Statistical properties of evolving random graphs are analyzed using kinetic theory. Treating the linking process dynamically, structural characteristics such as links, paths, cycles, and components are obtained analytically using the rate equation approach. Scaling laws for finite systems are derived using extreme statistics and scaling arguments.

Find SimilarView on arXiv

Entropic Dynamics of Networks

February 4, 2021

85% Match
Felipe Xavier Costa, Pedro Pessoa
Physics and Society
Statistical Mechanics
Social and Information Netwo...

Here we present the entropic dynamics formalism for networks. That is, a framework for the dynamics of graphs meant to represent a network derived from the principle of maximum entropy and the rate of transition is obtained taking into account the natural information geometry of probability distributions. We apply this framework to the Gibbs distribution of random graphs obtained with constraints on the node connectivity. The information geometry for this graph ensemble is ca...

Find SimilarView on arXiv

Moments of Uniform Random Multigraphs with Fixed Degree Sequences

September 19, 2019

85% Match
Philip S. Chodrow
Social and Information Netwo...
Probability
Data Analysis, Statistics an...
Physics and Society

We study the expected adjacency matrix of a uniformly random multigraph with fixed degree sequence $\mathbf{d} \in \mathbb{Z}_+^n$. This matrix arises in a variety of analyses of networked data sets, including modularity-maximization and mean-field theories of spreading processes. Its structure is well-understood for large, sparse, simple graphs: the expected number of edges between nodes $i$ and $j$ is roughly $\frac{d_id_j}{\sum_\ell{d_\ell}}$. Many network data sets are ne...

Find SimilarView on arXiv