ID: cond-mat/0408620

Kinetic Theory of Random Graphs: from Paths to Cycles

August 27, 2004

View on ArXiv

Similar papers 2

Directed cycles and related structures in random graphs: II--Dynamic properties

September 18, 2003

87% Match
Valmir C. Barbosa, Raul Donangelo, Sergio R. Souza
Statistical Mechanics

We study directed random graphs (random graphs whose edges are directed) as they evolve in discrete time by the addition of nodes and edges. For two distinct evolution strategies, one that forces the graph to a condition of near acyclicity at all times and another that allows the appearance of nontrivial directed cycles, we provide analytic and simulation results related to the distributions of degrees. Within the latter strategy, in particular, we investigate the appearance ...

Find SimilarView on arXiv

Growth and Optimality in Network Evolution

May 13, 2011

87% Match
Markus Brede
Disordered Systems and Neura...
Social and Information Netwo...
Adaptation and Self-Organizi...
Biological Physics

In this paper we investigate networks whose evolution is governed by the interaction of a random assembly process and an optimization process. In the first process, new nodes are added one at a time and form connections to randomly selected old nodes. In between node additions, the network is rewired to minimize its pathlength. For timescales, at which neither the assembly nor the optimization processes are dominant, we find a rich variety of complex networks with power law t...

Find SimilarView on arXiv

Kinetic growth walks on complex networks

April 22, 2005

87% Match
Carlos P. Herrero
Disordered Systems and Neura...

Kinetically grown self-avoiding walks on various types of generalized random networks have been studied. Networks with short- and long-tailed degree distributions $P(k)$ were considered ($k$, degree or connectivity), including scale-free networks with $P(k) \sim k^{-\gamma}$. The long-range behaviour of self-avoiding walks on random networks is found to be determined by finite-size effects. The mean self-intersection length of non-reversal random walks, $<l>$, scales as a pow...

Find SimilarView on arXiv

Randomness and Complexity in Networks

November 5, 2007

87% 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

A Simple Model of Scale-free Networks Driven by both Randomness and Adaptability

September 13, 2004

87% Match
Dinghua Shi, Xiang Zhu, Liming Liu
Data Analysis, Statistics an...

In this paper, we present a simple model of scale-free networks that incorporates both preferential & random attachment and anti-preferential & random deletion at each time step. We derive the degree distribution analytically and show that it follows a power law with the degree exponent in the range of (2,infinity). We also find a way to derive an expression of the clustering coefficient for growing networks and compute the average path length through simulation.

Find SimilarView on arXiv

Network-based kinetic models: Emergence of a statistical description of the graph topology

June 13, 2023

87% Match
Marco Nurisso, Matteo Raviola, Andrea Tosin
Physics and Society
Mathematical Physics

In this paper, we propose a novel approach that employs kinetic equations to describe the collective dynamics emerging from graph-mediated pairwise interactions in multi-agent systems. We formally show that for large graphs and specific classes of interactions a statistical description of the graph topology, given in terms of the degree distribution embedded in a Boltzmann-type kinetic equation, is sufficient to capture the collective trends of networked interacting systems. ...

Find SimilarView on arXiv

A statistical mechanics approach for scale-free networks and finite-scale networks

March 7, 2007

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

We present a statistical mechanics approach for the description of complex networks. We first define an energy and an entropy associated to a degree distribution which have a geometrical interpretation. Next we evaluate the distribution which extremize the free energy of the network. We find two important limiting cases: a scale-free degree distribution and a finite-scale degree distribution. The size of the space of allowed simple networks given these distribution is evaluat...

Find SimilarView on arXiv

Distribution of shortest cycle lengths in random networks

November 30, 2017

87% Match
Haggai Bonneau, Aviv Hassid, Ofer Biham, ... , Katzav Eytan
Disordered Systems and Neura...
Statistical Mechanics
Physics and Society

We present analytical results for the distribution of shortest cycle lengths (DSCL) in random networks. The approach is based on the relation between the DSCL and the distribution of shortest path lengths (DSPL). We apply this approach to configuration model networks, for which analytical results for the DSPL were obtained before. We first calculate the fraction of nodes in the network which reside on at least one cycle. Conditioning on being on a cycle, we provide the DSCL o...

Find SimilarView on arXiv

Growing Networks with Enhanced Resilience to Perturbation

May 5, 2004

87% Match
Markus Brede, John Finnigan
Disordered Systems and Neura...
Statistical Mechanics

Scale-free (SF) networks and small world networks have been found to occur in very diverse contexts. It is this striking universality which makes one look for widely applicable mechanisms which lead to the formation of such networks. In this letter we propose a new mechanism for the construction of SF networks: Evolving networks as interaction networks of systems which are distinguished by their stability if perturbed out of equilibrium. Stability is measured by the largest r...

Find SimilarView on arXiv

Dynamics of social networks

January 15, 2003

87% Match
Holger Ebel, Joern Davidsen, Stefan Bornholdt
Disordered Systems and Neura...
Statistical Mechanics

Complex networks as the World Wide Web, the web of human sexual contacts or criminal networks often do not have an engineered architecture but instead are self-organized by the actions of a large number of individuals. From these local interactions non-trivial global phenomena can emerge as small-world properties or scale-free degree distributions. A simple model for the evolution of acquaintance networks highlights the essential dynamical ingredients necessary to obtain such...

Find SimilarView on arXiv