改进的加权网络节点重要性评估的互信息方法

现有的复杂网络节点重要性评估研究主要集中在无向无权网络上,不能全面客观反映某些真实复杂网络的情况。针对无向加权和有向加权网络中评估指标适用范围有限、评估结果不够全面等问题,借鉴应用于无向无权网络的基于互信息的节点重要性评估方法,提出适用于无向加权网络和有向加权网络的互信息评估方法。该方法将网络中的每条边看作信息流,结合相应复杂网络的结构特点和"信息量"的定义方法,以求出的节点信息量作为节点的重要性评估指标。对实例网络进行分析可知,所提算法在保证评估准确性前提下,能更加细致刻画有向加权网络节点之间的差异性。在对ARPA网络的节点评估中,所提算法与以往指标所评估出的前5个最重要节点的节点编号尤其相近,凸显出该算法快速发掘核心节点的能力,为快速、准确评估无向加权和有向加权网络核心节点,提高网络抗毁性提供一定理论帮助。     

有向加权复杂网络抗毁性测度研究

为有效评估有向加权复杂网络的抗毁性能,考虑网络边的有向性和权重对复杂网络拓扑层抗毁性的影响,提出一种有向加权复杂网络抗毁性测度算法(IMADW)。IMADW利用最短调和距离度量节点之间以及整个网络节点对之间的连接紧密度,采用节点环路系数反映节点可选的路径数,由此得到网络拓扑层的全局抗毁性测度值。通过算法分析和实验仿真验证了该算法的准确性。     

一种面向有权重通信网络的关键节点识别方法

如何在已知网络拓扑的前提下，快速准确地找到复杂通信网络中的关键节点成为当前的研究热点。本文首先建立了一个有权重网络的关键节点识别系统模型。然后，提出了基于加权集体影响力的关键节点识别方法。该方法用集体影响力量化节点信息传播能力，同时结合加权思想，表征有权重网络节点的关键程度。最后，分别对5种典型复杂网络模型进行了随机权重和非随机权重的仿真。仿真结果表明所提方法优于原有集体影响力算法的性能，且算法对球半径的选择不敏感。     

基于时间加权的重叠社区检测算法研究

随着网络结构的不断扩大和日益复杂,重叠社区发现技术对挖掘复杂网络深层潜在结构具有重要意义.本文提出一种基于时间加权的重叠社区检测算法.该方法考虑了用户兴趣的时间因素,构建带有时间加权链接的用户-用户图.接着,基于网络节点的影响力计算用户全局相似度,在此基础上通过计算节点的中心度作为度量节点对社区结构影响力的重要性指标,...     

基于固定邻域规模的动态网络影响力最大化探测算法

以往对影响力最大化问题的研究大多是基于静态图进行优化研究,但在现实中,网络数据量随着时间不断增加,系统不可能实时获取到整个网络中节点之间的连接情况.在传统MaxG探测模型的基础上,采用固定邻域规模和节点邻域层级相结合的方式计算节点影响力大小,提出了新的动态网络探测算法RAS-MaxG(regular area scale-MaxG),解决了传统探测算法由于采用度来衡量节点影响力值所导致的节点之间区分性差的问题.最后通过在真实数据集上的实验对比,验证了所提算法在最终影响力覆盖范围方面具有更好的性能表现.     

一种基于贡献矩阵的有向网络节点关键度计算方法

复杂网络中的关键节点,其重要程度一般要比非关键节点拥有更大影响力。目前已有的关键节点的关键度计算算法大多根据不同的衡量指标进行计算。针对适用于有向网络的关键节点挖掘算法较少且算法中不同衡量指标的结合不够严谨的情况,提出一种基于贡献矩阵的有向网络节点关键度计算算法。该算法通过贡献矩阵结合节点关联关系和节点的位置作为衡量节点关键度标准。在实验网络上的传播实验表明,相较于基于关联关系关键节点挖掘算法（RelaCentrality）来评估关键节点重要性,该算法在挖掘关键节点的过程中效率更高,并且所挖掘得到的关键节点在网络中对信息的传播更为广泛。     

