随机增长网络的度分布

增长和择优机制是无标度网络中的两种重要的演化机制,在分析BA模型的基础上,提出了一种新的节点增长方式,即考虑了新增节点的连边数是随机变量的情况,从而建立了随机增长网络模型,并利用随机过程理论得到了在这种增长方式下网络的度分布,结果表明这个网络是无标度网络。     

A scale‐free network model for HIV transmission among men who have sex with men in China

Objective: The study aimed to analyze sexual networks and sex role preference as factors of HIV transmission among men who have sex with men (MSM) in China. Methods: We have developed a new scale‐free network model with a sex role preference framework to study HIV transmission among MSM. We have studied the influence of different sexual networks and the effect of different proportion of sex role preference upon HIV transmission. The results are that the average ones drawn from the scenarios have been simulated for more than 30 times. Results: Compared with the traditional mathematical model, the sexual networks provide a different prediction of the HIV transmission in the next 30 years. Without any intervention, the proportion of HIV carriers will descend after some time. Conclusions: There is significant associations among network characteristics, sex role preference, and HIV infection. Although network‐based intervention is efficient in reducing HIV transmission among MSM, there are only few studies of the characteristics of sexual network, and such gaps deserve more attention and exploration. Copyright © 2016 John Wiley & Sons, Ltd.     

On centripetal flows of entities in scale‐free networks with nodes of finite capability

We examine the transmission of entities from the peripheries of scale‐free networks toward their centers when the nodes of the network have finite processing capabilities. We look at varying network utilization, U and find that clogging of the network sets in after a threshold value has been exceeded, and that the congestion sets in at the downstream nodes (those nearer to the collector) having large numbers of upstream neighbors. Investigation of the question of the degree of correlation of several characteristics of scale‐free networks (such as the average path length to the collector <l_(min)> and the average clustering coefficient ) with the dynamics of centripetal flow in them reveals a negative answer: any correlation is indirect and will manifest in the number of producer nodes (which dictate the effective heaviness of the flow) and the interconnectedness of the feeder nodes, those nodes which are immediate neighbors of the collector node. An examination of reinforcement strategies shows dramatic improvements in both the finishing rate, and the average total transmission time, when the more centrally‐placed nodes are reinforced first, showing that the entities spend a large amount of their lifetime waiting in line at those nodes (which constitute the bottlenecks in the network) compared to the nodes in the periphery. Our results reinforce the importance of a network's hubs and their immediate environs, and suggest strategies for prioritizing elements of a network for optimization. © 2014 Wiley Periodicals, Inc. Complexity 21: 283–295, 2015     

Scale‐free power‐laws as interaction between progress and diffusion

While scale‐free power‐laws are frequently found in social and technological systems, their authenticity, origin, and gained insights are often questioned, and rightfully so. The article presents a newly found rank‐frequency power‐law that aligns the top‐500 supercomputers according to their performance. Pursuing a cautious approach in a systematic way, we check for authenticity, evaluate several potential generative mechanisms, and ask the “so what” question. We evaluate and finally reject the applicability of well‐known potential generative mechanisms such as preferential attachment, self‐organized criticality, optimization, and random observation. Instead, the microdata suggest that an inverse relationship between exponential technological progress and exponential technology diffusion through social networks results in the identified fat‐tail distribution. This newly identified generative mechanism suggests that the supply and demand of technology (“technology push” and “demand pull”) align in exponential synchronicity, providing predictive insights into the evolution of highly uncertain technology markets. © 2013 Wiley Periodicals, Inc. Complexity 19: 56–65, 2014     

Viral conductance: Quantifying the robustness of networks with respect to spread of epidemics

In this paper, we propose a novel measure, viral conductance (VC), to assess the robustness of complex networks with respect to the spread of SIS epidemics. In contrast to classical measures that assess the robustness of networks based on the epidemic threshold above which an epidemic takes place, the new measure incorporates the fraction of infected nodes at steady state for all possible effective infection strengths. Through examples, we show that VC provides more insight about the robustness of networks than does the epidemic threshold. We also address the paradoxical robustness of Barabási–Albert preferential attachment networks. Even though this class of networks is characterized by a vanishing epidemic threshold, the epidemic requires high effective infection strength to cause a major outbreak. On the contrary, in homogeneous networks the effective infection strength does not need to be very much beyond the epidemic threshold to cause a major outbreak. To overcome computational complexities, we propose a heuristic to compute the VC for large networks with high accuracy. Simulations show that the heuristic gives an accurate approximation of the exact value of the VC. Moreover, we derive upper and lower bounds of the new measure. We also apply the new measure to assess the robustness of different types of network structures, i.e. Watts–Strogatz small world, Barabási–Albert, correlated preferential attachment, Internet AS-level, and social networks. The extensive simulations show that in Watts–Strogatz small world networks, the increase in probability of rewiring decreases the robustness of networks. Additionally, VC confirms that the irregularity in node degrees decreases the robustness of the network. Furthermore, the new measure reveals insights about design and mitigation strategies of infrastructure and social networks.     

