数据科学如何最大化社交网络影响力?(上)

社交网络早已是我们生活中不可缺少的一部分,更是网络时代营销活动的重点投放渠道;如何使社交网络的影响力最大化,也成了数据科学关注的重点。本期,我们介绍线性阈值模型在影响力最大化问题中的应用~

在开始阅读本文之前,让我们先来考虑这样一个营销场景:假设你是A公司的销售经理,现在公司研制出一种新型产品,并且你手里有一些试用本,你计划选择一小部分人来免费试用这种产品,从而让他们通过社交网络把这款产品推荐给他们的朋友,再诱导他们的朋友推荐给他们朋友的朋友,以此类推。请问:你如何能知道这部分最初试用者最终可以影响到的最大人数?

上述情景是经典的“影响力最大化问题”在现实生活中的常见应用场景。影响力最大化问题作为社交数据科学领域中一个重要的研究方向,常常借助社交网络来解决它。通常,信息会从一小部分传播者开始向外传播,我们称这些初始的传播者为“种子”,这些种子会借助社交网络来传递信息给他们的朋友,这个过程称为“激活”。接下来,被激活的用户会继续传递信息给他们还没有被激活的朋友,重复这个过程,直到没有更多的用户可以被激活为止。这篇文章主要讲解一种时下较为流行的社交网络信息传递模型——线性阈值模型,并且会说明如何运用这个传播模型来解决影响力最大化问题。

在介绍这个模型之前,我们需要了解社交网络的基本概念和图形表达形式。说起社交网络,大多数人首先想到的应该是微博、微信之类的社交平台,通过这些平台,每个人都可以创建自己的用户标签和自己专属的人脉圈。通常,一个社交网络包含着大量的用户,不同用户间可以通过某种渠道发表和交换各自的想法、观点和信息等。在这篇文章中,我们定义社交网络为一个信息传播平台,通过这个平台,用户会以某种关系相连接并且能相互传递消息。

社交网络图是社交网络的形象化的图形表示,在社交网络图中,每个用户被表示为一个点,每对用户之间的关系被表示为两点之间的边,在这篇文章中,我们定义两点之间的边为信息传递的渠道。下图表示一个有向社交网络图,图中C用户可以传递信息给A用户和D用户(即C点可以激活A点和D点),但C用户不可以传递信息给B用户。

为了使线性阈值模型更易于理解,我们还需要知道如何计算社交网络图中每条边出现的可能性,——即C点会把信息传递给A点而不是D点的概率。假设现在有一个有向网络图G,G中的每个点x有Nx条对它传递信息的边,那么点x被任意一个它的“朋友”(射入点)y激活的概率Pr(x,y)为,并且点x与它所有“朋友”(射入点)间的边的概率的和为1。根据这个方法,我们可以得到G中每条边出现的概率。

做了这么多铺垫,现在我们正式开始对于线性阈值模型的学习。首先,我们定义:

G表示一个有向网络图

V表示G中所有的点的集合

S表示初始的传播者(种子)的集合

Pr(x,y)表示边(x, y)(出现)的概率

现在引入一个新的变量称为传播临界值,每个点都有一个专属的传播临界值,并且在0到1之间随机取值,越小表明这个点越容易被激活,越大表明这个点越难被激活。

线性阈值模型的基本原理为:以S中的所有点作为出发点,开始向外对它们的"朋友"(射出点)传播信息,在每次信息传播迭代的过程中,若某个未激活的点和它的已经被激活的"朋友"(射入点)间的边的概率的和不小于这个点的传播临界值,那么这个未激活的点被激活。每个点不能被重复激活也不能被灭活。重复这个过程,直到没有更多的未激活的点可以被激活为止,至此,我们就得到了S可以影响到的最大的点的个数。

我们以一个栗子来结束这篇文章:

上图可以看作是一个有向网络图G,它由A,B, C, D 和E五个点构成,B点有两个射入点A点和C点,所以Pr(A,B)和Pr(C,B)都等于1/2 = 0.5,同理可知Pr(E,D)和Pr(B,D)等于0.5。C点只有一个射入点A点,所以Pr(A,C)= 1。

假设A点是G中唯一一个种子S,除A点外,G中所有点的初始状态均为未激活状态,那么信息从A传给B再从B传给D的概率为0.5 * 0.5 = 0.25。显然,如果D的传播临界值为0.2,则D可以被激活,但若D点的传播临界值为0.3,那么D点无法被激活。按照这个方法,只要我们为每个点都随机分配一个介于0到1之间的传播临界值,最后所有被激活的点的个数,就是我们需要求得的S可以影响到的最大个数。

好了,本期文章我们介绍了如何使用线性阈值模型来解决影响力最大化问题,下期笔者会介绍另一种经典的可以用于计算社交网络中信息传播量的方法,希望大家会感兴趣~

最后,预祝大家圣诞快乐!:)

- END -

本文来自企鹅号 - KPMG大数据挖掘媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技评论

学界 | François Chollet谈深度学习的局限性和未来(下)

AI 科技评论按:本篇是 Keras 作者 François Chollet 撰写的一篇博客,文中作者结合自己丰富的开发经验分享一些自己对深度学习未来发展方向的...

9620
来自专栏量子位

连LeCun都推荐的Fashion-MNIST数据集,是这位华人博士的成果

允中 发自 凹非寺 量子位 报道 | 公众号 QbitAI 上周六,量子位在报道中提到德国时尚圈的科学家,推出一个名叫Fashion-MNIST的数据集。这个数...

43950
来自专栏新智元

【TensorFlow超级指南】你能想到的TF教程和资源都在这里了

【新智元导读】众所周知,TensorFlow已然成为机器学习的热门工具。不论是学习还是从事与机器学习相关的工作,能够灵活使用TensorFlow可以大幅提高作业...

11720
来自专栏量子位

怎样让AI完成人类搞不定的任务?OpenAI提出迭代扩增法给AI设目标

OpenAI今天提出了“迭代扩增”(iterated amplification),官方博客介绍说,这是一种AI安全技术,人类能运用这种方法,指导AI去完成那些...

10020
来自专栏新智元

过去5年最受欢迎机器学习论文+代码速查

【新智元导读】Papers with Code网站将ArXiv上的最新机器学习论文与GitHub上的代码联系起来。这个项目索引了大约5万篇论文和1万个GitHu...

15900
来自专栏机器学习之旅

总结:常见算法工程师面试题目整理(二)

答: boost的核心思想不同于bagging,它在基于样本预测结果对照与真实值得差距,进行修正,再预测再修正,逐步靠近正确值。

11120
来自专栏人工智能头条

手工艺品电商平台Etsy的个性化推荐

16830
来自专栏机器之心

学界 | 如何帮助大家找工作?领英利用深度表征学习提升人才搜索和推荐系统

领英征才解决方案(LinkedIn Talent Solutions,LTS)业务为领英贡献了大约 65% 的年收入,该业务方便职位提供者接触潜在应聘者,也方便...

12630
来自专栏机器之心

备战世界杯!先用深度学习与强化学习踢场 FIFA 18

构建能玩 FIFA 游戏的智能体与游戏内置的 Bot 是不一样的,它不能访问任何内部程序信息,只能与人一样获得屏幕的输出信息。游戏窗口截图就是所有需要馈送到智能...

14200
来自专栏ArrayZoneYour的专栏

TensorFlow强化学习入门(1)——双臂赌博机

强化学习不仅仅赋予了我们教会人工agent如何行动的能力,还使得agent可以通过我们提供的交互式环境进行学习。通过结合深度神经网络习得的复杂表示和RL age...

82690

扫码关注云+社区

领取腾讯云代金券