面向成本-收益好的无标度耦合网络构建方法

较大平均路径长度的网络会带来较大的网络延迟, 难以支持时间敏感业务与应用. 通过增加连接可以降低源和目的节点之间的跳数, 进而降低网络平均延迟, 使得更加快速地传播信息, 但是增加连接的同时也增加了网络构建成本. 分层网络是研究网络耦合的一个有效方法, 但目前网络构建过程中将每层网络分别处理并认为每层网络之间没有强相关性. 本文提出了一种面向成本-收益的无标度网络动态构建方法. 此方法将网络分为多层, 基于连续论在高层网络中添加连接, 使得网络演化为无标度网络. 此连续过程包括节点度增加过程和局部网络半径增长两个连续过程, 在增加连接的过程中引入表征网络构建成本和收益的成本-收益指标. 模拟结果表明引入成本-收益指标的无标度耦合网络构建方法能够在合理范围内有效降低网络平均路径长度, 提升网络性能, 并且本文给出了耦合网络的动态业务性能, 通过调整高层网络避免网络拥塞.     

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

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

Grand Canonical Ensembles of Sparse Networks and Bayesian Inference

Maximum entropy network ensembles have been very successful in modelling sparse network topologies and in solving challenging inference problems. However the sparse maximum entropy network models proposed so far have fixed number of nodes and are typically not exchangeable. Here we consider hierarchical models for exchangeable networks in the sparse limit, i.e., with the total number of links scaling linearly with the total number of nodes. The approach is grand canonical, i.e., the number of nodes of the network is not fixed a priori: it is finite but can be arbitrarily large. In this way the grand canonical network ensembles circumvent the difficulties in treating infinite sparse exchangeable networks which according to the Aldous-Hoover theorem must vanish. The approach can treat networks with given degree distribution or networks with given distribution of latent variables. When only a subgraph induced by a subset of nodes is known, this model allows a Bayesian estimation of the network size and the degree sequence (or the sequence of latent variables) of the entire network which can be used for network reconstruction.     

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.     

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

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

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.     

Complex networks: Dynamics and security

This paper presents a perspective in the study of complex networks by focusing on how dynamics may affect network security under attacks. In particular, we review two related problems: attack-induced cascading breakdown and range-based attacks on links. A cascade in a network means the failure of a substantial fraction of the entire network in a cascading manner, which can be induced by the failure of or attacks on only a few nodes. These have been reported for the internet and for the power grid (e.g., the August 10, 1996 failure of the western United States power grid). We study a mechanism for cascades in complex networks by constructing a model incorporating the flows of information and physical quantities in the network. Using this model we can also show that the cascading phenomenon can be understood as a phase transition in terms of the key parameter characterizing the node capacity. For a parameter value below the phase-transition point, cascading failures can cause the network to disintegrate almost entirely. We will show how to obtain a theoretical estimate for the phase-transition point. The second problem is motivated by the fact that most existing works on the security of complex networks consider attacks on nodes rather than on links. We address attacks on links. Our investigation leads to the finding that many scale-free networks are more sensitive to attacks on short-range than on long-range links. Considering that the small-world phenomenon in complex networks has been identified as being due to the presence of long-range links, i.e., links connecting nodes that would otherwise be separated by a long node-to-node distance, our result, besides its importance concerning network efficiency and security, has the striking implication that the small-world property of scale-free networks is mainly due to short-range links.     

Feedback arcs and node hierarchy in directed networks

Directed networks such as gene regulation networks and neural networks are connected by arcs(directed links). The nodes in a directed network are often strongly interwound by a huge number of directed cycles, which leads to complex information-processing dynamics in the network and makes it highly challenging to infer the intrinsic direction of information flow. In this theoretical paper, based on the principle of minimum-feedback, we explore the node hierarchy of directed networks and distinguish feedforward and feedback arcs. Nearly optimal node hierarchy solutions, which minimize the number of feedback arcs from lower-level nodes to higher-level nodes, are constructed by belief-propagation and simulated-annealing methods. For real-world networks, we quantify the extent of feedback scarcity by comparison with the ensemble of direction-randomized networks and identify the most important feedback arcs. Our methods are also useful for visualizing directed networks.     

交织型层级复杂网