Teaching complexity theory through student construction of a course wiki: The self‐organization of a scale‐free network

Complex systems are fascinating because emergent phenomena are often unpredictable and appear to arise ex nihilo. The other side of this fascination, however, is a certain difficulty in comprehending complex systems, particularly for students. To help students more fully understand emergence and self‐organization, a course on complexity theory was designed to not only be about these two concepts, but itself embody them. The principal design tool was a course wiki. Here, we quantitatively demonstrate that this course wiki self‐organized into a scale‐free network. This is particularly notable given the small size of the network. We conclude by noting a few qualitative examples of emergence, as well as offering recommendations for the future use of wikis in teaching complexity theory. © 2010 Wiley Periodicals, Inc. Complexity 16: 41–48, 2011     

Discovery Through Gossip

We study randomized gossip‐based processes in dynamic networks that are motivated by information discovery in large‐scale distributed networks such as peer‐to‐peer and social networks. A well‐studied problem in peer‐to‐peer networks is resource discovery, where the goal for nodes (hosts with IP addresses) is to discover the IP addresses of all other hosts. Also, some of the recent work on self‐stabilization algorithms for P2P/overlay networks proceed via discovery of the complete network. In social networks, nodes (people) discover new nodes through exchanging contacts with their neighbors (friends). In both cases the discovery of new nodes changes the underlying network — new edges are added to the network — and the process continues in the changed network. Rigorously analyzing such dynamic (stochastic) processes in a continuously changing topology remains a challenging problem with obvious applications. This paper studies and analyzes two natural gossip‐based discovery processes. In the push discovery or triangulation process, each node repeatedly chooses two random neighbors and connects them (i.e., “pushes” their mutual information to each other). In the pull discovery process or the two‐hop walk, each node repeatedly requests or “pulls” a random contact from a random neighbor and connects itself to this two‐hop neighbor. Both processes are lightweight in the sense that the amortized work done per node is constant per round, local, and naturally robust due to the inherent randomized nature of gossip. Our main result is an almost‐tight analysis of the time taken for these two randomized processes to converge. We show that in any undirected n‐node graph both processes take rounds to connect every node to all other nodes with high probability, whereas is a lower bound. We also study the two‐hop walk in directed graphs, and show that it takes time with high probability, and that the worst‐case bound is tight for arbitrary directed graphs, whereas Ω(n²) is a lower bound for strongly connected directed graphs. A key technical challenge that we overcome in our work is the analysis of a randomized process that itself results in a constantly changing network leading to complicated dependencies in every round. We discuss implications of our results and their analysis to discovery problems in P2P networks as well as to evolution in social networks. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 48, 565–587, 2016     

产学研合作创新网络规模、连接机制与创新绩效的关系研究——基于多主体仿真和动态系统论视角

为揭示产学研合作创新网络规模与连接机制对创新绩效的影响机理,运用Agent建模理论和Netlogo仿真平台构建产学研合作创新网络的仿真模型,对不同特性(小世界、无标度)偏好下的产学研合作创新网络进行仿真实验,并运用动态系统理论解释仿真的涌现现象。研究发现:①网络平均节点度(度数中心势)与网络平均创新绩效(节点加权平均收益的对数)之间存在鞍结分叉和跨临界分叉的组合现象;②网络平均距离(关系强度)与网络平均绩效之间呈指数增长分布轨道;③连接机制与网络平均绩效呈对数增长分布轨道;④实力择优连接机制提升网络平均节点度正向作用的效率较低;⑤随机组合择优连接机制更有利于提升小世界偏好网络平均距离的正向作用;⑥度择优连接机制更有利于提升无标度偏好网络平均创新绩效。     

