Multiple-predators-based capture process on complex networks

The predator/prey(capture) problem is a prototype of many network-related applications. We study the capture process on complex networks by considering multiple predators from multiple sources. In our model, some lions start from multiple sources simultaneously to capture the lamb by biased random walks, which are controlled with a free parameterα. We derive the distribution of the lamb's lifetime and the expected lifetime T. Through simulation, we find that the expected lifetime drops substantially with the increasing number of lions. Moreover, we study how the underlying topological structure affects the capture process, and obtain that locating on small-degree nodes is better than on largedegree nodes to prolong the lifetime of the lamb. The dense or homogeneous network structures are against the survival of the lamb. We also discuss how to improve the capture efficiency in our model.     

Do larger firms have more interfirm relationships?

In this study, we investigate interfirm networks by employing a unique data set containing information on more than 800,000 Japanese firms, about half of all corporate firms currently operating in Japan. First, we find that the number of relationships, measured by the indegree, has a fat-tail distribution, implying that there exist “hub” firms with a large number of relationships. Moreover, the indegree distribution for those hub firms also exhibits a fat tail, suggesting the existence of “super-hub” firms. Second, we find that larger firms tend to have more counterparts, but the relationship between firms’ size and the number of their counterparts is not necessarily proportional; firms that already have a large number of counterparts tend to grow without proportionately expanding it.     

Percolation on bipartite scale-free networks

Recent studies introduced biased (degree-dependent) edge percolation as a model for failures in real-life systems. In this work, such process is applied to networks consisting of two types of nodes with edges running only between nodes of unlike type. Such bipartite graphs appear in many social networks, for instance in affiliation networks and in sexual-contact networks in which both types of nodes show the scale-free characteristic for the degree distribution. During the depreciation process, an edge between nodes with degrees k and q is retained with a probability proportional to (kq)^−α, where α is positive so that links between hubs are more prone to failure. The removal process is studied analytically by introducing a generating functions theory. We deduce exact self-consistent equations describing the system at a macroscopic level and discuss the percolation transition. Critical exponents are obtained by exploiting the Fortuin-Kasteleyn construction which provides a link between our model and a limit of the Potts model.     

Growing community networks with local events

The study of community networks has attracted considerable attention recently. In this paper, we propose an evolving community network model based on local processes, the addition of new nodes intra-community and new links intra- or inter-community. Employing growth and preferential attachment mechanisms, we generate networks with a generalized power-law distribution of nodes’ degrees.     

A new local-world evolving network model

In some real complex networks, only a few nodes can obtain the global information about the entire networks, but most of the nodes own only local connections therefore own only local information of the networks. A new local-world evolving network model is proposed in this paper. In the model, not all the nodes obtain local network information, which is different from the local world network model proposed by Li and Chen (LC model). In the LC model, each node has only the local connections therefore owns only local information about the entire networks. Theoretical analysis and numerical simulation show that adjusting the ratio of the number of nodes obtaining the global information of the network to the total number of nodes can effectively control the valuing range for the power-law exponent of the new network. Therefore, if the topological structure of a complex network, especially its exponent of power-law degree distribution, needs controlling, we just add or take away a few nodes which own the global information of the network.     

Deterministic scale-free small-world networks of arbitrary order

In many real-life networks, both the scale-free distribution of degree and small-world behavior are important features. There are many random or deterministic models of networks to simulate these features separately. However, there are few models that combine the scale-free effect and small-world behavior, especially in terms of deterministic versions. What is more, all the existing deterministic algorithms running in the iterative mode generate networks with only several discrete numbers of nodes. This contradicts the purpose of creating a deterministic network model on which we can simulate some dynamical processes as widely as possible. According to these facts, this paper proposes a deterministic network generation algorithm, which can not only generate deterministic networks following a scale-free distribution of degree and small-world behavior, but also produce networks with arbitrary number of nodes. Our scheme is based on a complete binary tree, and each newly generated leaf node is further linked to its full brother and one of its direct ancestors. Analytical computation and simulation results show that the average degree of such a proposed network is less than 5, the average clustering coefficient is high (larger than 0.5, even for a network of size 2 million) and the average shortest path length increases much more slowly than logarithmic growth for the majority of small-world network models.     

Preferential survival in models of complex ad hoc networks

