Statistical properties of weighted complex networks characterized by metaweights

We propose several characterizations of weighted complex networks by incorporating the concept of metaweight into the clustering coefficient, degree correlation, and module decomposition. These incorporations make it possible to describe weighted networks depending on how strongly we emphasize weights. Using some applications to real-world weighted networks, we demonstrate that the proposed approach provides rich information that was inaccessible by previous analyses such as the degree correlation for a specific magnitude of weights or the community structure under controlling the importance of roles of the topology and weights.     

Revealing how network structure affects accuracy of link prediction

Link prediction plays an important role in network reconstruction and network evolution. The network structure affects the accuracy of link prediction, which is an interesting problem. In this paper we use common neighbors and the Gini coefficient to reveal the relation between them, which can provide a good reference for the choice of a suitable link prediction algorithm according to the network structure. Moreover, the statistical analysis reveals correlation between the common neighbors index, Gini coefficient index and other indices to describe the network structure, such as Laplacian eigenvalues, clustering coefficient, degree heterogeneity, and assortativity of network. Furthermore, a new method to predict missing links is proposed. The experimental results show that the proposed algorithm yields better prediction accuracy and robustness to the network structure than existing currently used methods for a variety of real-world networks.     

复杂网络的顶点着色及其在疾病免疫中的应用

在复杂网络研究中, 对于网络结构特征的分析已经引起了人们的极大关注, 而其中的网络着色问题却没有得到足够的重视. 为了理解网络结构与着色之间的关系, 本文研究了WS, BA网络以及不同宏观结构参量对于正常K色数的影响, 发现最大团数可以大致反映正常K色数的变化趋势, 而网络的平均度和匹配系数比异质性和聚类系数对于色数的影响更大. 对于一些实际网络的正常着色验证了本文的分析结果. 对复杂网络的顶点进行着色后, 根据独立集内任意两个顶点均不相邻的特点, 我们提出了基于独立集的免疫策略. 与全网随机免疫相比, 基于独立集的免疫策略可令网络更为脆弱, 从而有效抑制疾病的传播. 基于网络着色的独立集提供了一种崭新的免疫思路, 作为一个简单而适用的平台,有助于设计更为有效的免疫策略. 关键词： 复杂网络 正常着色 独立集 免疫策略     

Epidemic dynamics on an adaptive network

Many real-world networks are characterized by adaptive changes in their topology depending on the state of their nodes. Here we study epidemic dynamics on an adaptive network, where the susceptibles are able to avoid contact with the infected by rewiring their network connections. This gives rise to assortative degree correlation, oscillations, hysteresis, and first order transitions. We propose a low-dimensional model to describe the system and present a full local bifurcation analysis. Our results indicate that the interplay between dynamics and topology can have important consequences for the spreading of infectious diseases and related applications.     

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

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

On the degree distribution of projected networks mapped from bipartite networks

Many real-world systems can be represented by bipartite networks. In a bipartite network, the nodes are divided into two disjoint sets, and the edges connect nodes that belong to different sets. Given a bipartite network (i.e. two-mode network) it is possible to construct two projected networks (i.e. one-mode networks) where each one is composed of only one set of nodes. While network analyses have focused on unipartite networks, considerably less attention has been paid to the analytical study of bipartite networks. Here, we analytically derive simple mathematical relationships that predict degree distributions of the projected networks by only knowing the structure of the original bipartite network. These analytical results are confirmed by computational simulations using artificial and real-world bipartite networks from a variety of biological and social systems. These findings offer in our view new insights into the structure of real-world bipartite networks.     

复杂交通运输网络上的拥挤与效率问题研究

本文研究复杂交通运输网络上的拥挤与效率问题. 在无标度网络、随机网络以及小世界网络等不同拓扑结构中, 探讨了不同的能力分配方式和不同的OD (Origin-Destination) 交通需求分布对网络拥挤度和效率的影响. 随着平均交通需求的增加, 分析无标度网络、随机网络以及小世界网络从自由流状态到交通拥堵状态的变化规律. 为便于比较, 本文侧重研究网络拥挤度的倒数, 并将其定义为通畅度. 研究发现网络中的通畅度与效率之间存在线性相关关系, 并且不同网络中的线性比例系数 (或斜率)是不同的, 从而体现了不同网络具有不同的运输性能. 关键词： 复杂网络 拥挤 效率     

An Extended Correlation Dimension of Complex Networks

Fractal and self-similarity are important characteristics of complex networks. The correlation dimension is one of the measures implemented to characterize the fractal nature of unweighted structures, but it has not been extended to weighted networks. In this paper, the correlation dimension is extended to the weighted networks. The proposed method uses edge-weights accumulation to obtain scale distances. It can be used not only for weighted networks but also for unweighted networks. We selected six weighted networks, including two synthetic fractal networks and four real-world networks, to validate it. The results show that the proposed method was effective for the fractal scaling analysis of weighted complex networks. Meanwhile, this method was used to analyze the fractal properties of the Newman–Watts (NW) unweighted small-world networks. Compared with other fractal dimensions, the correlation dimension is more suitable for the quantitative analysis of small-world effects.     

