前言

任何社會性動物在個體與個體、群體與個體之間都存在著相互影響的關系，例如個體依從群體的行為會有利于獵食或減少被獵食的可能。而人類作為具有復雜交流手段的高級社會性動物，人際和社會影響力（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月