基于三跳速度衰减传播模型的影响力最大化方法及装置

摘要

本申请公开了基于三跳速度衰减传播模型的影响力最大化方法及装置，包括：将社交网络抽象为有向图数据结构G(V,E)，G表示有向图，V代表节点的集合，节点代表一个用户或者一个群组，E代表边的集合，每条边代表两个节点之间的关系，扫描图G，得出每个节点的出度w并保存，定义距离衰减因子μ和时间衰减因子根据μ和定义影响力传播速率v，根据μ和定义节点影响力目标函数σ，根据影响力传播速率v在图G进行传播，构建每个节点的三跳传播路径，利用影响力目标函数量化每个节点的影响力，进行算法迭代，寻找前z个影响力最大的节点并输出，同时还公开了基于三跳速度衰减传播模型的影响力最大化节点计算装置。

权利要求

1.一种基于三跳速度衰减传播模型的影响力最大化节点计算装置，其特征在于包括接收单元、数据预处理单元、计算单元、显示单元及主控单元，接收单元、数据预处理单元、计算单元、显示单元依次通过数据总线连接，主控单元和接收单元、数据预处理单元、计算单元、显示单元再通过信号总线分别和主控单元连接；

所述接收单元用于接收社交网络数据并保存；

所述数据预处理单元用于将接收的社交网络数据编号并转换成有向图数据结构G(V,E)；

所述计算单元的工作方式为：在有向图G中设定初始活跃状态节点及大于1的整数z后，综合距离衰减因子和时间衰减因子两项影响力因素定义影响力传播速率，利用影响力传播速率定义影响力目标函数，以建立基于三跳的信息衰减模型，信息在图G中开始传播并不断激活非活跃节点，在有向图中不再出现被成功激活的节点后，构建每个节点的三跳传播路径，利用定义的影响力目标函数量化每个节点的影响力，进行算法迭代，寻找社交网络图结构G中前z个影响力最大的节点；

所述显示单元用于将获取的z个节点的编号在屏幕上输出；

所述主控单元，用于控制数据及信号在各单元间的流动顺序以及控制整个装置的运行；所定义的距离衰减因子 d为图G(V,E)中某个节点与处于初始活跃状态的节点i之间的距离；时间衰减因子 其中e是自然常数，λ是根据社交网络的属性及社交网络上传播的信息类型而针对性地定义的值，t是信息从零时刻起开始传播到传播到某节点时所经历的延迟时间；所定义的影响力传播速率为所定义节点影响力目标函数σ(i)如下述公式：

其中i、j、k、l是信息传播路径上依次经过的四个节点，wi是节点i的出度，wj是节点j的出度，wk是节点k的出度，wl是节点l的出度， 表示节点i到节点j之间影响力传播速率，表示节点i到节点k之间影响力传播速率， 表示节点i到节点l之间影响力传播速率。

2.根据权利要求1所述的基于三跳速度衰减传播模型的影响力最大化节点计算装置，其特征在于：所述有向图数据结构用G(V,E)表示，其中G表示有向图，V代表节点的集合，每个节点代表一个用户或者一个群组，E代表节点间边的集合，每条边代表两个节点之间的关系，V的模|V|代表图G(V,E)中节点的数目，保存每个节点的出度信息及节点之间的距离。

3.根据权利要求1所述的基于三跳速度衰减传播模型的影响力最大化节点计算装置，其特征在于：主控单元的工作方式为：在初始状态启动总控单元及显示单元后，接收单元接收社交网络数据，数据接收完毕后，接收单元通过信号总线向总控单元发出总线信号，总控单元启动数据预处理单元，通过信号总线向接收单元发出控制信号，接收单元通过数据总线向数据预处理单元传送数据，数据预处理单元接收数据并进行处理，数据处理完毕后通过信号总线向总控单元发出总线信号，主控单元接收总线信号并启动计算单元，总控单元向计算单元发出总线信号，计算单元开始计算，计算完毕后向总控单元发出总线信号，主控单元接收总线信号后启动显示单元，主控单元向计算单元发出信号，然后计算单元通过数据总线向显示单元传输数据，数据传输完毕后通过数据总线向主控单元发出总线信号，主控单元控制显示单元进行数据显示。

