Modelling of weighted evolving networks with community structures

Many social and biological networks consist of communities–groups of nodes within which links are dense but among which links are sparse. It turns out that most of these networks are best described by weighted networks, whose properties and dynamics depend not only on their structures but also on the link weights among their nodes. Recently, there are considerable interests in the study of properties as well as modelling of such networks with community structures. To our knowledge, however, no study of any weighted network model with such a community structure has been presented in the literature to date. In this paper, we propose a weighted evolving network model with a community structure. The new network model is based on the inner-community and inter-community preferential attachments and preferential strengthening mechanism. Simulation results indicate that this network model indeed reflect the intrinsic community structure, with various power-law distributions of the node degrees, link weights, and node strengths.     

Finding communities in weighted networks through synchronization

Community detection in weighted networks is an important challenge. In this paper, we introduce a local weight ratio scheme for identifying the community structures of weighted networks within the context of the Kuramoto model by taking into account weights of links. The proposed scheme takes full advantage of the information of the link density among vertices and the closeness of relations between each vertex and its neighbors. By means of this scheme, we explore the connection between community structures and dynamic time scales of synchronization. Moreover, we can also unravel the hierarchical structures of weighted networks with a well-defined connectivity pattern by the synchronization process. The performance of the proposed method is evaluated on both computer-generated benchmark graphs and real-world networks.     

多关系网络上的流行病传播动力学研究

多关系网络已经吸引了许多人的注意, 目前的研究主要涉及其拓扑结构及其演化的分析、 不同类型关系的挖掘、重叠社区的检测、级联失效动力学等. 然而,多关系网络上流行病传播的研究还相对较少. 由此提出一种双关系网络模型(工作-朋友关系网), 研究多关系对于流行病传播动力学行为的影响. 在全接触模式下, 多关系的存在会显著降低网络中的爆发阈值, 使得疾病更容易流行而难以控制. 对比ER (Erdös-Rènyi), WS (Watts-Strogatz), BA (Barabási-Albert)三种网络, 由于结构异质性的差异, WS网络受到的影响最大, ER网络次之, BA网络最小. 有趣的是, 其爆发阈值的相对变化大小与网络结构无关. 在单点接触模式下, 增加强关系的权重将显著提升爆发阈值, 降低感染密度; 随着强关系的比例变化将出现最优值现象: 极大的爆发阈值和极小的感染密度. 随着强关系的边权增加, 达到最优值的边比例将减少. 更为有趣的是, 三个网络中优值出现的位置几乎一致, 独立于网络结构. 这一研究不但有助于理解多关系网络上的病毒传播过程, 也为多关系网络研究提供了一个新的视角. 关键词： 多关系网络 流行病传播 接触模式 爆发阈值     

Link prediction in complex networks via modularity-based belief propagation

Link prediction aims at detecting missing, spurious or evolving links in a network, based on the topological information and/or nodes' attributes of the network. Under the assumption that the likelihood of the existence of a link between two nodes can be captured by nodes' similarity, several methods have been proposed to compute similarity directly or indirectly, with information on node degree. However, correctly predicting links is also crucial in revealing the link formation mechanisms and thus in providing more accurate modeling for networks. We here propose a novel method to predict links by incorporating stochastic-block-model link generating mechanisms with node degree. The proposed method first recovers the underlying block structure of a network by modularity-based belief propagation, and based on the recovered block structural information it models the link likelihood between two nodes to match the degree sequence of the network. Experiments on a set of real-world networks and synthetic networks generated by stochastic block model show that our proposed method is effective in detecting missing, spurious or evolving links of networks that can be well modeled by a stochastic block model. This approach efficiently complements the toolbox for complex network analysis, offering a novel tool to model links in stochastic block model networks that are fundamental in the modeling of real world complex networks.     

权重分布对加权网络效率的影响

