Degree distributions of growing networks

The in-degree and out-degree distributions of a growing network model are determined. The in-degree is the number of incoming links to a given node (and vice versa for out-degree). The network is built by (i) creation of new nodes which each immediately attach to a preexisting node, and (ii) creation of new links between preexisting nodes. This process naturally generates correlated in-degree and out-degree distributions. When the node and link creation rates are linear functions of node degree, these distributions exhibit distinct power-law forms. By tuning the parameters in these rates to reasonable values, exponents which agree with those of the web graph are obtained.     

Voltage distribution in growing conducting networks

We investigate by random-walk simulations and a mean-field theory how growth by biased addition of nodes affects flow of the current through the emergent conducting graph, representing a digital circuit. In the interior of a large network the voltage varies with the addition time s < t of the node as V(s) ∼ ln(s)/s ^θ when constant current enters the network at last added node t and leaves at the root of the graph which is grounded. The topological closeness of the conduction path and shortest path through a node suggests that the charged random walk determines these global graph properties by using only local search algorithms. The results agree with mean-field theory on tree structures, while the numerical method is applicable to graphs of any complexity. Received 26 August 2002 Published online 29 November 2002     

Universality for the Distance in Finite Variance Random Graphs

We generalize the asymptotic behavior of the graph distance between two uniformly chosen nodes in the configuration model to a wide class of random graphs. Among others, this class contains the Poissonian random graph, the expected degree random graph and the generalized random graph (including the classical Erdős-Rényi graph). In the paper we assign to each node a deterministic capacity and the probability that there exists an edge between a pair of nodes is equal to a function of the product of the capacities of the pair divided by the total capacity of all the nodes. We consider capacities which are such that the degrees of a node have uniformly bounded moments of order strictly larger than two, so that, in particular, the degrees have finite variance. We prove that the graph distance grows like log  _ν N, where the ν depends on the capacities and N denotes the size of the graph. In addition, the random fluctuations around this asymptotic mean log  _ν N are shown to be tight. We also consider the case where the capacities are independent copies of a positive random Λ with , for some constant c and τ>3, again resulting in graphs where the degrees have finite variance. The method of proof of these results is to couple each member of the class to the Poissonian random graph, for which we then give the complete proof by adapting the arguments of van der Hofstad et al. (Random Struct. Algorithms 27(2):76–123, 2005).     

Continuous-time quantum walks on star graphs

In this paper, we investigate continuous-time quantum walk on star graphs. It is shown that quantum central limit theorem for a continuous-time quantum walk on star graphs for N-fold star power graph, which are invariant under the quantum component of adjacency matrix, converges to continuous-time quantum walk on K₂ graphs (complete graph with two vertices) and the probability of observing walk tends to the uniform distribution.     

Properties of a growing random directed network

We study a number of properties of a simple random growing directed network which can be used to model real directed networks such as the world-wide web and call graphs. We confirm numerically that the distributions of in- and out-degree are consistent with a power law, in agreement with previous analytical results and with empirical measurements from real graphs. We study the distribution and mean of the minimum path length, the high degree nodes, the appearance and size of the giant component and the topology of the nodes outside the giant component. These properties are compared with empirical studies of the world-wide web. Received 15 June 2001 and Received in final form 12 July 2001     

Empirical investigation of topological and weighted properties of a bus transport network from China

Many bus transport networks(BTNs) have evolved into directed networks. A new representation model for BTNs is proposed, called directed-space P. The bus transport network of Harbin(BTN-H) is described as a directed and weighted complex network by the proposed representation model and by giving each node weights. The topological and weighted properties are revealed in detail. In-degree and out-degree distributions, in-weight and out-weight distributions are presented as an exponential law, respectively. There is a strong relation between in-weight and in-degree(also between out-weight and out-degree), which can be fitted by a power function. Degree–degree and weight–weight correlations are investigated to reveal that BTN-H has a disassortative behavior as the nodes have relatively high degree(or weight). The disparity distributions of out-degree and in-degree follow an approximate power-law. Besides, the node degree shows a near linear increase with the number of routes that connect to the corresponding station. These properties revealed in this paper can help public transport planners to analyze the status quo of the BTN in nature.     

Social network based microblog user behavior analysis

The influence of microblog on information transmission is becoming more and more obvious. By characterizing the behavior of following and being followed as out-degree and in-degree respectively, a microblog social network was built in this paper. It was found to have short diameter of connected graph, short average path length and high average clustering coefficient. The distributions of out-degree, in-degree and total number of microblogs posted present power-law characters. The exponent of total number distribution of microblogs is negatively correlated with the degree of each user. With the increase of degree, the exponent decreases much slower. Based on empirical analysis, we proposed a social network based human dynamics model in this paper, and pointed out that inducing drive and spontaneous drive lead to the behavior of posting microblogs. The simulation results of our model match well with practical situation.     