社交网络节点中心性测度

研究节点影响力以及扩大节点影响力的范围在社交网络传播中具有重大意义。为了综合分析节点自身影响力与其潜在影响力,提出了PPI（Personal-Potential Influence,PPI）算法,用介数中心性值,紧密中心性值及k-shell值加权来评估节点自身影响力,再通过节点间的相互影响来评估其潜在影响力。实验结果表明PPI算法在评估节点影响力上有较好的准确性。     

基于核心节点扩散的有向网络重叠社团发现算法

复杂网络中的社团结构探测是当前复杂网络研究领域的一个热点问题。传统的社团划分算法主要以无向、无权网络作为分析对象,不能够适用于现实世界中各种有向网络、加权网络。在分析和研究各种社团划分算法的基础上,提出一种新的重叠社团发现算法。该算法从网络中的核心节点开始,不断合并适应度最大邻居节点,最终将网络划分为多个重叠的社团。最后,将该算法应用到两个有向网络中,实验表明该算法能够很好地划分出有向网络中的重叠社团。     

基于改进k-shell算法的节点影响力的识别

在复杂网络中具有较大影响力的节点在控制谣言传播、优化资源分配、高效传播信息、精确投放广告等方面发挥着重要作用。鉴于当前众多方法在识别节点的不同影响力时存在一定局限性，因此在k-shell方法的基础上，通过度量边的潜在重要性，考虑邻居节点的差异贡献性，从而定义了节点的加权度概念，并提出了MKS（Modified k-shell）算法，该算法综合考虑了节点的本身、位置以及局部属性。通过在具有代表性的Zachary空手道俱乐部网络上进行实现，并和其他典型方法进行比较分析，发现该算法改进了k-shell方法的粗粒化划分，其结果更加合理。     

一种基于加权复杂网络特征的K-means聚类算法

在分析了传统的基于划分的K-means聚类算法的优越性和存在不足的基础上,根据近两年复杂网络研究中部分新的理论成果,提出了复杂网络加权度、加权聚集度与加权聚集系数的定义,并将数据聚类转换为复杂网络上的节点聚类,提出基于加权复杂网络特征的K-means聚类算法(简称WCNFC算法)。实验结果表明,该算法根据节点加权复杂网络特征值,能够较好地找到聚类中心,有效地避免了对初始化选值敏感性的问题,从而使得聚类质量大大提高。     

有向相依网络的可控性研究

针对相依方式对有向相依网络可控性的影响,研究了不同相依方式下有向相依网络的可控性。通过构建基本的有向相依网络模型,结合严格可控性理论,给出了可控性评判指标。同时基于经典的有向随机网络和有向无标度网络,提出3种有向相依网络模型,并研究了随机相依条件下有向相依网络的可控性。随后定义了3种相依方式,并对比分析了在不同相依方式下有向相依网络的可控性。结果表明,在同等相依比例下,基于最低入度与最低出度节点相依的有向相依网络可控性最强,而基于最高入度与最高出度节点相依的有向相依网络可控性最弱,研究成果能够为实际有向相依网络的构建提供有益的参考和指导。     

融合节点重要性的无监督链路预测算法

提高加权网络链路预测算法精确度是研究复杂网络的基础问题之一。常用的基于局部网络结构的无监督预测方法没有考虑到重要性越高的节点越容易产生新连接,且在真实网络上中心性小的节点同样具有高度重要性。针对上述问题,提出一种融合节点重要性的无监督链路预测算法,从结构相似性和节点重要性两个角度计算新连接产生的可能性,并利用自定义系数调节影响程度。在5个真实加权网络数据集上进行实验,结果表明在解决小规模加权网络的快速预测问题上,该算法相比同类方法的预测精确度更高,有监督式链路预测方法并不适用。     

节点分类及失效对网络能控性的影响

