一类高聚类系数的加权无标度网络及其同步能力分析

针对真实世界中大规模网络都具有明显聚类效应的特点, 提出一类具有高聚类系数的加权无标度网络演化模型, 该模型同时考虑了优先连接、三角结构、随机连接和社团结构等四种演化机制. 在模型演化规则中, 以概率p增加单个节点, 以概率1–p增加一个社团. 与以往研究的不同在于新边的建立, 以概率φ在旧节点之间进行三角连接, 以概率1–φ进行随机连接. 仿真分析表明, 所提出的网络度、强度和权值分布都是服从幂律分布的形式, 且具有高聚类系数的特性, 聚类系数的提高与社团结构和随机连接机制有直接的关系. 最后通过数值仿真分析了网络演化机制对同步动态特性的影响, 数值仿真结果表明, 网络的平均聚类系数越小, 网络的同步能力越强. 关键词： 无标度网络 加权网络 聚类系数 同步能力     

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.     

A Mixed Mechanism of Weighted-Driven and Inner Selection in Networks

For most networks, the weight of connection is changing with their attachment and inner affinity. By introducing a mixed mechanism of weighted-driven and inner selection, the model exhibits wide range power-law distributions of node strength and edge weight, and the exponent can be adjusted by not only the parameter δ but also the probability q. Furthermore, we investigate the weighted average shortest distance, clustering coefficient, and the correlation of our network. In addition, the weighted assortativity coefficient which characterizes important information of weighted topological networks has been discussed, but the variation of coefficients is much smaller than the former researches.     

Flat-head power-law, size-independent clustering, and scaling of coevolutionary scale-free networks

Scale-free topology and high clustering coexist in some real networks, and keep invariant for growing sizes of the systems. Previous models could hardly give out size-independent clustering with selforganized mechanism when succeeded in producing power-law degree distributions. Always ignored, some empirical statistic results display flat-head power-law behaviors. We modify our recent coevolutionary model to explain such phenomena with the inert property of nodes to retain small portion of unfavorable links in self-organized rewiring process. Flat-head power-law and size-independent clustering are induced as the new characteristics by this modification. In addition, a new scaling relation is found as the result of interplay between node state growth and adaptive variation of connections.     

一种可大范围调节聚类系数的加权无标度网络模型

在Barrat, Barthélemy 和 Vespignani (BBV)加权无标度网络模型的基础上，提出了一种可大范围调节聚类系数的加权无标度网络模型——广义BBV模型(GBBV模型).理论分析和仿真实验表明，GBBV模型保留了BBV模型的许多特征，节点度、节点权重和边权值等都服从幂律分布.但是，GBBV模型克服了BBV模型只能小范围调节聚类系数的缺陷，从而可以用于具有大聚类系数网络的建模. 关键词： 无标度网络 加权网络 聚类系数     

Average weighted receiving time in recursive weighted Koch networks

Motivated by the empirical observation in airport networks and metabolic networks, we introduce the model of the recursive weighted Koch networks created by the recursive division method. As a fundamental dynamical process, random walks have received considerable interest in the scientific community. Then, we study the recursive weighted Koch networks on random walk i.e., the walker, at each step, starting from its current node, moves uniformly to any of its neighbours. In order to study the model more conveniently, we use recursive division method again to calculate the sum of the mean weighted first-passing times for all nodes to absorption at the trap located in the merging node. It is showed that in a large network, the average weighted receiving time grows sublinearly with the network order.     

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.     

Surveying network community structure in the hidden metric space

Most real-world networks from various fields share a universal topological property as community structure. In this paper, we propose a node-similarity based mechanism to explore the formation of modular networks by applying the concept of hidden metric spaces of complex networks. It is demonstrated that network community structure could be formed according to node similarity in the underlying hidden metric space. To clarify this, we generate a set of observed networks using a typical kind of hidden metric space model. By detecting and analyzing corresponding communities both in the observed network and the hidden space, we show that the values of the fitness are rather close, and the assignments of nodes for these two kinds of community structures detected based on the fitness parameter are extremely matching ones. Furthermore, our research also shows that networks with strong clustering tend to display prominent community structures with large values of network modularity and fitness.     

基于度与集聚系数的网络节点重要性度量方法研究

网络中节点重要性度量对于研究网络的鲁棒性具有十分重要的意义. 研究者们普遍运用度或集聚系数来度量节点的重要程度, 然而度指标只考虑节点自身邻居个数而忽略了其邻居之间的信息, 集聚系数只考虑节点邻居之间的紧密程度而忽略了其邻居的规模. 本文综合考虑节点的邻居个数, 以及其邻居之间的连接紧密程度, 提出了一种基于邻居信息与集聚系数的节点重要性评价方法. 对美国航空网络和美国西部电力网进行的选择性攻击实验表明, 采用该方法的效果较k-shell指标可以分别提高24%和112%. 本文的节点重要性度量方法只需要考虑网络局部信息, 因此非常适合于对大规模网络的节点重要性进行有效分析. 关键词： 网络科学 鲁棒性 节点重要性 集聚系数     

Ant colony clustering with fitness perception and pheromone diffusion for community detection in complex networks

Community structure detection in complex networks has been intensively investigated in recent years. In this paper, we propose an adaptive approach based on ant colony clustering to discover communities in a complex network. The focus of the method is the clustering process of an ant colony in a virtual grid, where each ant represents a node in the complex network. During the ant colony search, the method uses a new fitness function to percept local environment and employs a pheromone diffusion model as a global information feedback mechanism to realize information exchange among ants. A significant advantage of our method is that the locations in the grid environment and the connections of the complex network structure are simultaneously taken into account in ants moving. Experimental results on computer-generated and real-world networks show the capability of our method to successfully detect community structures.     

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.     

