Accelerating networks: Effects of preferential connections

Networks are commonly observed structures in complex systems with interacting and interdependent parts that self-organize. For nonlinearly growing networks, when the total number of connections increases faster than the total number of nodes, the network is said to accelerate. We propose a systematic model for the dynamics of growing networks represented by distribution kinetics equations. We define the nodal-linkage distribution, construct a population dynamics equation based on the association-dissociation process, and perform the moment calculations to describe the dynamics of such networks. For nondirectional networks with finite numbers of nodes and connections, the moments are the total number of nodes, the total number of connections, and the degree (the average number of connections per node), represented by the average moment. Size independent rate coefficients yield an exponential network describing the network without preferential attachment, and size dependent rate coefficients produce a power law network with preferential attachment. The model quantitatively describes accelerating network growth data for a supercomputer (Earth Simulator), for regulatory gene networks, and for the Internet.     

Detection of node group membership in networks with group overlap

Most networks found in social and biochemical systems have modular structures. An important question prompted by the modularity of these networks is whether nodes can be said to belong to a single group. If they cannot, we would need to consider the role of “overlapping communities.” Despite some efforts in this direction, the problem of detecting overlapping groups remains unsolved because there is neither a formal definition of overlapping community, nor an ensemble of networks with which to test the performance of group detection algorithms when nodes can belong to more than one group. Here, we introduce an ensemble of networks with overlapping groups. We then apply three group identification methods – modularity maximization, k-clique percolation, and modularity-landscape surveying – to these networks. We find that the modularity-landscape surveying method is the only one able to detect heterogeneities in node memberships, and that those heterogeneities are only detectable when the overlap is small. Surprisingly, we find that the k-clique percolation method is unable to detect node membership for the overlapping case.     

Growth, percolation, and correlations in disordered fiber networks

This paper studies growth, percolation, and correlations in disordered fiber networks. We start by introducing a 2D continuum deposition model with effective fiber-fiber interactions represented by a parameterp which controls the degree of clustering. Forp=1 the deposited network is uniformly random, while forp=0 only a single connected cluster can grow. Forp=0 we first derive the growth law for the average size of the cluster as well as a formula for its mass density profile. Forp>0 we carry out extensive simulations on fibers, and also needles and disks, to study the dependence of the percolation threshold onp. We also derive a mean-field theory for the threshold nearp=0 andp=1 and find good qualitative agreement with the simulations. The fiber networks produced by the model display nontrivial density correlations forp<1. We study these by deriving an approximate expression for the pair distribution function of the model that reduces to the exactly known case of a uniformly random network. We also show that the two-point mass density correlation function of the model has a nontrivial form, and discuss our results in view of recent experimental data on mss density correlations in paper sheets.     

相依网络上基于相连边的择优恢复算法

如何有效地应对和控制故障在相依网络上的级联扩散避免系统发生结构性破碎,对于相依网络抗毁性研究具有十分重要的理论价值和现实意义.最新的研究提出一种基于相依网络的恢复模型,该模型的基本思想是通过定义共同边界节点,在每轮恢复阶段找出符合条件的共同边界节点并以一定比例实施恢复.当前的做法是按照随机概率进行选择.这种方法虽然简单直观,却没有考虑现实世界中资源成本的有限性和择优恢复的必然性.为此,针对相依网络的恢复模型,本文利用共同边界节点在极大连通网络内外的连接边数计算边界节点的重要性,提出一种基于相连边的择优恢复算法(preferential recovery based on connectivity link,PRCL)算法.利用渗流理论的随机故障模型,通过ER随机网络和无标度网络构建的不同结构相依网络上的级联仿真结果表明,相比随机方法和度数优先以及局域影响力优先的恢复算法,PRCL算法具备恢复能力强、起效时间早且迭代步数少的优势,能够更有效、更及时地遏制故障在网络间的级联扩散,极大地提高了相依网络遭受随机故障时的恢复能力.     

The Critical Point of k-Clique Percolation in the Erdős–Rényi Graph

