Connectivity of growing networks with link constraints

We propose a growing network model with link constraint, in which new nodes are continuously introduced into the system and immediately connected to preexisting nodes, and any arbitrary node cannot receive new links when it reaches a maximum number of links k_m. The connectivity of the network model is then investigated by means of the rate equation approach. For the connection kernel A(k)=k^γ, the degree distribution n_k takes a power law if γ≥1 and decays stretched exponentially if 0≤γ< 1. We also consider a network system with the connection kernel A(k)=k^α(k_m-k)^β. It is found that n_k approaches a power law in the α> 1 case and has a stretched exponential decay in the 0≤α< 1 case, while it can take a power law with exponential truncation in the special α=β=1 case. Moreover, n_k may have a U-type structure if α> β.     

Evolution of imitation networks in Minority Game model

The Minority Game is adapted to study the “imitation dilemma”, i.e. the tradeoff between local benefit and global harm coming from imitation. The agents are placed on a substrate network and are allowed to imitate more successful neighbours. Imitation domains, which are oriented trees, are formed. We investigate size distribution of the domains and in-degree distribution within the trees. We use four types of substrate: one-dimensional chain; Erd?s-Rényi graph; Barabási-Albert scale-free graph; Barabási-Albert 'model A' graph. The behaviour of some features of the imitation network strongly depend on the information cost epsilon, which is the percentage of gain the imitators must pay to the imitated. Generally, the system tends to form a few domains of equal size. However, positive epsilon makes the system stay in a long-lasting metastable state with complex structure. The in-degree distribution is found to follow a power law in two cases of those studied: for Erd?s-Rényi substrate for any epsilon and for Barabási-Albert scale-free substrate for large enough epsilon. A brief comparison with empirical data is provided.     

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     

Wealth distributions in asset exchange models

A model for the evolution of the wealth distribution in an economically interacting population is introduced, in which a specified amount of assets are exchanged between two individuals when they interact. The resulting wealth distributions are determined for a variety of exchange rules. For “random” exchange, either individual is equally likely to gain in a trade, while “greedy” exchange, the richer individual gains. When the amount of asset traded is fixed, random exchange leads to a Gaussian wealth distribution, while greedy exchange gives a Fermi-like scaled wealth distribution in the long-time limit. Multiplicative processes are also investigated, where the amount of asset exchanged is a finite fraction of the wealth of one of the traders. For random multiplicative exchange, a steady state occurs, while in greedy multiplicative exchange a continuously evolving power law wealth distribution arises. Received: 13 August 1997 / Revised: 31 December 1997 / Accepted: 26 January 1998     

A Generalized Voter Model on Complex Networks

We study a generalization of the voter model on complex networks, focusing on the scaling of mean exit time. Previous work has defined the voter model in terms of an initially chosen node and a randomly chosen neighbor, which makes it difficult to disentangle the effects of the stochastic process itself relative to the network structure. We introduce a process with two steps, one that selects a pair of interacting nodes and one that determines the direction of interaction as a function of the degrees of the two nodes and a parameter α which sets the likelihood of the higher degree node giving its state to the other node. Traditional voter model behaviors can be recovered within the model, as well as the invasion process. We find that on a complete bipartite network, the voter model is the fastest process. On a random network with power law degree distribution, we observe two regimes. For modest values of α, exit time is dominated by diffusive drift of the system state, but as the high-degree nodes become more influential, the exit time becomes dominated by frustration effects dependent on the exact topology of the network.     

Ising Models on Power-Law Random Graphs

We study a ferromagnetic Ising model on random graphs with a power-law degree distribution and compute the thermodynamic limit of the pressure when the mean degree is finite (degree exponent τ>2), for which the random graph has a tree-like structure. For this, we closely follow the analysis by Dembo and Montanari (Ann. Appl. Probab. 20(2):565–592, 2010) which assumes finite variance degrees (τ>3), adapting it when necessary and also simplifying it when possible. Our results also apply in cases where the degree distribution does not obey a power law.     

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).     

Power, Lévy, exponential and Gaussian-like regimes in autocatalytic financial systems

