ID: 1404.2769

Random graph ensembles with many short loops

April 10, 2014

View on ArXiv

Similar papers 4

The entropy of network ensembles

February 20, 2008

82% Match
Ginestra Bianconi
Disordered Systems and Neura...
Statistical Mechanics

In this paper we generalize the concept of random networks to describe networks with non trivial features by a statistical mechanics approach. This framework is able to describe ensembles of undirected, directed as well as weighted networks. These networks might have not trivial community structure or, in the case of networks embedded in a given space, non trivial distance dependence of the link probability. These ensembles are characterized by their entropy which evaluate th...

Find SimilarView on arXiv

Connectedness matters: Construction and exact random sampling of connected graphs

September 8, 2020

82% Match
Szabolcs Horvát, Carl D. Modes
Physics and Society
Discrete Mathematics
Combinatorics

We describe a new method for the random sampling of connected networks with a specified degree sequence. We consider both the case of simple graphs and that of loopless multigraphs. The constraints of fixed degrees and of connectedness are two of the most commonly needed ones when constructing null models for the practical analysis of physical or biological networks. Yet handling these constraints, let alone combining them, is non-trivial. Our method builds on a recently intr...

Find SimilarView on arXiv

Unbiased sampling of network ensembles

June 4, 2014

82% Match
Tiziano Squartini, Rossana Mastrandrea, Diego Garlaschelli
Methodology
Social and Information Netwo...
Physics and Society

Sampling random graphs with given properties is a key step in the analysis of networks, as random ensembles represent basic null models required to identify patterns such as communities and motifs. An important requirement is that the sampling process is unbiased and efficient. The main approaches are microcanonical, i.e. they sample graphs that match the enforced constraints exactly. Unfortunately, when applied to strongly heterogeneous networks (like most real-world example...

Find SimilarView on arXiv

Graph and Network Theory in Physics

February 18, 2013

82% Match
Ernesto Estrada
Mathematical Physics
Physics and Society

A book Chapter consisting of some of the main areas of research in graph theory applied to physics. It includes graphs in condensed matter theory, such as the tight-binding and the Hubbard model. It follows the study of graph theory and statistical physics by means of the analysis of the Potts model. Then, we consider the use of graph polynomials in solving Feynman integrals, graphs and electrical networks, vibrational analysis in networked systems and random graphs. The seco...

Find SimilarView on arXiv

Free-energy density functional for Strauss's model of transitive networks

May 19, 2022

82% Match
Diego Escribano, José A. Cuesta
Statistical Mechanics
Physics and Society

Ensemble models of graphs are one of the most important theoretical tools to study complex networks. Among them, exponential random graphs (ERGs) have proven to be very useful in the analysis of social networks. In this paper we develop a technique, borrowed from the statistical mechanics of lattice gases, to solve Strauss's model of transitive networks. This model was introduced long ago as an ERG ensemble for networks with high clustering and exhibits a first-order phase tr...

Find SimilarView on arXiv

Randomness and Complexity in Networks

November 5, 2007

82% Match
T. S. Evans
Statistical Mechanics

I start by reviewing some basic properties of random graphs. I then consider the role of random walks in complex networks and show how they may be used to explain why so many long tailed distributions are found in real data sets. The key idea is that in many cases the process involves copying of properties of near neighbours in the network and this is a type of short random walk which in turn produce a natural preferential attachment mechanism. Applying this to networks of fi...

Find SimilarView on arXiv

Statistical ensemble of scale-free random graphs

April 9, 2001

82% Match
Z. Burda, J. D. Correia, A. Krzywicki
Statistical Mechanics
Disordered Systems and Neura...

A thorough discussion of the statistical ensemble of scale-free connected random tree graphs is presented. Methods borrowed from field theory are used to define the ensemble and to study analytically its properties. The ensemble is characterized by two global parameters, the fractal and the spectral dimensions, which are explicitly calculated. It is discussed in detail how the geometry of the graphs varies when the weights of the nodes are modified. The stability of the scale...

Find SimilarView on arXiv

Kinetic Theory of Random Graphs: from Paths to Cycles

August 27, 2004

82% Match
E. Ben-Naim, P. L. Krapivsky
Statistical Mechanics

Structural properties of evolving random graphs are investigated. Treating linking as a dynamic aggregation process, rate equations for the distribution of node to node distances (paths) and of cycles are formulated and solved analytically. At the gelation point, the typical length of paths and cycles, l, scales with the component size k as l ~ k^{1/2}. Dynamic and finite-size scaling laws for the behavior at and near the gelation point are obtained. Finite-size scaling laws ...

Find SimilarView on arXiv

Very large graphs

February 1, 2009

81% Match
Laszlo Lovasz
Combinatorics
Probability

In the last decade it became apparent that a large number of the most interesting structures and phenomena of the world can be described by networks: separable elements, with connections (or interactions) between certain pairs of them. These huge networks pose exciting challenges for the mathematician. Graph Theory (the mathematical theory of networks) faces novel, unconventional problems: these very large networks (like the Internet) are never completely known, in most cas...

Find SimilarView on arXiv

Self-Sustaining Oscillations in Complex Networks of Excitable Elements

September 2, 2010

81% Match
Patrick McGraw, Michael Menzinger
Disordered Systems and Neura...
Neurons and Cognition

Random networks of symmetrically coupled, excitable elements can self-organize into coherently oscillating states if the networks contain loops (indeed loops are abundant in random networks) and if the initial conditions are sufficiently random. In the oscillating state, signals propagate in a single direction and one or a few network loops are selected as driving loops in which the excitation circulates periodically. We analyze the mechanism, describe the oscillating states,...

Find SimilarView on arXiv