【大数据网络传播模型和算法-陈卫】——影响力最大化【持续更新】
本人当前研究方向为影响力最大化（基于机器学习的组合优化算法）。目前在学习陈卫编著的《大数据传播模型与算法》，该系列会定期分享影响力最大化的学习内容（持续更新…），希望大家能够一起交流学习！
前言
- 什么是影响？
- 什么是影响力？
- 什么是影响力最大化？
- 影响来自哪里？
- 影响如何传播？
- 在我们生活中有哪些直观应用？
1. 什么是影响？
小到听一首歌曲、看一部电影、读一本新书、选一个餐馆，大到买一处房产、选择职业方向、选择生活的城市、确定政治观点等，我们的各种选择和决定常常受到家人、同事、朋友以及更广泛的大众倾向的影响。举个简单的例子，我在一家餐厅吃饭，我觉得非常好吃并把该观点分享给我的朋友，这就是我对朋友观点的影响。
2. 什么是影响力？
在我们听一首歌曲、看一部电影、读一本书、选一个餐馆的时候，在我们买一处房产、选择职业方向、选择生活的城市、确定政治观点的时候，我们受到了谁的影响，哪些人的影响，哪些事物的影响？我们受到每一个人，每一个事物影响的程度都是影响力。
3. 什么是影响力最大化？
影响力最大化（IM）是一种经典的组合优化问题，旨在选择少数用户，从而最大限度地扩大在线社交影响力。
4. 影响来自哪里？
企业在做新产品推广时，可以利用对用户影响力及其传播的了解，选择有影响力的用户和传播渠道，从而帮助产品推广；公益机构可以通过影响力传播推动公益事业的发展，比如增强全民健康意识，推动扶助贫困地区等；政府可以选择合适的影响力群体和渠道来扩大其政策的影响或抵御谣言的传播。
5. 影响如何传播？
Christakis 和 Fowler 利用美国一个城市上万人 32 年的医疗记录数据验证了肥胖症和吸烟行为会在社交网络中相互影响和传播。
在抖音，哔哩哔哩，小红书，微博等APP上分享作品或者发布作品都会产生影响，而观看这些作品的人会受到影响。
6. 在我们生活中有哪些直观应用？
影响力最大化研究可以应用于病毒营销、网络监控、谣言屏蔽、社交推荐等领域。深入认识影响力的产生和传播模式有助于理解人类群体和个体的行为，从而使我们能够预测人们的行为，为政府、机构、企业等部门的决策提供可靠的依据和建议。比如企业在做新产品推广时，可以利用对用户影响力及其传播的了解，选择有影响力的用户和传播渠道，从而帮助产品推广；公益机构可以通过影响力传播推动公益事业的发展，比如增强全民健康意识，推动扶助贫困地区等；政府可以选择合适的影响力群体和渠道来扩大其政策的影响或抵御谣言的传播。
第一章 网络传播模型概述和分类
网络传播模型的种类繁多，侧重点各不同。本章节介绍了随机传播模型的基础定义，并基于这个定义对常用的传播模型进行了分类。
1. 基本概念
- 实体：代表网络传播中的对象，如用户、粉丝等更具体的对象；
- 有向图 G = ( V , E ) G=(V,E) G=(V,E)：代表一个社交网络，其中 V V V代表结点， E E E代表有向边；
- 有向边 ( u , ν ) ∈ E (u,\nu)\in E (u,ν)∈E：代表 u u u和 v v v有某种社交关系，方向代表实体在这个关系上的传播方向；那么 u u u是 v v v的入邻居， v v v是 u u u的出邻居；
- N + ( ν ) N^+(\nu) N+(ν)：节点 v v v的出邻居集合， N + ( ν ) N^+(\nu) N+(ν)大小为出度；
- N − ( ν ) N^-(\nu) N−(ν)：节点 v v v的入邻居集合， N − ( ν ) N^-(\nu) N−(ν)大小为入度；
- 举例：
- 微博中明星和粉丝的关系，对于粉丝来说，粉丝们关注了明星，所以她们可以收到明星发布的动态；对于明星来说来说，他如果没有回关粉丝，他就不会收到粉丝的动态，这就是一种单向的传播。这种情况就可以建立有向图来反映社交网络传播关系。
- 还是刚刚的例子，如果明星关注了他的粉丝们，那么他就可以收到粉丝的动态；再举个例子，微信好友默认就是一种双向的关系，这种图我们就可以使用无向图来表示，具体情况具体分析，根据实际问题的需求来建立相应的图结构。
2. 网络传播模型及分类
网络传播虽然多种多样，但实质上都可看成结点上与传播实体有关的状态依据网络的连通结构而发生有规律的改变。
- 定义 1.1 （随机传播模型）
一个随机传播模型由下列元素给出完整刻画：
（a）图结构 G = ( V , E ) G=(V,E) G=(V,E) ；
（b）每个结点的状态空间 Σ \Sigma Σ；
（c）传播概率空间 Ω \Omega Ω ；
（d）传播事件的时间序列 ( t 1 , v 1 ) , ( t 2 , v 2 ) , ⋯ , ( t i , v i ) , ⋯ (t_1,v_1),(t_2,v_2),\cdots,(t_i,v_i),\cdots (t1,v1),(t2,v2),⋯,(ti,vi),⋯ , 其中 0 < t 1 ⩽ t 2 ⩽ ⋯ ⩽ t i ⩽ ⋯ 0{<}t_1\leqslant t_2\leqslant\cdots\leqslant t_i\leqslant\cdots 0<t1⩽t2⩽⋯⩽ti⩽⋯ ,该序列可能是个确定性序列，也可能是个随机序列，且随机性由随机元 : ω ∈ Ω \operatorname{:}\omega\in\Omega :ω∈Ω 确定，并与结点状态有关，如果是后者，模型要给出序列的产生方法；
（e）每个结点的传播函数:
F ν : ∑ N − ( ν ) ∪ { v } × Ω → Σ F_\nu{:}\sum^{\mathcal{N}^-(\nu)\cup\{v\}}\times\Omega\to\Sigma Fν:∑N−(ν)∪{v}×Ω→Σ
对于任何一个在 0 时刻给定的各结点初始状态:
{ X ν , 0 ∈ ∑ ∣ ν ∈ V } \{X_{\nu,0}\in\sum|\nu\in V\} {Xν,0∈∑∣ν∈V}
传播过程如下：采样此次传播的随机元 ω ∈ Ω \omega\in\Omega ω∈Ω；在传播事件时刻 t i t_i ti , i > = 1 i>=1 i>=1，结点 v i v_i vi改变其状态,在任何其他时刻，结点的状态保持不变。 - 补充：因为传播过程是随机且结果具有不唯一性，传播概率空间 Ω \Omega Ω代表模型在传播过程所有随机性可能。其中一个随机元 ω ∈ Ω \omega\in\Omega ω∈Ω代表了一种传播情况。
- 网络传播模型的分类：
第二章 影响力传播的基本模型
- 影响力拓展度：在单实体二值状态递进模型中，一个种子集合 S 0 S_{0} S0在时刻 t > = 0 t>=0 t>=0的影响力拓展度是时刻 t t t活跃节点个数的期望值。即 σ t ( S 0 ) \sigma_t\left(S_0\right) σt(S0)。期望是对传播模型中的随即元 ω \omega ω取期望，即对多次随机传播结果取平均值。种子集合的影响力扩展度就是种子集合激活结点概率的和。
- 条件假设：
-
- 若种子集合为空，则影响力拓展度为0（不考虑自激活情况）；
-
- 影响的传播在下一时刻立即发生，不考虑传播延迟；
-
- 若某时刻的激活节点数量和上一时刻相同，则传播结束。
在影响力传播模型中，提出最早、研究最深入、应用最广泛的是独立级联模型（Independent Cascade Model）和线性阈值模型（Linear Threshold Model，下面首先介绍这两个模型。