基于连通正影响支配集的社交网络传播算法研究
发布时间：2020-12-25 14:12
通过影响网络中的正影响支配集(Positive Influence Dominating Set,简称为PIDS)可以有效的引导社交网络中的舆论,培养社会风气。对于许多社会问题例如抽烟、酗酒等,都有很大的实际意义。对于网络中的一个节点子集来说,如果网络中的所有节点都有半数以上的邻居节点处于该子集中,那么这样的节点子集就是该网络的一个PIDS。连通正影响支配集(Connected Positive Influence Dominating Set,简称为CPIDS)即在正影响支配集的基础上,进一步要求支配集内部连通。目前已有许多关于PIDS的研究,但其中的大部分方法计算量大,时间复杂度高,因此难以适用于大型的社交网络。在本文中,针对一些已有方法的不足,我们提出了一种高效的启发式算法TBCM来构建大规模社交网络中的CPIDS。文中实验结果表明,本文提出的TBCM算法在运行时间上优于现有的大规模网络算法。并且,考虑到正影响支配集在网络中占比较大,难以应用到实际的社交网络中,本文提出了将影响力最大化问题应用在网络中的CPIDS的想法,设计了基于网络中CPIDS的两步影响力传播算法LIBH,在得...
【文章来源】：哈尔滨工业大学黑龙江省 211工程院校 985工程院校
【文章页数】：62 页
【学位级别】：硕士
【部分图文】：
算法[25]在BA-250以及BA-300网络中的运行效果1)BA-2502)BA-300
ER-1024 786.0 76.75% 55.55 0.67 15000WS-256 231.1 90.23% 20.296 0.36 15000WS-512 430 83.98% 39.46 0.53 15000WS-1024 790.8 77.22% 77.70 0.66 15000Karate 31 91.17% 0.70<0.1 4292Dolphins 56.7 91.45% 2.27<0.1 10504Football 110 95.65% 7.15 0.16 15000Science 1152.3 78.87% 63.53 0.73 15000a)ER网络中PIDS占比结果 b)BA网络中PIDS占比结果
c)各算法在WS网络中的运行时间 d)各算法在实际网络中的运行时间图3-10 TBCM算法不同数据集上剪枝效果TBCM算法在时间运行方面具有更大的优势。图3-10中，显示了三种算法在不同数据集上的运行时间。可以看出，各个算法的运行时间都随着网络规模变大而增加，虽然Wang-Greedy算法在解集上优于SSA算法，但其在实际网络中运行时间过长，难以应用于实际的大规模网络中。例如对于真实网络数据集中的Astrophysics网络以及Email-Enron网络，在这两个数据集中Wang-Greedy的运行时间均超过10,000秒，因此在图3-10d)中并未显示该算法在这两个数据集上的运行时间。由于三种算法在运行时间方面差异过大，因此在实验结果图中，我们选择以指数坐标来显示算法的运行时间，但是仍然可以看出TBCM算法明显优于另外两种算法。这表明TBCM算法相对于另外两种算法来说更具有实际的应用价值。例如，在ego-Facebook数据集中，TBCM的运行时间仅为10.79秒，而在相同数据集上，SSA的运行时间为108.90秒，Wang-Greedy的运行时间为3205.45秒。可以看出，文章中提出的TBCM算法在运行时间上与其他对比算法相比有较大的优势。
【参考文献】：
期刊论文
[1]基于启发式和贪心策略的社交网络影响最大化算法[J]. 曹玖新,闵绘宇,徐顺,刘波. 东南大学学报(自然科学版). 2016(05)
[2]社交网络中求最小正影响支配集的改进算法[J]. 麦飞,陈卫东. 华南师范大学学报(自然科学版). 2016(03)
[3]国内在线社交网络群体行为研究现状与展望[J]. 孙国强,石文萍,王莉. 现代情报. 2016(02)
[4]网络拓扑特征对病毒式营销传播动态影响的研究——基于新浪微博大数据的实证分析[J]. 陆煊,江若尘. 新闻与传播研究. 2014(10)
[5]复杂网络中节点重要性排序的研究进展[J]. 刘建国,任卓明,郭强,汪秉宏. 物理学报. 2013(17)
[6]基于阈值的社交网络影响力最大化算法[J]. 陈浩,王轶彤. 计算机研究与发展. 2012(10)
[7]一种新型的社会网络影响最大化算法[J]. 田家堂,王轶彤,冯小军. 计算机学报. 2011(10)
本文编号：2937809
【文章来源】：哈尔滨工业大学黑龙江省 211工程院校 985工程院校
【文章页数】：62 页
【学位级别】：硕士
【部分图文】：
算法[25]在BA-250以及BA-300网络中的运行效果1)BA-2502)BA-300
ER-1024 786.0 76.75% 55.55 0.67 15000WS-256 231.1 90.23% 20.296 0.36 15000WS-512 430 83.98% 39.46 0.53 15000WS-1024 790.8 77.22% 77.70 0.66 15000Karate 31 91.17% 0.70<0.1 4292Dolphins 56.7 91.45% 2.27<0.1 10504Football 110 95.65% 7.15 0.16 15000Science 1152.3 78.87% 63.53 0.73 15000a)ER网络中PIDS占比结果 b)BA网络中PIDS占比结果
c)各算法在WS网络中的运行时间 d)各算法在实际网络中的运行时间图3-10 TBCM算法不同数据集上剪枝效果TBCM算法在时间运行方面具有更大的优势。图3-10中，显示了三种算法在不同数据集上的运行时间。可以看出，各个算法的运行时间都随着网络规模变大而增加，虽然Wang-Greedy算法在解集上优于SSA算法，但其在实际网络中运行时间过长，难以应用于实际的大规模网络中。例如对于真实网络数据集中的Astrophysics网络以及Email-Enron网络，在这两个数据集中Wang-Greedy的运行时间均超过10,000秒，因此在图3-10d)中并未显示该算法在这两个数据集上的运行时间。由于三种算法在运行时间方面差异过大，因此在实验结果图中，我们选择以指数坐标来显示算法的运行时间，但是仍然可以看出TBCM算法明显优于另外两种算法。这表明TBCM算法相对于另外两种算法来说更具有实际的应用价值。例如，在ego-Facebook数据集中，TBCM的运行时间仅为10.79秒，而在相同数据集上，SSA的运行时间为108.90秒，Wang-Greedy的运行时间为3205.45秒。可以看出，文章中提出的TBCM算法在运行时间上与其他对比算法相比有较大的优势。
【参考文献】：
期刊论文
[1]基于启发式和贪心策略的社交网络影响最大化算法[J]. 曹玖新,闵绘宇,徐顺,刘波. 东南大学学报(自然科学版). 2016(05)
[2]社交网络中求最小正影响支配集的改进算法[J]. 麦飞,陈卫东. 华南师范大学学报(自然科学版). 2016(03)
[3]国内在线社交网络群体行为研究现状与展望[J]. 孙国强,石文萍,王莉. 现代情报. 2016(02)
[4]网络拓扑特征对病毒式营销传播动态影响的研究——基于新浪微博大数据的实证分析[J]. 陆煊,江若尘. 新闻与传播研究. 2014(10)
[5]复杂网络中节点重要性排序的研究进展[J]. 刘建国,任卓明,郭强,汪秉宏. 物理学报. 2013(17)
[6]基于阈值的社交网络影响力最大化算法[J]. 陈浩,王轶彤. 计算机研究与发展. 2012(10)
[7]一种新型的社会网络影响最大化算法[J]. 田家堂,王轶彤,冯小军. 计算机学报. 2011(10)
本文编号：2937809
本文链接：https://www.wllwen.com/kejilunwen/yysx/2937809.html
