一种面向主题耦合的影响力最大化算法

《一种面向主题耦合的影响力最大化算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一种面向主题耦合的影响力最大化算法吕文渊周丽华廖仁建云南大学信息学院网络逐渐成为了人与人之间的主要社交工具，在网络中挖掘最有影响力的用户成为了非常值得关注的问题。在传统影响力最大化算法的基础上提出了一种面向主题耦合的影响力最大化算法，该算法首先分析网络屮不同主题之间的耦合相似性，在综合考虑主题之间耦合相似性与用户对不同主题偏好的基础上扩展独立级联模型，并使用经典的贪心算法挖掘最具有影响力的用户。与不考虑主题耦合的影响力最大化算法相比，所提算法考虑了传播主题之间的耦合相似性，并iL能够与用户偏好进行

2、更为有效地结合。最后，实验表明，相比于经典的影响力最大化算法，该算法能够更为有效地挖掘在特定主题下最具有影响力的种子节点。关键词：社会网络;影响力最大化;耦合相似度;主题;随着时代的进步，互联网思维已经紧紧地与市场结合在一起。近几年较为流行的“病毒营销”［1-2］和“口碑效应”［3-4］恰恰利用了人与人之间的互相影响。在互联网上利用多种多样的社交网络进行病毒式营销，往往会以极小的成本获得巨大影响，从而使产品销量大大提高，影响力最大化算法就是解决“病毒营销”问题的关键所在。影响力最大化问题是“病毒营

3、销”中的关键问题。谁是营销过程中最具有“病毒”传播能力的用户呢?找到这些最A传播能力的用广就如同在谷堆中找到最优良的种子一样既复杂又关键，只有找到了最优良的“种子”才能使影响力最大化问题取得最优解。因此，如何发现影响力最人化问题的最优“种子”成为一个十分重要的研宄问题。在过去的研宂中已经有学荠提出而向主题的影响力最大化问题［9,12］，但是并没有考虑主题之间的耦合相似度，因此本文提出一种面向主题糊合的影响力最大化算法GACT（GreedyAlgorithmBasedontheCoupedTopic

4、s）来解决该问题。本文首先针对具体的问题选择主题，为传播过程屮信息的不同主题建立描述属性的集合，并且通过这个集合分析不同主题之间的耦合关系，即不同主体（信息资源）建立在同一客体（信息资源）基础上所形成的和互之间的潜在联系，进而通过这种潜在的联系衡量主题之间的耦合相似度，然后在独立级联模型的基础上修改节点之间的激活概率，以用户对耦合主题的偏好重新定义激活概率，并以此建立一个面向主题耦合的影响力传播模型。最后通过实验将GACT算法与解决影响力最大问题的贪心算法进行比较。2相关工作木节将对影响力最大化问

5、题的研宄背景和传播模型做相关介绍。2.1影响力最大化问题影响力最大化问题最初由Richardson和Domingos［5］引入社会网络领域，他们给出了社会网络上影响力最大化问题的详细定义和评价指标。Kempe等［6］在影响力最大化问题引入社会网络后对该问题进行了详细的研宄，提出使用贪心算法求解影响力最大化问题，并提出了两种经典的传播模型:独立级联模型1C(IndependentCascade)［7］和线性阈值模型LT(LinearThreshold)［8］。在此之后，Tang等人［9］提出了基于主

6、题的社会网络影响力最人化问题。他们在网络中找到每个节点的主题偏好，并且划分出每个主题的网络子图，在这个子图中找到节点对于特定主题的影响力权值并在这样的模型下研宄影响力最大化问题，通过实验发现不同主题的信息在网络上传播的效果也是不同的。但是Tang等人并没有研宄网络上传播的信息所属的不同主题之间的相互关系。虽然主题之间可能因时间或空间的距离没有直接联系，但是如果主题与主题之间存在着某种耦合的关系，则主题作为主体通过相同的客体的一种联系纽带会在主题之间建立一种间接联系，这种间接联系可以体现两个事物之间

7、共同的特征交集。比如，若两个导演共同聘请过同一个演员，则就形成了一种耦合关系，代表着两个导演之间的相似性。本文研究如何通过主题之间的耦合关系促进影响力最大化问题的求解。2.2影响力传播模型独立级联模型是应用得最为广泛的传播模型，同时也是一种以发送者为中心的概率模型。独立级联模型的设计基于概率论中的相互粒子系统，是动态级联模型概念屮最简化的一个模型。独立级联模型按照随机的过程展开。(1)当节点u在t-1时刻被激活时，在t时刻节点u有唯一的一次机会激活它的邻居节点V，激活概率为匕。Puv值越高，节点u

8、越有可能对节点V产生影响。若在t时刻节点V有多个邻居节点对它进行激活，则V的邻居节点以任意顺序激活节点V。(2)完成节点u激活节点v的过程后，无论v是否被激活，在吋间t以后的吋刻u都不能再次对其邻居节点V进行激活。当整个社交网络中再也没有新的节点被激活时，整个激活过程结束。线性阈值模型是以接收者为核心的离散模型。在该模型中每个用户节点U都从(0，1)中选择一个被激活的阈值eu,节点u被它的邻居节点vEN(u)以权重buv影响(buv