4.根据权利要求1所述的基于三跳速度衰减传播模型的影响力最大化节点计算装置，其特征在于：接收单元、数据预处理单元、计算单元、显示单元间的数据总线为单向数据总线，接收单元、数据预处理单元、计算单元、显示单元同主控单元间的信号总线为双向信号总线。

5.一种基于三跳速度衰减传播模型的影响力最大化方法，其特征在于包括如下步骤：

S1、通过接收单元获取社交网络数据，然后通过数据预处理单元将社交网络抽象为有向图数据结构G(V,E)并编号，其中G表示有向图，V代表节点的集合，每个节点代表一个用户或者一个群组，E代表节点间边的集合，每条边代表两个节点之间的关系，V的模|V|代表图G中节点的数目，社交网络有向图结构G(V,E)中的每个节点有两种状态：活跃状态和非活跃状态；处于活跃状态的节点会对其处于非活跃状态的邻居节点产生激励，这种激励会使处于非活跃状态的节点以概率p变成活跃状态的节点；

S2、预设定节点集合V中的某一个节点i为初始活跃状态节点，预设定值大于1的整数z；

S3、扫描有向图G(V,E)，得出每个节点的出度w并保存；

S4、捕捉影响力因素，建立基于三跳的信息衰减模型，所述影响力因素包括距离衰减因素和时间衰减因素，构建基于三跳的信息衰减模型具体方法如下：S41、定义距离衰减因子 d为图G(V,E)中某个节点与处于初始活跃状态的节点i之间的距离；

S42、定义时间衰减因子 其中e是自然常数，λ是根据社交网络的属性及社交网络上传播的信息类型而针对性地定义的值，t是信息从零时刻起开始传播到传播到某节点时所经历的延迟时间；

S43、根据步骤S41所述的距离衰减因子μ和步骤S42所述的时间衰减因子定义影响力传播速率

S5、根据步骤S3得到的图G(V,E)各节点的出度w和步骤S43得到的影响力传播速率v定义节点影响力目标函数σ(i)如下述公式：其中i、j、k、l是信息传播路径上依次经过的四个节点，wi是节点i的出度，wj是节点j的出度，wk是节点k的出度，wl是节点l的出度， 表示节点i到节点j之间影响力传播速率，表示节点i到节点k之间影响力传播速率， 表示节点i到节点l之间影响力传播速率；

S6、在零时刻信息从步骤S2中所定义的处于初始活跃状态的节点i开始以单位速度开始在社交网络图G(V,E)进行传播，传播速度逐渐衰减，直到集合中没有被激活的节点，传播过程结束，构建每个节点的三跳传播路径，利用步骤S5中定义的影响力目标函数量化每个节点的影响力，进行算法迭代，寻找社交网络图结构G(V,E)中前z个影响力最大的节点并通过显示单元显示。

6.根据权利要求5所述的基于三跳速度衰减传播模型的影响力最大化方法，其特征在于：步骤S1中所述邻居节点为：在有向图G(V,E)中，如果存在一条从节点i指向节点j的有向边，则称节点j为节点i的邻居节点。

7.根据权利要求5所述的基于三跳速度衰减传播模型的影响力最大化方法，其特征在于：步骤S6中所述三跳传播路径为：在有向图G(V,E)中，若存在一条信息传播路径i‑>j‑>k‑>l，在量化节点i的影响力时，只计算包含节点j、k、l在内的节点i对其所有三跳范围以内邻居的节点的影响力，对信息从l节点开始继续在图G(V,E)中传播时被激活的节点，不将其包括在量化节点i的影响力范围内。

说明书

基于三跳速度衰减传播模型的影响力最大化方法及装置

技术领域

[0001] 本申请涉及社交网络研究领域，特别是涉及一种基于三跳速度衰减传播模型的影响力最大化方法及装置。

背景技术

[0002] 近年来，互联网技术极速发展，网络用户数量越来越庞大，为社交网络的研究提供了大量的数据，网络中蕴藏的潜在价值也越来越高，人们的生活和社交网络的联系也越来越紧密，网络对人们现实生活的影响也逐渐增大，社交网络影响力模型问题最近成为社交
网络分析的热点，社交网络中的一个重要的问题是影响力最大化问题，此问题的研究有着
很重要的现实意义，针对此问题，现在已经有很多相关的研究和产业，如：广告营销，舆论监控等。

