有限步传播范围期望指标判别节点传播影响力

在线社交网络逐渐成为人们不可或缺的重要工具,识别网络中具有高影响力的节点作为初始传播源,在社会感知与谣言控制等方面具有重要意义.本文基于独立级联模型,给出了一个描述有限步传播范围期望的指标-传播度,并设计了一种高效的递推算法.该指标在局部拓扑结构信息的基础上融合了传播概率对影响力进行刻画,能够较好地反映单个节点的传播影响力.对于多传播源影响力极大化问题,本文提出了一种基于传播度的启发式算法-传播度折扣算法,使得多个传播源的联合影响力最大.最后,将上述方法应用到三个真实网络中,与经典指标和方法相比,该方法不需要知道网络的全局结构信息,而是充分了利用网络的局部结构信息,可以较快地筛选出高传播影响力的传播源.

Distinguishing node propagation influence by expected index of finite step propagation range

On-line social networks have gradually become an indispensable tool for people.Identifying nodes with high influence in the network as an initial source of communication is of great significance in social perception and rumor control.According to the independent cascade model,in this paper we present an index describing the finite step propagation range expectation as the degree of propagation,and design an efficient recursive algorithm.Based on the local topology information,the index combines the propagation probability to characterize the influence,which can better reflect the propagation influence of a single node.For a single propagation source influence ordering problem,the node degree of propagation and propagation capability are better consistent with each other.And the propagation degree can well describe the propagation influence of nodes under different networks and propagation probabilities.For maximizing the multi-propagation source influence,in this paper we propose a propagation-based heuristic algorithm which is called propagation discount algorithm.This algorithm makes the joint influence of multiple propagation sources maximized.Finally,in this paper we apply the above method to three real networks,showing better effects than the classic indicators and methods.The algorithm has three advantages.First,the expected value of the final propagation range of each node in the small network can be accurately calculated.Second,the degree of propagation fully considers the local topology of the node and belongs to a locality indicator.Third,the indicator combines the effect of propagation probability and yields good outcomes under different networks and propagation probabilities.