Universal robustness of scale‐free networks against cascading edge failures

Considering the effect of the local topology structure of an edge on cascading failures, we investigate the cascading reaction behaviors on scale‐free networks with respect to small edge‐based initial attacks. Adopt the initial load of an edge ij in a network to be L_ij = (k_ik_j)^α[(∑k_a)(∑k_b)]^β with k_i and k_j being the degrees of the nodes connected by the edge ij, where α and β are tunable parameters, governing the strength of the edge initial load, and Γ_i and Γ_j are the sets of neighboring nodes of i and j, respectively. Our aim is to explore the relationship between some parameters and universal robustness characteristics against cascading failures on scale‐free networks. We find by the theoretical analysis that the Baraba'si‐Albert (BA) scale‐free networks can reach the strongest robustness level against cascading failures when α + β = 1, where the robustness is quantified by a transition from normal state to collapse. And the network robustness has a positive correlation with the average degree. We furthermore confirm by the numerical simulations these results.     

Broad scaling region in a spatial ecological system

The ubiquity of scale‐free patterns in ecological systems has raised the possibility that these systems operate near criticality. Critical phenomena (CP) require the tuning of parameters and typically exhibit a narrow scaling region in which power laws hold. Here we show that an individual‐based predator‐prey model exhibits scaling properties similar to CP, generated by a percolation‐like transition but with a broader scaling region. There are no drastic changes in ecological quantities across this critical point and species coexist broadly in parameter space. The implications of these findings for the stability of ecological systems “near” criticality is discussed. © 2003 Wiley Periodicals, Inc.     

A social network model with proximity prestige property

In general, many real-world networks not only possess scale-free and high clustering coefficient properties, but also have a fast information transmission capability. However, the existing network models are unable to well present the intrinsic fast information transmission feature. The initial infected nodes and the network topology are two factors that affect the information transmission capability. By using preferential attachment to high proximity prestige nodes and triad formation, we provide a proximity prestige network model, which has scale-free property and high clustering coefficient. Simulation results further indicate that the new model also possesses tunable information transmission capability archived by adjusting its parameters. Moreover, comparing with the BA scale-free network, the proximity prestige network PPNet05 achieves a higher transmission capability when messages travel based on SIR and SIS models. Our conclusions are directed to possible applications in rumor or information spreading mechanisms.     

A one-parameter family of stationary solutions in the Susceptible-Infected-Susceptible epidemic model

We study the uncorrelated Susceptible-Infected-Susceptible (SIS) model in epidemiology on top of a one parameter family of networks whose connectivity distribution ranges from scale free (SF) to exponential. For each network, the fraction of the population infected in the long term is a recursively defined hypergeometric function. For highly contagious diseases, with a high infection rate, the fraction of the population infected is lower when the network is SF. For less contagious diseases, the fraction of the population infected is lower when the network is exponential. This result points to an evolutionary advantage for a network being SF—namely an SF network is more resistant to the spread of a deadly disease.     

Clifford algebra method for network expression,computation, and algorithm construction

Clifford algebra is introduced as a theoretical foundation for network topology expression and algorithm construction. Network nodes are coded with basis vectors in a vector space , and the edges and k‐walk routes can be expressed by 2‐blades and k‐blades, respectively, in the Clifford algebra Cl(n,0). The topologies among nodes, edges, and routes of networks can be directly calculated, and the network routes can be extended and traversed with oriented join products. The network algorithm construction processes based on Clifford algebra are instantiated by the single source shortest path algorithm. The experimental results on different scale random networks suggest that Clifford algebra is suited for network expression and relation computation. The Clifford algebra‐based shortest path algorithm is vivid and clear in geometric meaning and has great advantage on temporal and spatial complexity. Copyright © 2013 John Wiley & Sons, Ltd.     

M-G-P型复杂网络中有寿命节点的进入退出机制

现实中复杂网络结构复杂,形式多样,处在高度动态变化的过程.为了更好地理解真实网络的演化,基于复杂网络的特性进行分析,建立了Poissotn连续时间增长节点具有寿命的M-G-P型复杂网络模型,模型中包括:新节点加入、节点老化和老节点退出等,基于齐次马尔可夫链对模型的度分布进行计算,得出M-G-P型网络的度分布符合幂律分布,模型和BA模型一样能产生指数γ=3的无标度网络,验证了导致无标度网络度分布特征起关键性作用的是链接的偏好特性.     