[0003] 在社交网络影响力最大化研究领域中，对信息传播过程中其影响力的扩散进行建模是一个重要的问题和挑战，在影响力传播问题中，用图数据结构表述社交网络，我们的目标是在图中找出最具有影响力的z个节点，使得社交网络中最终被影响的节点最多，信息传播范围最大。信息在社交网络传播过程中都遵循一定的模型，我们称之为信息传播模型，在影响力传播图模型中，一个活跃节点通过激活其未活跃的邻居节点接受新观点或新产品来
达到影响扩散的目的，该问题就是找到一小部分节点作为初始活跃节点进行传播，以使最
终的影响力达到最大。现有技术中主要算法是此问题研究初期的贪心算法，贪心算法大多
采用蒙特卡洛模拟，此方法对小型网络中信息传播的模拟比较精确，但是在大型网络上，当数据规模较大的情况下，此方法的时间复杂度极高，这使得将相关算法运用到解决现实工
作生活中的大型网络中的问题时不太现实，于是很多学者对贪心算法进行了改进，提出了
一些启发式算法，如：爬山算法，此类算法虽然大大降低了算法的时间复杂度，但是也会导致最终求解的精确度下降。由于现实生活中新问题的出现和需求推动，有研究学者提出了
针对特定问题的影响力最大化算法，如：在有预算限制下的影响力最大化算法、动态网络上的影响力最大化算法，还有一些学者将经济学概念、Shapley‑Value概念和遗传算法相结合来以解决问题。但是在影响力最大化领域，针对信息传播的影响强度随着时间的推移而衰
减方面的研究成果几乎没有，目前急需一种高效率的算法且精确度也足够高的算法以有效
地处理此类问题。

发明内容

[0004] 本申请的目的是提供一种基于三跳速度衰减传播模型的影响力最大化方法及装置，以解决上述现有技术存在的问题，在保证算法准确度的前提下大幅度提高算法的时间
效率。

[0005] 为实现上述目的，本申请提供了如下方案：本申请提供一种基于三跳速度衰减传播模型的影响力最大化方法及装置。

[0006] 如图7所示，本申请首先公开了一种基于三跳速度衰减传播模型的影响力最大化节点计算装置，包括如下内容：

[0007] 一种基于三跳速度衰减传播模型的影响力最大化节点计算装置，其特征在于包括接收单元、数据预处理单元、计算单元、显示单元及主控单元，接收单元、数据预处理单元、计算单元、显示单元依次通过数据总线连接，主控单元和接收单元、数据预处理单元、计算单元、显示单元再通过信号总线分别和主控单元连接；

[0008] 所述接收单元用于接收社交网络数据并保存；

[0009] 所述数据预处理单元用于将接收的社交网络数据编号并转换成有向图数据结构G(V,E)；

[0010] 所述计算单元的工作方式为：在有向图G(V,E)中设定初始活跃状态节点及大于1的整数z后，综合距离衰减因子和时间衰减因子两项影响力因素定义影响力传播速率，利用影响力传播速率定义影响力目标函数，以建立基于三跳的信息衰减模型，信息在图G(V,E)
中开始传播并不断激活非活跃节点，在有向图中不再出现被成功激活的节点后，构建每个
节点的三跳传播路径，利用定义的影响力目标函数量化每个节点的影响力，进行算法迭代，寻找社交网络图结构G(V,E)中前z个影响力最大的节点；

[0011] 所述显示单元用于将获取的z个节点的编号在屏幕上输出；

[0012] 所述主控单元，用于控制数据及信号在各单元间的流动顺序以及控制整个装置的运行；

[0013] 所述有向图数据结构用G(V,E)表示，其中G(V,E)表示有向图，V代表节点的集合，每个节点代表一个用户或者一个群组，E代表节点间边的集合，每条边代表两个节点之间的关系，V的模|V|代表图G(V,E)中节点的数目，保存每个节点的出度信息及节点之间的距离；