The complexity nature of large-scale software systems

In software engineering, class diagrams are often used to describe the system's class structures in Unified Modelling Language (UML). A class diagram, as a graph, is a collection of static declarative model elements, such as classes, interfaces, and the relationships of their connections with each other. In this paper, class graphs are examined within several Java software systems provided by Sun and IBM, and some new features are found. For a large-scale Java software system, its in-degree distribution tends to an exponential distribution, while its out-degree and degree distributions reveal the power-law behaviour. And then a directed preferential-random model is established to describe the corresponding degree distribution features and evolve large-scale Java software systems.     

Space use by foragers consuming renewable resources

Through the analysis of unbiased random walks on fractal trees and continuous time random walks, we show that even if a process is characterized by a mean square displacement (MSD) growing linearly with time (standard behaviour) its diffusion properties can be not trivial. In particular, we show that the following scenarios are consistent with a linear increase of MSD with time: (i) the high-order moments, ?x(t) ^q ? for q > 2 and the probability density of the process exhibit multiscaling; (ii) the random walk on certain fractal graphs, with non integer spectral dimension, can display a fully standard diffusion; (iii) positive order moments satisfying standard scaling does not imply an exact scaling property of the probability density.     

A large-scale study of the world wide web: network correlation functions with scale-invariant boundaries

We performed a large-scale crawl of the world wide web, covering 6.9 million domains and 57 million subdomains, including all high-traffic sites of the internet. We present a study of the correlations found between quantities measuring the structural relevance of each node in the network (the in- and out-degree, the local clustering coefficient, the first-neighbor in-degree and the Alexa rank). We find that some of these properties show strong correlation effects and that the dependencies occurring out of these correlations follow power laws not only for the averages, but also for the boundaries of the respective density distributions. In addition, these scale-free limits do not follow the same exponents as the corresponding averages. In our study we retain the directionality of the hyperlinks and develop a statistical estimate for the clustering coefficient of directed graphs. We include in our study the correlations between the in-degree and the Alexa traffic rank, a popular index for the traffic volume, finding non-trivial power-law correlations. We find that sites with more/less than about 10³ links from different domains have remarkably different statistical properties, for all correlation functions studied, indicating towards an underlying hierarchical structure of the world wide web.     

On Connected Diagrams and Cumulants of Erdős-Rényi Matrix Models

Regarding the adjacency matrices of n-vertex graphs and related graph Laplacian we introduce two families of discrete matrix models constructed both with the help of the Erdős-Rényi ensemble of random graphs. Corresponding matrix sums represent the characteristic functions of the average number of walks and closed walks over the random graph. These sums can be considered as discrete analogues of the matrix integrals of random matrix theory. We study the diagram structure of the cumulant expansions of logarithms of these matrix sums and analyze the limiting expressions as n → ∞ in the cases of constant and vanishing edge probabilities.     

Network Models in Class C on Arbitrary Graphs

We consider network models of quantum localisation in which a particle with a two-component wave function propagates through the nodes and along the edges of an arbitrary directed graph, subject to a random SU(2) rotation on each edge it traverses. The propagation through each node is specified by an arbitrary but fixed S-matrix. Such networks model localisation problems in class C of the classification of Altland and Zirnbauer [1], and, on suitable graphs, they model the spin quantum Hall transition. We extend the analyses of Gruzberg, Ludwig and Read [5] and of Beamond, Cardy and Chalker [2] to show that, on an arbitrary graph, the mean density of states and the mean conductance may be calculated in terms of observables of a classical history-dependent random walk on the same graph. The transition weights for this process are explicitly related to the elements of the S-matrices. They are correctly normalised but, on graphs with nodes of degree greater than 4, not necessarily non-negative (and therefore interpretable as probabilities) unless a sufficient number of them happen to vanish. Our methods use a supersymmetric path integral formulation of the problem which is completely finite and rigorous.     

Open Quantum Random Walks

A new model of quantum random walks is introduced, on lattices as well as on finite graphs. These quantum random walks take into account the behavior of open quantum systems. They are the exact quantum analogues of classical Markov chains. We explore the “quantum trajectory” point of view on these quantum random walks, that is, we show that measuring the position of the particle after each time-step gives rise to a classical Markov chain, on the lattice times the state space of the particle. This quantum trajectory is a simulation of the master equation of the quantum random walk. The physical pertinence of such quantum random walks and the way they can be concretely realized is discussed. Differences and connections with the already well-known quantum random walks, such as the Hadamard random walk, are established.     