We study by theoretical analysis and by direct numerical simulation the dynamics of a wide class of asynchronous stochastic systems composed of many autocatalytic degrees of freedom. We describe the generic emergence of truncated power laws in the size distribution of their individual elements. The exponents α of these power laws are time independent and depend only on the way the elements with very small values are treated. These truncated power laws determine the collective time evolution of the system. In particular the global stochastic fluctuations of the system differ from the normal Gaussian noise according to the time and size scales at which these fluctuations are considered. We describe the ranges in which these fluctuations are parameterized respectively by: the Lévy regime α < 2, the power law decay with large exponent ( α > 2), and the exponential decay. Finally we relate these results to the large exponent power laws found in the actual behavior of the stock markets and to the exponential cut-off detected in certain recent measurement. Received 29 July 2000 and Received in final form 25 September 2000     

Adaptive random walks on the class of Web graphs

We study random walk with adaptive move strategies on a class of directed graphs with variable wiring diagram. The graphs are grown from the evolution rules compatible with the dynamics of the world-wide Web [B. Tadić, Physica A 293, 273 (2001)], and are characterized by a pair of power-law distributions of out- and in-degree for each value of the parameter β, which measures the degree of rewiring in the graph. The walker adapts its move strategy according to locally available information both on out-degree of the visited node and in-degree of target node. A standard random walk, on the other hand, uses the out-degree only. We compute the distribution of connected subgraphs visited by an ensemble of walkers, the average access time and survival probability of the walks. We discuss these properties of the walk dynamics relative to the changes in the global graph structure when the control parameter β is varied. For β≥ 3, corresponding to the world-wide Web, the access time of the walk to a given level of hierarchy on the graph is much shorter compared to the standard random walk on the same graph. By reducing the amount of rewiring towards rigidity limit β↦β_c≲ 0.1, corresponding to the range of naturally occurring biochemical networks, the survival probability of adaptive and standard random walk become increasingly similar. The adaptive random walk can be used as an efficient message-passing algorithm on this class of graphs for large degree of rewiring.     

Morphological differences between Bi, Ag and Sb nano-particles and how they affect the percolation of current through nano-particle networks

Nano-particles of Bi, Ag and Sb have been produced in an inert gas aggregation source and deposited between lithographically defined electrical contacts on SiN. The morphology of these films have been examined by atomic force microscopy and scanning electron microscopy. The Bi nano-particles stick well to the SiN substrate and take on a flattened dome shape. The Ag nano-particles also stick well to the SiN surface; however they retain a more spherical shape. Whereas, many of the Sb nano-particles bounce off the SiN surface with only a small fraction of the Sb nano-particles aggregating at defects resulting in a non-random distribution of the clusters. These nano-scale differences in the film morphology influence the viability of applying percolation theory to in situ macroscopic measurements of the film conductivity, during the deposition process. For Bi and Ag nano-particles the increase in conductivity follows a power law. The power law exponent, t, was found to be 1.27 ±0.13 and 1.40 ±0.14, for Bi and Ag respectively, in agreement with theoretical predictions of t ≈1.3 for 2D random continuum percolation networks. Sb cluster networks do not follow this model and due to the majority of the Sb clusters bouncing off the surface. Differences in the current onset times and final conductance values of the films are also discussed.     

新节点的边对网络无标度性影响

分析新节点边对网络无标度性的影响.虽然亚线性增长网络瞬态平均度分布尾部表现出了幂律分布性质，但是，这个网络的稳态度分布并不是幂律分布，由此可见，计算机模拟预测不出网络稳态度分布，它只能预测网络的瞬态度分布.进而建立随机增长网络模型，利用随机过程理论得到了这个模型的度分布的解析表达式，结果表明这个网络是无标度网络.     

新节点的边对网络无标度性影响

分析新节点边对网络无标度性的影响.虽然亚线性增长网络瞬态平均度分布尾部表现出了幂律分布性质,但是,这个网络的稳态度分布并不是幂律分布,由此可见,计算机模拟预测不出网络稳态度分布,它只能预测网络的瞬态度分布.进而建立随机增长网络模型,利用随机过程理论得到了这个模型的度分布的解析表达式,结果表明这个网络是无标度网络. 关键词： 复杂网络 无标度网络 小世界网络 度分布     