Motivated by the success of a k-clique percolation method for the identification of overlapping communities in large real networks, here we study the k-clique percolation problem in the Erdős–Rényi graph. When the probability p of two nodes being connected is above a certain threshold p _c (k), the complete subgraphs of size k (the k-cliques) are organized into a giant cluster. By making some assumptions that are expected to be valid below the threshold, we determine the average size of the k-clique percolation clusters, using a generating function formalism. From the divergence of this average size we then derive an analytic expression for the critical linking probability p _c (k).     

The gateway coefficient: a novel metric for identifying critical connections in modular networks

The modular structure of a complex network is an important and well-studied topological property. Within this modular framework, particular nodes which play key roles have been previously identified based on the node’s degree, and on the node’s participation coefficient, a measure of the diversity of a node’s intermodular connections. In this contribution, we develop a generalization of the participation coefficient, called the gateway coefficient, which measures not only the diversity of the intermodular connections, but also how critical these connections are to intermodular connectivity; in brief, nodes which form rare or unique “gateways” between sparsely connected modules rank highly in this measure. We illustrate the use of the gateway coefficient with simulated networks with defined modular structure, as well as networks obtained from air transportation data and functional neuroimaging.     

Infinite Canonical Super-Brownian Motion and Scaling Limits

We construct a measure valued Markov process which we call infinite canonical super-Brownian motion, and which corresponds to the canonical measure of super-Brownian motion conditioned on non-extinction. Infinite canonical super-Brownian motion is a natural candidate for the scaling limit of various random branching objects on when these objects are critical, mean-field and infinite. We prove that ICSBM is the scaling limit of the spread-out oriented percolation incipient infinite cluster above 4 dimensions and of incipient infinite branching random walk in any dimension. We conjecture that it also arises as the scaling limit in various other models above the upper-critical dimension, such as the incipient infinite lattice tree above 8 dimensions, the incipient infinite cluster for unoriented percolation above 6 dimensions, uniform spanning trees above 4 dimensions, and invasion percolation above 6 dimensions.     

二分网上的靴襻渗流

靴襻渗流最早应用于统计物理学中研究磁铁因非磁性杂质导致磁有序的降低并最终消失的现象. 随着复杂网络研究的深入, 许多学者展开网络上的靴襻渗流研究. 在自然界中, 许多系统自然呈现出二分结构, 二分网络是复杂网络中的一种重要的网络模式. 本文通过建立动力学方程和计算机仿真模拟的方法研究二分网上的靴襻渗流, 关注的参数是二分网中两类节点初始的活跃比例和活跃阈值, 分别用f₁, f₂和Ω₁, Ω₂表示, 得到二分网两类节点终态活跃比例随初始活跃比例的变化会发生相变等结论. 同时 验证了动力学方程与仿真模拟的一致性.     

Rapid self-organised initiation of ad hoc sensor networks close above the percolation threshold

This work shows potentials for rapid self-organisation of sensor networks where nodes collaborate to relay messages to a common data collecting unit (sink node). The study problem is, in the sense of graph theory, to find a shortest path tree spanning a weighted graph. This is a well-studied problem where for example Dijkstra’s algorithm provides a solution for non-negative edge weights. The present contribution shows by simulation examples that simple modifications of known distributed approaches here can provide significant improvements in performance. Phase transition phenomena, which are known to take place in networks close to percolation thresholds, may explain these observations. An initial method, which here serves as reference, assumes the sink node starts organisation of the network (tree) by transmitting a control message advertising its availability for its neighbours. These neighbours then advertise their current cost estimate for routing a message to the sink. A node which in this way receives a message implying an improved route to the sink, advertises its new finding and remembers which neighbouring node the message came from. This activity proceeds until there are no more improvements to advertise to neighbours. The result is a tree network for cost effective transmission of messages to the sink (root). This distributed approach has potential for simple improvements which are of interest when minimisation of storage and communication of network information are a concern. Fast organisation of the network takes place when the number k of connections for each node (degree) is close above its critical value for global network percolation and at the same time there is a threshold for the nodes to decide to advertise network route updates.     

Fully-connected networks with local connections