[0014] 所定义的距离衰减因子 d为图G(V,E)中某个节点与处于初始活跃状态的节点i之间的距离；时间衰减因子 其中e是自然常数，λ是根据社交网络的属性及
社交网络上传播的信息类型而针对性地定义的值，t是信息从零时刻起开始传播到传播到
某节点时所经历的延迟时间；所定义的影响力传播速率为

[0015] 所定义节点影响力目标函数σ(i)如下述公式：

[0016]

[0017] 其中i、j、k、l是信息传播路径上依次经过的四个节点，wi是节点i的出度，wj是节点j的出度，wk是节点k的出度，wl是节点l的出度， 表示节点i到节点j之间影响力传播速率，表示节点i到节点k之间影响力传播速率， 表示节点i到节点l之间影响力传播速率；

[0018] 所述主控单元的工作方式为：在初始状态启动总控单元及显示单元后，接收单元接收社交网络数据，数据接收完毕后，接收单元通过信号总线向总控单元发出总线信号，总控单元启动数据预处理单元，通过信号总线向接收单元发出控制信号，接收单元通过数据
总线向数据预处理单元传送数据，数据预处理单元接收数据并进行处理，数据处理完毕后
通过信号总线向总控单元发出总线信号，主控单元接收总线信号并启动计算单元，总控单
元向计算单元发出总线信号，计算单元开始计算，计算完毕后向总控单元发出总线信号，主控单元接收总线信号后启动显示单元，主控单元向计算单元发出信号，然后计算单元通过
数据总线向显示单元传输数据，数据传输完毕后通过数据总线向主控单元发出总线信号，
主控单元控制显示单元进行数据显示；

[0019] 所述接收单元、数据预处理单元、计算单元、显示单元间的数据总线为单向数据总线，接收单元、数据预处理单元、计算单元、显示单元同主控单元间的信号总线为双向总线；

[0020] 同时本申请还公开一种基于三跳速度衰减传播模型的影响力最大化方法，包括如下步骤：

[0021] S1、通过接收单元获取社交网络数据，然后通过数据预处理单元将社交网络抽象为有向图数据结构G(V,E)并编号，其中G表示有向图，V代表节点的集合，每个节点代表一个用户或者一个群组，E代表节点间边的集合，每条边代表两个节点之间的关系，V的模|V|代表图G(V,E)中节点的数目，社交网络有向图结构G(V,E)中的每个节点有两种状态：活跃状
态和非活跃状态；处于活跃状态的节点会对其处于非活跃状态的邻居节点产生激励，这种
激励会使处于非活跃状态的节点以概率p变成活跃状态的节点；

[0022] S2、预设定节点集合V中的某一个节点i为初始活跃状态节点，预设定值大于1的整数z；

[0023] S3、扫描有向图G(V,E)，得出每个节点的出度w并保存；

[0024] S4、捕捉影响力因素，建立基于三跳的信息衰减模型，所述影响力因素包括距离衰减因素和时间衰减因素，构建基于三跳的信息衰减模型具体方法如下：

[0025] S41、定义距离衰减因子 d为图G(V,E)中某个节点与处于初始活跃状态的节点i之间的距离；

[0026] S42、定义时间衰减因子 其中e是自然常数，λ是根据社交网络的属性及社交网络上传播的信息类型而针对性地定义的值，t是信息从步骤S2中所述的零时刻起开
始传播到传播到某节点时所经历的延迟时间；

[0027] S43、根据步骤S41所述的距离衰减因子μ和步骤S42所述的时间衰减因子 定义影响力传播速率

[0028] S5、根据步骤S3得到的图G(V,E)各节点的出度w和步骤S43得到的影响力传播速率v定义节点影响力目标函数σ(i)如下述公式：

[0029]

[0030] 其中i、j、k、l是信息传播路径上依次经过的四个节点，wi是节点i的出度，wj是节点j的出度，wk是节点k的出度，wl是节点l的出度， 表示节点i到节点j之间影响力传播速率，表示节点i到节点k之间影响力传播速率， 表示节点i到节点l之间影响力传播速率；