为研究两个异质关联网络复合后的结构特征与节点中心性特征,本文提出了交织型层级复杂网络的概念,可描述由两个具有部分相同节点,连接边属性近似的子网所构成的层级复杂网络,并定义了节点交织系数、路径交织系数和网络交织系数3种测度用于衡量两个子网之间的密切程度.针对该类网络,研究并改进了节点度中心性和介数中心性的计算方法,同时提出一种新的中心性指标—助联性,用于衡量子网的某一节点对另一子网联通性和流通性的助益.通过实验分析,验证了本文各类指标的有效性.     

一种信息传播促进网络增长的网络演化模型

为了研究信息传播过程对复杂网络结构演化的影响,提出了一种信息传播促进网络增长的网络演化模型,模型包括信息传播促进网内增边、新节点通过局域世界建立第一条边和信息传播促进新节点连边三个阶段,通过多次自回避随机游走模拟信息传播过程,节点根据路径节点的节点度和距离与其选择性建立连接。理论分析和仿真实验表明,模型不仅具有小世界和无标度特性,而且不同参数下具有漂移幂律分布、广延指数分布等分布特性,呈现小变量饱和、指数截断等非幂律现象,同时,模型可在不改变度分布的情况下调节集聚系数,并能够产生从同配到异配具有不同匹配模式的网络.     

Maximum modular graphs

Modularity has been explored as an important quantitative metric for community and cluster detection in networks. Finding the maximum modularity of a given graph has been proven to be NP-complete and therefore, several heuristic algorithms have been proposed. We investigate the problem of finding the maximum modularity of classes of graphs that have the same number of links and/or nodes and determine analytical upper bounds. Moreover, from the set of all connected graphs with a fixed number of links and/or number of nodes, we construct graphs that can attain maximum modularity, named maximum modular graphs. The maximum modularity is shown to depend on the residue obtained when the number of links is divided by the number of communities. Two applications in transportation networks and data-centers design that can benefit of maximum modular partitioning are proposed.     

Studying Asymmetric Structure in Directed Networks by Overlapping and Non-Overlapping Models

We consider the problem of modeling and estimating communities in directed networks. Models to this problem in the previous literature always assume that the sending clusters and the receiving clusters have non-overlapping property or overlapping property simultaneously. However, previous models cannot model the directed network in which nodes in sending clusters have overlapping property, while nodes in receiving clusters have non-overlapping property, especially for the case when the number of sending clusters is no larger than that of the receiving clusters. This kind of directed network exists in the real world for its randomness, and by the fact that we have little prior knowledge of the community structure for some real-world directed networks. To study the asymmetric structure for such directed networks, we propose a flexible and identifiable Overlapping and Non-overlapping model (ONM). We also provide one model as an extension of ONM to model the directed network, with a variation in node degree. Two spectral clustering algorithms are designed to fit the models. We establish a theoretical guarantee on the estimation consistency for the algorithms under the proposed models. A small scale computer-generated directed networks are designed and conducted to support our theoretical results. Four real-world directed networks are used to illustrate the algorithms, and the results reveal the existence of highly mixed nodes and the asymmetric structure for these networks.     

相依网络的条件依赖群逾渗

相依网络鲁棒性研究多集中于满足无反馈条件的一对一依赖,但现实网络节点往往依赖于多节点构成的依赖群,即使群内部分节点失效也不会导致依赖节点失效.针对此现象提出了一种相依网络的条件依赖群逾渗模型,该模型允许依赖群内节点失效比例不超过容忍度γ时,依赖节点仍可正常工作.通过理论分析给出了基于生成函数方法的模型巨分量方程,仿真结果表明方程理论解与相依网络模拟逾渗值相吻合,增大γ值和依赖群规模可提高相依网络鲁棒性.本文模型有助于更好地理解现实网络逾渗现象,对如何增强相依网络鲁棒性有一定指导作用.     

Cascading failure in multilayer networks with dynamic dependency groups

