Levels of a scale‐free tree

Consider the random graph model of Barabási and Albert, where we add a new vertex in every step and connect it to some old vertices with probabilities proportional to their degrees. If we connect it to only one of the old vertices the graph will be a tree. These graphs have been shown to have power law degree distributions, the same as observed in some large real‐world networks. We show that the degree distribution is the same on every sufficiently high level of the tree. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Vulnerability of complex networks

We consider normalized average edge betweenness of a network as a metric of network vulnerability. We suggest that normalized average edge betweenness together with is relative difference when certain number of nodes and/or edges are removed from the network is a measure of network vulnerability, called vulnerability index. Vulnerability index is calculated for four synthetic networks: Erdős–Rényi (ER) random networks, Barabási–Albert (BA) model of scale-free networks, Watts–Strogatz (WS) model of small-world networks, and geometric random networks. Real-world networks for which vulnerability index is calculated include: two human brain networks, three urban networks, one collaboration network, and two power grid networks. We find that WS model of small-world networks and biological networks (human brain networks) are the most robust networks among all networks studied in the paper.     

The degree sequence of a scale‐free random graph process

Recently, Barabási and Albert [2] suggested modeling complex real‐world networks such as the worldwide web as follows: consider a random graph process in which vertices are added to the graph one at a time and joined to a fixed number of earlier vertices, selected with probabilities proportional to their degrees. In [2] and, with Jeong, in [3], Barabási and Albert suggested that after many steps the proportion P(d) of vertices with degree d should obey a power law P(d)αd^?γ. They obtained γ=2.9±0.1 by experiment and gave a simple heuristic argument suggesting that γ=3. Here we obtain P(d) asymptotically for all d≤n^1/15, where n is the number of vertices, proving as a consequence that γ=3. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18, 279–290, 2001     

Parallel cleaning of a network with brushes

We consider the process of cleaning a network where at each time step, all vertices that have at least as many brushes as incident, contaminated edges, send brushes down these edges and remove them from the network. An added condition is that, because of the contamination model used, the final configuration must be the initial configuration of another cleaning of the network. We find the minimum number of brushes required for trees, cycles, complete bipartite networks; and for all networks when all edges must be cleaned on each step. Finally, we give bounds on the number of brushes required for complete networks.     

The average path length of scale free networks

In this paper, the exact solution of average path length in Barabási–Albert model is given. The average path length is an important property of networks and attracts much attention in many areas. The Barabási–Albert model, also called scale free model, is a popular model used in modeling real systems. Hence it is valuable for us to examine the average path length of scale free model. There are two answers, regarding the exact solution for the average path length of scale free networks, already provided by Newman and Bollobas respectively. As Newman proposed, the average path length grows as log(n) with the network size n. However, Bollobas suggested that while it was true when m = 1, the answer changed to log(n)/log(log(n)) when m > 1. In this paper, as we propose, the exact solution of average path length of BA model should approach log(n)/log(log(n)) regardless the value of m. Finally, the simulation is presented to show the validity of our result.     

Exploring express delivery networks in China based on complex network theory

Based on the complex network theory, we explore an express delivery system in China, which consists of two delivery networks, namely, the air delivery network (ADN) and the ground delivery network (GDN). Systematic structural analysis indicates that both delivery networks exhibit small‐world phenomenon, disassortative mixing behavior, and rich‐club phenomenon. However, there are significant differences between ADN and GDN in terms of degree distribution property and community structure. On the basis of the Barabási‐Albert model, we have proposed a network model incorporating the structural features of the two delivery networks to reveal their evolutionary mechanisms. Lastly, the parcel strength and the distance strength are analyzed, which, respectively, reflect the number of parcels and the long‐haul delivery distance handled by a node city. The strengths are highly heterogeneous in both delivery networks and have intense correlations with topological structures. These works are beneficial for express enterprises to construct or extend their express delivery networks, and provide some useful insights on improving parcel delivery service. © 2014 Wiley Periodicals, Inc. Complexity 21: 166–179, 2015     

Cooperation in changing environments: Irreversibility in the transition to cooperation in complex networks

In the framework of the evolutionary dynamics of the Prisoner’s Dilemma game on complex networks, we investigate the possibility that the average level of cooperation shows hysteresis under quasi-static variations of a model parameter (the “temptation to defect”). Under the “discrete replicator” strategy updating rule, for both Erdös–Rényi and Barabási–Albert graphs we observe cooperation hysteresis cycles provided one reaches tipping point values of the parameter; otherwise, perfect reversibility is obtained. The selective fixation of cooperation at certain nodes and its organization in cooperator clusters, that are surrounded by fluctuating strategists, allows the rationalization of the “lagging behind” behavior observed.     