[0031] S6、在零时刻信息从步骤S2中所定义的处于初始活跃状态的节点i开始以单位速度开始在社交网络图G(V,E)进行传播，传播速度逐渐衰减，直到集合中没有被激活的节点，传播过程结束，构建每个节点的三跳传播路径，利用步骤S5中定义的影响力目标函数量化
每个节点的影响力，进行算法迭代，寻找社交网络图结构G(V,E)中前z个影响力最大的节点并通过显示单元显示。

[0032] 所述步骤S1中所述邻居节点为：在有向图G(V,E)中，如果存在一条从节点i指向节点j的有向边，则称节点j为节点i的邻居节点。

[0033] 所述步骤S6中所述三跳传播路径为：在有向图G(V,E)中，若存在一条信息传播路径i‑>j‑>k‑>l，在量化节点i的影响力时，只计算包含节点j、k、l在内的节点i对其所有三跳范围以内邻居的节点的影响力，对信息从l节点开始继续在图G(V,E)中传播时被激活的节
点，不将其包括在量化节点i的影响力范围内。

[0034] 本申请公开了以下技术效果：本申请在对信息传播模型进行建模时考虑到了信息传播过程中信息开始会在人群中迅速地蔓延，但随着时间的推移，会发生或迅速或缓慢不
同程度的消失，即信息会随着时间而衰减，本申请准确地捕捉到这种衰减会对影响力最大
化研究产生重要影响，同时考虑到网络中信息的扩散会在三跳之后减弱很多，只考虑三跳
传播依然可以最大程度上利用网络的结构信息，从而准确地捕捉到影响力衰减因素，建立
了基于三跳的信息衰减传播模型，同时研究了三跳方法在信息传播模拟中的有效性，提出
了一种新型的信息传播模型，该模型省略了信息传播过程中不活跃的后半部分，提高了时
间效率，且准确捕获到了扩散过程中影响力的衰减因素，并对影响力及其扩散过程进行量
化，用传播过程中激活节点的度折损后的累加和衡量一个节点的影响力，这样不仅可以体
现一个节点本身的影响力，还可以弥补三跳模拟带来的细微影响力缺失，利用节点的影响
力值，进行算法迭代，寻找top‑z个最有影响力的节点，基于此传播模型，本申请提出了一个三跳的启发式影响力最大化算法，此算法在保证精确度的同时能大幅度减少计算时间，从
而能有效地解决现实生活中社交网络数据量很大时如何合理选择初始用户集合使得产品
推广影响力最大的问题。

附图说明

[0035] 为了更清楚地说明本申请实施例或现有技术中的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本申请的一些实施
例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

[0036] 图1为本申请改进的IMMRA算法流程图；

[0037] 图2为社交网络示意图；

[0038] 图3为在DBLP数据集上运行本申请改进的IMMRA算法与传统的贪心算法的影响力结果对比图；

[0039] 图4为在DBLP数据集上运行传统贪心算法和本申请IMMRA算法的时间效率对比图；

[0040] 图5为在FACEBOOK数据集上运行本申请改进的IMMRA算法与传统的贪心算法的影响力结果对比图；

[0041] 图6为在FACEBOOK数据集上运行传统贪心算法和本申请IMMRA算法的时间效率对比图；

[0042] 图7为本申请基于三跳速度衰减传播模型的影响力最大化节点计算装置的功能单元连接示意图。

[0043] 其中，图2中内部有字母标号的圆圈代表节点，节点之间的连线代表边。

具体实施方式

[0044] 下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他
实施例，都属于本申请保护的范围。

[0045] 为使本申请的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本申请作进一步详细的说明。

[0046] 参见图1‑7所示，本申请提供一种基于三跳速度衰减传播模型的影响力最大化方法及装置，针对现有的影响力最大化算法所存在的问题，提出改进的启发式算法，在保证精确度的前提下提高了运算效率，并通过实验作出验证。

[0047] 如图2所示，本申请用图G(V,E)表示社交网络，V是社交网络中节点的集合，v∈V表示社交网络图结构中的节点，即一个用户或一个群组，E是社交网络中边的集合，用边e＝(i,k)∈E表示节点i到节点k的边，每条边表示两个结点之间的关系，N＝|V|代表社交网络
中节点的数目。在影响力传播过程中节点的激活是指新的产品或者观点传播的过程，网络
中的节点分为两种状态，即活跃状态和非活跃状态，已经接受新信息的节点被认为是处于
活跃状态的节点，未接受新信息的节点被认为是处于非活跃状态，其中处于活跃状态的节
点v会对处于非活跃状态的邻居节点u产生影响，这种影响会使非活跃节点u变成活跃状态
的节点，这个过程就称为节点的激活过程，这个激活过程持续发生，随着时间的推移，越来越多的节点由非活跃状态转变为非活跃状态，这就是信息传播的过程。