Self-Organization of Topology and Weight Dynamics on Networks from Merging and Regeneration

We propose a model of weighted networks in which the structural evolution is coupled with weight dynamics. Based on a simple merging and regeneration process, the model gives powel-law distributions of degree, strength and weight, as observed in many real networks. It should be emphasized that, in our model, the nontrivial degree-strength correlation can be reproduced and in agreement with empirical data. Moreover, the size-growing evolution model is also presented to meet the properties of real-world systems.     

A Collaboration Network Model with Multiple Evolving Factors

To describe the empirical data of collaboration networks,several evolving mechanisms have been proposed,which usually introduce different dynamics factors controlling the network growth.These models can reasonably reproduce the empirical degree distributions for a number of well-studied real-world collaboration networks.On the basis of the previous studies,in this work we propose a collaboration network model in which the network growth is simultaneously controlled by three factors,including partial preferential attachment,partial random attachment and network growth speed.By using a rate equation method,we obtain an analytical formula for the act degree distribution.We discuss the dependence of the act degree distribution on these different dynamics factors.By fitting to the empirical data of two typical collaboration networks,we can extract the respective contributions of these dynamics factors to the evolution of each networks.     

Phase transitions for information diffusion in random clustered networks

We study the conditions for the phase transitions of information diffusion in complexnetworks. Using the random clustered network model, a generalisation of the Chung-Lurandom network model incorporating clustering, we examine the effect of clustering underthe Susceptible-Infected-Recovered (SIR) epidemic diffusion model with heterogeneouscontact rates. For this purpose, we exploit the branching process to analyse informationdiffusion in random unclustered networks with arbitrary contact rates, and provide noveliterative algorithms for estimating the conditions and sizes of global cascades,respectively. Showing that a random clustered network can be mapped into a factor graph,which is a locally tree-like structure, we successfully extend our analysis to randomclustered networks with heterogeneous contact rates. We then identify the conditions forphase transitions of information diffusion using our method. Interestingly, for variouscontact rates, we prove that random clustered networks with higher clustering coefficientshave strictly lower phase transition points for any given degree sequence. Finally, weconfirm our analytical results with numerical simulations of both synthetically-generatedand real-world networks.     

Self-similar scaling of density in complex real-world networks

Despite their diverse origin, networks of large real-world systems reveal a number of common properties including small-world phenomena, scale-free degree distributions and modularity. Recently, network self-similarity as a natural outcome of the evolution of real-world systems has also attracted much attention within the physics literature. Here we investigate the scaling of density in complex networks under two classical box-covering renormalizations–network coarse-graining–and also different community-based renormalizations. The analysis on over 50 real-world networks reveals a power-law scaling of network density and size under adequate renormalization technique, yet irrespective of network type and origin. The results thus advance a recent discovery of a universal scaling of density among different real-world networks [P.J. Laurienti, K.E. Joyce, Q.K. Telesford, J.H. Burdette, S. Hayasaka, Universal fractal scaling of self-organized networks, Physica A 390 (20) (2011) 3608–3613] and imply an existence of a scale-free density also within–among different self-similar scales of–complex real-world networks. The latter further improves the comprehension of self-similar structure in large real-world networks with several possible applications.     

Efficient overlapping community detection in huge real-world networks

The detection of overlapping community structure in networks can give insight into the structures and functions of many complex systems. In this paper, we propose a simple but efficient overlapping community detection method for very large real-world networks. Taking a high-quality, non-overlapping partition generated by existing, efficient, non-overlapping community detection methods as input, our method identifies overlapping nodes between each pair of connected non-overlapping communities in turn. Through our analysis on modularity, we deduce that, to become an overlapping node without demolishing modularity, nodes should satisfy a specific condition presented in this paper. The proposed algorithm outputs high quality overlapping communities by efficiently identifying overlapping nodes that satisfy the above condition. Experiments on synthetic and real-world networks show that in most cases our method is better than other algorithms either in the quality of results or the computational performance. In some cases, our method is the only one that can produce overlapping communities in the very large real-world networks used in the experiments.     

Interspecific competition underlying mutualistic networks

Multiple classes of interactions may exist affecting one another in a given system. For the mutualistic networks of plants and pollinating animals, it has been known that the degree distribution is broad but often deviates from power-law form more significantly for plants than animals. To illuminate the origin of such asymmetry, we study a model network in which links are assigned under generalized preferential-selection rules between two groups of nodes and find the sensitive dependence of the resulting connectivity pattern on the model parameters. The nonlinearity of preferential selection can come from interspecific interactions among animals and among plants. The model-based analysis of real-world mutualistic networks suggests that a new animal determines its partners not only by their abundance but also under the competition with existing animal species, which leads to the stretched-exponential degree distributions of plants.     

