论文部分内容阅读
复杂网络的研究对于人们从宏观和微观上理解系统的运行机制以及系统中个体在运行过程中所起作用有很大帮助。近年来,传播动力学作为复杂网络研究的一个重要方面,得到了人们的广泛关注。传播过程在我们的生活中无处不在,事实上,识别并充分地利用网络中传播能力较强的节点,有利于在社交网络中控制舆论的导向,促进新产品的大规模推广,抑制接触网络中流行病的爆发等。目前已有大量中心性指标被提出用于识别和衡量复杂网络中传播能力较强的节点。这些指标从不同的角度考察节点在网络中节点的重要性,各有优势及不足。如度中心性和k-shell分解算法,算法实现简单,时间复杂度较低,但通常情况下划分粒度较粗,与真实情况存在一定差距。接近中心性、介数中心性、特征向量中心性考虑的因素更具全局性,但时间复杂度相对更高,不适合在大规模网络中应用。结合目前的研究现状以及存在的问题,本文主要创新性工作及研究成果概括为以下两个方面:1)设计了分类邻居算法,根据节点在k-shell分解过程中被移除顺序,将节点的邻居分类,通过给不同类别的邻居分配不同权重,区分邻居对节点传播能力的贡献。本文认为节点的邻居越多并且邻居越接近于网络的核心,则节点的传播能力越强。将分类邻居算法与度中心性算法,k-shell分解算法,混合度分解算法(MDD)进行对比。实验结果表明,与其他三种算法相比,分类邻居算法得到的节点传播能力排名更接近于利用经典传染病模型SIR仿真得到的结果,并且分类邻居算法得到的节点排名区分度更大。时间复杂度方面,由于分类邻居算法是在k-shell分解算法基础上实现对节点邻居的分类,所以分析同一个网络耗时稍高于k-shell分解算法,但与MDD算法相比有较明显的优势。2)分析并改进了原始重力中心性算法。原始的重力中心性算法将节点的k-shell值看作节点的“质量”,计算节点对其N步内可达邻居的影响力之和。论文将不同中心性指标作为节点的“质量”,考察基于不同中心性指标的重力中心性算法的表现。考虑到当将节点的度作为节点的“质量”时,待考察节点的度以及该节点对其所有邻居的“引力”之和均考虑了该节点邻居的规模,为消除这种过度考虑对结果带来的影响,本文创造性的提出将k-shell值作为待考察节点的“质量”,用度作为其邻居节点的“质量”。分别在6个真实网络和4个BA无标度网络中进行仿真实验,实验结果表明,大多数情况下,与将其他中心性指标作为节点“质量”的重力中心性算法相比,将k-shell值作为待考察节点的“质量”,将度作为其邻居“质量”的重力中心性算法具有更好的表现。