A Weighted Evolving Network with Community Size Preferential Attachment

Community structure is an important characteristic in real complex network. It is a network consists of groups of nodes within which links are dense but among which links are sparse. In this paper, the evolving network include node, link and community growth and we apply the community size preferential attachment and strength preferential attachment to a growing weighted network model and utilize weight assigning mechanism from BBV model. The resulting network reflects the intrinsic community structure with generalized power-law distributions of nodes＇ degrees and strengths.     

A weight’s agglomerative method for detecting communities in weighted networks based on weight’s similarity

This paper proposes the new definition of the community structure of the weighted networks that groups of nodes in which the edge’s weights distribute uniformly but at random between them. It can describe the steady connections between nodes or some similarity between nodes’ functions effectively. In order to detect the community structure efficiently,a threshold coefficient κ to evaluate the equivalence of edges’ weights and a new weighted modularity based on the weight’s similarity are proposed. Then,constructing the weighted matrix and using the agglomerative mechanism,it presents a weight’s agglomerative method based on optimizing the modularity to detect communities. For a network with n nodes,the algorithm can detect the community structure in time O(n 2 log n 2 ). Simulations on networks show that the algorithm has higher accuracy and precision than the existing techniques. Furthermore,with the change of κ the algorithm discovers a special hierarchical organization which can describe the various steady connections between nodes in groups.     

Mirror nodes in growing random networks

In this article, we consider mirror nodes, which are widely used to reduce local burden, and present two models that are practical for the Internet and probably some other networks. One model introduces an upper limit to the number of links that a node can have, beyond which the node will share the total links with a newly introduced one. Similarly, in the second model, if the number of links exceeds a limit, a new node will be introduced. Unlike the first model, the new node shares with the old one the chance of receiving new links but not the existing links. These models are analytically treated, and from the degree distribution, we can see that the number of nodes with medium links (half the upper limit) increases at the expense of the loss of highly connected nodes. By reducing the burden, this may improve the robustness of the networks.     

Epidemic propagation on adaptive coevolutionary networks with preferential local-world reconnecting strategy

In the propagation of an epidemic in a population, individuals adaptively adjust their behavior to avoid the risk of an epidemic. Differently from existing studies where new links are established randomly, a local link is established preferentially in this paper. We propose a new preferentially reconnecting edge strategy depending on spatial distance (PR- SD). For the PR-SD strategy, the new link is established at random with probability p and in a shortest distance with the probability 1 p. We establish the epidemic model on an adaptive network using Cellular Automata, and demonstrate the effectiveness of the proposed model by numerical simulations. The results show that the smaller the value of parameter p, the more difficult the epidemic spread is. The PR-SD strategy breaks long-range links and establishes as many short-range links as possible, which causes the network efficiency to decrease quickly and the propagation of the epidemic is restrained effectively.     

A self-organizing shortest path finding strategy on complex networks

The shortcomings of traditional methods to find the shortest path are revealed,and a strategy of finding the selforganizing shortest path based on thermal flux diffusion on complex networks is presented.In our method,the shortest paths between the source node and the other nodes are found to be self-organized by comparing node temperatures.The computation complexity of the method scales linearly with the number of edges on underlying networks.The effects of the method on several networks,including a regular network proposed by Ravasz and Baraba’si which is called the RB network,a real network,a random network proposed by Ravasz and Baraba’si which is called the ER network and a scale-free network,are also demonstrated.Analytic and simulation results show that the method has a higher accuracy and lower computational complexity than the conventional methods.     

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.     

Detecting and describing the modular structures of weighted networks

In the functional properties of complex networks, modules play a central role. In this paper, we propose a new method to detect and describe the modular structures of weighted networks. In order to test the proposed method, as an example, we use our method to analyse the structural properties of the Chinese railway network. Here, the stations are regarded as the nodes and the track sections are regarded as the links. Rigorous analysis of the existing data shows that using the proposed algorithm, the nodes of network can be classified naturally. Moreover, there are several core nodes in each module. Remarkably, we introduce the correlation function Grs, and use it to distinguish the different modules in weighted networks.     