There has been a rich interplay in recent years between (i) empirical investigations of real-world dynamic networks, (ii) analytical modeling of the microscopic mechanisms that drive the emergence of such networks, and (iii) harnessing of these mechanisms to either manipulate existing networks, or engineer new networks for specific tasks. We continue in this vein, and study the deletion phenomenon in the web by the following two different sets of websites (each comprising more than 150,000 pages) over a one-year period. Empirical data show that there is a significant deletion component in the underlying web networks, but the deletion process is not uniform. This motivates us to introduce a new mechanism of preferential survival (PS), where nodes are removed according to the degree-dependent deletion kernel, D(k)∝k^−α, with α≥0. We use the mean-field rate equation approach to study a general dynamic model driven by Preferential Attachment (PA), Double PA (DPA), and a tunable PS (i.e., with any α>0), where c nodes (c<1) are deleted per node added to the network, and verify our predictions via large-scale simulations. One of our results shows that, unlike in the case of uniform deletion (i.e., where α=0), the PS kernel when coupled with the standard PA mechanism, can lead to heavy-tailed power-law networks even in the presence of extreme turnover in the network. Moreover, a weak DPA mechanism, coupled with PS, can help to make the network even more heavy-tailed, especially in the limit when deletion and insertion rates are almost equal, and the overall network growth is minimal. The dynamics reported in this work can be used to design and engineer stable ad hoc networks and explain the stability of the power-law exponents observed in real-world networks.     

Preferential spreading on scale-free networks

Based on a classical contact model, the spreading dynamics on scale-free networks is investigated by taking into account exponential preferentiality in both sending out and accepting processes. In order to reveal the macroscopic and microscopic dynamic features of the networks, the total infection density ρ and the infection distribution ρ(k), respectively, are discussed under various preferential characters. It is found that no matter what preferential accepting strategy is taken, priority given to small degree nodes in the sending out process increases the total infection density ρ. To generate maximum total infection density, the unbiased preferential accepting strategy is the most effective one. On a microscopic scale, a small growth of the infection distribution ρ(k) for small degree classes can lead to a considerable increase of ρ. Our investigation, from both macroscopic and microscopic perspectives, consistently reveals the important role the small degree nodes play in the spreading dynamics on scale-free networks.     

Identifying influential nodes in complex networks

Identifying influential nodes that lead to faster and wider spreading in complex networks is of theoretical and practical significance. The degree centrality method is very simple but of little relevance. Global metrics such as betweenness centrality and closeness centrality can better identify influential nodes, but are incapable to be applied in large-scale networks due to the computational complexity. In order to design an effective ranking method, we proposed a semi-local centrality measure as a tradeoff between the low-relevant degree centrality and other time-consuming measures. We use the Susceptible-Infected-Recovered (SIR) model to evaluate the performance by using the spreading rate and the number of infected nodes. Simulations on four real networks show that our method can well identify influential nodes.     

一种基于势博弈的无线传感器网络拓扑控制算法

在实际的应用中,无线传感器网络常常由大量电池资源有限的传感器节点组成.如何降低网络功耗,最大化网络生存时间,是传感器网络拓扑控制技术的重要研究目标.随着传感节点的运行,节点的能量分布可能越来越不均衡,需要在考虑该因素的情况下,动态地调整节点的网络负载以均衡节点的能耗,达到延长网络生存时间的目的.该文引入博弈理论和势博弈的概念,综合考虑节点的剩余能量和节点发射功率等因素,设计了一种基于势博弈的拓扑控制模型,并证明了该模型纳什均衡的存在性.通过构造兼顾节点连通性和能耗均衡性的收益函数,以确保降低节点功耗的同时维持网络的连通性.通过提高邻居节点的平均剩余能量值以实现将剩余能量多的节点选择作为自身的邻居节点,提高节点能耗的均衡性.在此基础上,提出了一种分布式的能耗均衡拓扑控制算法.理论分析证明了该算法能保持网络的连通性.与现有基于博弈理论的DIA算法和MLPT算法相比,本算法形成的拓扑负载较重、剩余能量较小的瓶颈节点数量较少,节点剩余能量的方差较小,网络生存时间更长.     

Phase Transitions and Spatio-Temporal Fluctuations in Stochastic Lattice Lotka–Volterra Models

We study the general properties of stochastic two-species models for predator-prey competition and coexistence with Lotka–Volterra type interactions defined on a d-dimensional lattice. Introducing spatial degrees of freedom and allowing for stochastic fluctuations generically invalidates the classical, deterministic mean-field picture. Already within mean-field theory, however, spatial constraints, modeling locally limited resources, lead to the emergence of a continuous active-to-absorbing state phase transition. Field-theoretic arguments, supported by Monte Carlo simulation results, indicate that this transition, which represents an extinction threshold for the predator population, is governed by the directed percolation universality class. In the active state, where predators and prey coexist, the classical center singularities with associated population cycles are replaced by either nodes or foci. In the vicinity of the stable nodes, the system is characterized by essentially stationary localized clusters of predators in a sea of prey. Near the stable foci, however, the stochastic lattice Lotka–Volterra system displays complex, correlated spatio-temporal patterns of competing activity fronts. Correspondingly, the population densities in our numerical simulations turn out to oscillate irregularly in time, with amplitudes that tend to zero in the thermodynamic limit. Yet in finite systems these oscillatory fluctuations are quite persistent, and their features are determined by the intrinsic interaction rates rather than the initial conditions. We emphasize the robustness of this scenario with respect to various model perturbations.     

Information Bottleneck Classification in Extremely Distributed Systems

