社交网络影响力最大化-白红宇

社交网络影响力最大化（Influence Maximization）

1、社交网络概述

社交网络归根结底就是一个

图G(V,E,P)，V是节点集，E是边集，P是所有边的概率集。一个用户就是一个节点v，用户与用户之间的关系就是边e，每条边都有一条概率p，信息会在图上按照边的概率进行传播。

2、影响力最大化问题分类

影响力最大化问题主要分为两种：

（1）是给定节点数k，选择出k个节点作为种子集使得种子集能影响的节点数最多；

（2）是给定所要求产生的影响力，找到满足条件的最小节点集合

3、社交网络影响力最大化作用

影响力最大化的应用场景十分丰富，包括病毒营销，推荐系统，信息扩散，时间探测，专家发现，链接预测等。

我拿病毒营销举个例子，比如某一公司想要推广自家商品，希望通过病毒式营销手段，先选择少部分人让其免费试用所需推广的商品，当选中的用户（种子节点）对商品满意时便要通过网络向自己的同事朋友推荐该商品，使得更多的人了解并最终购买该商品。应该如何找出这部分人来试用商品能够使得最终购买商品的人数最多就是公司所需要考虑的最核心的问题

4、传播模型

最经典的两种模型分别是：

独立级联（IC）模型和

线性阈值（LT）模型。

4.1独立级联模型（Independent Cascade Model）简称 IC 模型

它是一种

概率型的传播模型。独立级联模型的

基本原理描述如下：

在社交网络G=（V，E）中，点集V中的节点具有两种状态一种是激活状态，一种是待激活状态，初始状态下，处于激活状态的节点会以一定的概率将与其相连的处于待激活状态下的节点激活。

独立级联模型的影响力传播过程如下：

(1) 在初始状态下，即 t=0 时，有且仅有种子集合 S 中的节点全部被设置为激活状态。

(2) 当 t=k 时，所有在 t=k-1 时由待激活状态转变为激活状态态的全部节点，以一定的概率去尝试影响它们所有处于待激活态的邻居节点。例如点 i 在 t=k-1 时被激活，则 t=k 时，如果点 i 的邻居节点 j 仍处于待激活态，则点 i 以概率pij去尝试激活点 j。无论激活行为是否成功，在下一时刻，i 节点都将不再具备激活其他节点的能力。

(3) 当某时刻整个网络中所剩余的具备激活其他节点能力的节点数为 0 时，传播过程结束

4.2线性阈值模型（Linear Threshold Model）简称LT模型

在线性阈值模型下，每个节点v包含从间隔[0,1]中随机均匀选择的激活阈值θv。此外，LT规定所有进入边缘权重的总和最多为1，其它的进入节点对它的影响是累加的，当影响超过阈值时，该节点被激活。

社交网络中的节点都有激活和待激活两种状态，每个节点由系统随机分配一个

Python实现线性阈值模型算法下载：

其他参考资料：

博客学习：

：

学习

是实现社交网络影响最大化算法的基础

NetWorkx学习：https://networkx.github.io/documentation/stable/reference/algorithms/clique.html#