数据科学如何最大化社交网络影响力？（上）

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

在开始阅读本文之前，让我们先来考虑这样一个营销场景：假设你是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 -