Time evolution of dense multigraph limits under edge‐conservative preferential attachment dynamics

We define the edge reconnecting model, a random multigraph evolving in time. At each time step we change one endpoint of a uniformly chosen edge: the new endpoint is chosen by linear preferential attachment. We consider a sequence of edge reconnecting models where the sequence of initial multigraphs is convergent in a sense which is a natural generalization of the notion of convergence of dense graph sequences, defined by Lovász and Szegedy (J. Combin. Theory Ser B 96 (2006) 933–957). We investigate how the limit object evolves under the edge reconnecting dynamics if we rescale time properly: we give the complete characterization of the time evolution of the limit object from its initial state up to the stationary state, which is described in the companion paper (Ráth and Szakács, in press). In our proofs we use the theory of exchangeable arrays, queuing and diffusion processes. The number of parallel edges and the degrees evolve on different timescales and because of this the model exhibits subaging. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

基于二项分布随机增长的无标度网络

提出—个具有随机增长的无标度网络模型．该模型的演化规则仍然是BA模型的增长和择优连接,但是每一时间间隔添加到网络中的边数是—个具有二项分布的随机变量．通过率方程方法,本文证明了该网络的度分布具有幂律尾部,该模型生成了—个无标度网络．     

Effect of vaccination strategies on the dynamic behavior of epidemic spreading and vaccine coverage

The transmission of infectious, yet vaccine-preventable, diseases is a typical complex social phenomenon, where the increasing level of vaccine update in the population helps to inhibit the epidemic spreading, which in turn, however, discourages more people to participate in vaccination campaigns, due to the “externality effect” raised by vaccination. We herein study the impact of vaccination strategies, pure, continuous (rather than adopt vaccination definitely, the individuals choose to taking vaccine with some probabilities), or continuous with randomly mutation, on the vaccination dynamics with a spatial susceptible-vaccinated-infected-recovered (SVIR) epidemiological model. By means of extensive Monte-Carlo simulations, we show that there is a crossover behavior of the final vaccine coverage between the pure-strategy case and the continuous-strategy case, and remarkably, both the final vaccination level and epidemic size in the continuous-strategy case are less than them in the pure-strategy case when vaccination is cheap. We explain this phenomenon by analyzing the organization process of the individuals in the continuous-strategy case in the equilibrium. Our results are robust to the SVIR dynamics defined on other spatial networks, like the Erdős–Rényi and Barabási–Albert networks.     

Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules

O (c+d) steps using constant-size queues, where c is the congestion of the paths in the network, and d is the length of the longest path. The proof, however, used the Lovász Local Lemma and was not constructive. In this paper, we show how to find such a schedule in time, with probability , for any positive constant β, where is the sum of the lengths of the paths taken by the packets in the network, and m is the number of edges used by some packet in the network. We also show how to parallelize the algorithm so that it runs in NC. The method that we use to construct the schedules is based on the algorithmic form of the Lovász Local Lemma discovered by Beck. Received: July 8, 1996     

Asymptotics of quantum spin networks at a fixed root of unity

A classical spin network consists of a ribbon graph (i.e., an abstract graph with a cyclic ordering of the vertices around each edge) and an admissible coloring of its edges by natural numbers. The standard evaluation of a spin network is an integer number. In a previous paper, we proved an existence theorem for the asymptotics of the standard evaluation of an arbitrary classical spin network when the coloring of its edges are scaled by a large natural number. In the present paper, we extend the results to the case of an evaluation of quantum spin networks of arbitrary valency at a fixed root of unity. As in the classical case, our proofs use the theory of G-functions of André, together with some new results concerning holonomic and q-holonomic sequences of Wilf-Zeilberger.     

Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs

This paper addresses sensitivity analysis questions concerning the shortest path problem and the maximum capacity path problem in an undirected network. For both problems, we determine the maximum and minimum weights that each edge can have so that a given path remains optimal. For both problems, we show how to determine these maximum and minimum values for all edges in O(m + K log K) time, where m is the number of edges in the network, and K is the number of edges on the given optimal path.     

A Markov Renewal Based Model for Wireless Networks

We propose a queueing network model which can be used for the integration of the mobility and teletraffic aspects that are characteristic of wireless networks. In the general case, the model is an open network of infinite server queues where customers arrive according to a non-homogeneous Poisson process. The movement of a customer in the network is described by a Markov renewal process. Moreover, customers have attributes, such as a teletraffic state, that are driven by continuous time Markov chains and, therefore, change as they move through the network. We investigate the transient and limit number of customers in disjoint sets of nodes and attributes. These turn out to be independent Poisson random variables. We also calculate the covariances of the number of customers in two sets of nodes and attributes at different time epochs. Moreover, we conclude that the arrival process per attribute to a node is the sum of independent Poisson cluster processes and derive its univariate probability generating function. In addition, the arrival process to an outside node of the network is a non-homogeneous Poisson process. We illustrate the applications of the queueing network model and the results derived in a particular wireless network.     