复杂系统间的相互作用能够用复杂网络描述.复杂网络中某些节点遭受攻击或破坏会造成网络故障,导致整个网络能控性变化.不同节点失效会对网络能控性有不同的影响.本文提出一种网络节点的分类方式,将网络中的节点根据边的方向和匹配关系分成九种类型,并给出了辨识节点类型的算法.另外,本文给出了基于此分类方式下复杂网络中某类节点失效时,...     

基于复杂网络的社区发现算法研究

近年来,高质量社区的挖掘和发现已经成为复杂网络研究的一个热点。目前大多的社区发现算法主要针对无向网络,但现在的很多真实网络通常都是有向加权的。同时,标签传播算法(LPA)是一种接近线性复杂度的社区发现算法,该算法具有简单高效、不需要提供社区规模和社区个数等先验知识的特点,因而得到了广泛关注和应用。针对有向加权网络,提出了一种基于节点重要性和节点相似性的改进标签传播算法(CRJ-LPA)。该算法综合考虑节点的边权、节点的信息传播能力、节点相似度以及节点集聚系数等因素。算法通过加权的ClusterRank获得节点重要性列表用以避免LPA中的随机选择;然后,采用Jaccard系数度量节点的相似度,结合节点重要性列表计算出一个新的度量CRJ(重要度和相似度),提高了算法的稳定性。实验结果表明,该算法有效可行,且具有较好的鲁棒性。     

Controllability emerging from conditional path reachability in complex networks

Controllability of complex networks is a fundamental requirement to orientate the networks toward a sustainable way of development. Determination of link weights and calculation of eigenvalues of large‐scale matrices are two inevitable problems in applying the exact controllability framework in complex networks. Here, we introduce a novel controllability analysis approach based on the controllability index and the reachability matrix to identify the minimum set of driver nodes, in order to achieve complete regulation of arbitrary networks with general configurations. An effective algorithm is theoretically developed via using only the 0–1 binary structure of the network. Theoretical analysis and numerical examples show that our proposed algorithm possesses structural adaptability and control robustness under the weighted perturbation. Copyright © 2017 John Wiley & Sons, Ltd.     

Deducing Complete Selection Rule Set for Driver Nodes to Guarantee Network's Structural Controllability

Structural controllability is critical for operating and controlling large-scale complex networks. In real applications, for a given network, it is always desirable to have more selections for driver nodes which make the network structurally controllable. Different from the works in complex network field where structural controllability is often used to explore the emergence properties of complex networks at a macro level, in this paper, we investigate it for control design purpose at the application level and focus on describing and obtaining the solution space for all selections of driver nodes to guarantee structural controllability. In accord with practical applications, we define the complete selection rule set as the solution space which is composed of a series of selection rules expressed by intuitive algebraic forms. It explicitly indicates which nodes must be controlled and how many nodes need to be controlled in a node set and thus is particularly helpful for freely selecting driver nodes. Based on two algebraic criteria of structural controllability, we separately develop an input-connectivity algorithm and a relevancy algorithm to deduce selection rules for driver nodes. In order to reduce the computational complexity, we propose a pretreatment algorithm to reduce the scale of network's structural matrix efficiently, and a rearrangement algorithm to partition the matrix into several smaller ones. A general procedure is proposed to get the complete selection rule set for driver nodes which guarantee network's structural controllability. Simulation tests with efficiency analysis of the proposed algorithms are given and the result of applying the proposed procedure to some real networks is also shown, and these all indicate the validity of the proposed procedure.      

Pinning control and controllability of complex dynamical networks

In this article, the notion of pinning control for directed networks of dynamical systems is introduced, where the nodes could be either single-input single-output (SISO) or multi-input multi-output (MIMO) dynamical systems, and could be non-identical and nonlinear in general but will be specified to be identical linear time-invariant (LTI) systems here in the study of network controllability. Both state and structural controllability problems will be discussed, illustrating how the network topology, node-system dynamics, external control inputs and inner dynamical interactions altogether affect the controllability of a general complex network of LTI systems, with necessary and sufficient conditions presented for both SISO and MIMO settings. To that end, the controllability of a special temporally switching directed network of linear time-varying (LTV) node systems will be addressed, leaving some more general networks and challenging issues to the end for research outlook.