We present a new decentralized classification system based on a distributed architecture. This system consists of distributed nodes, each possessing their own datasets and computing modules, along with a centralized server, which provides probes to classification and aggregates the responses of nodes for a final decision. Each node, with access to its own training dataset of a given class, is trained based on an auto-encoder system consisting of a fixed data-independent encoder, a pre-trained quantizer and a class-dependent decoder. Hence, these auto-encoders are highly dependent on the class probability distribution for which the reconstruction distortion is minimized. Alternatively, when an encoding–quantizing–decoding node observes data from different distributions, unseen at training, there is a mismatch, and such a decoding is not optimal, leading to a significant increase of the reconstruction distortion. The final classification is performed at the centralized classifier that votes for the class with the minimum reconstruction distortion. In addition to the system applicability for applications facing big-data communication problems and or requiring private classification, the above distributed scheme creates a theoretical bridge to the information bottleneck principle. The proposed system demonstrates a very promising performance on basic datasets such as MNIST and FasionMNIST.     

A highly clustered scale-free network evolved by random walking

In present paper, we propose a highly clustered weighted network model that incorporates the addition of a new node with some links, new links between existing nodes and the edge's weight dynamical evolution based on weight-dependent walks at each time step. The analytical approach and numerical simulation show that the system grows into a weighted network with the power-law distributions of strength, weight and degree. The weight-dependent walk length l will not influence the strength distribution, but the clustering coefficient of the network is sensitive to l. Particularly, the clustering coefficient is especially high and almost independent of the network size when l=2.     

Effects of the heterogeneous landscape on a predator-prey system

In order to understand how a heterogeneous landscape affects a predator-prey system, a spatially explicit lattice model consisting of predators, prey, grass, and landscape was constructed. The predators and preys randomly move on the lattice space and the grass grows in its neighboring site according to its growth probability. When predators and preys meet at the same site at the same time, a number of prey, equal to the number of predators are eaten. This rule was also applied to the relationship between the prey and grass. The predator (prey) could give birth to an offspring when it ate prey (grass), with a birth probability. When a predator or prey animal was initially introduced, or newly born, its health state was set at a given high value. This health state decreased by one with every time step. When the state of an animal decreased to less than zero, the animal died and was removed from the system. The heterogeneous landscape was characterized by parameter H, which controlled the heterogeneity according to the neutral model. The simulation results showed that H positively or negatively affected a predator’s survival, while its effect on prey and grass was less pronounced. The results can be understood by the disturbance of the balance between the prey and predator densities in the areas where the animals aggregated.     

Ranking spreaders by decomposing complex networks

Ranking the nodes? ability of spreading in networks is crucial for designing efficient strategies to hinder spreading in the case of diseases or accelerate spreading in the case of information dissemination. In the well-known k-shell method, nodes are ranked only according to the links between the remaining nodes (residual links) while the links connecting to the removed nodes (exhausted links) are entirely ignored. In this Letter, we propose a mixed degree decomposition (MDD) procedure in which both the residual degree and the exhausted degree are considered. By simulating the epidemic spreading process on real networks, we show that the MDD method can outperform the k-shell and degree methods in ranking spreaders.     

Growing random networks with fitness

Three models of growing random networks with fitness-dependent growth rates are analysed using the rate equations for the distribution of their connectivities. In the first model (A), a network is built by connecting incoming nodes to nodes of connectivity k and random additive fitness η, with rate (k−1)+η. For η>0 we find the connectivity distribution is power law with exponent γ=〈η〉+2. In the second model (B), the network is built by connecting nodes to nodes of connectivity k, random additive fitness η and random multiplicative fitness ζ with rate ζ(k−1)+η. This model also has a power law connectivity distribution, but with an exponent which depends on the multiplicative fitness at each node. In the third model (C), a directed graph is considered and is built by the addition of nodes and the creation of links. A node with fitness (α,β), i incoming links and j outgoing links gains a new incoming link with rate α(i+1), and a new outgoing link with rate β(j+1). The distributions of the number of incoming and outgoing links both scale as power laws, with inverse logarithmic corrections.     

Generating weighted community networks based on local events

Many realistic networks have community structures, namely, a network consists of groups of nodes within which links are dense but among which links are sparse. This paper proposes a growing network model based on local processes, the addition of new nodes intra-community and new links intra- or inter-community. Also, it utilizes the preferential attachment for building connections determined by nodes' strengths, which evolves dynamically during the growth of the system. The resulting network reflects the intrinsic community structure with generalized power-law distributions of nodes' degrees and strengths.     

Extended Petersen networks

A new type of network growth rule is studied, which comprises nodes adding, plus a rewiring procedure, and replacing of nodes with the complete bipartite graph K2,3 acting on Petersen graph. The 3-regular extended Petersen networks have 0 clustering coefficient, short diameter, high connectivity and the Hamilton path. All these properties play an important role in the information transfer of the network, as they cannot only increase the security but also save time and system resources.