前言

任何社会性动物在个体与个体、群体与个体之间都存在着相互影响的关系，例如个体依从群体的行为会有利于猎食或减少被猎食的可能。而人类作为具有复杂交流手段的高级社会性动物，人际和社会影响力（Social Influence）在人们的社会生活中更是无处不在。小到听一首歌曲、看一部电影、读一本新书、选一个餐馆，大到买一处房产、选择职业方向、选择生活的城市、确定政治观点等，我们的各种选择和决定常常受到家人、同事、朋友以及更广泛的大众倾向的影响。深入认识影响力的产生和传播模式有助于理解人类群体和个体的行为，从而使我们能够预测人们的行为，为政府、机构、企业等部门的决策提供可靠的依据和建议。比如企业在做新产品推广时，可以利用对用户影响力及其传播的了解，选择有影响力的用户和传播渠道，从而帮助产品推广；公益机构可以通过影响力传播推动公益事业的发展，比如增强全民健康意识，推动扶助贫困地区等；政府可以选择合适的影响力群体和渠道来扩大其政策的影响或抵御谣言的传播。很多通俗畅销书对影响力、社交网络及其对社会生活各方面的重要性进行了广泛的讨论。

社会影响力的研究在社会科学和市场学领域已有较长的历史，奠定了影响力传播研究的基础。比如Christakis和Fowler利用美国一个城市上万人32年的医疗记录数据验证了肥胖症和吸烟行为会在社交网络中相互影响和传播。而伴随着互联网、在线社交网络和大数据的兴起及其日益广泛的应用，在更大规模下更深入地研究影响力的传播也成为可能。比如基于著名的社交网站脸书（Facebook）平台展开的两项大数据研究通过在线随机实验的方式，分别验证了影响力在选举意愿和应用选择中的存在性及其决定性因素。

对信息和影响力在网络中传播的研究属于典型的交叉学科研究领域。研究者们可以从计算机科学、复杂网络、统计物理、概率论、社会学、心理学、管理科学等多个角度对其各个方面进行研究探索。本书主要从计算机科学的视角，介绍、讨论影响力网络传播研究方面主要的研究成果，并辅助介绍相关的复杂网络等方面的成果。与其他学科领域相比，计算机科学研究的一个主要特点是强调算法的设计和分析，这也是贯穿本书的主要线索。正如本书的题目所示，本书的阐述主要围绕影响力网络传播的两个方面——模型和算法进行。我们先介绍影响力传播的基本模型，再介绍在基本模型上的主要优化问题及其算法；介绍完基本的模型和算法后，进一步展开介绍各种拓展模型及其在拓展模型上的优化算法。由于算法要在大数据环境下适用于大规模的网络，因此我们会专门详细介绍高效可扩展的优化算法的设计及其分析。

本书的写作力求在严谨地表述传播模型和算法的同时，给读者一些直观的洞见和启发，使读者了解一些模型和算法背后的思想和方法。本书涵盖了计算机科学领域在近20年中研究影响力传播的主要结果以及作者在这方面近期的一些研究成果。由于篇幅有限，而且这个领域的范围广泛并在不断更新，作者选择了一些主要的内容加以细致讨论，而其他相关内容以每章结尾的文献小结形式加以总结，并适当提示了一些可能的进一步研究方向。有些章节还加入了作者本人对相应问题的进一步理解和思考，超出了原始文献的讨论范围。

本书面向的读者首先包括广大对影响力和网络研究感兴趣或已投入研究的学者、专家和学生，希望这些读者能通过本书对这一领域有较为全面的、系统的了解，并从中找到感兴趣的进一步研究的方向。其次，本书对于众多业界的实践者（如大数据工程师、网络分析师等）了解这一仍在快速成长的领域也很有益处，这些读者可以从中了解网络传播研究的背景、基本问题和最新动态，从而发现有可能与实践相结合的机会。本书也可以作为高校网络科学和大数据技术课程的一部分授课内容。

本书的组织结构如下。第1章抽象概括了传播模型的一般形式，并对本书后续论述的模型在这个一般形式下加以分类。第2章详细介绍了影响力传播的基本模型，包括在后文中以及在整个研究领域中经常用到的独立级联模型、线性阈值模型、触发模型、通用阈值模型等，并介绍了与算法设计密切相关的传播模型的单调性和次模性。第3章集中介绍了基本影响力传播模型下的影响力扩展度计算问题，这一计算问题为后面的优化问题打下了基础。第4章介绍了影响力传播研究中的一个核心问题，即影响力最大化问题。简单地说，这个问题就是要在给定的网络和传播模型下，找到一定数量的结点使得它们的传播效果最好。这个问题直接对应了网络中的病毒式营销应用，它的变种也在其他方面（如信息传播监控、流言控制等）有很多应用。这一章着重论述了影响力最大化的计算复杂性及其主要近似算法，花了很大篇幅给出了一个高效可扩展的影响力最大化算法的完整分析，以及与其他算法的比较。作者希望这个详尽的分析讨论会对有志于从事这方面研究的学者和学生有很好的帮助，因而也可以说第4章是本书的一个核心章节。第5章将影响力最大化在一般单实体传播模型中进一步拓展，讨论了7个影响力最大化的拓展问题，这些都是当前学术界仍然很活跃的研究方向。第6章介绍了多实体的传播模型，这个方向涵盖了多实体相互竞争或相互补充的传播模型，并讨论了多实体传播模型下次模性质的变化和对算法设计的影响。第7章简要介绍了在文献中出现的其他传播模型，比如选举模型（Voter Model）、传染病模型、基于博弈论的模型等，也介绍了复杂网络研究中的一个重要课题，即网络传播的相变分析。第8章概述了网络传播中基于数据挖掘的若干方向，如影响力传播模型学习、传播源头推断等。结束语部分对本书做了一个总结，并简要讨论了该领域的进一步发展方向。本书的附录给出了书中常用的符号列表，以便于读者阅读查找。在所有技术章节的结尾，作者专门附上一节文献小结和补充资料，介绍本章主要内容的出处和扩展阅读资料，也提出了一些可以进一步研究的开放问题。

影响力的研究和应用是一个涵盖范围很广的课题，本书不可能覆盖其中所有的方面和文献，但作者尽量做到在突出重点的同时包括尽可能多的相关方向和资料。关于这个领域也有其他的综述文章和专著，其中作者和Lakshmanan、Castillo合著的《Information and Influence Propagation in Social Networks》是这方面的第一本专著，但从其成书的2013年到现在，这个方向又有了很多发展，因此本书包括很多上述专著没有包含的内容，如基于反向影响力采样的可扩展算法、自适应影响力最大化、在线影响力最大化等。其他的综述文章也简要介绍了这个领域一个或多个方向的近期研究结果，读者可参考阅读，相互印证。另外，网络科学是一个包含网络影响力传播的更大的研究领域，对于这一领域，作者建议读者参考阅读这方面的经典教科书。

本书包括了作者与众多合作者的研究成果。在此作者对所有的合作者表示由衷的感谢。在成书过程中，作者与李建、彭炳辉、赵浩宇等人的讨论帮助改进了书中的某些理论分析。左金航、盛翊伦等人帮助校对了部分章节。在此作者对这些人的帮助一并表示感谢。

陈卫

2019年11月