Novel hybrid mitigation strategy for improving the resiliency of hierarchical networks subjected to attacks

This paper studies the resiliency of hierarchical networks when subjected to random errors, static attacks, and cascade attacks. The performance is compared with existing Erdös–Rényi (ER) random networks and Barabasi and Albert (BA) scale-free networks using global efficiency as the common performance metric. The results show that critical infrastructures modeled as hierarchical networks are intrinsically efficient and are resilient to random errors, however they are more vulnerable to targeted attacks than scale-free networks. Based on the response dynamics to different attack models, we propose a novel hybrid mitigation strategy that combines discrete levels of critical node reinforcement with additional edge augmentation. The proposed modified topology takes advantage of the high initial efficiency of the hierarchical network while also making it resilient to attacks. Experimental results show that when the level of damage inflicted on a critical node is low, the node reinforcement strategy is more effective, and as the level of damage increases, the additional edge augmentation is highly effective in maintaining the overall network resiliency.     

Enhancement of Cooperation and Reentrant Phase of Prisoner’s Dilemma Game on Signed Networks

We studied the prisoner’s dilemma game as applied to signed networks. In signed networks, there are two types of links: positive and negative. To establish a payoff matrix between players connected with a negative link, we multiplied the payoff matrix between players connected with a positive link by −1. To investigate the effect of negative links on cooperating behavior, we performed simulations for different negative link densities. When the negative link density is low, the density of the cooperator becomes zero because there is an increasing temptation payoff, b. Here, parameter b is the payoff received by the defector from playing the game with a cooperator. Conversely, when the negative link density is high, the cooperator density becomes almost 1 as b increases. This is because players with a negative link will suffer more payoff damage if they do not cooperate with each other. The negative link forces players to cooperate, so cooperating behavior is enhanced.     

Detecting the structure of complex networks by quantum bosonic dynamics

In this paper, we introduce a non-interacting boson model to investigate the topological structure of complex networks. By exactly solving this model, we show that it provides a powerful analytical tool in uncovering the important properties of realistic networks. We find that the ground-state degeneracy of this model is equal to the number of connected components in a network and the square of each coefficient in the expansion of the ground state gives the average time that a random walker spends at each node in the infinite time limit. To show the usefulness of this approach in practice, we also carry out numerical simulations on some concrete complex networks. Our results are completely consistent with the previous conclusions derived by graph theory methods. Furthermore, we show that the first excited state appears always on the largest connected component of the network. The relationship between the first excited energy and the average shortest path length in networks is also discussed.     

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.     

Hierarchy Depth in Directed Networks

In this study, we explore the depth measures for flow hierarchy in directed networks. Two simple measures are defined—rooted depth and relative depth—and their properties are discussed. The method of loop collapse is introduced, allowing investigation of networks containing directed cycles. The behavior of the two depth measures is investigated in Erdös-Rényi random graphs, directed Barabási-Albert networks, and in Gnutella p2p share network. A clear distinction in the behavior between non-hierarchical and hierarchical networks is found, with random graphs featuring unimodal distribution of depths dependent on arc density, while for hierarchical systems the distributions are similar for different network densities. Relative depth shows the same behavior as existing trophic level measure for tree-like networks, but is only statistically correlated for more complex topologies, including acyclic directed graphs.     

Mixing search on complex networks

In this article, we derive the first passage time (FPT) distribution and the mean first passage time (MFPT) of random walks from multiple sources on networks. On the basis of analysis and simulation, we find that the MFPT drops substantially when particle number increases at the first stage, and converges to the shortest distance between the sources and the destination when particle number tends to infinite. Given the fact that a Brownian particle from a high-degree node often needs a large number of steps to reach an expected low-degree node, which is the bottleneck for a single random walk, we propose a mixing search model to improve the efficiency of search processes by using random walks from multiple sources to continue the searches from high-degree nodes to destinations. We compare our model with the mixing navigation model proposed by Zhou on complex networks and find that our model converges much faster with lower hardware cost than Zhou’s model. Moreover, simulations on scale-free networks show that the search efficiency of our model is much higher than that of a single random walk, and comparable to that of multiple random walks which have much higher hardware cost than our model. Finally, we discuss the traffic cost of our model, and propose an absorption strategy for our model to recover the additional walkers in networks. Simulations indicate that this strategy reduces the traffic cost of our model effectively.     

Deep Neural Network Model for Approximating Eigenmodes Localized by a Confining Potential

We study eigenmode localization for a class of elliptic reaction-diffusion operators. As the prototype model problem we use a family of Schrödinger Hamiltonians parametrized by random potentials and study the associated effective confining potential. This problem is posed in the finite domain and we compute localized bounded states at the lower end of the spectrum. We present several deep network architectures that predict the localization of bounded states from a sample of a potential. For tackling higher dimensional problems, we consider a class of physics-informed deep dense networks. In particular, we focus on the interpretability of the proposed approaches. Deep network is used as a general reduced order model that describes the nonlinear connection between the potential and the ground state. The performance of the surrogate reduced model is controlled by an error estimator and the model is updated if necessary. Finally, we present a host of experiments to measure the accuracy and performance of the proposed algorithm.     

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

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