Fully-connected mesh networks with local connections are described. Each connector links only nearest neighbors of the node lattice and carries enough passive pass-through vias to provide direct one-to-one links between all the nodes. If the nodes form a one-dimensional ring, then each connector must contain at least N(N−1)/2 physical channels. However, if the nodes are arranged in a d-dimensional hyper-torus, the number of channels per connector drops to N(N ^1/d −1)/2, which scales much more favorably at large N. Such arrangements can provide fully-meshed connectivity when parts of the network are physically inaccessible or when the network needs to be scaled up in a modular fashion.     

一类基于随机行走机理的优化路由改进策略

在对随机行走过程的研究中发现:单个粒子通过某条特定路径的时间正比于该路径上所有节点度的连乘积.据此,文章提出基于随机行走机理的优化路由改进策略.该策略以节点度连乘积最小化为原则,通过调节可变参数,建立节点处理能力均匀分布的情况下最佳路由策略.通过分析比较不同路由策略条件下平均路由介数中心度,网络的临界负载量,平均路径长度以及平均搜索信息量等性能指标,研究结果表明,此改进路由策略在保证网络平均路径长度较少增加的前提下,使网络的传输能力获得最大幅度的提升. 关键词： 复杂网络 路由策略 负载传输     

Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks

Random walks on complex networks, especially scale-free networks, have attracted considerable interest in the past few years. A lot of previous work showed that the average receiving time (ART), i.e., the average of mean first-passage time (MFPT) for random walks to a given hub node (node with maximum degree) averaged over all starting points in scale-free small-world networks exhibits a sublinear or linear dependence on network order N (number of nodes), which indicates that hub nodes are very efficient in receiving information if one looks upon the random walker as an information messenger. Thus far, the efficiency of a hub node sending information on scale-free small-world networks has not been addressed yet. In this paper, we study random walks on the class of Koch networks with scale-free behavior and small-world effect. We derive some basic properties for random walks on the Koch network family, based on which we calculate analytically the average sending time (AST) defined as the average of MFPTs from a hub node to all other nodes, excluding the hub itself. The obtained closed-form expression displays that in large networks the AST grows with network order as N ln N, which is larger than the linear scaling of ART to the hub from other nodes. On the other hand, we also address the case with the information sender distributed uniformly among the Koch networks, and derive analytically the global mean first-passage time, namely, the average of MFPTs between all couples of nodes, the leading scaling of which is identical to that of AST. From the obtained results, we present that although hub nodes are more efficient for receiving information than other nodes, they display a qualitatively similar speed for sending information as non-hub nodes. Moreover, we show that that AST from a starting point (sender) to all possible targets is not sensitively affected by the sender’s location. The present findings are helpful for better understanding random walks performed on scale-free small-world networks.     

Percolation transitions are not always sharpened by making networks interdependent

We study a model for coupled networks introduced recently by Buldyrev et al., [Nature (London) 464, 1025 (2010)], where each node has to be connected to others via two types of links to be viable. Removing a critical fraction of nodes leads to a percolation transition that has been claimed to be more abrupt than that for uncoupled networks. Indeed, it was found to be discontinuous in all cases studied. Using an efficient new algorithm we verify that the transition is discontinuous for coupled Erd?s-Rényi networks, but find it to be continuous for fully interdependent diluted lattices. In 2 and 3 dimensions, the order parameter exponent β is larger than in ordinary percolation, showing that the transition is less sharp, i.e., further from discontinuity, than for isolated networks. Possible consequences for spatially embedded networks are discussed.     

High-Dimensional Incipient Infinite Clusters Revisited

The incipient infinite cluster (IIC) measure is the percolation measure at criticality conditioned on the cluster of the origin to be infinite. Using the lace expansion, we construct the IIC measure for high-dimensional percolation models in three different ways, extending previous work by the second-named author and Járai. We show that each construction yields the same measure, indicating that the IIC is a robust object. Furthermore, our constructions apply to spread-out versions of both finite-range and long-range percolation models. We also get estimates on structural properties of the IIC, such as the volume of the intersection between the IIC and Euclidean balls.     

