基于线性阈值模型的社交网络影响最大化研究

发布时间：2020-12-13 19:48

　　近年来,随着网络技术的不断完善,社交网络得到了迅猛的发展,如CSDN、BLOG、Weibo等。随着信息的高速传播,影响最大化问题成为社交网络中的热门研究话题。影响最大化的研究对市场营销、广告宣传以及舆情控制等方面具有重要意义。Kempe首次证明了影响最大化是NP-hard问题,并提出了贪心算法。贪心算法能够达到（1-1/e）的近似最优,但其计算开销巨大,不能适用于大型网络。启发式方法,能够快速地找出种子集合,但是不能保证影响的传播范围。混合式算法采用启发式和贪心相结合的方式,有效的解决了贪心算法的时间开销问题。在启发阶段,混合式算法利用节点邻域信息选取最具"潜力"节点,这些节点能积累大量的影响力使得周围未激活的节点更容易被激活;在贪心阶段,大量的节点已被激活或者更容易被激活,从而贪心的时间开销得到了大幅度的降低。但是,如何选取最有潜力节点以及怎样加快贪心寻找,仍然是一个待解决的问题。针对以上问题,本文提出了基于H阶邻居的混合式算法,旨在扩大最终的传播范围的同时,减少算法的时间复杂度。基于H阶邻居的混合式算法同样采用两个阶段实现种子节点的选取:启发阶段和贪心阶段。在启发阶段,由于大型社交... 

【文章来源】：大连海事大学辽宁省 211工程院校

【文章页数】：62 页

【学位级别】：硕士

【部分图文】：

图１．１用图来表示的社交网络??Ｆｉｇ．?１．１?Ａ?ｓｏｃｉａｌ?ｎｅｔｗｏｒｋ?ｄｅｐｉｃｔｅｄ?ｂｙ?ａ?ｇｒａｐｈ??网络影响力最大化研有着十分重要的现实意义，并且己在多个领

图３．１节点Ｖ的邻接图??Ｆｉｇ．?３．１?Ａｄｊａｃｅｎｔ?ｇｒａｐｈ?ｏｆ?ｎｏｄｅ?ｖ??

（ａ）?（ｂ）??图３．２节点的两阶出边图??Ｆｉｇ．?３．２?Ｔｗｏ－ｆｌｏｏｒ?ｏｕｔｃｏｍｉｎｇ?ｇｒａｐｈ?ｏｆ?ｎｏｄｅｓ??０＾５）??０．?６＼?〇？??？?Ｂ??（ａ）?（ｂ）??图３．３相同影响力情况下不同的出边邻居激活阈值??Ｆｉｇ．?３．３?Ｄｉｆｆｅｒｅｎｔ?ｔｈｒｅｓｈｏｌｄ?ｏｆ?ｏｕｔｃｏｍｉｎｇ?ｎｏｄｅｓ?ｗｉｔｈ?ｔｈｅ?ｓａｍｅ?ｉｎｆｌｕｅｎｃｅ??除了节点对其Ｈ阶内节点产生的影响之外，Ｈ阶内节点自身的激活阈值也需??要被考虑到选择最具有潜在影响力节点的过程中。从图３．３我们可以看出，虽然ｘ??节点和ｙ节点对其出边节点的影响力相同，但是由于其出边节点的激活阈值不同，??因此带来不同的结果。图３．３（ａ）中ｘ节点可以激活阈值为０．４的节点，而在图３．３（ｂ）??中阈值为０．５和０．３的节点都可以被ｙ节点激活。因此，对于节点ｘ和ｙ，对出边??节点有同样的影响力，激活结果却不同。??－２２－??

【参考文献】：
期刊论文
[1]边缘覆盖去重的社交网络影响力最大化算法[J]. 胡敏,孙欣然,黄宏程.  计算机科学与探索. 2017(05)
[2]社交网络影响力传播研究[J]. 陈卫.  大数据. 2015(03)
[3]基于用户行为的微博用户社会影响力分析[J]. 毛佳昕,刘奕群,张敏,马少平.  计算机学报. 2014(04)
[4]在线社交网络影响力分析[J]. 吴信东,李毅,李磊.  计算机学报. 2014(04)
[5]在线社会网络的测量与分析[J]. 徐恪,张赛,陈昊,李海涛.  计算机学报. 2014(01)
[6]在线社会网络中信息扩散[J]. 李栋,徐志明,李生,刘挺,王秀文.  计算机学报. 2014(01)
[7]一种新型的社会网络影响最大化算法[J]. 田家堂,王轶彤,冯小军.  计算机学报. 2011(10)

硕士论文
[1]社交网络中节点影响力的评价与优化机制研究[D]. 陈一帆.中南大学 2014



本文编号：2915084