Uncovering missing links with cold ends

To evaluate the performance of prediction of missing links, the known data are randomly divided into two parts, the training set and the probe set. We argue that this straightforward and standard method may lead to terrible bias, since in real biological and information networks, missing links are more likely to be links connecting low-degree nodes. We therefore study how to uncover missing links with low-degree nodes, namely links in the probe set are of lower degree products than a random sampling. Experimental analysis on ten local similarity indices and four disparate real networks reveals a surprising result that the Leicht–Holme–Newman index [E.A. Leicht, P. Holme, M.E.J. Newman, Vertex similarity in networks, Phys. Rev. E 73 (2006) 026120] performs the best, although it was known to be one of the worst indices if the probe set is a random sampling of all links. We further propose an parameter-dependent index, which considerably improves the prediction accuracy. Finally, we show the relevance of the proposed index to three real sampling methods: acquaintance sampling, random-walk sampling and path-based sampling.     

Random matrix theory models of electric grid topology

The random matrix theory is useful in the study of large systems such as electric grids. These transmission systems can be modeled as complex networks, with high-voltage lines the edges that connect nodes representing power plants and substations. We draw upon established literature of complex systems theory and introduce methods from nuclear and statistical physics to identify new characteristics of these networks. We show that most grids can be characterized by the Gaussian Orthogonal Ensemble, an indicator of chaos in many complex systems. Under certain circumstances, however, grids may be described by Poisson statistics, an indicator of regularity. We use the random matrix formalism to describe the interconnection of multiple grids and construct a simple model of a distributed grid.     

Stochastic epidemics and rumours on finite random networks

In this paper, we investigate the stochastic spread of epidemics and rumours on networks. We focus on the general stochastic (SIR) epidemic model and a recently proposed rumour model on networks in Nekovee et al. (2007) [3], and on networks with different random structures, taking into account the structure of the underlying network at the level of the degree–degree correlation function. Using embedded Markov chain techniques and ignoring density correlations between neighbouring nodes, we derive a set of equations for the final size of the epidemic/rumour on a homogeneous network that can be solved numerically, and compare the resulting distribution with the solution of the corresponding mean-field deterministic model. The final size distribution is found to switch from unimodal to bimodal form (indicating the possibility of substantial spread of the epidemic/rumour) at a threshold value that is higher than that for the deterministic model. However, the difference between the two thresholds decreases with the network size, n, following a n^−1/3 behaviour. We then compare results (obtained by Monte Carlo simulation) for the full stochastic model on a homogeneous network, including density correlations at neighbouring nodes, with those for the approximating stochastic model and show that the latter reproduces the exact simulation results with great accuracy. Finally, further Monte Carlo simulations of the full stochastic model are used to explore the effects on the final size distribution of network size and structure (using homogeneous networks, simple random graphs and the Barabasi–Albert scale-free networks).     

Social power and opinion formation in complex networks

In this paper we investigate the effects of social power on the evolution of opinions in model networks as well as in a number of real social networks. A continuous opinion formation model is considered and the analysis is performed through numerical simulation. Social power is given to a proportion of agents selected either randomly or based on their degrees. As artificial network structures, we consider scale-free networks constructed through preferential attachment and Watts–Strogatz networks. Numerical simulations show that scale-free networks with degree-based social power on the hub nodes have an optimal case where the largest number of the nodes reaches a consensus. However, given power to a random selection of nodes could not improve consensus properties. Introducing social power in Watts–Strogatz networks could not significantly change the consensus profile.     

Research on the search ability of Brownian particles on networks with an adaptive mechanism

In this paper, we focus on the search ability of Brownian particles with an adaptive mechanism. In the adaptive mechanism, nodes are allowed to be able to change their own accepting probability according to their congestion states. Two searching-traffic models, the static one in which nodes have fixed accepting probability to the incoming particles and the adaptive one in which nodes have adaptive accepting probability to the incoming particles are presented for testing the adaptive mechanism. Instead of number of hops, we use the traveling time, which includes not only the number of hops for a particle to jump from the source node to the destination but also the time that the particle stays in the queues of nodes, to evaluate the search ability of Brownian particles. We apply two models to different networks. The experiment results show that the adaptive mechanism can decrease the network congestion and the traveling time of the first arriving particle. Furthermore, we investigate the influence of network topologies on the congestion of networks by addressing several main properties: degree distribution, average path length, and clustering coefficient. We show the reason why random topologies are more able to deal with congested traffic states than others. We also propose an absorption strategy to deal with the additional Brownian particles in networks. The experiment results on Barabási–Albert (BA) scale-free networks show that the absorption strategy can increase the probability of a successful search and decrease the average per-node particles overhead for our models.     

