基于用户复杂联系的最大影响力节点发现算法.pdfVIP

I 1 ， l ‘^ 文章编号：1007—1423(2015)03—0006—04 DOI：10．39696．issn．1007—1423．2015．03．002 基于用户复杂联系的最大影响力节点发现算法 谢世娜 ．李J (四川大学计算机学院，成都 610065) 摘要 ： 提出基于用户联系的信息网络中最具影响力用户的发现算法，基于现实社会网络启示得到的假定 “与越多易受影响 用户有联系的这类用户 的影响力越大”，且给出无向网络和有 向网络 中节点影响力的度量模型。实验表明．该方案优 于求解影响力最大化 的贪心算法达到的影响范围，能够较准确地刻画社会 网络 中节点影响力 关键词 ： 影响力：有影响力的节点：贪心算法 0 引言 心性 (BetweennessCentrality)等 。有研究 O【l表明 ：大众 思想的大规模改变也即新事物的传播．是 由容易被影 社会网络 (SocialNetwork)通常指实体与实体间联 响的用户去影响其他容易被影响的用户推动 ．从而促 系构成 的复杂信息网络 (Informati0nNetwork)．即由节 进信息的广泛传播 点和边组成 的．反映一定社会结构关系的网络或图 其 中．节点可表示个人或组织等实体．节点之间的链接或 1 相关工作 边表示实体之间的联系，例如合作关系、朋友关系 、认 1．1 独立级联模 型 同关系等。当我们考察信息传播时 ，发现 ：社会网络的 常用的信息传播模型为独立级联模型 它借鉴交 结构担当着非常重要的作用 当一用户接受某新事物 互粒子系统和概率论的理念l1】在独立级联模型 巾．若 之后 ，会向其邻居、好友推荐该事物 ，其中一部分人就 节点U在第 t步被激活．则它只有一次机会去激活其邻 会受其影响接受该新事物，且进一步向他们的邻居、朋 居节点 ：而其邻居节点 被 U激活的概率为P．也被称 友推荐 在这样一个传播过程 中．一个人 的社会关系及 为信息转移概率．换句话说 ．若节点 的邻居中有 Z个 其朋友的行为会影响到他 的决策_l1社会 网络 中节点影 节点处于活动状态 ．则 以 1一(1-p)的概率被激活 如 响力的研究 由来 已久2[-7]近年来 ．随着各大社交网站的 果节 点 被成功激活 ．将成为 ￡+1步被激活 的节点 ： 兴起，如Facebook、Twitter等 ．使得该研究再次成为热 在 以后的激活过程 中节点 “就失去激活其他节点的机 点 而这些社交网站的庞大用户数量 以及用户间的复 会 若 有多个 已激活的邻居节点．则他们激活 的顺 杂联系等特点也给相关研究带来巨大的挑战 一个基 序是随机的 与线性阈值模型类似．独立级联模型下的