加权网络可以对复杂系统的相互作用结构提供更加细致的刻画,而改变边权也成为调整和改善网络性质与功能的新途径.基于已有无权网络的效率概念,文中给出了相似权和相异权网络的网络效率定义,并研究了权重分布对于网络效率的影响.从平权的规则网络出发,通过改变权重的分布形式考察权重分布对网络效率的影响,结果发现,在规则网络上,权重分布随机性的增加提高了网络效率,而在几种常见的权重分布形式中,指数分布对网络效率的改进最为显著.同时,权重随机化之后网络最小生成树的总权重减小,意味着网络的运输成本随着权重异质性的增加而降低.以上结果为深入理解权重对网络结构与功能的影响提供了基础. 关键词： 复杂网络 加权网络 权重 网络效率     

Synchronization in complex clustered networks

Synchronization in complex networks has been an active area of research in recent years. While much effort has been devoted to networks with the small-world and scale-free topology, structurally they are often assumed to have a single, densely connected component. Recently it has also become apparent that many networks in social, biological, and technological systems are clustered, as characterized by a number (or a hierarchy) of sparsely linked clusters, each with dense and complex internal connections. Synchronization is fundamental to the dynamics and functions of complex clustered networks, but this problem has just begun to be addressed. This paper reviews some progress in this direction by focusing on the interplay between the clustered topology and network synchronizability. In particular, there are two parameters characterizing a clustered network: the intra-cluster and the inter-cluster link density. Our goal is to clarify the roles of these parameters in shaping network synchronizability. By using theoretical analysis and direct numerical simulations of oscillator networks, it is demonstrated that clustered networks with random inter-cluster links are more synchronizable, and synchronization can be optimized when inter-cluster and intra-cluster links match. The latter result has one counterintuitive implication: more links, if placed improperly, can actually lead to destruction of synchronization, even though such links tend to decrease the average network distance. It is hoped that this review will help attract attention to the fundamental problem of clustered structures/synchronization in network science.      

有倾向性重连产生的反匹配网络

在具有网络结构的系统中度关联属性对于动力学行为具有重要的影响, 所以产生适当度关联网络的方法对于大量网络系统的研究具有重要的作用. 尽管产生正匹配网络的方法已经得到很好的验证, 但是产生反匹配网络的方法还没有被系统的讨论过. 重新连接网络中的边是产生度关联网络的一个常用方法. 这里我们研究使用重连方法产生反匹配无标度网络的有效性. 我们的研究表明, 有倾向的重连可以增强网络的反匹配属性. 但是有倾向重连不能使皮尔森度相关系数下降到-1, 而是存在一个依赖于网络参数的最小值. 我们研究了网络的主要参数对于网络度相关系数的影响, 包括网络尺寸, 网络的连接密度和网络节点的度差异程度. 研究表明在网络尺寸大的情况下和节点度差异性强的情况下, 重连的效果较差. 我们研究了真实Internet网络, 发现模型产生的网络经过重连不能达到真实网络的度关联系数.     

On synchronizability and heterogeneity in unweighted networks

Synchronization in classes of continuous-time dynamical unweighted networks with different topologies is investigated. A synchronization-optimal network model based on rewiring of links is proposed. Compared with other networks, it exhibits a stronger synchronizability. We presented link density and investigated the correlation of synchronizability, link density and heterogeneity in degree distribution. In this work, it will be shown that synchronizability of Type I networks is independent of heterogeneity in the degree distribution when the link density is smaller than 0.02. Synchronizability and link density are proportional. When the link density is larger than 0.025, heterogeneity decides the curve slope. The synchronizability of Type II networks is drastically enhanced by enhancing the link density when the link density is smaller than 0.025. However synchronizability increases weakly by enhancing the link density when the link density is larger than 0.025.     

A novel similarity measure for mining missing links in long-path networks

