复杂网络节点影响力排序与影响最大化研究

发布时间：2020-07-16 07:19

【摘要】：随着互联网的快速发展,网络数据爆炸式的增长,复杂网络已成为当下国内外专家、学者的研究热点。在近些年的研究过程中,研究人员通过收集大量真实网络数据,总结出了不同领域的复杂网络的特征,并发现复杂网络中节点影响力最大化的研究对于社会发展中的商业推广、信息监控和控制疾病传播等多个领域有着非常重要的意义。通过阅读大量的文献资料,学习复杂网络领域的相关基础理论并深入的分析k-shell分解算法和结构洞特征的节点影响力排序问题,以及对选择最佳种子节点影响最大化的不足。结合目前的研究现状及存在的问题,提出以下两种算法。首先,针对k-shell分解算法划分粗粒化的问题,提出一种基于k-shell与结构洞特征的节点影响力排序算法。该算法考虑形成结构洞特征网络中存在伪核心节点和网络中真实度分布,然后结合“结构洞”约束系数对节点局部属性的影响与衰减函数的对伪核心节点的作用,得到节点影响力排序的相关系数指标,进而识别出节点影响力排序的精准度。其次,深入学习分析启发式VoteRank算法的影响最大化特征,提出一种基于启发式双层投票的影响最大化算法。该算法考虑节点集间存在传播影响力重叠问题,充分利用次邻居节点的投票贡献度,选取最佳种子节点集合,并采用独立级联模型,依据感染比例和感染概率衡量指标,评价提出的算法有效性。最后,分别选取三个真实的网络数据集在SIR传播模型和独立级联模型上进行仿真实验,并与几个经典算法作对比,分析实验结果并得出结论。
【学位授予单位】：燕山大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP301.6;O157.5
【图文】：

简单网络

排序算法 k-shell 分解算法性指标仅考虑节点直接邻居的数量，认为邻居数量相同则仅仅考虑节点的邻居数量是不够全面的，许多研究都表明点所处的位置有很重要的关系，若节点的度值很小，但处那么它的影响力也会很大。基于此，Kitsak 等人提出用 k中节点的核心节点。类似于剥洋葱的方法，将网络中外围剩下的处于内层的节点就是拥有较高影响力的核心节点。网络中度为 1 的节点及其所连边，如果网络中出现新的度，直至网络中再也找不到度为 1 的节点为止，那么已去除掉一层之后，节点在剩下的网络中的度称为节点的剩余度中剩余度为 2 的节点，得到 2-壳，重复上述操作，直到剥下面将根据图 2-1 分析 k-shell 分解算法的算例分析。

示意图,算法,示意图,节点

图 2-2 kl 算法示意图分解 Mdd 算法解算法在对网络进行动态分解的过程中，网络中剩余节点中都会进行更新，然而已被移除的节点的信息却完全没有人[51]针对 k-shell 分解方法仅仅考虑了网络剩余度 kr的影节点外部度 ke(即为节点移除已分解的节点后，该节点耗设计了一个带可调参数的混合度分解方法，如式(2-11i i iMdd kr k e，Mdd 算法与 k-shell 分解算法一致，只考虑了节点的剩法与度中心性算法却是相同的。所以，参数的值在 0法中的壳值也不在是整数，可以更好的对节点进行排序的理解混合度分解 Mdd 算法，下面将根据图 2-3 简单图程描述，其中参数 =0.7取，具体步骤如下。

示意图,混合度,算法,文献

图 2-3 混合度分解 MDD 算法示意图，取自文献[51]4 影响力传播模型4.1 独立级联 IC 模型独立级联(Independent Cascade Midel)模型[52]在当前研究中使用范围最广型首先按照节点在网络信息传递中的角色将其分成两种，在传递中接受信息进行传递的节点为激活节点。如果未参与信息传递过程则为未激活节点。在级联模型中，网络的每条边都会被赋予一个权重uvp ，表示节点 u 通过边u率uvp 影响到节点v。该模型具体传播过程如下。(1) 首先定义网络中，节点的状态要么是激活状态，要么就是未激活状态且节点的状态被激活后，不能在变成未激活状态；(2) 经过一段传播时间内，如果节点 v 的非激活状态邻居节点 w 变为激活，那么节点 w 对节点 v 的激活成功的概率是vwp ，相应的，激活失败的概率 p。需要注意的是，当节点 w 试图激活节点 v 却失败时，那么以后节点

【参考文献】