[0048] 在社交网络中，一般都存在一个信息传播中心，一个节点对其邻居节点的影响力的强弱随着时间变化是不同的，在传播一个信息时，起初信息在用户之间的传播是非常快
的，随着时间的推移，距离信息传播中心越远的用户对此信息的接受和传播会变得越来越
缓慢。所以，信息在传播过程中，会随着时间的推移和离信息传播中心距离的增加变得越来越慢，本申请定义这种信息传播由快到慢的性质为传播速度。

[0049] 在社交网络图数据结构中，距离信息源越远的节点，和信息源点的关系也越疏离，相应的此节点对信息的响应速度会变慢，对此信息的接受程度也会变小。假设社交网络图中存在有i、j、k、l四个节点，信息传播路径为i‑>j‑>k‑>l，其中节点i为信息源点，在信息传播过程中，信息传播速度会随着传播过程中递减，本申请定义μ为距离衰减因子，公式如下：

[0050]

[0051] 其中，d为图G(V,E)中某个节点与处于初始活跃状态的节点i之间的距离，d越大，速度越小。

[0052] 同时，在社交网络图数据结构中，影响力也会随着时间的推移而减弱。比如当我们使用了一款非常好的产品，我们会非常兴奋并且急着推荐给朋友们，这种推荐会非常大程度的影响他们买这种产品，但是随着时间的推移，这种相互影响力会变得很弱。本申请对这种信息传播速度会随着时间消失而变得越来越慢的递减过程进行建模，即定义时间衰减因
子 如下式所示：

[0053]

[0054] 其中，e是自然常数，λ是根据不同网络而设置的不同参数，根据不同的网络或者传播的信息而针对性地定义其值，t是延迟时间，当信息刚开始传播时，t值趋向于0， 趋向于1，这时影响力没有受到时间推移的影响，没有减弱，随着t的变大， 也会随着变小，即影响力受到了时间推移的影响。

[0055] 基于上文定义的距离衰减因子μ和时间衰减因子 本申请定义影响力传播速率v，

[0056]

[0057] d＝1,t＝0

[0058]

[0059]

[0060] 这里 表示节点i到节点j之间影响力传播速率， 表示节点i到节点k之间影响力传播速率， 表示节点i到节点l之间影响力传播速率。当d＝1，t＝0时， 这时，影响
力并没有衰减，依然是原先的数据，这里所有速率值v都是小于等于1的值，当i节点是影响力传播的初始节点时，v值等于1，其他速率值都小于1，当速率乘以相应节点的影响力时，这个节点的影响力就会小于原先的值，相应的影响力会衰减。

[0061] 下面以t＝0时刻时处于初始活跃状态的i节点为例说明本申请基于三跳的速度衰减的传播模型的含义：在t＝0时刻时，影响力从某一初始处于活跃状态的种子节点i开始向其邻居节点传播，此时影响力衰减为0，传播速率为1,t＝1时刻时，从节点i的被成功激活的邻居节点向它们的邻居节点传播，此时影响力有衰减，但传播速率不为0，重复此过程，直到影响力传播到初始种子节点i的三跳邻居为止。此时，虽然传播过程并未结束，但是由于之后的影响力传播可以忽略不计，所以该模型对三跳以外的传播不再模拟。

[0062] 在现实生活中，越接近信息源头的用户受到信息的影响越大，向外扩散的强度也越大。根据提出的模型，于是，我们得出相应的影响力目标函数σ(*)，其中通用符*代表节点编号，以节点i为例，其影响力目标函数为σ如下式所示：

[0063]