Network information mining is the study of the network topology, which may answer a large number of application-based questions towards the structural evolution and the function of a real system. The question can be related to how the real system evolves or how individuals interact with each other in social networks. Although the evolution of the real system may seem to be found regularly, capturing patterns on the whole process of evolution is not trivial. Link prediction is one of the most important technologies in network information mining, which can help us understand the evolution mechanism of real-life network. Link prediction aims to uncover missing links or quantify the likelihood of the emergence of nonexistent links from known network structures. Currently, widely existing methods of link prediction almost focus on short-path networks that usually have a myriad of close triangular structures. However, these algorithms on highly sparse or long-path networks have poor performance. Here, we propose a new index that is associated with the principles of structural equivalence and shortest path length (SESPL) to estimate the likelihood of link existence in long-path networks. Through a test of 548 real networks, we find that SESPL is more effective and efficient than other similarity-based predictors in long-path networks. Meanwhile, we also exploit the performance of SESPL predictor and of embedding-based approaches via machine learning techniques. The results show that the performance of SESPL can achieve a gain of 44.09% over GraphWave and 7.93% over Node2vec. Finally, according to the matrix of maximal information coefficient (MIC) between all the similarity-based predictors, SESPL is a new independent feature in the space of traditional similarity features.     

Optimization and scale-freeness for complex networks

Complex networks are mapped to a model of boxes and balls where the balls are distinguishable. It is shown that the scale-free size distribution of boxes maximizes the information associated with the boxes provided configurations including boxes containing a finite fraction of the total amount of balls are excluded. It is conjectured that for a connected network with only links between different nodes, the nodes with a finite fraction of links are effectively suppressed. It is hence suggested that for such networks the scale-free node-size distribution maximizes the information encoded on the nodes. The noise associated with the size distributions is also obtained from a maximum entropy principle. Finally, explicit predictions from our least bias approach are found to be borne out by metabolic networks.     

加权网络中基于冗余边过滤的k-核分解排序算法

k-核分解排序法对于度量复杂网络上重要节点的传播影响力具有重要的理论意义和应用价值,但其排序粗粒化的缺陷也不容忽视.最新研究发现,一些真实网络中存在局域连接稠密的特殊构型是导致上述问题的根本原因之一.当前的解决方法是利用边两端节点的外部连边数度量边的扩散性,采取过滤网络边来减少这种稠密结构给k-核分解过程造成的干扰,但这种方法并没有考虑现实网络上存在权重的普遍性.本文利用节点权重和权重分布重新定义边的扩散性,提出适用于加权网络结构的基于冗余边过滤的k-核分解排序算法:filter-core.通过世界贸易网、线虫脑细胞网和科学家合著网等真实网络的SIR(susceptible-infectedrecovered)传播模型的仿真结果表明,该算法相比其他加权k-核分解法,能够更准确地度量加权网络上具有重要传播影响力的核心节点及核心层.     

Stabilization of avalanche processes on dynamical networks

The stabilization of avalanches on dynamical networks has been studied. Dynamical networks are networks where the structure of links varies in time owing to the presence of the individual “activity” of each site, which determines the probability of establishing links with other sites per unit time. An interesting case where the times of existence of links in a network are equal to the avalanche development times has been examined. A new mathematical model of a system with the avalanche dynamics has been constructed including changes in the network on which avalanches are developed. A square lattice with a variable structure of links has been considered as a dynamical network within this model. Avalanche processes on it have been simulated using the modified Abelian sandpile model and fixed-energy sandpile model. It has been shown that avalanche processes on the dynamical lattice under study are more stable than a static lattice with respect to the appearance of catastrophic events. In particular, this is manifested in a decrease in the maximum size of an avalanche in the Abelian sandpile model on the dynamical lattice as compared to that on the static lattice. For the fixed-energy sandpile model, it has been shown that, in contrast to the static lattice, where an avalanche process becomes infinite in time, the existence of avalanches finite in time is always possible.     

多重边复杂网络系统的稳定性分析

根据网络中边的不同性质提出了网络拆分的思想,通过引入时滞进行拆分,从而建立了多重边复杂网络的动力学模型. 基于Lyapunov稳定理论研究了多重边复杂网络的稳定性问题,给出了节点动力学无时滞和有时滞两种情况下网络稳定的充分条件. 最后通过数值仿真验证了结论的正确性和有效性.     

Weighted evolving networks.