Network formed by traces of random walks

We propose a model of time evolving networks in which a kind of transport between vertices generates new edges in the graph. We call the model “Network formed by traces of random walks”, because the transports are represented abstractly by random walks. Our numerical calculations yield several important properties observed commonly in complex networks, although the graph at initial time is only a one-dimensional lattice. For example, the distribution of vertex degree exhibits various behaviors such as exponential, power law like, and bi-modal distribution according to change of probability of extinction of edges. Another property such as strong clustering structure and small mean vertex–vertex distance can also be found. The transports represented by random walks in a framework of strong links between regular lattice is a new mechanisms which yields biased acquisition of links for vertices.     

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     

Network robustness to targeted attacks. The interplay of expansibility and degree distribution

We study the property of certain complex networks of being both sparse and highly connected, which is known as “good expansion” (GE). A network has GE properties if every subset S of nodes (up to 50% of the nodes) has a neighborhood that is larger than some “expansion factor” φ multiplied by the number of nodes in S. Using a graph spectral method we introduce here a new parameter measuring the good expansion character of a network. By means of this parameter we are able to classify 51 real-world complex networks — technological, biological, informational, biological and social — as GENs or non-GENs. Combining GE properties and node degree distribution (DD) we classify these complex networks in four different groups, which have different resilience to intentional attacks against their nodes. The simultaneous existence of GE properties and uniform degree distribution contribute significantly to the robustness in complex networks. These features appear solely in 14% of the 51 real-world networks studied here. At the other extreme we find that ∼40% of all networks are very vulnerable to targeted attacks. They lack GE properties, display skewed DD — exponential or power-law — and their topologies are changed more dramatically by targeted attacks directed at bottlenecks than by the removal of network hubs.     

Flocculation and percolation in reversible cluster-cluster aggregation

Off-lattice dynamic Monte-Carlo simulations were done of reversible cluster-cluster aggregation for spheres that form rigid bonds at contact. The equilibrium properties were found to be determined by the life time of encounters between two particles (t_e). t_e is a function not only of the probability to form or break a bond, but also of the elementary step size of the Brownian motion of the particles. In the flocculation regime the fractal dimension of the clusters is d_f=2.0 and the size distribution has a power law decay with exponent τ=1.5. At larger values of t_e transient gels are formed. Close to the percolation threshold the clusters have a fractal dimension d_f=2.7 and the power law exponent of the size distribution is τ=2.1. The transition between flocculation and percolation occurs at a characteristic weight average aggregation number that decreases with increasing volume fraction.     

Phase transition in annihilation-limited processes

A system of particles is studied in which the stochastic processes are one-particle type-change (or one-particle diffusion) and multi-particle annihilation. It is shown that, if the annihilation rate tends to zero but the initial values of the average number of the particles tend to infinity, so that the annihilation rate times a certain power of the initial values of the average number of the particles remain constant (the double scaling) then if the initial state of the system is a multi-Poisson distribution, the system always remains in a state of multi-Poisson distribution, but with evolving parameters. The large time behavior of the system is also investigated. The system exhibits a dynamical phase transition. It is seen that for a k-particle annihilation, if k is larger than a critical value k_c, which is determined by the type-change rates, then annihilation does not enter the relaxation exponent of the system; while for k < k_c, it is the annihilation (in fact k itself) which determines the relaxation exponent.     

Properties of wealth distribution in multi-agent systems of a complex network

We present a simple model for examining the wealth distribution with agents playing evolutionary games (the Prisoners’ Dilemma and the Snowdrift Game) on complex networks. Pareto’s power law distribution of wealth (from 1897) is reproduced on a scale-free network, and the Gibbs or log-normal distribution for a low income population is reproduced on a random graph. The Pareto exponents of a scale-free network are in agreement with empirical observations. The Gini coefficient of an ER random graph shows a sudden increment with game parameters. We suggest that the social network of a high income group is scale-free, whereas it is more like a random graph for a low income group.