The cascading failure often occurs in real networks. It is significant to analyze the cascading failure in the complex network research. The dependency relation can change over time. Therefore, in this study, we investigate the cascading failure in multilayer networks with dynamic dependency groups. We construct a model considering the recovery mechanism.In our model, two effects between layers are defined. Under Effect 1, the dependent nodes in other layers will be disabled as long as one node does not belong to the largest connected component in one layer. Under Effect 2, the dependent nodes in other layers will recover when one node belongs to the largest connected component. The theoretical solution of the largest component is deduced and the simulation results verify our theoretical solution. In the simulation, we analyze the influence factors of the network robustness, including the fraction of dependent nodes and the group size, in our model. It shows that increasing the fraction of dependent nodes and the group size will enhance the network robustness under Effect 1. On the contrary, these will reduce the network robustness under Effect 2. Meanwhile, we find that the tightness of the network connection will affect the robustness of networks. Furthermore, setting the average degree of network as 8 is enough to keep the network robust.     

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.     

Transforming a complex network to an acyclic one

Acyclic networks are a class of complex networks in which links are directed and do not have closed loops. Here we present an algorithm for transforming an ordinary undirected complex network into an acyclic one. Further analysis of an acyclic network allows one to find the structural properties of the network. With our approach one can find the communities and key nodes in complex networks. Also we propose a new parameter of complex networks which can mark the most vulnerable nodes of the system. The proposed algorithm can be applied to finding communities and bottlenecks in general complex networks.     

Ricci Curvature-Based Semi-Supervised Learning on an Attributed Network

In recent years, on the basis of drawing lessons from traditional neural network models, people have been paying more and more attention to the design of neural network architectures for processing graph structure data, which are called graph neural networks (GNN). GCN, namely, graph convolution networks, are neural network models in GNN. GCN extends the convolution operation from traditional data (such as images) to graph data, and it is essentially a feature extractor, which aggregates the features of neighborhood nodes into those of target nodes. In the process of aggregating features, GCN uses the Laplacian matrix to assign different importance to the nodes in the neighborhood of the target nodes. Since graph-structured data are inherently non-Euclidean, we seek to use a non-Euclidean mathematical tool, namely, Riemannian geometry, to analyze graphs (networks). In this paper, we present a novel model for semi-supervised learning called the Ricci curvature-based graph convolutional neural network, i.e., RCGCN. The aggregation pattern of RCGCN is inspired by that of GCN. We regard the network as a discrete manifold, and then use Ricci curvature to assign different importance to the nodes within the neighborhood of the target nodes. Ricci curvature is related to the optimal transport distance, which can well reflect the geometric structure of the underlying space of the network. The node importance given by Ricci curvature can better reflect the relationships between the target node and the nodes in the neighborhood. The proposed model scales linearly with the number of edges in the network. Experiments demonstrated that RCGCN achieves a significant performance gain over baseline methods on benchmark datasets.     

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

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

Topology of evolving networks: local events and universality

Networks grow and evolve by local events, such as the addition of new nodes and links, or rewiring of links from one node to another. We show that depending on the frequency of these processes two topologically different networks can emerge, the connectivity distribution following either a generalized power law or an exponential. We propose a continuum theory that predicts these two regimes as well as the scaling function and the exponents, in good agreement with numerical results. Finally, we use the obtained predictions to fit the connectivity distribution of the network describing the professional links between movie actors.     

Degree and wealth distribution in a network induced by wealth

A network induced by wealth is a social network model in which wealth induces individuals to participate as nodes, and every node in the network produces and accumulates wealth utilizing its links. More specifically, at every time step a new node is added to the network, and a link is created between one of the existing nodes and the new node. Innate wealth-producing ability is randomly assigned to every new node, and the node to be connected to the new node is chosen randomly, with odds proportional to the accumulated wealth of each existing node. Analyzing this network using the mean value and continuous flow approaches, we derive a relation between the conditional expectations of the degree and the accumulated wealth of each node. From this relation, we show that the degree distribution of the network induced by wealth is scale-free. We also show that the wealth distribution has a power-law tail and satisfies the 80/20 rule. We also show that, over the whole range, the cumulative wealth distribution exhibits the same topological characteristics as the wealth distributions of several networks based on the Bouchaud-Mèzard model, even though the mechanism for producing wealth is quite different in our model. Further, we show that the cumulative wealth distribution for the poor and middle class seems likely to follow by a log-normal distribution, while for the richest, the cumulative wealth distribution has a power-law behavior.