Planar unclustered scale-free graphs as models for technological and biological networks

Many real life networks present an average path length logarithmic with the number of nodes and a degree distribution which follows a power law. Often these networks have also a modular and self-similar structure and, in some cases — usually associated with topological restrictions — their clustering is low and they are almost planar. In this paper we introduce a family of graphs which share all these properties and are defined by two parameters. As their construction is deterministic, we obtain exact analytic expressions for relevant properties of the graphs including the degree distribution, degree correlation, diameter, and average distance, as a function of the two defining parameters. Thus, the graphs are useful to model some complex networks, in particular several families of technological and biological networks, and in the design of new practical communication algorithms in relation to their dynamical processes. They can also help understanding the underlying mechanisms that have produced their particular structure.     

A random growth model for power grids and other spatially embedded infrastructure networks

We propose a model to create synthetic networks that may also serve as a narrative of a certain kind of infrastructure network evolution. It consists of an initialization phase with the network extending tree-like for minimum cost and a growth phase with an attachment rule giving a trade-off between cost-optimization and redundancy. Furthermore, we implement the feature of some lines being split during the grid's evolution. We show that the resulting degree distribution has an exponential tail and may show a maximum at degree two, suitable to observations of real-world power grid networks. In particular, the mean degree and the slope of the exponential decay can be controlled in partial independence. To verify to which extent the degree distribution is described by our analytic form, we conduct statistical tests, showing that the hypothesis of an exponential tail is well-accepted for our model data.     

基于Kendall改进的同步算法癫痫脑网络分析

提出了一种基于Kendall等级相关改进的同步算法IRC(inverse rank correlation).Kendall等级相关是非线性动力学分析的一般化算法,可有效地度量变量间的非线性相关性.复杂网络的研究已逐渐深入到社会科学的各个领域,脑网络的研究已经成为当今脑功能研究的热点.利用改进的IRC算法,基于脑电EEG(electroencephalogram)数据来构建大脑功能性网络.对构建的脑功能网络的度指标进行了分析,以调查癫痫脑功能网络是否异于正常人.结果显示:使用该改进的算法能够对癫痫和正常脑功能网络显著区分,且只需要记录很短的脑电数据.实验结果数据表明,该方法适用于区分癫痫和正常脑组织网络度指标,它可有助于进一步地加深对大脑的神经动力学行为的研究,并为临床诊断提供有效工具.     

Detecting local community structures in complex networks based on local degree central nodes

Detecting local communities in real-world graphs such as large social networks, web graphs, and biological networks has received a great deal of attention because obtaining complete information from a large network is still difficult and unrealistic nowadays. In this paper, we define the term local degree central node whose degree is greater than or equal to the degree of its neighbor nodes. A new method based on the local degree central node to detect the local community is proposed. In our method, the local community is not discovered from the given starting node, but from the local degree central node that is associated with the given starting node. Experiments show that the local central nodes are key nodes of communities in complex networks and the local communities detected by our method have high accuracy. Our algorithm can discover local communities accurately for more nodes and is an effective method to explore community structures of large networks.     

An LCOR model for suppressing cascading failure in weighted complex networks

Based on the relationship between capacity and load, cascading failure on weighted complex networks is investigated, and a load-capacity optimal relationship (LCOR) model is proposed in this paper. Compared with three other kinds of load-capacity linear or non-linear relationship models in model networks as well as a number of real-world weighted networks including the railway network, the airports network and the metro network, the LCOR model is shown to have the best robustness against cascading failure with less cost. Furthermore, theoretical analysis and computational method of its cost threshold are provided to validate the effectiveness of the LCOR model. The results show that the LCOR model is effective for designing real-world networks with high robustness and less cost against cascading failure.     

Change of network load due to node removal

The interplay between topology changes and the redistribution of traffic plays a significant role in many real-world networks. In this paper we study how the load of the remaining network changes when nodes are removed. This removal operation can model attacks and errors in networks, or the planned control of network topology. We consider a scenario similar to the data communication networks, and measure the load of a node by its betweenness centrality. By analysis and simulations, we show that when a single node is removed, the change of the remaining network’s load is positively correlated with the degree of the removed node. In multiple-node removal, by comparing several node removal schemes, we show in detail how significantly different the change of the remaining network’s load will be between starting the removal from small degree/betweenness nodes and from large degree/betweenness nodes. Moreover, when starting the removal from small degree/betweenness nodes, we not only observe that the remaining network’s load decreases, which is consistent with previous studies, but also find that the load of hubs keeps decreasing. These results help us to make a deeper understanding about the dynamics after topology changes, and are useful in planned control of network topology.