[0064] 其中，wi是节点i的出度，wj是节点j的出度，wk是节点k的出度，wl是节点l的出度。度，是计算机科学数据结构中的一个术语，节点的度表示与节点相连接的边数，在有向图
中，节点的出度是指从节点出发的边的条数， 表示节点i到节点j之间影响力传播速率，
表示节点i到节点k之间影响力传播速率， 表示节点i到节点l之间影响力传播速率，从
上述公式以看出速度越大，影响力的衰减越小，速度越小，影响力相应减少越多。

[0065] 下面以t＝0时刻处于活跃状态的节点集合S0为例说明本申请提出的基于三跳的速度衰减传播模型过程：

[0066] (1)在t＝0时刻，信息从初始传播种子集合S0开始在图G(V,E)中进行传播；

[0067] (2)在t＝1时刻，集合中活跃节点vi，vi∈St―1，节点vi会以概率pij尝试去激活它的非活跃邻居节点vj，若节点vj被成功激活，则将节点vj加入集合S1，重复这个过程；

[0068] (3)在t＝3时，初始传播种子集合S0中的节点的传播过程结束。

[0069] 算法的伪代码详见如下。

[0070]

[0071]

[0072] 在算法IMMRA(G＝(V,E),z)中，第一行用于给初始种子赋值为空，第二行用于定义节点状态集合。第三行到五行计算网络中所有节点的度数，第六行到第十四行循环查找
top‑z个种子节点。第十五行计算种子集合Sz的影响力，这里的影响力是以Sz开始进行传播，传播结束时激活的节点的数量，这里的传播是基于三跳的传播，直到传播过程结束，接下来输出种子集合和其影响力，算法结束。

[0073] 本申请选择真实的有向网络数据集DBLP数据集和FACEBOOK数据集。其中DBLP数据集是论文合作网络数据集，网络中节点表示作者，边表示两个作者之间存在的合作关系。
DBLP网络中的节点数是1000，有9887条边，FACEBOOK数据集网络中有3722个节点，118117条边。

[0074] 本申请算法实验中，在数据预处理部分对实验使用的部分进行了简单的整理。实验主要部分使用了本申请提出的IMMRA算法进行了种子节点的选取，信息传播模拟使用了
本申请提出的基于三跳的速度衰减传播模型。

[0075] 为了验证本申请所提算法的有效性，本申请使用2个真实数据：DBLP数据集和FACEBOOK数据集，并选择了该研究领域最经典的贪心算法作为比较的基准，对本申请提出
IMMRA算法和传统的贪心算法的实验结果进行对比分析，并且作为对比的传统的贪心算法
未经过改进和减枝处理，从而最终的信息模拟准确率高，比较结果也最精确。

[0076] 社交网络中影响力最大化算法的评价指标是影响效果，影响效果即在算法寻找的初始传播种子集合下，使得传播最终结束时受到影响的节点数量最多，以DBLP数据集为研
究对象(DBLP是计算机领域内对研究的成果以作者为核心的一个计算类英文文献的集成数
据库系统，按年代列出了作者的科研成果，包括国际期刊和会议等公开发表的论文)，在图3所示实验结果折线图中，X轴表示种子节点数z，Y轴表示影响效果，本申请在DBLP数据集上设置不同的z值来多次比较本申请IMMRA算法和传统的贪心算法的有效性。

[0077] 图3中方形线段为传统贪心算法在不同z值时影响力结果，星形线段为本申请算法IMMRA在数据集DBLP上的影响力结果。从图3中可以看出，本申请算法精确度基本接近了传
统贪心算法的精确度。

[0078] 图4为在DBLP数据集上运行传统贪心算法和本申请IMMRA算法的时间效率对比，白色柱体表示传统贪心算法的实验运行时间，黑色柱体表示本申请提出的算法的运行时间，
从图4中可以很清晰地看出，在同样的网络上寻找同样多数量的种子节点，本申请的IMMRA
算法的运行时间比传统的贪心算法要少很多。将图4所示的运行时间比较图和图3所示实验
影响力结果图结合起来，可以看出本申请提出的IMMRA算法可以在达到相差不多的精确度
的同时大大地提高时间效率。

