1.本发明涉及社交网络技术领域，更具体的说是涉及一种独立级联模型下基于动态关系的最佳跳扩散方法及系统。
背景技术：2.随着文明的进步，越来越多的人使用互联网来分享信息和想法。这一现象也渐渐导致了社交网络的出现。社交网络是一个海量的信息传播平台。在过去几十年中，社交网络蓬勃发展，产生了前所未有的内容。社交网络的普及引起了人们对信息传播的高度重视。这种扩散现象已被证明在许多应用中非常强大。其中一个经典应用是“病毒式营销”。公司利用最具影响力的用户来推广其产品并实现利润最大化，这也促进了影响力最大化问题(im)的产生。im是信息扩散研究中的一个关键问题，由于其存在巨大的商业价值，近年来得到了广泛的研究。im的目的是在社交网络中找到影响传播最大的节点子集。
3.domingos和richardson是最先调查im问题的人之一。在此基础上，kempe等人定义了im问题，并确定其为np难题。他们还提出了独立级联模型(icm)和线性阈值模型(ltm)。这两个模型为im的发展奠定了基础。随后，kempe等人引入了一种爬山贪婪方法来解决im问题，该算法可以将最优值近似到63％以内。爬山贪婪算法是精确的，但效率较低，因为它需要反复搜索以获得每个顶点的边际影响。
4.因此，人们提出了各种启发式算法来解决效率问题。例如degreediscount和pmia。虽然这些启发式算法缩短了运行时间，但其准确性无法保证。这是因为上述启发式算法通过近似估计节点的影响值甚至根本不计算节点的影响值来选择最有影响力的节点。因此，如何在保证效率的同时准确解决社交网络影响力最大化问题，是亟待解决的。
技术实现要素：5.有鉴于此，本发明提供了一种独立级联模型下基于动态关系的最佳跳扩散方法及系统来平衡效率和准确性，设计合理，克服了现有方法的不足，该方法更适合于解决影响力最大化问题。
6.为了实现上述目的，本发明采用如下技术方案：一种独立级联模型下基于动态关系的最佳跳扩散方法，具体步骤包括如下：
7.构建有向社交网络，获取传播概率；
8.基于传播概率和跳数的动态关系策略，对输入的所述传播概率执行循环，得到对每个节点的跳数；
9.根据所述传播概率和所述跳数计算各个节点的扩散分数；
10.选择前k个所述扩散分数最大的节点作为种子集。
11.可选的，所述有向社交网络为：
12.g＝(v,e)；
13.其中，g表示有向社交网络，|v|＝n，v表示大小为n的节点集合，|e|＝m，e表示大小
为m的边集合。
14.可选的，所述跳数的获取步骤为：
15.初始化字典bp[i，初始化种子集s；
[0016]
执行循环选择，如果传播概率0＜p＜0.1，则跳数h等于1，如果传播概率0.2≤p＜0.3，则跳数h等于3，如果传播概率0.4≤p＜0.6，则跳数h于4，否则跳数h等于5。
[0017]
可选的，计算各个节点的扩散分数的步骤为：
[0018]
计算各个节点的度数d[i
[0019]
各个节点的扩散分数的计算公式如下：
[0020]
bpv＝dv+p
h+1
[0021]
其中，bpv表示节点v的扩散分数，dv表示节点v的度数，p表示传播概率，h表示跳数。
[0022]
可选的，种子集的获取步骤为：
[0023]
s4.1、选出扩散分数字典中数值最大的节点加入种子集；
[0024]
s4.2、将被选择的节点从扩散分数字典中删除；
[0025]
s4.3、重复步骤s4.1和步骤s4.2，直到种子集中的节点数达到k为止。
[0026]
另一方面，一种独立级联模型下基于动态关系的最佳跳扩散系统，包括依次相连的网络搭建模块、数据获取模块、扩散分数计算模块、数据处理模块；其中，
[0027]
所述网络搭建模块，用于构建有向社交网络，获取传播概率；
[0028]
所述数据获取模块，用于基于传播概率和跳数的动态关系策略，对输入的所述传播概率执行循环，得到对每个节点的跳数；
[0029]
所述扩散分数计算模块，用于根据所述传播概率和所述跳数计算各个节点的扩散分数；
[0030]
所述数据处理模块，用于选择前k个所述扩散分数最大的节点作为种子集。
[0031]
经由上述的技术方案可知，与现有技术相比，本发明公开提供了一种独立级联模型下基于动态关系的最佳跳扩散方法及系统，具有以下有益的技术效果：首先，通过使用传播概率和跳数的动态关系策略，改变了一般启发式算法查找种子集的方式，不同的传播概率具有相应的跳数；然后，计算每个节点的扩散分数；最后，最终的种子集由扩散分数最高的前k个节点组成。该方法的影响扩散准确性优于现有的度启发式算法，并保持了可接受的运行时间。因此，所提出的方法有效地解决了社交网络影响力最大化问题。
附图说明
[0032]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。
[0033]
图1是本发明的方法流程图；
[0034]
图2是本发明与现有算法在wiki-vote社交网络的影响范围效果对比图；
[0035]
图3是本发明与现有算法在p2p-gnutella31社交网络的影响范围效果对比图；
[0036]
图4是本发明与现有算法在soc-epinions1社交网络的影响范围效果对比图；
[0037]
图5是本发明与现有算法在cit-hepph社交网络的影响范围效果对比图；
[0038]
图6是本发明与现有算法在wiki-vote社交网络上运行时间对比图；
[0039]
图7是本发明与现有算法在p2p-gnutella31社交网络上运行时间对比图；
[0040]
图8是本发明与现有算法在soc-epinions1社交网络上运行时间对比图；
[0041]
图9是本发明与现有算法在cit-hepph社交网络上运行时间对比图。
具体实施方式
[0042]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0043]
本发明实施例1公开了一种独立级联模型下基于动态关系的最佳跳扩散方法，如图1所示，具体步骤包括如下：
[0044]
s1、构建有向社交网络：g＝(v,e)，|v|＝n,|e|＝m,规定种子集的大小k和传播概率p。
[0045]
其中，g表示有向社交网络，v表示大小为n的节点集合，e表示大小为m的边集合；
[0046]
s2、确定每个节点的跳数h。
[0047]
从s1中得到传播概率p，使用传播概率p和跳数h的动态关系策略，对输入的传播概率p执行循环，得到对应的跳数h；
[0048]
s2的具体步骤为：
[0049]
s2.1、初始化字典bp[i]，初始化种子集s；
[0050]
s2.2、执行循环选择，如果传播概率0＜p＜0.1，则跳数h等于1，如果传播概率0.2≤p＜0.3，则跳数h等于3，如果传播概率0.4≤p＜0.6，则跳数h于4，否则跳数h等于5。
[0051]
s3、计算各个节点的扩散分数。
[0052]
从s1中得到传播概率p，从s2中得到对应的跳数h，对输入的有向社交网络g中的每个节点计算它的度d[i]，扩散分数bp[i]由度数d[i]，传播概率p和跳数h经过计算得到：
[0053]
s3.1、计算各个节点的度数d[i]
[0054]
s3.2、各个节点的扩散分数的计算公式如下：
[0055]
bpv＝dv+p
h+1
[0056]
其中，bpv表示节点v的扩散分数,dv表示节点v的度数，p表示扩散概率，h表示跳数。
[0057]
s4、选择节点加入种子集。
[0058]
从步骤3中得到各个节点的扩散分数bp[i]，选择前k个扩散分数最大的节点作为种子集；
[0059]
s4.1、选出扩散分数字典中数值最大的节点加入种子集；
[0060]
s4.2、将被选择的节点从扩散分数字典中删除；
[0061]
s4.3、重复步骤4.1和步骤4.2，直到种子集中的节点数达到k为止。
[0062]
本发明实施例2公开了一种独立级联模型下基于动态关系的最佳跳扩散系统，包括依次相连的网络搭建模块、数据获取模块、扩散分数计算模块、数据处理模块；其中，
[0063]
网络搭建模块，用于构建有向社交网络，获取传播概率；
[0064]
数据获取模块，用于基于传播概率和跳数的动态关系策略，对输入的传播概率执
行循环，得到对每个节点的跳数；
[0065]
扩散分数计算模块，用于根据传播概率和跳数计算各个节点的扩散分数；
[0066]
数据处理模块，用于选择前k个所述扩散分数最大的节点作为种子集。
[0067]
利用具体实施例验证本发明的技术效果：
[0068]
一、数据集
[0069]
该实施例中，使用来自snap(http://snap.stanford.edu/data/)的四个不同规模的公开的数据集，分别是wiki-vote数据集，p2p-gnutella31数据集，soc-epinions1数据集和cit-hepph数据集。wiki-vote数据集是一个维基百科投票网络，该数据集包含7115个节点和103689条边。从维基百科建立到2008年1月，该网络拥有所有投票数据。p2p-gnutella31数据集包含62586个节点和147892条边。该数据集是一个称为gnutella的对等网络。gnutella网络拓扑中的节点表示主机，网络中的边缘表示主机之间的关系。soc-epinions1数据集有75879个节点和508837条边。这是一个在线社交网络上的通用消费者评论网站。在这个网站上，用户可以选择是否相互“信任”。信任网络由所有消费者的信任关系构成。cit-hepph数据集有34546个节点和421578条边，这是一个高能物理引用网络。数据涵盖的时间跨度为1993年初至2003年初。(超过120个月)。这四个数据集的具体内容如表1所示。
[0070]
表1
[0071]
networks#nodes#edgesavg.degreewiki-vote711510368914.573p2p-gnutella31625861478922.363soc-epinions1758795088376.706cit-hepph3454642157812.203
[0072]
二、实验设置和对比算法
[0073]
本发明在影响传播的过程中使用独立级联模型，其激活概率其中in(v)表示节点v的入度。
[0074]
以下实施例所有的实验中使用的对比算法如下：对种子节点的邻居节点进行度折扣的degreediscount算法、基于强连通组件(scc)的无向图启发式sccheuristic算法、im的两阶段迭代结构的tifim算法、进一步扩展单折扣算法的dhicm算法和基于最大影响力子树的启发式算法pmia与本发明bhicm(best hop diffusion method for dynamic relationships under the independent cascade model)作比较。
[0075]
三、参数的选择
[0076]
通过综合考虑影响传播与运行时间，本发明对传播概率p进行广泛测试，以确定最佳传播概率值使本发明可以达到最佳效果。
[0077]
当传播概率从0.1提高到0.7时，影响扩散显著增加。当传播概率从0.7增加到0.9时，影响扩散几乎没有增加，但运行时间增加。因此，考虑到影响扩散和运行时间，传播概率调整为0.7。
[0078]
四、影响范围
[0079]
图2至图5分别展示了种子集规模在10到330之间，间隔为40时本发明bhicm算法与
其他五种算法degreediscount、sccheuristic、tifim、dhicm和pmia在wiki-vote，p2p-gnutella31，soc-epinions1和cit-hepph四个数据集上影响范围对比图。从这些图可以看出，种子集的大小与影响扩散几乎呈线性正相关。
[0080]
随着种子集的增长，影响传播也会增加。在四个社交网络上，bhicm的性能优于所有的比较算法。关于wiki-vote、p2p-gnutella31和soc-epinions1社交网络，提出的方法比对比算法更准确。
[0081]
具体来说，本发明平均比degreediscount算法、sccheuristic算法、pbmh算法、tifim算法和dhicm算法分别高出49.79％、118.19％、18.54％、8.87％和6.04％。在cithepph数据集中，dhicm比本发明的方法略胜一筹，但本发明的方法优于所有其他比较方法。具体来说，该方法比degreediscount算法、sccheuristic算法、pbmh算法和tifim算法分别好17.67％、122.51％、15.25％和4.55％。上述现象归因于本发明的种子集查找方式保证了精度。综合考虑所有社会网络，可以发现，本发明提出的方法在影响传播方面表现良好。
[0082]
五、运行时间
[0083]
图6至图9分别展示了种子集规模在10到330之间，间隔为40时本发明bhicm与其他五种算法degreediscount、sccheuristic、tifim、dhicm和pmia在wiki-vote，p2p-gnutella31，soc-epinions1和cit-hepph四个数据集上运行时间对比图。
[0084]
pbmh的传播时间太长，与其他五种算法的数量级不同。这是不可比的。因此，本发明只比较了bhicm、degreediscount、sccheuristic、tifim和dhicm。如图所示，当种子集增加时，每种方法的传播时间都有相当大的波动范围。这种现象在degreediscount算法、tifim和dhicm中更为明显。具体而言，本发明的运行时间比degreediscount算法、tifim算法和dhicm算法分别快43.28％、62.31％和66.91％。尽管bhicm的传播时间略长于sccheuristic，但相对于其影响传播而言，传播时间的增加并不重要。
[0085]
综上所述，可以得出以下结论：首先，本发明使用传播概率和跳数之间的动态关系来计算扩散分数，避免了处理种子节点的邻居。然后，定义了扩散分数作为选择种子节点的准则，保证了算法的准确性和效率。本发明的影响扩散性能优于现有的度启发式算法，并保持了可接受的运行时间。因此，本发明提出的方法更适合于解决影响力最大化问题。
[0086]
本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的装置而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。
[0087]
对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。
技术特征：1.一种独立级联模型下基于动态关系的最佳跳扩散方法，其特征在于，具体步骤包括如下：构建有向社交网络，设置传播概率；基于传播概率和跳数的动态关系策略，对输入的所述传播概率执行循环，得到对每个节点的跳数；根据所述传播概率和所述跳数计算各个节点的扩散分数；选择前k个所述扩散分数最大的节点作为种子集。2.根据权利要求1所述的一种独立级联模型下基于动态关系的最佳跳扩散方法，其特征在于，所述有向社交网络为：g＝(v,e)；其中，g表示有向社交网络，|v|＝n，v表示大小为n的节点集合，|e|＝m，e表示大小为m的边集合。3.根据权利要求1所述的一种独立级联模型下基于动态关系的最佳跳扩散方法，其特征在于，所述跳数的获取步骤为：初始化字典bp[i]，初始化种子集s；执行循环选择，如果传播概率0＜p＜0.1，则跳数h等于1，如果传播概率0.2≤p＜0.3，则跳数h等于3，如果传播概率0.4≤p＜0.6，则跳数h于4，否则跳数h等于5。4.根据权利要求1所述的一种独立级联模型下基于动态关系的最佳跳扩散方法，其特征在于，计算各个节点的扩散分数的步骤为：计算各个节点的度数d[i]各个节点的扩散分数的计算公式如下：bp
v
＝d
v
+p
h+1
其中，bp
v
表示节点v的扩散分数，d
v
表示节点v的度数，p表示传播概率，h表示跳数。5.根据权利要求1所述的一种独立级联模型下基于动态关系的最佳跳扩散方法，其特征在于，种子集的获取步骤为：s4.1、选出扩散分数字典中数值最大的节点加入种子集；s4.2、将被选择的节点从扩散分数字典中删除；s4.3、重复步骤s4.1和步骤s4.2，直到种子集中的节点数达到k为止。6.一种独立级联模型下基于动态关系的最佳跳扩散系统，其特征在于，包括依次相连的网络搭建模块、数据获取模块、扩散分数计算模块、数据处理模块；其中，所述网络搭建模块，用于构建有向社交网络，获取传播概率；所述数据获取模块，用于基于传播概率和跳数的动态关系策略，对输入的所述传播概率执行循环，得到对每个节点的跳数；所述扩散分数计算模块，用于根据所述传播概率和所述跳数计算各个节点的扩散分数；所述数据处理模块，用于选择前k个所述扩散分数最大的节点作为种子集。
技术总结本发明公开了一种独立级联模型下基于动态关系的最佳跳扩散方法及系统，涉及社交网络技术领域。具体步骤为：构建有向社交网络，获取传播概率；基于传播概率和跳数的动态关系策略，对输入的所述传播概率执行循环，得到对每个节点的跳数；根据所述传播概率和所述跳数计算各个节点的扩散分数；选择前k个所述扩散分数最大的节点作为种子集。本方法的影响扩散准确性优于现有的度启发式算法，并保持了可接受的运行时间。因此，本发明方法有效地解决了社交网络影响力最大化问题。交网络影响力最大化问题。交网络影响力最大化问题。
技术研发人员：仇丽青 刘玉莹
受保护的技术使用者：山东科技大学
技术研发日：2022.03.28
技术公布日：2022/7/5