Random walks on colored graphs

We initiate a study of random walks on undirected graphs with colored edges. In our model, a sequence of colors is specified before the walk begins, and it dictates the color of edge to be followed at each step. We give tight upper and lower bounds on the expected cover time of a random walk on an undirected graph with colored edges. We show that, in general, graphs with two colors have exponential expected cover time, and graphs with three or more colors have doubly-exponential expected cover time. We also give polynomial bounds on the expected cover time in a number of interesting special cases. We described applications of our results to understanding the dominant eigenvectors of products and weighted averages of stochastic matrices, and to problems on time-inhomogeneous Markov chains. © 1994 John Wiley & Sons, Inc.     

Asymmetry and structural information in preferential attachment graphs

Graph symmetries intervene in diverse applications, from enumeration, to graph structure compression, to the discovery of graph dynamics (e.g., node arrival order inference). Whereas Erd?s‐Rényi graphs are typically asymmetric, real networks are highly symmetric. So a natural question is whether preferential attachment graphs, where in each step a new node with m edges is added, exhibit any symmetry. In recent work it was proved that preferential attachment graphs are symmetric for m = 1, and there is some nonnegligible probability of symmetry for m = 2. It was conjectured that these graphs are asymmetric when m ≥ 3. We settle this conjecture in the affirmative, then use it to estimate the structural entropy of the model. To do this, we also give bounds on the number of ways that the given graph structure could have arisen by preferential attachment. These results have further implications for information theoretic problems of interest on preferential attachment graphs.     

Morphing Planar Graph Drawings with Bent Edges

We give an algorithm to morph between two planar drawings of a graph, preserving planarity, but allowing edges to bend. The morph uses a polynomial number of elementary steps, where each elementary step is a linear morph that moves each vertex in a straight line at uniform speed. Although there are planarity-preserving morphs that do not require edge bends, it is an open problem to find polynomial-size morphs. We achieve polynomial size at the expense of edge bends.     

A Fast Algorithm For Finding A Maximum Free Multiflow In An Inner Eulerian Network And Some Generalizations

be a network, where is an undirected graph with nodes and edges, is a set of specified nodes of , called terminals, and each edge of has a nonnegative integer capacity . If the total capacity of edges with one end at is even for every non-terminal node , then is called inner Eulerian. A free multiflow is a collection of flows between arbitrary pairs of terminals such that the total flow through each edge does not exceed its capacity. In this paper we first generalize a method in Karzanov [11] to find a maximum integer free multiflow in an inner Eulerian network, in time, where is the complexity of finding a maximum flow between two terminals. Next we extend our algorithm to solve the so-called laminar locking problem on multiflows, also in time. We then consider analogs of the above problems in inner balanced directed networks, which means that for each non-terminal node , the sums of capacities of arcs entering and leaving are the same. We show that for such a network a maximum integer free multiflow can be constructed in time, and then extend this result to the corresponding locking problem. Received: March 24, 1997     

Network reinforcement

We give an algorithm for the following problem: given a graph G=(V,E) with edge-weights and a nonnegative integer k, find a minimum cost set of edges that contains k disjoint spanning trees. This also solves the following reinforcement problem: given a network, a number k and a set of candidate edges, each of them with an associated cost, find a minimum cost set of candidate edges to be added to the network so it contains k disjoint spanning trees. The number k is seen as a measure of the invulnerability of a network. Our algorithm has the same asymptotic complexity as |V| applications of the minimum cut algorithm of Goldberg & Tarjan. Received: April, 2004     

Bounds for the number of meeting edges in graph partitioning

Let G be a weighted hypergraph with edges of size at most 2. Bollobás and Scott conjectured that G admits a bipartition such that each vertex class meets edges of total weight at least (w ₁?Δ₁)/2+2w ₂/3, where wi is the total weight of edges of size i and Δ₁ is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph G (i.e., multi-hypergraph), we show that there exists a bipartition of G such that each vertex class meets edges of total weight at least (w ₀?1)/6+(w ₁?Δ₁)/3+2w ₂/3, where w ₀ is the number of edges of size 1. This generalizes a result of Haslegrave. Based on this result, we show that every graph with m edges, except for K ₂ and K _1,3, admits a tripartition such that each vertex class meets at least [2m/5] edges, which establishes a special case of a more general conjecture of Bollobás and Scott.