Degree and connectivity of the Internet’s scale-free topology

This paper theoretically and empirically studies the degree and connectivity of the Internet’s scale-free topology at an autonomous system (AS) level. The basic features of scale-free networks influence the normalization constant of degree distribution p(k). It develops a new mathematic model for describing the power-law relationships of Internet topology. From this model we theoretically obtain formulas to calculate the average degree,the ratios of the k min -degree (minimum degree) nodes and the k max -degree (maximum degree) nodes,and the fraction of the degrees (or links) in the hands of the richer (top best-connected) nodes. It finds that the average degree is larger for a smaller power-law exponent λ and a larger minimum or maximum degree. The ratio of the k min -degree nodes is larger for larger λ and smaller k min or k max . The ratio of the k max -degree ones is larger for smaller λ and k max or larger k min . The richer nodes hold most of the total degrees of Internet AS-level topology. In addition,it is revealed that the increased rate of the average degree or the ratio of the k min -degree nodes has power-law decay with the increase of k min . The ratio of the k max -degree nodes has a power-law decay with the increase of k max ,and the fraction of the degrees in the hands of the richer 27% nodes is about 73% (the ’73/27 rule’). Finally,empirically calculations are made,based on the empirical data extracted from the Border Gateway Protocol,of the average degree,ratio and fraction using this method and other methods,and find that this method is rigorous and effective for Internet AS-level topology.     

Adaptive local routing strategy on a scale-free network

Due to the heterogeneity of the structure on a scale-free network,making the betweennesses of all nodes become homogeneous by reassigning the weights of nodes or edges is very difficult.In order to take advantage of the important effect of high degree nodes on the shortest path communication and preferentially deliver packets by them to increase the probability to destination,an adaptive local routing strategy on a scale-free network is proposed,in which the node adjusts the forwarding probability with the dynamical traffic load(packet queue length) and the degree distribution of neighbouring nodes.The critical queue length of a node is set to be proportional to its degree,and the node with high degree has a larger critical queue length to store and forward more packets.When the queue length of a high degree node is shorter than its critical queue length,it has a higher probability to forward packets.After higher degree nodes are saturated(whose queue lengths are longer than their critical queue lengths),more packets will be delivered by the lower degree nodes around them.The adaptive local routing strategy increases the probability of a packet finding its destination quickly,and improves the transmission capacity on the scale-free network by reducing routing hops.The simulation results show that the transmission capacity of the adaptive local routing strategy is larger than that of three previous local routing strategies.     

Network analysis and spatial agglomeration of China’s high-speed rail: A dual network approach

China has the largest high-speed railway(HSR) system in the world, and it has gradually reshaped the urban network.The HSR system can be represented as different types of networks in terms of the nodes and various relationships(i.e.,linkages) between them. In this paper, we first introduce a general dual network model, including a physical network(PN)and a logical network(LN) to provide a comparative analysis for China’s high-speed rail network via complex network theory. The PN represents a layout of stations and rail tracks, and forms the basis for operating all trains. The LN is a network composed of the origin and destination stations of each high-speed train and the train flows between them. China’s high-speed railway(CHSR) has different topological structures and link strengths for PN in comparison with the LN. In the study, the community detection is used to analyze China’s high-speed rail networks and several communities are found to be similar to the layout of planned urban agglomerations in China. Furthermore, the hierarchies of urban agglomerations are different from each other according to the strength of inter-regional interaction and intra-regional interaction, which are respectively related to location and spatial development strategies. Moreover, a case study of the Yangtze River Delta shows that the hub stations have different resource divisions and are major contributors to the gap between train departure and arrival flows.     

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.     

社交网络中基于贝叶斯和半环代数模型的节点影响力计算机理

