Abstract: To study the identification of a group of influential nodes in complex network, a key and challenging problem is how to get a good balance between accuracy and time complexity. Firstly, considering the interaction between the nodes, this paper proposes a heuristic central index, namely local collective influence index (LCII) that evaluates the influence of nodes, and then designs a local collective influence rank algorithm (LCIR) for influential nodes identification. Although the time complexity of this algorithm is low, in some special networks, the number of selected influential nodes is related to the heterogeneity of networks, it may have the limitation of insufficient selection of influential nodes. Thus, by introducing the idea of influential nodes candidate set and adaptive recalculation method, this paper puts forward a local collective influence rank-adaptive recalculation algorithm (LCIR-AR), which is an improved algorithm of LCIR, and verifies its good performance through the independent cascade model (IC) and network destructive experiments on four real data sets, meanwhile, reveals that low-degree nodes play a major broker role in the network can be powerful influencers.

Key words: complex network, influential nodes, collective influence, identification of nodes

摘要： 对复杂网络中一组影响力节点的识别进行研究，一个关键且充满挑战性的问题是如何在精度和时间复杂度之间取得很好的权衡。考虑到节点间相互作用，提出了评估节点影响力大小的启发式中心性指标——局部集体影响指标（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）传播模型及网络破坏性实验验证了该算法的良好性能，同时揭示了在网络中扮演主要经纪人角色的低度节点的强大影响力。

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