基于社区的社交网络影响力最大化研究

发布时间：2020-08-25 00:36

【摘要】：近年来,随着微信、微博等在生活的中普及,社交网络在人们的生活中逐渐变得不可或缺。利用在线社交网络,人们可以建立社会关系,对同一件热点事件进行交流并分享想法,社交网络逐渐成为一种有价值的营销媒体。同时,人们逐渐发现在社交网络上进行广告投放可以取得很好的反馈,影响力最大化问题也就随之产生。传统的影响力最大化问题主要从个体层面去进行影响力分析,很少考虑在线社交网络中的用户一般都会形成社区这样一个客观事实。从个体层面去挖掘网络中最具影响力的节点是一个NP-hard问题,现有研究中的贪婪算法可以保证其解的近似最优,但是其不足之处在于,在大规模网络上该算法运行时间成本较高。基于此,为了提高在大规模网络上解决此问题的算法的运行效率,本文提出基于社区的影响力最大化算法NVPA-IM(Neighborhood Vector Propagation Algorithm-Influence Maximization)算法,该算法主要利用网络的社区结构选择影响力最大的k个节点。本文主要包括以下几点:第一、在社交网络中,具有同样属性的用户联系更趋向于紧密,那么在社交网络中就会形成各种虚拟社区结构。而挖掘网络中的社区结构对于人们理解信息在网络中的传播具有重要的作用。本文提出的解决影响力最大化问题的算法的第一步就是获取网络的社区结构。选择何种社区划分算法是一个需要考量的问题,本文基于社区划分算法的性质,选择NVPA社区划分算法,并且选择具有代表性的贪心算法快速纽曼算法FN(Fast Newman),基于相似度的聚合算法HClustering(Hierarchical Clustering)及经典的标签传播算法LPA(Label Propagation Algorithm)作为对比算法对网络进行社区划分,并从影响力的角度对划分结果进行对比分析。第二、本文分析了从社区角度出发的种子节点选取算法。传统的从网络中选择节点的策略主要有两种:启发式策略和贪心策略。算法效率较高的是启发式策略,度中心算法和随机算法是两种典型的启发式策略,一般情况下作为对比算法使用。贪心策略主要是贪婪爬山算法。该算法精度很高,但是效率低。而本文基于NVPA社区划分算法的性质,提出了一种度中心算法的扩展算法NVPA-IM种子节点选取算法,并且从影响覆盖的角度对NVPA-IM算法进行了性能验证。
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP301.6;TP393.09
【图文】：

社区结构,社区,划分算法

图 2-1 一个具有简单社区结构的网络Fig 2-1 The network with a simple community structure度优化思想的 FN 社区发现算法衡量社区划分算法划分网络的所获得的社区的结构强

相似度,向量值,初始向量,邻域

图 2-2 NVPA 算法示例:（a）节点初始向量；（b）经过邻域向量传播后节点的领域向量值和节点之间的相似度Fig. 2-2 NVPA algorithm example: (a) initialize vectors; (b) vectors propagate through neighbors,and calculate similarities在邻域向量定义阶段，正如第二章所介绍的，为了避免相似度只考虑一跳邻居节点的情况，NVPA 算法在计算相似度时考虑了与节点并非直接相邻的多跳邻居

伪代码,降维,邻域,向量

图 2-3 邻域向量降维规则伪代码. 2-3 Pseudo code of neighborhood vector reducing dimension，i jn 、 n分别表示社区i jv 、 v的中的节点数，同时5 中的迭代终止条件一般是 Newman 等人提出的模因为基于社区层面挖掘网络中最具影响力的k 个节

【相似文献】