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

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

一种新的复杂网络影响力最大化发现方法

复杂网络中影响力最大化建模与分析是社会网络分析的关键问题之一, 其研究在理论和现实应用中都有重大的意义. 在给定s值的前提下, 如何寻找发现s个最大影响范围的节点集, 这是个组合优化问题, Kempe等已经证明该问题是NP-hard问题. 目前已有的随机算法时间复杂度低, 但是结果最差; 其他贪心算法时间复杂度很高, 不能适用于大型社会网络中, 并且这些典型贪心算法必须以了解网络的全局信息为前提, 而获取整个庞大复杂且不断发展变化的社会网络结构是很难以做到的. 我们提出了一种新的影响力最大化算法模型RMDN, 及改进的模型算法RMDN++, 模型只需要知道随机选择的节点以及其邻居节点信息, 从而巧妙地回避了其他典型贪心算法中必须事先掌握整个网络全局信息的问题, 算法的时间复杂度仅为O(s log(n)); 然后, 我们利用IC模型和LT模型在4种不同的真实复杂网络数据集的实验显示, RMDN, RMDN++算法有着和现有典型算法相近的影响力传播效果, 且有时还略优, 同时在运行时间上则有显著的提高; 我们从理论上推导证明了方法的可行性. 本文所提出的模型算法适用性更广, 可操作性更强, 为这项具有挑战性研究提供了新的思路和方法.