On fuzzy cliques in fuzzy networks

A definition of fuzzy clique in social networks is suggested which overcomes five limitations of current definitions. This definition is based on the networks in which the 0–1 strengths, the weighted strengths, and fuzzy strengths are all allowed. The fuzzy distance in such a network is defined. The node‐clique and clique‐clique coefficients are suggested. The core and the periphery of fuzzy cliques are discussed formally. A “cone like” property of the cores is discovered. The network structures are discussed using the new definition. A “no circle” property of networks is found. Basic fuzzy tools and the related algorithms are also discussed. Some examples are analyzed to demonstrate the theory.     

An Evolving Random Network and Its Asymptotic Structure

In this paper, we propose an evolving random network. The model is a linear combination of preferential attachment model and uniform model. We show that scaling limit distribution of the number of leaves at time $n$ is approximated by normal distribution and the proportional degree sequence obeys power law. The branching structure and maximum degree are also discussed in this paper.     

General results on preferential attachment and clustering coefficient

This is a review paper that covers some recent results on the behavior of the clustering coefficient in preferential attachment networks and scale-free networks in general. The paper focuses on general approaches to network science. In other words, instead of discussing different fully specified random graph models, we describe some generic results which hold for classes of models. Namely, we first discuss a generalized class of preferential attachment models which includes many classical models. It turns out that some properties can be analyzed for the whole class without specifying the model. Such properties are the degree distribution and the global and average local clustering coefficients. Finally, we discuss some surprising results on the behavior of the global clustering coefficient in scale-free networks. Here we do not assume any underlying model.     

An inverse‐free ADI algorithm for computing Lagrangian invariant subspaces

The numerical computation of Lagrangian invariant subspaces of large‐scale Hamiltonian matrices is discussed in the context of the solution of Lyapunov equations. A new version of the low‐rank alternating direction implicit method is introduced, which, in order to avoid numerical difficulties with solutions that are of very large norm, uses an inverse‐free representation of the subspace and avoids inverses of ill‐conditioned matrices. It is shown that this prevents large growth of the elements of the solution that may destroy a low‐rank approximation of the solution. A partial error analysis is presented, and the behavior of the method is demonstrated via several numerical examples. Copyright © 2015 John Wiley & Sons, Ltd.     

Modeling networked systems using the topologically distributed bounded rationality framework

In networked systems research, game theory is increasingly used to model a number of scenarios where distributed decision making takes place in a competitive environment. These scenarios include peer‐to‐peer network formation and routing, computer security level allocation, and TCP congestion control. It has been shown, however, that such modeling has met with limited success in capturing the real‐world behavior of computing systems. One of the main reasons for this drawback is that, whereas classical game theory assumes perfect rationality of players, real world entities in such settings have limited information, and cognitive ability which hinders their decision making. Meanwhile, new bounded rationality models have been proposed in networked game theory which take into account the topology of the network. In this article, we demonstrate that game‐theoretic modeling of computing systems would be much more accurate if a topologically distributed bounded rationality model is used. In particular, we consider (a) link formation on peer‐to‐peer overlay networks (b) assigning security levels to computers in computer networks (c) routing in peer‐to‐peer overlay networks, and show that in each of these scenarios, the accuracy of the modeling improves very significantly when topological models of bounded rationality are applied in the modeling process. Our results indicate that it is possible to use game theory to model competitive scenarios in networked systems in a way that closely reflects real world behavior, topology, and dynamics of such systems. © 2016 Wiley Periodicals, Inc. Complexity 21: 123–137, 2016     

Robust exponential stability of discrete‐time uncertain impulsive neural networks with time‐varying delay

The purpose of this paper is to investigate the robust exponential stability of discrete‐time uncertain impulsive neural networks with time‐varying delay. By using Lyapunov functions together with Razumikhin technique, some new robust exponential stability criteria are presented. The obtained results show that the robust stability can be retained under certain impulsive perturbations for the neural network, which has the robust stability property. The obtained results also show that impulses can robustly stabilize the neural network, which does not have the robust stability property. Some examples, together with their simulations, are also given to show the effectiveness and the advantage of the presented results. It should be noted that the impulsive robust exponential stabilization result for discrete‐time neural network with time‐varying delay is given for the first time. Copyright © 2012 John Wiley & Sons, Ltd.