Role of fractal dimension in random walks on scale-free networks

Fractal dimension is central to understanding dynamical processes occurring on networks; however, the relation between fractal dimension and random walks on fractal scale-free networks has been rarely addressed, despite the fact that such networks are ubiquitous in real-life world. In this paper, we study the trapping problem on two families of networks. The first is deterministic, often called (x,y)-flowers; the other is random, which is a combination of (1,3)-flower and (2,4)-flower and thus called hybrid networks. The two network families display rich behavior as observed in various real systems, as well as some unique topological properties not shared by other networks. We derive analytically the average trapping time for random walks on both the (x,y)-flowers and the hybrid networks with an immobile trap positioned at an initial node, i.e., a hub node with the highest degree in the networks. Based on these analytical formulae, we show how the average trapping time scales with the network size. Comparing the obtained results, we further uncover that fractal dimension plays a decisive role in the behavior of average trapping time on fractal scale-free networks, i.e., the average trapping time decreases with an increasing fractal dimension.     

Epidemic threshold and immunization on generalized networks

The susceptible–infected–susceptible (SIS) model is widely adopted in the studies of epidemic dynamics. When it is applied on contact networks, these networks mostly consist of nodes connected by undirected and unweighted edges following certain statistical properties, whereas in this article we consider the threshold and immunization problem for the SIS model on generalized networks that may contain different kinds of nodes and edges which are very possible in the real situation. We proved that an epidemic will become extinct if and only if the spectral radius of the corresponding parameterized adjacent matrix (PAM) is smaller than 1. Based on this result, we can evaluate the efficiency of immune strategies and take several prevailing ones as examples. In addition, we also develop methods that can precisely find the optimal immune strategies for networks with the given PAM.     

Inferring Users’ Social Roles with a Multi-Level Graph Neural Network Model

Users of social networks have a variety of social statuses and roles. For example, the users of Weibo include celebrities, government officials, and social organizations. At the same time, these users may be senior managers, middle managers, or workers in companies. Previous studies on this topic have mainly focused on using the categorical, textual and topological data of a social network to predict users’ social statuses and roles. However, this cannot fully reflect the overall characteristics of users’ social statuses and roles in a social network. In this paper, we consider what social network structures reflect users’ social statuses and roles since social networks are designed to connect people. Taking an Enron email dataset as an example, we analyzed a preprocessing mechanism used for social network datasets that can extract users’ dynamic behavior features. We further designed a novel social network representation learning algorithm in order to infer users’ social statuses and roles in social networks through the use of an attention and gate mechanism on users’ neighbors. The extensive experimental results gained from four publicly available datasets indicate that our solution achieves an average accuracy improvement of 2% compared with GraphSAGE-Mean, which is the best applicable inductive representation learning method.     

Stability and dynamical properties of material flow systems on random networks

The theory of complex networks and of disordered systems is used to study the stability and dynamical properties of a simple model of material flow networks defined on random graphs. In particular we address instabilities that are characteristic of flow networks in economic, ecological and biological systems. Based on results from random matrix theory, we work out the phase diagram of such systems defined on extensively connected random graphs, and study in detail how the choice of control policies and the network structure affects stability. We also present results for more complex topologies of the underlying graph, focussing on finitely connected Erdös-Réyni graphs, Small-World Networks and Barabási-Albert scale-free networks. Results indicate that variability of input-output matrix elements, and random structures of the underlying graph tend to make the system less stable, while fast price dynamics or strong responsiveness to stock accumulation promote stability.     

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.     

Surface conductance in seamless microtubules

The cyto-architecture of eukaryotic cells contains self-assembled long cylinder-like structures called microtubules (MTs) which play an important role in a number of cellular activities such as cell division, motility, information processing and intracellular transport. In this paper we present a theoretical analysis of the surface conductance of a single seamless MT by representing each tubulin dimer as a resistor. Periodic boundary conditions were utilised both lengthwise (so the MT is pictured as a very large toroidal structure) and around its circumference. Firstly we have investigated the conductance matrix and found the eigenvalues and eigenvectors exactly. Then Wu’s formula has been used to calculate the conductance in terms of them numerically. To check our results we have performed a series of computer simulations of random walks on the lattice of monomers utilising the widely known relationship between such a stochastic process and the theory of electrical networks. We obtain very good agreement between the two approaches.     

Reducing congestion on complex networks by dynamic relaxation processes

We study the effects of relaxational dynamics on the congestion pressure in general transport networks. We show that the congestion pressure is reduced in scale-free networks if a relaxation mechanism is utilized, while this is in general not the case for non-scale-free graphs such as random graphs. We also present evidence supporting the idea that the emergence of scale-free networks arise from optimization mechanisms to balance the load of the networks nodes.