Transport Properties of Random Walks on Scale-Free/Regular-Lattice Hybrid Networks

We study numerically the mean access times for random walks on hybrid disordered structures formed by embedding scale-free networks into regular lattices, considering different transition rates for steps across lattice bonds (F) and across network shortcuts (f). For fast shortcuts (f/F≫1) and low shortcut densities, traversal time data collapse onto a universal curve, while a crossover behavior that can be related to the percolation threshold of the scale-free network component is identified at higher shortcut densities, in analogy to similar observations reported recently in Newman-Watts small-world networks. Furthermore, we observe that random walk traversal times are larger for networks with a higher degree of inhomogeneity in their shortcut distribution, and we discuss access time distributions as functions of the initial and final node degrees. These findings are relevant, in particular, when considering the optimization of existing information networks by the addition of a small number of fast shortcut connections.     

A Simple Asymmetric Evolving Random Network

We introduce a new oriented evolving graph model inspired by biological networks. A node is added at each time step and is connected to the rest of the graph by random oriented edges emerging from older nodes. This leads to a statistical asymmetry between incoming and outgoing edges. We show that the model exhibits a percolation transition and discuss its universality. Below the threshold, the distribution of component sizes decreases algebraically with a continuously varying exponent depending on the average connectivity. We prove that the transition is of infinite order by deriving the exact asymptotic formula for the size of the giant component close to the threshold. We also present a thorough analysis of aging properties. We compute local-in-time profiles for the components of finite size and for the giant component, showing in particular that the giant component is always dense among the oldest nodes but invades only an exponentially small fraction of the young nodes close to the threshold.     

Iterated Fully Coordinated Percolation on a Square Lattice

We study, on a square lattice, an extension to fully coordinated percolation which we call iterated fully coordinated percolation. In fully coordinated percolation, sites become occupied if all four of its nearest neighbors are also occupied. Repeating this site selection process again yields the iterated fully coordinated percolation model. Our results show a large enhancement in the size of highly connected regions after each iteration (from ordinary to fully coordinated and then to iterated fully coordinated percolation); enhancements that are much larger than an extension of correlations by an extra lattice constant might suggest. We also study the universality among the three problems by determining the corresponding static and dynamic critical exponents. Specifically, a new method to directly calculate the walk dimension, d _w , using finite size scaling applied to normal mode analysis is used. This method is applicable to any geometry and requires significantly less computation than previously known calculations to determine d _w .     

Transport in weighted networks: partition into superhighways and roads

Transport in weighted networks is dominated by the minimum spanning tree (MST), the tree connecting all nodes with the minimum total weight. We find that the MST can be partitioned into two distinct components, having significantly different transport properties, characterized by centrality--the number of times a node (or link) is used by transport paths. One component, superhighways, is the infinite incipient percolation cluster, for which we find that nodes (or links) with high centrality dominate. For the other component, roads, which includes the remaining nodes, low centrality nodes dominate. We find also that the distribution of the centrality for the infinite incipient percolation cluster satisfies a power law, with an exponent smaller than that for the entire MST. The significance of this finding is that one can improve significantly the global transport by improving a tiny fraction of the network, the superhighways.     

Random Graph Asymptotics on High-Dimensional Tori

We investigate the scaling of the largest critical percolation cluster on a large d-dimensional torus, for nearest-neighbor percolation in sufficiently high dimensions, or when d > 6 for sufficiently spread-out percolation. We use a relatively simple coupling argument to show that this largest critical cluster is, with high probability, bounded above by a large constant times V ^2/3 and below by a small constant times , where V is the volume of the torus. We also give a simple criterion in terms of the subcritical percolation two-point function on under which the lower bound can be improved to small constant times , i.e. we prove random graph asymptotics for the largest critical cluster on the high-dimensional torus. This establishes a conjecture by [1], apart from logarithmic corrections. We discuss implications of these results on the dependence on boundary conditions for high-dimensional percolation. Our method is crucially based on the results in [11, 12], where the scaling was proved subject to the assumption that a suitably defined critical window contains the percolation threshold on . We also strongly rely on mean-field results for percolation on proved in [17–20].