本文综合考虑网络结构及节点间的互动等关键因素, 提出了一种节点影响力分布式计算机理. 首先根据节点交互行为在时域上的自相似特性, 运用带折扣因子的贝叶斯模型计算节点间的直接影响力; 然后运用半环模型来分析节点间接影响力的聚合; 最后根据社交网络的小世界性质及传播门限, 综上计算出节点的综合影响力. 仿真结果表明, 本文给出的模型能有效抑制虚假粉丝导致的节点影响力波动, 消除了虚假粉丝的出现对节点影响力计算带来的干扰, 从中选择影响力高的若干节点作为传播源节点, 可以将信息传播到更多数目的节点, 促进了信息在社交网络中的传播. 关键词： 社交网络 影响力 贝叶斯 半环代数     

Growing community networks with local events

The study of community networks has attracted considerable attention recently. In this paper, we propose an evolving community network model based on local processes, the addition of new nodes intra-community and new links intra- or inter-community. Employing growth and preferential attachment mechanisms, we generate networks with a generalized power-law distribution of nodes’ degrees.     

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.     

虚拟社区网络的演化过程研究

模拟了虚拟社区网络的演化过程并研究其拓扑结构.发现虚拟社区网络在演化过程中，节点的加入、边的加入、网络中度分布、节点的度与其加入网络时间的关系、平均度随时间的变化等方面与传统的无标度网络有所不符.根据国内某论坛的实际网络数据统计与分析，提出了虚拟社区网络的演化机理——虚拟社区网络构造算法.仿真结果表明，模拟以互联网论坛为代表的虚拟社区网络时，该模型能够得到与真实网络相符的特性. 关键词： 复杂网络 虚拟社区 无标度网络     

A highly clustered scale-free network evolved by random walking

In present paper, we propose a highly clustered weighted network model that incorporates the addition of a new node with some links, new links between existing nodes and the edge's weight dynamical evolution based on weight-dependent walks at each time step. The analytical approach and numerical simulation show that the system grows into a weighted network with the power-law distributions of strength, weight and degree. The weight-dependent walk length l will not influence the strength distribution, but the clustering coefficient of the network is sensitive to l. Particularly, the clustering coefficient is especially high and almost independent of the network size when l=2.     

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

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

两层星形网络的特征值谱及同步能力

多层网络是当今网络科学研究的一个前沿方向.本文深入研究了两层星形网络的特征值谱及其同步能力的问题.通过严格导出的两层星形网络特征值的解析表达式,分析了网络的同步能力与节点数、层间耦合强度和层内耦合强度的关系.当同步域无界时,网络的同步能力只与叶子节点之间的层间耦合强度和网络的层内耦合强度有关;当叶子节点之间的层间耦合强度比较弱时,同步能力仅依赖于叶子节点之间的层间耦合强度;而当层内耦合强度比较弱时,同步能力依赖于层内耦合强度;当同步域有界时,节点数、层间耦合强度和层内耦合强度对网络的同步能力都有影响.当叶子节点之间的层间耦合强度比较弱时,增大叶子节点之间的层间耦合强度会增强网络的同步能力,而节点数、中心节点之间的层间耦合强度和层内耦合强度的增大反而会减弱网络的同步能力;而当层内耦合强度比较弱时,增大层内耦合强度会增强网络的同步能力,而节点数、层间耦合强度的增大会减弱网络的同步能力.进一步,在层间和层内耦合强度都相同的基础上,讨论了如何改变耦合强度更有利于同步.最后,对两层BA无标度网络进行数值仿真,得到了与两层星形网络非常类似的结论.     

Network growth with preferential attachment for high indegree and low outdegree

We study the growth of a directed transportation network, such as a food web, in which links carry resources. We propose a growth process in which new nodes (or species) preferentially attach to existing nodes with high indegree (in food-web language, number of prey) and low outdegree (or number of predators). This scheme, which we call inverse preferential attachment, is intended to maximize the amount of resources available to each new node. We show that the outdegree (predator) distribution decays at least exponentially fast for large outdegree and is continuously tunable between an exponential distribution and a delta function. The indegree (prey) distribution is poissonian in the large-network limit.