论文部分内容阅读
摘要：社会网络影响力最大化是社会网络分析领域的一个重要研究问题，该问题旨在寻找出社会网络中具有最大影响力的节点集合。从社会网络影响力最大化问题产生背景出发，介绍影响力最大化问题的求解过程与求解过程中用到的基础模型，归纳总结了现有的几种主要传播模型、影响力最大化算法及研究现状。最后，讨论了该研究存在的问题和对未来的展望。
关键词：社会网络;传播模型;影响力最大化算法
中图分类号：TP393 文献标识码：A
文章编号：1009-3044（2019）32-0036-03
1概述
近年来，随着4G网络技术日渐成熟，5G网络的迅速发展，微信、微博等社交软件与抖音、今日头条等信息传播软件的兴起，互联网与网络基础设施已经改变了人们的生活方式。通过社会网络传播信息已经成为人们日常生活中的一部分，海量交互信息数据得到存储，社会网络的研究受到学者们广泛关注，为研究社会网络中信息传播与扩散过程，挖掘具有最大影响力的节点集合，社会网络影响力最大化问题成为研究热点。
2基础知识
2.1影响力最大化问题
影响力最大化问题最初由Domingos和Richardsom提出的I”，即给定一个社会网络G（V，E），通过特定的影响力传播模型进行模拟，找到含有K个节点的种子节点集合S（K为整数，且小于给定网络中的节点数），使得在影响力下激活的种子节点数量最多，公式如下：
2.2求解影响力最大化问题流程图
影响力最大化问题是依据影响力传播模型与影响力最大化算法进行求解。影响力传播模型主要为独立级联（Indepen-dent Cascade，IC）模型与线性阈值（Linear Threshold，LT）模型以及它们的扩展模型，影响力最大化算法分为两类，分别为贪心算法和启发式算法。求解该问題时，影响力传播模型与影响力最大化算法是同时存在的，影响力传播模型的构建影响影响力最大化算法的选择。求解影响力最大化问题流程图如图1。
2.3影响力最大化基础传播模型
社会网络是由代表个人或组织的节点构成的一种社会结构，代表各种社会关系，经由这些社会关系，把从偶然相识的泛泛之交到紧密结合的家庭关系的各种人们或组织串连起来。一般的，社会网络用图G（V，E）表示，其中y代表节点集合，E代表边集，G（V，E）中节点只有两种激活状态，分别为活跃（active）状态、不活跃（inactive）状态。活跃状态的节点可以通过一定的概率去激活不活跃状态的邻居节点，直到激活行为不再发生时，传播过程结束，且传播过程中活跃状态节点不能变为不活跃，这类传播模型称为渐进型模型，主要为Ic模型与LT模型;若传播过程中节点可以由活跃切换到不活跃状态，将这类模型称为对称型模型，例如传染病模型嘲，博弈论模型。
在真实社会网络中，一个人被朋友影响后，显然这个人并不切换到未受影响的状态。因此，渐进型模型相比于对称型模型更适合描述真实的社会网络中影响传播。因此，研究社交网络中影响最大化问题的主要的两个基本传播模型是独立级联模型和线性阈值模型。
独立级联（IC）模型是一种概率模型，该模型在社会网络图G（V，E）中各个节点之间都会给定一个在【0，1】的传播概率pu，v，即每条边的概率值;给定一个激活节点集Ao，集合中每个节点“以概率值pu，v去激活自己的邻居节点v，同时每个节点只有一次机会去激活邻居节点，一旦失败，就永远不能再次激活。假如在激活过程，有节点同时去激活同一个邻居节点，则该节点会随机排序被激活顺序，使得该激活过程在同一时刻激活完成;当社会网络中没有节点进行激活行为时，该传播过程结束。
3影响力最大化传播模型
影响力最大化传播模型的构建直接影响传播结果，因此，传播模型在影响力最大化问题中占有至关重要的位置。IC模型与LT模型对现实生活中不同场景下都具有一定的通用性，但也并不完全适用于不同的场景，在不同场景下的构建不同的传播模型是非常有必要的。因此，基于两类基础模型的扩展模型被提出。
3.1IC扩展模型
2003年，Kempe等州首次提出应用独立级联模型解决影响力最大化问题。随后，Kempe等嗍于2005年又提出了一个递减级联模型（DCM），该模型考虑了节点间影响衰减效应，当一个节点被其邻居节点多次激活后，则再有新的邻居节点激活时概率会下降。
2016年，Hosseini-Pozveh等针对真实社会网络中存在的不信任因素提出了IC的扩展模型，该模型称为符号感知级联（sc）模型，该模型利用真实社会网络中的不信任因素规定为主动节点对节点执行相反动作或采纳相反意见进行建模。
2018年，刘勇等依据TIC模型进一步提出了基于主题一兴趣的独立级联（TI-IC）模型，该模型利用EM算法求解用户兴趣的主题分布和传播项的主题分布，通过蒙特卡洛模拟的方法来计算用户间的影响概率，TI-IC模型与TIC模型相比，TI-IC模型考虑了用户之间的主题兴趣爱好，TIC模型只考虑了朋友之间的兴趣在不同主题上的分布程度。
2019年，Hosseini-Pozveh等对真实的网络中存在的不信任因素提出另一种方案，真实社会网络中的不信任因素规定为主动节点对节点不再执行相应的动作或采纳相应的意见，相应的基于Ic模型扩展构建了包含堵塞节点的符号感知级联（SC-B）模型，通过与sC模型对比，证明了真实社会网络中存在不信任因素时节点往往不再执行相应的动作或采纳相应的意见。
3.2LT扩展模型
2003年，Kempe等首次提出应用线性阈值模型解决影响力最大化问题。
2016年，Wang等提出了多级姿态的线性阈值模型（LT-MLA），该模型与传统的线性阈值模型相比，增加了捕捉用户交互态度状态和能力。 2018年，张云飞等㈣提出了关联影响力线性阈值模型（CLT，该模型充分考虑了不同信息传播过程中的相互促进关系，增加了信息传播过程的准确性。
2019年，Hosseini-Pozveh等基于线性阈值模型，提出了包含消极节点的信任生成阈值（TG-T-N）模型与包含堵塞节点的信任生成阈值（TG-T-B）模型，同样证明了真实社会网络中存在不信任因素时节点往往不再执行相应的动作或采纳相应的意见。
3.3其他模型
影响力最大化是一个应用性很强的问题，应用领域广泛。因此，除基于Ic模型和IT模型的扩展模型外，还有其他传播模型。如Wang等人提出了一种新的影响扩散模型一流体扩散（Fluidspread）模型，该模型利用流体动力学理论揭示了影响扩散的时间演化过程。谭振华等㈣基于引力学思想提出了一种新的谣言传播模型GPRModel，该模型充分考虑了用户间的关系、信息在用户间的传播关系、谣言接触率与转发率对用户的影响，对谣言信息的传播进行量化，构建出GPRModel。
4影响力最大化算法
4.1贪心算法
贪心算法，又称贪婪算法，该算法的思想是每次求解问题时，都去求解最优解来得到全局最优解。针对影响力最大化问题，Kempe等首次从离散化的角度提出了如何选择出有影响力的种子节点，并提出用贪心算法来近似求解。贪心算法的优点在于求解精度比较高，可以达到（1-1/e），但该算法的劣势也很明显，求解过程时间复杂度较高，用时较长，无法应用到大规模社交网络计算。针对这一不足，很多优化策略被提出以优化该算法使其能在大规模网络中运行。Leskove等根据问题的子模性提出了CELF算法，使算法的执行效率提升700多倍。Goyal等人进一步优化了CELF算法，提出了CELF 算法，与CELF算法相比，CELF 算法将效率提高了35%～55%。另外，Chen等㈣提出了两种改进的贪心算法NewGreedy和MixedGreedy，进一步对传统贪心算法进行了优化。
4.2启发式算法
针对贪心算法的低效性，近年来涌现出了大量启发式算法。Chen等在度的基础上提出了DegreeDiscount算法，该算法的思想是当一个节点有邻居节点被选为种子节点时，在计算它的度时要打一定的折扣。Luo等提出首先用PageRank算法对网络中的节点排序，再从排序较高的节点中选择种子节点。Song等的动态网络图中搜寻种子节点，基本思想是在动态图的网络快照的基础上，随着时间的推移，每变换一张图，就在前一阶段的种子集合的基础上，建立种子集合的更新策略。缺点是，算法只针对网络中边的增加和消失，权重的改变，并未考虑到节点增加或者减少带来的影响。Chen等用最大影响力路径来估算影响力的传播，并据此提出了PMIA算法，有良好的性能和精确度。
5影响力最大化问题存在的问题与展望
影响力最大化问题存在的问题及展望：
（1）影响力最大化问题中构建传播模型至关重要，现实中不同场景下构建的传播模型不同，如何针对不同的场景，构建有效且适合该场景的模型，值得研究者们注意。
（2）现有的影响力传播模型多数为静态传播模型，但现实社会网络时时刻刻都在发生变化，如何构建有效的动态传播模型是研究者们值得研究的重要问题。
（3）影响力最大化算法主要分为贪心算法和启发式算法，贪心算法时效差，启发式算法精度低，如何保证精度高的情况下，时效高的算法有待研究。
（4）现实世界中的复杂网络有很多，如交通系统中的城市网、生态系统中的神经元网等等，能否将影响力最大化问题应用到这些复杂网络中，来解决复杂网络中的相关问题。
6总结
社会网络中影响最大化问题具有很强的学术价值与实践意义，是近年来的研究热点之一。本文从影响力最大化问题、影响傳播模型、影响力最大化算法三个方面进行总结归纳，对影响传播模型与影响力最大化算法相关成果进行了介绍。随着研究不断深入，该方向将取得巨大突破，可以有效解决更多实际问题。
关键词：社会网络;传播模型;影响力最大化算法
中图分类号：TP393 文献标识码：A
文章编号：1009-3044（2019）32-0036-03
1概述
近年来，随着4G网络技术日渐成熟，5G网络的迅速发展，微信、微博等社交软件与抖音、今日头条等信息传播软件的兴起，互联网与网络基础设施已经改变了人们的生活方式。通过社会网络传播信息已经成为人们日常生活中的一部分，海量交互信息数据得到存储，社会网络的研究受到学者们广泛关注，为研究社会网络中信息传播与扩散过程，挖掘具有最大影响力的节点集合，社会网络影响力最大化问题成为研究热点。
2基础知识
2.1影响力最大化问题
影响力最大化问题最初由Domingos和Richardsom提出的I”，即给定一个社会网络G（V，E），通过特定的影响力传播模型进行模拟，找到含有K个节点的种子节点集合S（K为整数，且小于给定网络中的节点数），使得在影响力下激活的种子节点数量最多，公式如下：
2.2求解影响力最大化问题流程图
影响力最大化问题是依据影响力传播模型与影响力最大化算法进行求解。影响力传播模型主要为独立级联（Indepen-dent Cascade，IC）模型与线性阈值（Linear Threshold，LT）模型以及它们的扩展模型，影响力最大化算法分为两类，分别为贪心算法和启发式算法。求解该问題时，影响力传播模型与影响力最大化算法是同时存在的，影响力传播模型的构建影响影响力最大化算法的选择。求解影响力最大化问题流程图如图1。
2.3影响力最大化基础传播模型
社会网络是由代表个人或组织的节点构成的一种社会结构，代表各种社会关系，经由这些社会关系，把从偶然相识的泛泛之交到紧密结合的家庭关系的各种人们或组织串连起来。一般的，社会网络用图G（V，E）表示，其中y代表节点集合，E代表边集，G（V，E）中节点只有两种激活状态，分别为活跃（active）状态、不活跃（inactive）状态。活跃状态的节点可以通过一定的概率去激活不活跃状态的邻居节点，直到激活行为不再发生时，传播过程结束，且传播过程中活跃状态节点不能变为不活跃，这类传播模型称为渐进型模型，主要为Ic模型与LT模型;若传播过程中节点可以由活跃切换到不活跃状态，将这类模型称为对称型模型，例如传染病模型嘲，博弈论模型。
在真实社会网络中，一个人被朋友影响后，显然这个人并不切换到未受影响的状态。因此，渐进型模型相比于对称型模型更适合描述真实的社会网络中影响传播。因此，研究社交网络中影响最大化问题的主要的两个基本传播模型是独立级联模型和线性阈值模型。
独立级联（IC）模型是一种概率模型，该模型在社会网络图G（V，E）中各个节点之间都会给定一个在【0，1】的传播概率pu，v，即每条边的概率值;给定一个激活节点集Ao，集合中每个节点“以概率值pu，v去激活自己的邻居节点v，同时每个节点只有一次机会去激活邻居节点，一旦失败，就永远不能再次激活。假如在激活过程，有节点同时去激活同一个邻居节点，则该节点会随机排序被激活顺序，使得该激活过程在同一时刻激活完成;当社会网络中没有节点进行激活行为时，该传播过程结束。
3影响力最大化传播模型
影响力最大化传播模型的构建直接影响传播结果，因此，传播模型在影响力最大化问题中占有至关重要的位置。IC模型与LT模型对现实生活中不同场景下都具有一定的通用性，但也并不完全适用于不同的场景，在不同场景下的构建不同的传播模型是非常有必要的。因此，基于两类基础模型的扩展模型被提出。
3.1IC扩展模型
2003年，Kempe等州首次提出应用独立级联模型解决影响力最大化问题。随后，Kempe等嗍于2005年又提出了一个递减级联模型（DCM），该模型考虑了节点间影响衰减效应，当一个节点被其邻居节点多次激活后，则再有新的邻居节点激活时概率会下降。
2016年，Hosseini-Pozveh等针对真实社会网络中存在的不信任因素提出了IC的扩展模型，该模型称为符号感知级联（sc）模型，该模型利用真实社会网络中的不信任因素规定为主动节点对节点执行相反动作或采纳相反意见进行建模。
2018年，刘勇等依据TIC模型进一步提出了基于主题一兴趣的独立级联（TI-IC）模型，该模型利用EM算法求解用户兴趣的主题分布和传播项的主题分布，通过蒙特卡洛模拟的方法来计算用户间的影响概率，TI-IC模型与TIC模型相比，TI-IC模型考虑了用户之间的主题兴趣爱好，TIC模型只考虑了朋友之间的兴趣在不同主题上的分布程度。
2019年，Hosseini-Pozveh等对真实的网络中存在的不信任因素提出另一种方案，真实社会网络中的不信任因素规定为主动节点对节点不再执行相应的动作或采纳相应的意见，相应的基于Ic模型扩展构建了包含堵塞节点的符号感知级联（SC-B）模型，通过与sC模型对比，证明了真实社会网络中存在不信任因素时节点往往不再执行相应的动作或采纳相应的意见。
3.2LT扩展模型
2003年，Kempe等首次提出应用线性阈值模型解决影响力最大化问题。
2016年，Wang等提出了多级姿态的线性阈值模型（LT-MLA），该模型与传统的线性阈值模型相比，增加了捕捉用户交互态度状态和能力。 2018年，张云飞等㈣提出了关联影响力线性阈值模型（CLT，该模型充分考虑了不同信息传播过程中的相互促进关系，增加了信息传播过程的准确性。
2019年，Hosseini-Pozveh等基于线性阈值模型，提出了包含消极节点的信任生成阈值（TG-T-N）模型与包含堵塞节点的信任生成阈值（TG-T-B）模型，同样证明了真实社会网络中存在不信任因素时节点往往不再执行相应的动作或采纳相应的意见。
3.3其他模型
影响力最大化是一个应用性很强的问题，应用领域广泛。因此，除基于Ic模型和IT模型的扩展模型外，还有其他传播模型。如Wang等人提出了一种新的影响扩散模型一流体扩散（Fluidspread）模型，该模型利用流体动力学理论揭示了影响扩散的时间演化过程。谭振华等㈣基于引力学思想提出了一种新的谣言传播模型GPRModel，该模型充分考虑了用户间的关系、信息在用户间的传播关系、谣言接触率与转发率对用户的影响，对谣言信息的传播进行量化，构建出GPRModel。
4影响力最大化算法
4.1贪心算法
贪心算法，又称贪婪算法，该算法的思想是每次求解问题时，都去求解最优解来得到全局最优解。针对影响力最大化问题，Kempe等首次从离散化的角度提出了如何选择出有影响力的种子节点，并提出用贪心算法来近似求解。贪心算法的优点在于求解精度比较高，可以达到（1-1/e），但该算法的劣势也很明显，求解过程时间复杂度较高，用时较长，无法应用到大规模社交网络计算。针对这一不足，很多优化策略被提出以优化该算法使其能在大规模网络中运行。Leskove等根据问题的子模性提出了CELF算法，使算法的执行效率提升700多倍。Goyal等人进一步优化了CELF算法，提出了CELF 算法，与CELF算法相比，CELF 算法将效率提高了35%～55%。另外，Chen等㈣提出了两种改进的贪心算法NewGreedy和MixedGreedy，进一步对传统贪心算法进行了优化。
4.2启发式算法
针对贪心算法的低效性，近年来涌现出了大量启发式算法。Chen等在度的基础上提出了DegreeDiscount算法，该算法的思想是当一个节点有邻居节点被选为种子节点时，在计算它的度时要打一定的折扣。Luo等提出首先用PageRank算法对网络中的节点排序，再从排序较高的节点中选择种子节点。Song等的动态网络图中搜寻种子节点，基本思想是在动态图的网络快照的基础上，随着时间的推移，每变换一张图，就在前一阶段的种子集合的基础上，建立种子集合的更新策略。缺点是，算法只针对网络中边的增加和消失，权重的改变，并未考虑到节点增加或者减少带来的影响。Chen等用最大影响力路径来估算影响力的传播，并据此提出了PMIA算法，有良好的性能和精确度。
5影响力最大化问题存在的问题与展望
影响力最大化问题存在的问题及展望：
（1）影响力最大化问题中构建传播模型至关重要，现实中不同场景下构建的传播模型不同，如何针对不同的场景，构建有效且适合该场景的模型，值得研究者们注意。
（2）现有的影响力传播模型多数为静态传播模型，但现实社会网络时时刻刻都在发生变化，如何构建有效的动态传播模型是研究者们值得研究的重要问题。
（3）影响力最大化算法主要分为贪心算法和启发式算法，贪心算法时效差，启发式算法精度低，如何保证精度高的情况下，时效高的算法有待研究。
（4）现实世界中的复杂网络有很多，如交通系统中的城市网、生态系统中的神经元网等等，能否将影响力最大化问题应用到这些复杂网络中，来解决复杂网络中的相关问题。
6总结
社会网络中影响最大化问题具有很强的学术价值与实践意义，是近年来的研究热点之一。本文从影响力最大化问题、影响傳播模型、影响力最大化算法三个方面进行总结归纳，对影响传播模型与影响力最大化算法相关成果进行了介绍。随着研究不断深入，该方向将取得巨大突破，可以有效解决更多实际问题。