复杂网络中Top-k影响力节点的识别算法

来源：计算机科学与探索杂志2018年第6期北京时间：

作者：宋甲秀，杨晓翠，张曦煌

单位：江南大学 物联网工程学院，江苏 无锡 214122

摘要：对复杂网络中一组影响力节点的识别进行研究，一个关键且充满挑战性的问题是如何在精度和时间复杂度之间取得很好的权衡。考虑到节点间相互作用，提出了评估节点影响力大小的启发式中心性指标——局部集体影响指标（local collective influence index，LCII），并设计了影响力节点识别的局部集体影响排序算法（local collective influence rank algorithm，LCIR）。该算法时间复杂度虽低，但具有一定的局限性，其所选取影响力节点的数目与网络的异质性有关，在某些经典的网络中，可能选取的影响力节点集合较小。因此，引入影响力节点候选集的思路以及自适应重新计算的方法，对LCIR算法进行改进，提出基于局部集体影响的自适应排序算法（local collective influence rank-adaptive recalculation algorithm，LCIR-AR）。通过4个真实数据集上的IC（independent cascade）传播模型及网络破坏性实验验证了该算法的良好性能，同时揭示了在网络中扮演主要经纪人角色的低度节点的强大影响力。

关键词：复杂网络,影响力节点,集体影响,节点识别