社交网络中影响最大化研究

《社交网络中影响最大化研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、哈尔滨工业大学工学硕士学位论文第1章绪论1.1课题研究背景以及研究意义在社交网络中，有graph图()的存在，如图1-1就是一个社交网络图的例子[25]。一个社交网络是一个连接独立个体和组织的网络。现在有很多网络，例如Facebook，Twitter，论文引用网络，Skype通信网络，博客网络和人人网络等等呈现出了一片繁荣的景象。在社交网络中顶点代表一个对象，例如：论文，传感器网络，城市，人群等等。边代表顶点与顶点之间的关系。而顶点常常是指的人，在这种情况下，则关系有很多。例如合作论文的关系，朋友关系，导师与学生的关系，论文的引用关系等等。而且信息可以沿

2、着这些人与人之间的关系边来传播，从而将信息的影响力传播开来。最后这些信息沿着边传播是有传播概率的。在现代社会，信息是最重要的。如果目前我们有了一份信息，而我们想要最大化地传播信息，则我们得考虑如何选择切入点，选择哪些人作为初始传播的节点，可以使全网受到信息的影响最大。随着移动设备和无线技术的繁荣昌盛和发展，移动社交网络也迅速的变得可用了。移动社交网络在信息流动和传播中以口口相传的方式扮演着一个基本的角色。其中有一个任务比较重要，在一个社交网路中发现一个子集的独立个体，把他们设定为目标(例如，派发新产品的目标)去最大化信息的传播(进一步推广新的产品)。发现

3、一个受影响的独立个体的子集有很多的应用。考虑一个社交网络承担着平台和市场的角色，一个公司想向市场推广一个新的产品，希望它能被网络中的大部分人群所接受。公司计划初始化地把一小部分人群作为目标人群，然后向他们派送免费的产品样本(产品非常的昂贵，所以公司要限制预算，仅仅只能选择一小部分人群派发)。公司希望这些初始选择的用户可以推荐这些产品给他们的朋友，他们的朋友会影响他们朋友的朋友。如此下去，这样的话会有许多个体最终会被影响着去接受这些新的产品。通过这些口口相传的世界的强大影响力，或者可以叫做病毒市场。这里面的问题是如何去选择一个独立个体的集合去发放免费的物品

4、，以至于在社交网络中他们能影响最大个数的人群。-1-哈尔滨工业大学工学硕士学位论文形式化的说这个问题叫做影响最大化。就是对于一个参数k，去发现一个k个初始种子节点的集合，这里面的影响是使用随机瀑布模型来定义的。图1-1一个社交网络图的例子[25]1.1研究现状我们要研究的问题为Top-k影响节点最大化问题，下面简述一下：在图()中，信息可以在节点之间按照一定的概率传播。为了考虑idea或者信息通过一个社交网络(一个有向图)传播的可操作模型，我们认为一个独立的个体或者是active(一个信息的接受者)的或者是inactive的。节点可以从inactive的

5、状态变成active，但是不能从相反方向转变。现在定义两个基本的流动模型：(1)首先，我们定义了IC(独立瀑布模型),两个节点之间有一个传播概率，节点独立的被邻居节点影响激活。例如在step节点v首先被选择成active节点，每一个v的邻居w都可以被v以概率()来激活，和以前的所有历史都无关，-2-哈尔滨工业大学工学硕士学位论文这个过程比较像马尔科夫随机域。但是无论v成功与否，v不会再次尝试激活w了，这个过程一直持续到没有更多可能的激活为止。(2)线性阈值模型(LT)：一个节点被所有邻居节点影响，将影响的值加在一起，如果得到的值大于一定的阈值，则节点被激

6、活。形式化的最优化问题，上面的模型都涉及到一个问题：选择一个好的初始节点种子集合。我们定义节点集合A的influence为()，这个值是最终期望受到影响的节点的个数。条件是：A被选择为初始种子集合。InfluenceSpreadmaximization影响最大化的问题：给定一个参数k，发现一个k个节点的初始种子集合A，使得()最大。研究现状：DomingosandRichardson[17]首先研究了影响最大化问题，并且提出了一个概率解法。Kempe[6]等人把发现一个小集合的影响节点的问题形式化成了一个离散最优化问题。他们证明了最优化问题是一个NP-h

7、ard的问题，并且给出了一个GreedyAlgorithm(GA)，保证了影响的节点的值是最优化值的(1-1/e)近似。GA算法的基本的思想是去计算每一个节点的influence，并且轮流去选择有着最大的影响值的节点直到k个节点都被选择出来为止。他们的实验研究显示出了贪心算法在影响最大化方面显著的超越了度方法或者基于中心点的启发式方法。贪心算法的主要缺点是有效性不够，也就是速度比较慢，特别是当社交网络包含了大批节点的时候。Leskovec[9]等人提出了一个最优化的贪心算法，叫做Cost-EffectiveLazyForward(CELF)框架，CELF

8、优化方法使用了影响最大化目标的次模属性去减少节点的传播估计计算。很多文章都是用这