Density-based shrinkage for revealing hierarchical and overlapping community structure in networks

The investigation of community structure in networks is an important issue in many disciplines, which still remains a challenging task. First, complex networks often show a hierarchical structure with communities embedded within other communities. Moreover, communities in the network may overlap and have noise, e.g., some nodes belonging to multiple communities and some nodes marginally connected with the communities, which are called hub and outlier, respectively. Therefore, a good algorithm is desirable to be able to not only detect hierarchical communities, but also to identify hubs and outliers. In this paper, we propose a parameter-free hierarchical network clustering algorithm DenShrink. By combining the advantages of density-based clustering and modularity optimization methods, our algorithm can reveal the embedded hierarchical community structure efficiently in large-scale weighted undirected networks, and identify hubs and outliers as well. Moreover, it overcomes the resolution limit possessed by other modularity-based methods. Our experiments on the real-world and synthetic datasets show that DenShrink generates more accurate results than the baseline methods.     

一种能耗均衡的无线传感器网络加权无标度拓扑研究

针对无线传感器网络节点能耗不均衡问题,通过对节点生命期建模,得出节点生命期受节点剩余能量和通信距离的影响,进而将两端节点生命期作为构建拓扑时边权重的影响因子,通过边权重控制节点权重,最终得出了一种能耗均衡的无线传感器网络加权无标度拓扑模型,并理论证明了该模型的点权、边权和节点度均服从幂律分布.实验结果表明,该模型具有无标度拓扑的强容错性,并有效的均衡了网络中的节点能耗,延长了网络的生命期.     

一种新的网络传播中最有影响力的节点发现方法

在复杂网络的传播模型研究中, 如何发现最具影响力的传播节点在理论和现实应用中都有重大的意义. 目前的研究一般使用节点的度数、紧密度、介数和K-shell等中心化指标来评价影响力, 这种方法虽然简单, 但是由于它们仅利用了节点自身的内部属性, 因而在评价影响力时精确度并不高, 普遍性适用性较弱.为了解决这个问题, 本文提出了KSC (K-shell and community centrality)指标模型. 此模型不但考虑了节点的内部属性, 而且还综合考虑了节点的外部属性, 例如节点所属的社区等. 然后利用SIR (susceptible-infected-recovered)模型对传播过程进行仿真, 实验证明所提出的方法可以更好地发现最具有影响力的节点, 且可适用于各种复杂网络. 本文为这项具有挑战性研究提供了新的思想和方法. 关键词： 复杂网络 最具影响力的节点 社区划分 中性化测量     

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

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

Synchronization speed of identical oscillators on community networks

Synchronizability of complex oscillators networks has attracted much research interest in recent years. In contrast, in this paper we investigate numerically the synchronization speed, rather than the synchronizability or synchronization stability, of identical oscillators on complex networks with communities. A new weighted community network model is employed here, in which the community strength could be tunable by one parameter δ. The results showed that the synchronization speed of identical oscillators on community networks could reach a maximal value when δ is around 0.1. We argue that this is induced by the competition between the community partition and the scale-free property of the networks. Moreover, we have given the corresponding analysis through the second least eigenvalue λ₂ of the Laplacian matrix of the network which supports the previous result that the synchronization speed is determined by the value of λ₂.     

Kernel spectral clustering with memory effect

Evolving graphs describe many natural phenomena changing over time, such as social relationships, trade markets, metabolic networks etc. In this framework, performing community detection and analyzing the cluster evolution represents a critical task. Here we propose a new model for this purpose, where the smoothness of the clustering results over time can be considered as a valid prior knowledge. It is based on a constrained optimization formulation typical of Least Squares Support Vector Machines (LS-SVM), where the objective function is designed to explicitly incorporate temporal smoothness. The latter allows the model to cluster the current data well and to be consistent with the recent history. We also propose new model selection criteria in order to carefully choose the hyper-parameters of our model, which is a crucial issue to achieve good performances. We successfully test the model on four toy problems and on a real world network. We also compare our model with Evolutionary Spectral Clustering, which is a state-of-the-art algorithm for community detection of evolving networks, illustrating that the kernel spectral clustering with memory effect can achieve better or equal performances.     

基于社团结构的城市地铁网络模型研究

本文运用复杂网络理论, 对我国北京、上海、广州和深圳等城市的地铁网络进行了实证研究. 分别研究了地铁网络的度分布、聚类系数和平均路径长度. 研究表明, 该网络具有高的聚类系数和短的平均路径长度, 显示小世界网络的特征, 其度分布并不严格服从幂律分布或指数分布, 而是呈多段的分布, 显示层次网络的特征. 此外, 它还具有重叠的社团结构特征. 基于实证研究的结果, 提出一种基于社团结构的交通网络模型, 并对该模型进行了模拟分析, 模拟结果表明, 该模型的模拟结果与实证研究结果相符. 此外, 该模型还能解释其他类型的复杂网络(如城市公共汽车交通网络)的网络特性. 关键词： 复杂网络 地铁网络 小世界 社团     

交通流驱动的含权网络

文章对含权复杂网络研究的最近进展给予了评述，特别报道了文章作者最近提出的一个交通流驱动的含权技术网络模型。这一模型能够同时给出网络连接度分布的幂函数律、网络强度分布的幂函数律、网络权重分布的幂函数律，以及高聚集性和非相称混合性等五大特征，因此成功地刻画了真实技术网络的无尺度性质和小世界效应     

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.