Many biological, ecological, and economic systems are best described by weighted networks, as the nodes interact with each other with varying strength. However, most evolving network models studied so far are binary, the link strength being either 0 or 1. In this paper we introduce and investigate the scaling properties of a class of models which assign weights to the links as the network evolves. The combined numerical and analytical approach indicates that asymptotically the total weight distribution converges to the scaling behavior of the connectivity distribution, but this convergence is hampered by strong logarithmic corrections.     

Assortative mixing in networks

A network is said to show assortative mixing if the nodes in the network that have many connections tend to be connected to other nodes with many connections. Here we measure mixing patterns in a variety of networks and find that social networks are mostly assortatively mixed, but that technological and biological networks tend to be disassortative. We propose a model of an assortatively mixed network, which we study both analytically and numerically. Within this model we find that networks percolate more easily if they are assortative and that they are also more robust to vertex removal.     

Local affinity in heterogeneous growing networks

In this paper we present a study of the influence of local affinity in heterogeneous preferential attachment (PA) networks. Heterogeneous PA models are a generalization of the Barabási-Albert model to heterogeneous networks, where the affinity between nodes biases the attachment probability of links. Threshold models are a class of heterogeneous PA models where the affinity between nodes is inversely related to the distance between their states. We propose a generalization of threshold models where network nodes have individual affinity functions, which are then combined to yield the affinity of each potential interaction. We analyze the influence of the affinity functions in the topological properties averaged over a network ensemble. The network topology is evaluated through the distributions of connectivity degrees, clustering coefficients and geodesic distances. We show that the relaxation of the criterion of a single global affinity still leads to a reasonable power-law scaling in the connectivity and clustering distributions under a wide spectrum of assumptions. We also show that the richer behavior of the model often exhibits a better agreement with the empirical observations on real networks.     

The influence of tie strength on evolutionary games on networks: An empirical investigation

Extending previous work on unweighted networks, we present here a systematic numerical investigation of standard evolutionary games on weighted networks. In the absence of any reliable model for generating weighted social networks, we attribute weights to links in a few ways supported by empirical data ranging from totally uncorrelated to weighted bipartite networks. The results of the extensive simulation work on standard complex network models show that, except in a case that does not seem to be common in social networks, taking the tie strength into account does not change in a radical manner the long-run steady-state behavior of the studied games. Besides model networks, we also included a real-life case drawn from a coauthorship network. In this case also, taking the weights into account only changes the results slightly with respect to the raw unweighted graph, although to draw more reliable conclusions on real social networks many more cases should be studied as these weighted networks become available.     

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.     

一种全局同质化相依网络耦合模式

相依网络的相依模式(耦合模式)是影响其鲁棒性的重要因素之一.本文针对具有无标度特性的两个子网络提出一种全局同质化相依网络耦合模式.该模式以子网络的总度分布均匀化为原则建立相依网络的相依边,一方面压缩度分布宽度,提高其对随机失效的抗毁性,另一方面避开对度大节点(关键节点)的相依,提高其对蓄意攻击的抗毁性.论文将其与常见的节点一对一的同配、异配及随机相依模式以及一对多随机相依模式作了对比分析,仿真研究其在随机失效和蓄意攻击下的鲁棒性能.研究结果表明,本文所提全局同质化相依网络耦合模式能大大提高无标度子网络所构成的相依网络抗级联失效能力.本文研究成果能够为相依网络的安全设计等提供指导意义.     

Congestion analysis of traffic networks with direction-dependant heterogeneity

Traffic flow directionality and network weight asymmetry are widespread notions in traffic networks. This paper investigates the influence of direction-dependant heterogeneity on traffic congestion. To capture the effect of the link directionality and link weight asymmetry, the heterogeneity indexes of complex networks and the traffic flow model are introduced. The numerical results show that the critical value of heterogeneity determines congestion transition processes. The congestion degree increases with heterogeneity when the network heterogeneity is at a subcritical region. A network is more tolerant of congestion if the heterogeneity of the network is smaller or larger than the critical value. Furthermore, when heterogeneity reaches the critical value, the average number of accumulated vehicles arrives at the maximum and the traffic flow is under a serious congestion state. A significant improvement on the tolerance to congestion of traffic networks can be made if the network heterogeneity is controlled within a reasonable range.