Spectral determinant on graphs with generalized boundary conditions

The spectral determinant of the Schr?dinger operator ( - Δ + V(x)) on a graph is computed for general boundary conditions. (Δ is the Laplacian and V(x) is some potential defined on the graph). Applications to restricted random walks on graphs are discussed. Received 9 July 2001     

Asymptotic properties of multistate random walks. I. Theory

A calculation is presented of the long-time behavior of various random walk properties (moments, probability of return to the origin, expected number of distinct sites visited) formultistate random walks on periodic lattices. In particular, we consider inhomogeneous periodic lattices, consisting of a periodically repeated unit cell which contains a finite number of internal states (sites). The results are identical to those for perfect lattices except for a renormalization of coefficients. For walks without drift, it is found that all the asymptotic random walk properties are determined by the diffusion coefficients for the multistate random walk. The diffusion coefficients can be obtained by a simple matrix algorithm presented here. Both discrete and continuous time random walks are considered. The results are not restricted to nearest-neighbor random walks but apply as long as the single-step probability distributions associated with each of the internal states have finite means and variances.     

Core percolation in random graphs: a critical phenomena analysis

We study both numerically and analytically what happens to a random graph of average connectivity α when its leaves and their neighbors are removed iteratively up to the point when no leaf remains. The remnant is made of isolated vertices plus an induced subgraph we call the core. In the thermodynamic limit of an infinite random graph, we compute analytically the dynamics of leaf removal, the number of isolated vertices and the number of vertices and edges in the core. We show that a second order phase transition occurs at α = e = 2.718 ... : below the transition, the core is small but above the transition, it occupies a finite fraction of the initial graph. The finite size scaling properties are then studied numerically in detail in the critical region, and we propose a consistent set of critical exponents, which does not coincide with the set of standard percolation exponents for this model. We clarify several aspects in combinatorial optimization and spectral properties of the adjacency matrix of random graphs. Received 31 January 2001 and Received in final form 26 June 2001     

Transience, Recurrence and Critical Behavior¶for Long-Range Percolation

We study the behavior of the random walk on the infinite cluster of independent long-range percolation in dimensions d= 1,2, where x and y are connected with probability . We show that if d<s<2d, then the walk is transient, and if s≥ 2d, then the walk is recurrent. The proof of transience is based on a renormalization argument. As a corollary of this renormalization argument, we get that for every dimension d≥ 1, if d>s>2d, then there is no infinite cluster at criticality. This result is extended to the free random cluster model. A second corollary is that when d≥& 2 and d>s>2d we can erase all long enough bonds and still have an infinite cluster. The proof of recurrence in two dimensions is based on general stability results for recurrence in random electrical networks. In particular, we show that i.i.d. conductances on a recurrent graph of bounded degree yield a recurrent electrical network. Received: 27 October 2000 / Accepted: 29 November 2001     

Random Walks and Polymers in the Presence of Quenched Disorder

After a general introduction to the field, we describe some recent results concerning disorder effects on both ‘random walk models’, where the random walk is a dynamical process generated by local transition rules, and on ‘polymer models’, where each random walk trajectory representing the configuration of a polymer chain is associated to a global Boltzmann weight. For random walk models, we explain, on the specific examples of the Sinai model and of the trap model, how disorder induces anomalous diffusion, aging behaviours and Golosov localization, and how these properties can be understood via a strong disorder renormalization approach. For polymer models, we discuss the critical properties of various delocalization transitions involving random polymers. We first summarize some recent progresses in the general theory of random critical points: thermodynamic observables are not self-averaging at criticality whenever disorder is relevant, and this lack of self-averaging is directly related to the probability distribution of pseudo-critical temperatures T _c(i,L) over the ensemble of samples (i) of size L. We describe the results of this analysis for the bidimensional wetting and for the Poland–Scheraga model of DNA denaturation.Conference Proceedings “Mathematics and Physics”, I.H.E.S., France, November 2005     

A directed network of Greek and Roman mythology

We construct a directed network using a dictionary of Greek and Roman mythology in which the nodes represent the entries listed in the dictionary and we make directional links from an entry to other entries that appear in its explanatory part. We find that this network is clearly not a random network but a directed scale-free network in which the distributions of out-degree and in-degree follow a power-law with exponents γ_out≈3.0 and γ_in≈2.5, respectively. Also we measure several quantities which describe the topological properties of the network and compare it to that of other real networks.