作者：陈卫
出版社：人民邮电出版社有限公司
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
大数据网络传播模型和算法试读：
内 容 提 要
信息和影响力在人际网络中的传播无处不在。大规模社交网络平台的普及和大数据技术的应用为研究信息和影响力在网络中的传播提供了全新的机会。本书系统总结了信息和影响力传播模型和算法方面的近二十年的研究成果。在传播模型方面，本书详细介绍了若干经典的随机传播模型，准确论述了模型之间的关系和模型的主要性质。在传播算法方面，本书以影响力最大化为主线，介绍了适用于不同场景的基于影响力传播的优化问题和算法。此外，本书也介绍了其他传播模型和基于数据的网络传播的推断和学习方法等。本书以扎实的理论论述为基础，将基础理论与多方面的应用背景结合，并介绍了相关方面的最新研究成果。
《国之重器出版工程》
编 辑 委 员 会编辑委员会主任:苗 圩
编辑委员会副主任:刘利华 辛国斌
编辑委员会委员:
冯长辉 梁志峰 高东升 姜子琨 许科敏
陈 因 郑立新 马向晖 高云虎 金 鑫
李 巍 高延敏 何 琼 刁石京 谢少锋
闻 库 韩 夏 赵志国 谢远生 赵永红
韩占武 刘 多 尹丽波 赵 波 卢 山
徐惠彬 赵长禄 周 玉 姚 郁 张 炜
聂 宏 付梦印 季仲华
专家委员会委员(按姓氏笔画排列):
于 全 中国工程院院士
王 越 中国科学院院士、中国工程院院士
王少萍 “长江学者奖励计划”特聘教授
王建民 清华大学软件学院院长
王哲荣 中国工程院院士
尤肖虎 “长江学者奖励计划”特聘教授
邓宗全 中国工程院院士
甘晓华 中国工程院院士
叶培建 中国科学院院士
朱英富 中国工程院院士
朵英贤 中国工程院院士
邬贺铨 中国工程院院士
刘大响 中国工程院院士
刘怡昕 中国工程院院士
刘韵洁 中国工程院院士
孙逢春 中国工程院院士
苏彦庆 “长江学者奖励计划” 特聘教授
苏哲子 中国工程院院士
李伯虎 中国工程院院士
李应红 中国科学院院士
李新亚 国家制造强国建设战略咨询委员会委员、中国机械工业联合会副会长
杨德森 中国工程院院士
张宏科 北京交通大学下一代互联网互联设备国家工程实验室主任
陆建勋 中国工程院院士
陆燕荪 国家制造强国建设战略咨询委员会委员、原机械工业部副部长
陈一坚 中国工程院院士
陈懋章 中国工程院 院士
金东寒 中国工程院院士
周立伟 中国工程院院士
郑纬民 中国计算机学会原理事长
郑建华 中国科学院院士
屈贤明 国家制造强国建设战略咨询委员会委员、工业和信息化部智能制造专家咨询委员会副主任
项昌乐 “长江学者奖励计划” 特聘教授，中国科协书记处书记，北京理工大学党委副书记、副校长
柳百成 中国工程院院士
闻雪友 中国工程院院士
徐德民 中国工程院院士
唐长红 中国工程院院士
黄维中 国科学院院士、西北工业大学常务副校长
黄卫东 “长江学者奖励计划” 特聘教授
黄先祥 中国工程院院士
董景辰 工业和信息化部智能制造专家咨询委员会委员
焦宗夏 “长江学者奖励计划” 特聘教授
丛书总序
大数据、人工智能、云计算、物联网、移动互联网和产业互联网等成为新一代信息技术的特征，其中大数据与上述技术和应用都有密切关系。大数据来自于移动互联网、产业互联网和物联网等，其存储需要云计算，其挖掘依靠人工智能，而人工智能也有赖于大数据的支撑，大数据是产业互联网的重要基础。大数据不仅可以用于社会的精细化管理，更好地服务民生，大数据产业也将形成信息产业新的分支，其间接的产业影响将更大。可以说，大数据是数字经济的重要支柱。
很多国家都将大数据作为新时期的国家发展战略。2015年，国务院印发大数据发展的首个权威性、系统性文件《促进大数据发展行动纲要》，2016年国家发展和改革委员会批复了13个大数据领域的国家工程实验室，我国一些省市也纷纷制定大数据发展战略与规划。当前，我国在大数据共享开放、大数据资源开发、大数据技术研发、大数据挖掘应用、大数据产业培育、大数据安全管理、大数据人才培养和大数据法规研究等方面全面部署，为我国实现供给侧结构性改革，促进产业升级和转型，提升国家竞争力，争取在国际领域的话语权和实现跨越式发展起到了不可或缺的作用。
然而，我国的大数据发展也面临一些亟待解决的问题，例如基础研究薄弱、创新能力不强、产业链条缺口、数据资源封闭、法律法规滞后、数据安全不力、数据人才短缺和数据设施布局不合理及利用率不高等。为了使我国的大数据应用与产业可持续健康发展，需要多管齐下，其中普及大数据科学是重要的一环。为此，《学术中国·大数据》丛书编委会组织多个大数据领域优秀的研究团队的专家，基于国家“973”计划、“863”计划、国家自然科学基金、国家重点研究计划等科研项目的创新研究成果和国内外大数据应用的成功实践，编写了这套丛书，内容涵盖大数据存储、数据管理、数据挖掘、分析平台、优化算法等核心技术领域。
本丛书的出版对传播大数据科学知识、推动大数据的学术探讨、鼓励大数据领域的产学研用协同创新、促进大数据标准化研究、加快大数据核心技术研发、培训大数据技术人才、引导大数据应用与产业化发展以及完善大数据有关的制度建设，都将起到积极作用。2017年12月
前 言
任何社会性动物在个体与个体、群体与个体之间都存在着相互影响的关系，例如个体依从群体的行为会有利于猎食或减少被猎食的可能。而人类作为具有复杂交流手段的高级社会性动物，人际和社会影响力（Social Influence）在人们的社会生活中更是无处不在。小到听一首歌曲、看一部电影、读一本新书、选一个餐馆，大到买一处房产、选择职业方向、选择生活的城市、确定政治观点等，我们的各种选择和决定常常受到家人、同事、朋友以及更广泛的大众倾向的影响。深入认识影响力的产生和传播模式有助于理解人类群体和个体的行为，从而使我们能够预测人们的行为，为政府、机构、企业等部门的决策提供可靠的依据和建议。比如企业在做新产品推广时，可以利用对用户影响力及其传播的了解，选择有影响力的用户和传播渠道，从而帮助产品推广；公益机构可以通过影响力传播推动公益事业的发展，比如增强全民健康意识，推动扶助贫困地区等；政府可以选择合适的影响力群体和渠道来扩大其政策的影响或抵御谣言的传播。很多通俗畅销书对影响力、社交网络及其对社会生活各方面的重要性进行了广泛[1]的讨论。
社会影响力的研究在社会科学和市场学领域已有较长的历史，奠定了影响力传播研究的基础。比如Christakis和Fowler利用美国一个城市上万人32年的医疗记录数据验证了肥胖症和吸烟行为会在社交网[2]络中相互影响和传播。而伴随着互联网、在线社交网络和大数据的兴起及其日益广泛的应用，在更大规模下更深入地研究影响力的传播也成为可能。比如基于著名的社交网站脸书（Facebook）平台展开的两项大数据研究通过在线随机实验的方式，分别验证了影响力在选[3]举意愿和应用选择中的存在性及其决定性因素。
对信息和影响力在网络中传播的研究属于典型的交叉学科研究领域。研究者们可以从计算机科学、复杂网络、统计物理、概率论、社会学、心理学、管理科学等多个角度对其各个方面进行研究探索。本书主要从计算机科学的视角，介绍、讨论影响力网络传播研究方面主要的研究成果，并辅助介绍相关的复杂网络等方面的成果。与其他学科领域相比，计算机科学研究的一个主要特点是强调算法的设计和分析，这也是贯穿本书的主要线索。正如本书的题目所示，本书的阐述主要围绕影响力网络传播的两个方面——模型和算法进行。我们先介绍影响力传播的基本模型，再介绍在基本模型上的主要优化问题及其算法；介绍完基本的模型和算法后，进一步展开介绍各种拓展模型及其在拓展模型上的优化算法。由于算法要在大数据环境下适用于大规模的网络，因此我们会专门详细介绍高效可扩展的优化算法的设计及其分析。
本书的写作力求在严谨地表述传播模型和算法的同时，给读者一些直观的洞见和启发，使读者了解一些模型和算法背后的思想和方法。本书涵盖了计算机科学领域在近20年中研究影响力传播的主要结果以及作者在这方面近期的一些研究成果。由于篇幅有限，而且这个领域的范围广泛并在不断更新，作者选择了一些主要的内容加以细致讨论，而其他相关内容以每章结尾的文献小结形式加以总结，并适当提示了一些可能的进一步研究方向。有些章节还加入了作者本人对相应问题的进一步理解和思考，超出了原始文献的讨论范围。
本书面向的读者首先包括广大对影响力和网络研究感兴趣或已投入研究的学者、专家和学生，希望这些读者能通过本书对这一领域有较为全面的、系统的了解，并从中找到感兴趣的进一步研究的方向。其次，本书对于众多业界的实践者（如大数据工程师、网络分析师等）了解这一仍在快速成长的领域也很有益处，这些读者可以从中了解网络传播研究的背景、基本问题和最新动态，从而发现有可能与实践相结合的机会。本书也可以作为高校网络科学和大数据技术课程的一部分授课内容。
本书的组织结构如下。第1章抽象概括了传播模型的一般形式，并对本书后续论述的模型在这个一般形式下加以分类。第2章详细介绍了影响力传播的基本模型，包括在后文中以及在整个研究领域中经常用到的独立级联模型、线性阈值模型、触发模型、通用阈值模型等，并介绍了与算法设计密切相关的传播模型的单调性和次模性。第3章集中介绍了基本影响力传播模型下的影响力扩展度计算问题，这一计算问题为后面的优化问题打下了基础。第4章介绍了影响力传播研究中的一个核心问题，即影响力最大化问题。简单地说，这个问题就是要在给定的网络和传播模型下，找到一定数量的结点使得它们的传播效果最好。这个问题直接对应了网络中的病毒式营销应用，它的变种也在其他方面（如信息传播监控、流言控制等）有很多应用。这一章着重论述了影响力最大化的计算复杂性及其主要近似算法，花了很大篇幅给出了一个高效可扩展的影响力最大化算法的完整分析，以及与其他算法的比较。作者希望这个详尽的分析讨论会对有志于从事这方面研究的学者和学生有很好的帮助，因而也可以说第4章是本书的一个核心章节。第5章将影响力最大化在一般单实体传播模型中进一步拓展，讨论了7个影响力最大化的拓展问题，这些都是当前学术界仍然很活跃的研究方向。第6章介绍了多实体的传播模型，这个方向涵盖了多实体相互竞争或相互补充的传播模型，并讨论了多实体传播模型下次模性质的变化和对算法设计的影响。第7章简要介绍了在文献中出现的其他传播模型，比如选举模型（Voter Model）、传染病模型、基于博弈论的模型等，也介绍了复杂网络研究中的一个重要课题，即网络传播的相变分析。第8章概述了网络传播中基于数据挖掘的若干方向，如影响力传播模型学习、传播源头推断等。结束语部分对本书做了一个总结，并简要讨论了该领域的进一步发展方向。本书的附录给出了书中常用的符号列表，以便于读者阅读查找。在所有技术章节的结尾，作者专门附上一节文献小结和补充资料，介绍本章主要内容的出处和扩展阅读资料，也提出了一些可以进一步研究的开放问题。
影响力的研究和应用是一个涵盖范围很广的课题，本书不可能覆盖其中所有的方面和文献，但作者尽量做到在突出重点的同时包括尽可能多的相关方向和资料。关于这个领域也有其他的综述文章和专著，其中作者和Lakshmanan、Castillo合著的《Information and Influence Propagation in Social Networks》是这方面的第一本专著，但从其成书的2013年到现在，这个方向又有了很多发展，因此本书包括很多上述专著没有包含的内容，如基于反向影响力采样的可扩展算法、自适应影响力最大化、在线影响力最大化等。其他的综述文章也简要介[4]绍了这个领域一个或多个方向的近期研究结果，读者可参考阅读，相互印证。另外，网络科学是一个包含网络影响力传播的更大的研究[5]领域，对于这一领域，作者建议读者参考阅读这方面的经典教科书。
本书包括了作者与众多合作者的研究成果。在此作者对所有的合作者表示由衷的感谢。在成书过程中，作者与李建、彭炳辉、赵浩宇等人的讨论帮助改进了书中的某些理论分析。左金航、盛翊伦等人帮助校对了部分章节。在此作者对这些人的帮助一并表示感谢。陈 卫2019年11月
注释
[1]BERGER J. Contagious: why things catch on[M]. New York: Simon & Schuster, 2016. CHRISTAKIS N A, FOWLER J H. Connected: the amazing power of social networks and how they shape our lives[M]. New York: Harper Collins Publishers, 2011. GRENNY J, PATTERSON K, MAXFIELD D, et al. Influencer: the new science of leading change[M]. New York: McGraw-Hill Education, 2013.
[2]CHRISTAKIS N A, FOWLER J H. The spread of obesity in a large social network over 32 years[J]. New England Jouranl of Medicine, 2007, 357(4): 370-379. CHRISTAKIS N A, FOWLER J H. The collective dynamics of smoking in a large social network[J]. New England Journal of Medicine, 2008, 358(21): 2249-2258.
[3]ARAL S, WALKER D. Identifying infuential and susceptible members of social networks[J]. Science, 2012(337): 337-341. BOND R M, FARISS C J, JONES J J, et al. A 61-million-person experiment in social influence and political mobilization[J]. Nature, 2012(489): 295-298.
[4]SUN J, TANG J. A survey of models and algorithms for social influence analysis[M]//Social network data analysis. Dordrecht: Kluwer Academic Publishers, 2011: 177-214.吴信东, 李毅, 李磊. 在线社交网络影响力分析[J]. 计算机学报, 2014, 37(4): 735-752.陈卫. 社交网络影响力传播研究[J]. 大数据, 2015, 1(3): 2015031. LI Y, FAN J, WANG Y, et al. Influence maximization on social graphs: a survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(10): 1852-1872.
[5]EASLEY D, KLEINBERG J. Networks, crowds, and markets: reasoning about a highly connected world[M]. Cambridge: Cambridge University Press, 2010. NEWMAN M E J. Networks: an introduction[M]. New York: Oxford University Press, 2010.汪小帆, 李翔, 陈关荣. 网络科学导论[M]. 北京: 高等教育出版社, 2012.
第1章 网络传播模型概述和分类
网络传播模型的种类繁多，侧重点各有不同。本章抽取常用传播模型的共性，给出了一般随机传播模型的基本定义，并基于这一一般定义将常用传播模型加以分类。第2章会在这个基本定义的基础上介绍若干常用的传播模型及其性质。
本书以社交网络及其上的传播为主要的研究对象，当然网络及其上的传播并不限于人与人之间的社交网络。本书的内容在很大程度上也适用于其他类型的网络，如计算机网络中的信息和计算机病毒的传播、动物网络中的病毒传播等。但为了叙述直观方便，统一用人与人之间的社交网络作为描述对象。
社交网络中传播的实体也多种多样。从具有物理实体的病毒和细菌，到虚拟形式的信息、想法、观念、文化基因（Meme，也称迷因）等，都可在社交网络中传播。因此，关于网络传播的模型种类也很多。本章抽取出这些模型的基本共性将其作为网络传播模型的基础，并在此基础上根据不同模型的特点，将模型分类。本章的目的是让读者对网络传播模型有一个总体的认识，然后在后续章节中对几个典型模型再加以具体论述。本章统一用“实体”一词来表示网络中传播的对象。在后面章节中再根据模型的具体应用场景将“实体”具体化为影响力或病毒等更为具体的对象。
在后续各章中，我们会把一个社交网络描述成一个有向图（Directed Graph）G=(V , E )，其中V是结点（Vertex，Node）的集合，是有向边（Directed Edge）的集合。统一用n=|V|表示图中的结点数，m=|E|表示图中的有向边数。每一个结点v∈ V代表一个社交网络中的人，每一条边(u , v )∈E代表结点u和v有某种直接的社交关系，如他们是朋友、熟人、网友等。边是有方向的，(u , v )表示边从u指向v。这个方向表示了实体在这个关系或这条边上的传播方向，即(u , v )表示信息、病毒或观念等实体会从u传向v。有向边(u , v )对于u来讲是一条出边，对于v来讲是一条入边；u是这条边的起点，v是这条边的终点。如果(u , v )∈E，那么u是v的一个入邻居（In-Neighbor），v是u的一个出邻居（Out-Neighbor）。在图G中，用表示结点v的所有出邻居的集合，用表示结点v的所有入邻居的集合。当需要指明所讨论的图时，用和表示。我们称N++--(v)的大小|N(v)|为v的出度（Out-Degree），N( v )的大小|N(v)|为v的入度（In-Degree），由有向边组成的图称为有向图。本书还会用到有关有向图的其他术语，比如有向图中的一个（有向）路径（Path）是一个图中的结点序列(v , v,B,v)，使得每两个相邻结点v和12ki-1v（i=2,B,k）都在图中对应一条有向边(v,v )。一个简单路径ii-1i（Simple Path）是指除了首尾两个结点外没有任何两个结点相同的路径。其他相关概念和术语在需要时再做介绍。本书附录中列出了常用符号列表，便于读者统一查找。
在线社交网络中一个典型的有向图是微博网络，如新浪微博和推特（Twitter）。在微博网络中，当一个用户v关注了另一个用户u时，u的微博消息就会从u传到v，所以建一条从u到v的有向边。如果u并没有关注v，那么v的微博消息是不会直接传到u的，所以在图上就没有v到u的反向边。这也是我们用有向边和有向图来表示微博网络的原+因。在这样建起的有向图中，结点v的出邻居集合N (v )就是所有关注v的用户，即v的粉丝，而v的出度就是v的粉丝数。反之，v的入邻居集合-
N(v )就是所有v关注的用户，v的入度就是v关注的人的个数。如果一条微博从结点v产生，从v传到v的出邻居v后，v加以转发又11122传给了v的出邻居v，而v又转发给了v，那么（v, v , v , v）就23341234是这条微博传播的一个路径。
如果想表示实体在这个关系中可以双向传播，可以用两条边(u,v)和(v,u)来表示。比如微信的朋友圈和脸书（Facebook）的朋友关系都是双向的，需要一方发出邀请另一方接受才能建立朋友关系，之后信息可以在这个朋友关系上双向传播。对于这样的网络我们用双向边或无向边来表示，对应的图称为无向图。在无向图中，一个结点v的出邻居和入邻居集合是重合的，统称为邻居集合，用N( v )表示，它的大小|N ( v )|称为v的度。
网络传播虽然多种多样，但实质上都可看成结点上与传播实体有关的状态依据网络的连通结构而发生有规律的改变。下面给出网络传播的形式化表达，用R+表示所有非负实数的集合。对于任意结点v∈ V及任意时刻，用表示结点v在时刻t的状态，用 X表示在t时刻t所有结点状态的向量，为方便起见，有时也用表示该向量。这个状态可取值集合∑与传播实体的特性有关，比如我们可以规定，0表示结点v在时刻t没有得到传播实体，而1表示结点v在时刻t得到了传播实体。状态X也可以是个实数，如区间[0,1]v,t的任意实数，用以表达v拥有实体的程度。如果被传播的实体是对某一观点的支持态度，那么0表示完全反对，1表示完全支持，而0到1之间的数可以表示部分支持的程度。状态X根据需要还可以取其他v,t更复杂的形式，比如在多实体同时传播的模型中，状态X本身可以v,t是个向量，表示结点v对每个实体的拥有情况。作者在后面章节的具体传播模型描述中会给出对结点状态的具体描述。本章用抽象的Xv,t来表示结点状态。
实体在网络中的传播就是在网络中的结点上发生了一系列传播事件，而每一个传播事件引起结点状态的变化，并且一个结点状态的改变会进一步造成它的邻居结点的状态发生改变。下面给出传播事件和结点状态变化的数学表述。我们用表示结点v在时刻t之前的状态；用(t,v)表示一个传播事件，即在时刻t结点v发生了一个传播事件。它的意义是指结点v受其自身在时刻t之前的状态及v的所有入邻居在时刻t之前的状态的共同影响，在时刻t从状态改变为X。一般在这种状态改变中会引入随机性，使得和v,t并不唯一确定状态X，而是只决定可能的状v,t态分布，而是在这个状态分布下的一个随机取样。为方便起见，我们用Ω表示一个抽象的概率空间，而一个随机元代表了一次传播过程中的所有随机性取值。那么可以说、和ω共同唯一确定了t时刻v的状态。我们用传播函数 F来表达这种状态转换，即v。
举个例子。假设所有结点的状态都是二值{0,1}状态，结点v有两个入邻居u、w。如果定义 F为v，这意味着只要u或w中有一个结点在时刻t之前的状态是1，且结点v在时刻t发生一个传播事件，那么v在时刻t发生了（可能的）状态改变，改变之后的状态是1。如果ω是从[0,1]区间随机均匀抽取的一个数，我们定义，则当u或w中有一个点在时刻t之前的状态是1时，有50%的概率v在时刻t也变成1。因此传播函数F给出了状态在网络邻居间转化的准确数学表达。v
要完整地描述一个网络传播过程，还需要给出传播在0时刻的初始状态以及所有传播事件发生的时刻和所在结点(t,v)。事件发生的时刻和结点可以是确定的，也可以有自己的随机性。
综上所述，我们可以给出如下关于随机传播模型（Stochastic Diffusion Model）的一般定义。
定义1.1 （随机传播模型）。一个随机传播模型由下列元素给出完整刻画：（a）图结构G=(V,E)；（b）每个结点的状态空间∑；（c）传播概率空间Ω；（d）传播事件的时间序列：(t , v ),(t , v ),B,(t , 1122iv ),B , 其中,该序列可能是个确定性序列，i也可能是个随机序列，且随机性由随机元ω∈Ω确定，并与结点状态有关，如果是后者，模型要给出序列的产生方法；（e）每个结点的传播函数。对于任何一个在0时刻给定的各结点初始状态，传播过程如下：采样此次传播的随机元ω∈Ω；在传播事件时刻t，i≥1，结点v改变其状态至ii；在任何其他时刻，结点的状态保持不变。
备注1.1 补充说明一下，传播概率空间Ω包括了模型在传播过程中的所有随机性可能。在文献及本书后文中我们也把它称为可能世界（Possible World）的空间，而其中一个随机元ω∈Ω表达了一个可能
试读结束[说明：试读内容隐藏了图片]