2004/08/12 by Zoltán Toroczkai, Zoltan Toroczkai, B. Kozma +10 · 4 citations
Mathematics · Physics and Astronomy · #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Physical sciences #Graph theory and applications #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.dis-nn #cond-mat.stat-mech
paper · pdf · doi:10.48550/arxiv.cond-mat/0408262
20 pages, 8 postscript figures included, submitted for publication
arxiv created 2004/08/12 · openalex publication_date 2004/08/12 · arxiv updated 2009/12/01 · openalex created_date 2024/04/10 · openalex updated_date 2026/07/28
We define gradient networks as directed graphs formed by local gradients of a scalar field distributed on the nodes of a substrate network G. We derive an exact expression for the in-degree distribution of the gradient network when the substrate is a binomial (Erdos-Renyi) random graph, G(N,p). Using this expression we show that the in-degree distribution R(l) of gradient graphs on G(N,p) obeys the power law R(l)~1/l for arbitrary, i.i.d. random scalar fields. We then relate gradient graphs to congestion tendency in network flows and show that while random graphs become maximally congested in the large network size limit, scale-free networks are not, forming fairly efficient substrates for transport. Combining this with other constraints, such as uniform edge cost, we obtain a plausible argument in form of a selection principle, for why a number of spontaneously evolved massive networks are scale-free. This paper also presents detailed derivations of the results recently reported in Nature, vol. 428, pp. 716 (2004).