[0079] 为了继续验证本申请IMMRA算法的有效性，本申请在另一数据集FACEBOOK数据集上做了实验。图5是在不同z值时，传统贪心算法和本申请IMMRA算法的实验结果，方形线段是传统贪心算法，星形线段是本申请IMMRA算法，从中可以看出，两个算法实验结果有细微差值，本申请算法的精确度接近传统贪心算法的精确度。根据折线段趋势，可以看出，在网络节点数目增加和寻找的种子节点增多时，本申请算法结果趋近传统贪心算法结果。

[0080] 图6展示的是在FACEBOOK数据集上实验时，本申请IMMRA算法和传统的贪心算法所使用的时间对比。图6中上方虚线段是传统贪心算法随z值变化时所使用的时间的变化趋
势，图6中下方实线段是本申请IMMRA算法随z值变化时所使用的时间的变化趋势，从中可以很明确地看出，在z值相同时，本申请IMMRA算法的时间效率要远远高于传统的贪心算法，并且随着z值的增大，传统的贪心算法的时间增长趋势近似指数增长，这个时间计算效率是无法忍受的。从图6中可以看出，本申请IMMRA算法在基本接近传统贪心算法效果时，时间效率大大提高。

[0081] 同时，本发明还提供了一种基于三跳速度衰减传播模型的影响力最大化节点计算装置，如图7所示，此计算装置包括接收单元、数据预处理单元、计算单元、显示单元、总控单元。

[0082] 数据获取单元用于接收社交网络数据并保存。

[0083] 数据预处理单元用于将数据获取单元获取的社交网络数据构造成有向图G(V,E)数据结构，其中G表示有向图，V代表节点的集合，每个节点代表一个用户或者一个群组，E代表节点间边的集合，每条边代表两个节点之间的关系，V的模|V|代表图G(V,E)中节点的数
目，保存每个节点的出度信息及节点之间的距离。

[0084] 计算单元的功能为：在零时刻预设定节点集合V中的某一个节点i为初始活跃状态节点，预设定值大于1的整数z，捕捉影响力因素，建立基于三跳的信息衰减模型，所述影响力因素包括距离衰减因素和时间衰减因素，构建基于三跳的信息衰减模型具体方法如下：

[0085] 1)定义距离衰减因子 d为图G(V,E)中某个节点与处于初始活跃状态的节点i之间的距离；

[0086] 2)定义时间衰减因子 其中e是自然常数，λ是根据社交网络的属性及社交网络上传播的信息类型而针对性地定义的值，t是信息从零时刻起开始传播到传播到某
节点时所经历的延迟时间；

[0087] 3)根据步骤1)所述的距离衰减因子μ和步骤2)所述的时间衰减因子 定义影响力传播速率

[0088] 4)根据得到的图G(V,E)各节点的出度w信息和步骤3)得到的影响力传播速率v定义节点影响力目标函数σ(i)如下述公式：

[0089]

[0090] 其中i、j、k、l是信息传播路径上依次经过的四个节点，wi是节点i的出度，wj是节点j的出度，wk是节点k的出度，wl是节点l的出度， 表示节点i到节点j之间影响力传播速率，表示节点i到节点k之间影响力传播速率， 表示节点i到节点l之间影响力传播速率；

[0091] 在零时刻信息从预设定的处于初始活跃状态的节点i开始以单位速度开始在社交网络图G(V,E)进行传播，传播速度逐渐衰减，直到集合中没有被激活的节点，传播过程结
束，构建每个节点的三跳传播路径，利用定义的影响力目标函数量化每个节点的影响力，进行算法迭代，寻找社交网络图结构G(V,E)中前z个影响力最大的节点。

[0092] 输出单元的功能是将计算单元计算得到的影响力最大的z个节点的编号进行输出。

[0093] 实验证明，本申请的IMMRA算法作为传统贪心算法的改进算法，算法准确度与传统的贪心算法相近，但算法效率要远高于传统的贪心算法，从而能够将本申请中的IMMRA算法用于解决现实生活中计算社交网络影响力最大的z个节点的问题。

[0094] 在本申请的描述中，需要理解的是，术语“纵向”、“横向”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本申请，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本申请的限制。

[0095] 以上所述的实施例仅是对本申请的优选方式进行描述，并非对本申请的范围进行限定，在不脱离本申请设计精神的前提下，本领域普通技术人员对本申请的技术方案做出
的各种变形和改进，均应落入本申请权利要求书确定的保护范围内。