社交网络对齐

版权信息

书名：社交网络对齐

ISBN：978-7-115-62215-0

本书由人民邮电出版社发行数字版。版权所有，侵权必究。

您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。

我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。

如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。

版　　权

著    张忠宝

责任编辑 杨 凌

人民邮电出版社出版发行　　北京市丰台区成寿寺路11号

邮编　100164 　电子邮件　315@ptpress.com.cn

网址　http://www.ptpress.com.cn

读者服务热线：(010)81055410

反盗版热线：(010)81055315

内容提要

本书分为基础知识、社交网络表示和社交网络对齐方法三部分内容，针对社交网络对齐中的用户对齐与社区对齐场景，系统介绍了社交网络对齐关键技术体系及其应用。

第一部分“基础知识”定义了社交网络并进行建模，介绍了后续各种对齐方法中所涉及的图神经网络、图表示学习等。第二部分“社交网络表示”分别从微分方程和狄利克雷分布两个角度，介绍了基于微分方程的动态图表示学习算法和基于狄利克雷分布的知识图谱表示方法。第三部分“社交网络对齐方法”以模型建立、算法介绍、实验分析的逻辑，重点分析了5种社交网络对齐方法：静态的社交网络用户对齐方法、动态的社交网络用户对齐方法、基于无监督学习的社交网络用户对齐方法、基于迁移学习的社交网络用户对齐方法和基于双曲空间的社交网络社区对齐方法。

本书既可以作为对社交网络、数据挖掘、图神经网络感兴趣的高年级本科生和研究生的入门书，也可以作为人工智能领域开发者和研究者的技术参考书。

前  言

以人为节点，以人与人之间的关系为边，所组成的网络即为社交网络。近些年来，随着移动互联网的发展，各种社交网络平台不断涌现，用户数持续攀升，用户发布推文数快速增加。据统计，目前全球社交网络平台已经超过4000个，其中主流社交网络平台已经超过200个。在社交网络中，人作为最重要的实体，往往以多重身份存在于多个网络空间。人们习惯在不同的社交网络中开展不同的活动，例如，用微信交流私人情感，用微博发布新闻状态，用领英进行求职，用ResearchGate进行学术交流，等等。但是，社交账号彼此之间往往相互独立，缺乏对应关系。如何以人为本，实现多个网络空间中人与人之间身份的相互对应（即社交网络对齐），以供社交网络融合，这一点至关重要。

然而，目前国内外鲜有专门介绍社交网络对齐方面的图书。因此，本书旨在弥补该方面的不足，重点介绍社交网络表示与对齐中的应用与前沿进展，期望能给对社交网络感兴趣的高年级本科生和研究生带来一些启发。

本书主要分为三部分：基础知识、社交网络表示、社交网络对齐方法。第一部分主要为读者介绍阅读本书必备的基础知识；第二部分为读者介绍社交网络表示的相关内容；第三部分为本书的重点，着重介绍社交网络对齐，包含社交网络用户对齐和社交网络社区对齐。各部分内容具体安排如下。

第一部分：基础知识。本部分包括第1～3章，主要介绍社交网络的发展历程、图神经网络的基础知识，以及图表示学习相关内容。

第1章首先介绍社交网络的定义及发展史，并介绍了3种常见的社交网络形式化表示方式；其次介绍图的算法与结构；最后在此基础上介绍了几种经典的社交网络模型。

第2章首先介绍图神经网络相关的基础知识以及图神经网络的发展历程；其次介绍图机器学习中常见的3种神经网络模型：频域图卷积神经网络、空域图卷积神经网络和图注意力网络，为理解下一章图表示学习的相关内容打下基础。

第3章首先介绍图嵌入的概念及其相关理论，其次介绍基于随机游走的3种图表示学习算法，最后介绍基于深度学习的3种图表示学习算法。

第二部分：社交网络表示。本部分包括第4～5章，分别从微分方程和狄利克雷分布的角度介绍了基于微分方程的动态图表示学习算法和基于狄利克雷分布的知识图谱表示方法。

第三部分：社交网络对齐方法。本部分包括第6～10章，主要介绍5种社交网络用户对齐或社区对齐的方法。

第6章与第7章分别从静态社交网络和动态社交网络的角度介绍社交网络用户对齐方法。这两种方法能够通过有监督学习，分别在结构相对稳定的社交网络和具有明显动态性的社交网络中发现用户的关联关系。

第8章与第9章分别介绍基于无监督学习和基于迁移学习的社交网络用户对齐方法。无监督学习社交网络用户对齐方法能够解决对齐问题标注种子节点少的问题，迁移学习社交网络用户对齐方法能够更有效地将对齐模式迁移到目标域，进一步改善目标域的对齐。

第10章介绍基于双曲空间的社交网络社区对齐方法。双曲空间作为表示空间，较欧氏空间能够有效地减少数据失真问题。同时，对于社区这类具有明显层次结构的簇，双曲空间也有其优越性。

在本书成书的过程中，叶均达、王飞扬、孙笠、曹画锋、李根、高帅、高宇航、祝梓毅、罗子霄、陈睿扬等同学为收集素材做了大量的准备工作，在此表示衷心的感谢。由于水平及时间所限，书中如存在疏漏和不足之处，敬请广大读者批评指正。

作者

2023年4月于北京

第1章　社交网络与图

社会学家Georg Simmel在冷战期间提出了一种社会学视角——社会网络，旨在分析社会中不同实体之间的联系如何影响实体的行为方式。随着冷战期间互联网思想的诞生与技术的革新发展，互联网时代的社交打破了人与人之间的地域限制，极大地降低了人们的社交成本。由此，着眼于人与人之间交互、沟通和联系的社交网络逐渐从社会网络中分离出来，成为一门独立的综合学科。本章将介绍社交网络的定义、发展史、影响和研究方向等内容，便于读者全面认识社交网络。

为了更好地研究社交网络，研究者需要提取社交网络的特征并形式化地表示社交网络。因此，本章给出了3种常见的社交网络形式化表示方式，分别为语义表示、矩阵表示和图表示方式。其中，图表示方式最为重要。此外，本章还介绍了图的相关知识，包括图的经典算法、图的结构分析和特殊的图，并介绍了这些知识在社交网络中的应用。

考虑到社交网络的复杂性和不规则结构，所有能更好地表示真实社交网络的模型的构建规则都应该具有一定的随机性，该要求与构建规则固定的图表示方式（又称规则网络）相违背。因此，研究者提出了复杂网络的概念，即能够呈现高度复杂结构的网络。本章介绍了复杂网络的小世界现象与无标度特性，并详细介绍了常见的社交网络模型。

1.1　社交网络

社交网络是一种以网络的形式反映社会实体间的组织方式的社会学研究视角。有别于传统的“社群”研究视角，社交网络以顶点表示参与社交活动的实体，以连接顶点的边表示实体间的交互关系。社交网络侧重于研究实体间的交互与联系，而非着力探究不同社群间的划分方式。社交性是人区别于其他生物的重要特点。以人为顶点，以社会关系为边，即可刻画出各种各样的关系，包括人与人之间的情感交流、沟通互动、价值交换、冲突与合作等。例如，在族谱中，网络的顶点表示此家族内的成员，而连接顶点的边表示家族的世系繁衍；在学者合作图中，网络的每个顶点对应一名学者，而连接顶点的边表示学者们的合作情况；在引文关系图中，网络的每个顶点对应一篇文献，而连接顶点的边表示文献的引用关系；在演员共演图中，网络的顶点表示演员，而连接顶点的边表示此边关联的演员曾经出演过同一部作品。

1969年，为了应对冷战中苏联发射的人造地球卫星的威胁，美军委托4所知名美国大学开始了阿帕网（Advanced Research Projects Agency Network，ARPANET）的研究。此研究旨在将4台大型计算设备互相连通，保证在其中任何一台计算设备被苏军摧毁的情况下，与其互联的其他设备都可以跨过被摧毁的顶点，继续维持系统运转。这一“互相连通”的思想催生了现在人们所熟知的互联网。经过几十年的蓬勃发展，互联网的规模急剧扩张，根据中国互联网络信息中心（China Internet Network Information Center，CNNIC）的数据，截至2022年12月底，中国互联网用户数已经达到10.67亿，互联网普及率更是达到惊人的75.6%。互联网的飞速发展彻底打破了人与人之间的地域限制。社交网络迈入了互联网时代，本书聚焦于互联网时代下的社交网络，为便于读者阅读，后文将统一把互联网时代的社交网络简称为社交网络。

本节将着重从社交软件、社交网络的影响、社交网络研究等角度详细介绍社交网络，并给出社交网络的3种典型表示方法，其中社交网络的图表示方法最为重要。

1.1.1　社交网络概述

随着互联网的井喷式发展，一批社交软件如雨后春笋般涌出。这批社交软件以用户为中心，既为使用者提供了向其他用户发布他们想要分享的信息的功能，又满足了使用者根据自身喜好搜索、浏览和关注其他用户发布的内容并与他人建立社交联系的需求，使得其用户在此类软件上能够自由地拓展自己的社交网络，因而广受欢迎^[1]。

1. 社交软件

国内外一些具有代表性的社交软件见表1-1。

表1-1　国内外具有代表性的社交软件

从21世纪初到现在，国内外社交软件的发展呈现出了相似的规律——更多样、更快速、更私密。

（1）更多样。用户交流互动的方式由单一的文字逐渐多元化，并呈现出了短视频化的趋势。专注或局限于某一细分领域的垂直型社交平台（如人人网）已经无法在市场上取得成功。只有“通用”型的社交软件，即可以满足多元化社交需求的产品，才能占领市场。

（2）更快速。用户更加偏好低时延的社交模式，因而社交软件对推荐算法的依赖程度渐渐增强。随着移动互联智能技术和大数据算法的发展，社交软件通过对用户的年龄、性格和爱好等进行智能化检测和快速精确分析，提升用户体验，进而极大地提高了用户黏性。

（3）更私密。用户对社交私密性的需求逐步提升，使得社交软件的隐私保护能力不断加强。脸书、Instagram和TikTok等社交软件都因收集和挖掘用户数据而遭到质疑。未来，对数据隐私和安全的保护是社交软件发展的大方向。

2. 社交网络的影响

伴随着近20年的蓬勃发展，社交软件已然成为大众工作、学习和生活中不可分割的部分。因此，社交网络对整个社会的影响举足轻重，展示出了其空前的力量。

2016年，文艺片《百鸟朝凤》正式公映，因其聚焦于冷僻的题材且缺少有号召力的演员而导致票房表现不佳。该片的联合出品人在直播中恳切请求观众关注优秀的文艺片与逐渐消失的民间艺术。该视频因其强大的感染力在社交网络中火速走红，吸引了大量好奇的观众。最终，《百鸟朝凤》的票房由起初的300多万元飙升至8000多万元。

2020年，山西省大同市政府联合诸位明星进行快手的扶贫助农活动专场。在直播中，多位明星试吃当地美食，为老乡带货。这场直播吸引了众多用户的关注，也引爆了下单的热潮。

2022年10月，山西省大同市的部分小区为有效控制新冠病毒传染实行管控，一位老人因三叉神经疼痛在社区微信群中向邻居求助。群友们看到后纷纷热心响应，与志愿服务中心、社区物业和附近药房联系，主动帮助老人购买药品。

从宣传冷门电影到扶贫带货再到救助老人，社交网络为人们带来了前所未有的便捷。人们能比以往任何时候都更快速地获取、分享、传递和发布消息。然而，社交网络也是一把双刃剑。

2016年，高某通过直播骗取受害者的信任，谎称自己具有占卜通灵的能力，前后骗取了受害者5万余元人民币。2018年，黄某谎称自己是女性，在社交网络中与受害者谈起了网恋，黄某先后以买礼物、买车票等理由向受害者索要4万余元人民币。2022年，微博上有一张聊天截图被数以万计地转发，这张图的内容是：北京大学的“韦神”韦东奕帮助某博士团队解决了困扰他们4个月的难题，使得预测数据与真实数据的相似度高达99.98%。但当记者联系韦东奕时，他立刻否认了这件事的真实性，急忙澄清这是假新闻。

总而言之，社交网络上的诈骗、信息泄露、舆论渗透、引导与攻击已经成为国际社会关注的重点方向。社交网络在一系列重大事件中发挥了重要的组织和策划作用，对国际政治乃至国际社会的安全稳定造成了重大影响。可见，如何控制社交网络的影响力，使其发挥正面作用，是当前社会必须解决的重大问题。

3. 社交网络研究

社交网络的普及在给人们带来巨大便利的同时，也催化了虚假新闻、网络诈骗的传播，将用户置于个人信息泄露的风险中，甚至对国际社会的安全稳定造成了重大影响。正因为如此，正确理解社交网络的形成与演化，发掘信息在社交网络中的传播与扩散途径，认识社交网络对参与者心理与行为的影响，对社会治理有着重要的意义。由此诞生了一门通过计算机技术分析社交网络结构与特性的学科——社交网络分析。

当前对社交网络分析的研究主要分为两类：以结构为导向的社交网络分析研究和以内容为导向的社交网络分析研究。以结构为导向的社交网络分析主要关注社交网络的结构特征，包括发掘社交网络中的特殊顶点、预测社交网络的演化、进行社交网络连接的可视化等。而以内容为导向的社交网络分析侧重于研究社交网络上的媒体信息，包括文字、图像和视频等多模态信息。

社区发现是以结构为导向的社交网络分析的经典议题，旨在发掘社交网络中连接紧密的结构，这些具有高内聚、低耦合特征的结构被称为社交网络中的社区。社区检测问题通常与图的聚类问题密切相关。社交影响分析也是基于结构的社交网络分析议题，聚焦于研究社交网络中参与者的影响力与影响的传播。

情感分析则是以内容为导向的社交网络分析的研究课题，旨在依据参与者在社交网络中表达的观点（包括文字与行为），使用自然语言处理等方法，分析其情感倾向。

虽然社交网络的研究可以分为结构类研究和内容类研究，但这两者之间并不是泾渭分明的。在很多问题的解决中，往往将结构和内容结合起来。例如，在社交网络谣言检测中，不仅可以依托内容对谣言做出判断，也可以从传播方式等结构角度对谣言进行甄别。关于社交网络中的谣言检测，本书也会在后文详细展开讨论。

4. 社交网络数据的获取

目前，社交网络数据的获取主要有两种方式：通过社交软件的应用程序接口（Application Program Interface，API）直接获取数据和自动化收集社交网络数据。大多数社交软件通过API提供了一种便捷、有效获取社交网络数据的方式^[2]。此外，也可利用爬虫工具（如Selenium）在社交软件页面上自动地搜索、收集和整理相关数据。尽管现在大多数人乐于尝试并使用各种社交软件，但是，由于不同社交软件间的封闭性，社交网络数据难以跨平台连通使用。由此诞生了社交网络对齐这一课题，其旨在把同一用户在不同社交平台上的信息关联对应起来，从而打破不同社交软件的屏障，连通用户的全部社交信息。

1.1.2　社交网络的形式化表示

社交网络分析能正确进行的前提是能够用恰当的表示方式对社交网络的重要特征进行抽象。可以说，恰当的表示方法对从社交网络中有效地提取和分析知识起到了决定性作用。由此，社交网络的表示方法研究应运而生。

1. 社交网络的语义表示

社交网络可以用语义（Semantic）的方式进行表示。“语义”这一概念在1998年由Tim Berners-Lee提出。他主张用一种计算机可以理解的语言（即语义）去丰富原有的网页信息，使得计算机能够根据网页的语义自主地学习并进行智能判断。这些可被计算机理解的语义数据被称为本体（Ontology），它以明确规定的形式高度抽象地概括了网页的本质特征，对整个网页的知识进行了集中的总结规范。语义网的实现主要依赖两项技术：可扩展标记语言和资源描述框架。

2008年，Gruber TR首次提出将语义的概念应用到社交网络领域，即把社交网络表示为：社交网络参与者生成的内容信息和提炼概括社交网络的语义元数据^[3]。在社交网络的语义表示中，最重要的本体被称为“Friend-of-a-Friend”，简称FOAF。这个本体被用于描述人与人的互动关系，包括用户信息（如昵称）、连接方式（如关注）和网页使用（如网络日志）等。未来，设计新的语义框架并应用于社交网络的动态表示和分析将成为一条值得探索的道路。

2. 社交网络的矩阵表示

社交网络也可以采取矩阵的方式来表示。最简单的矩阵表示模型以社交网络的顶点数为行数和列数，矩阵中每个元素的值表示对应的顶点间是否直接连通。以A[i][ j]为例，若A[i][ j]=0，则社交网络的第i个顶点和第j个顶点间不存在边；若A[i][ j]=1，则社交网络的第i个顶点和第j个顶点间存在边。这样的表示方法被称为社交网络的邻接矩阵表示法。

除邻接矩阵外，在有的模型中，A[i][ j]的值也可以表示社交网络的第i个顶点和第j个顶点连接的紧密程度、重要程度或优先级别等其他信息，这使得A[i][ j]的取值不再局限于整数0或1。为了更好地表示社交网络中顶点与相邻顶点的连接关系，有学者提出了拉普拉斯矩阵。这样的矩阵L由度矩阵D（即D[i][i]的值等于社交网络中以第i个顶点为端点的边数的矩阵）减去邻接矩阵A得到：

L=D-A　　（1-1）

拉普拉斯矩阵的元素L[i][ j]为

　　（1-2）

其中，v_i表示社交网络中的第i个顶点，deg(v_i)表示以v_i为端点的边数。

社交网络的矩阵表示法虽然简单且容易理解，但这种表示方法给社交网络上与路径相关的任务［如：判断社交网络中是否存在一条从第i个顶点到第j个顶点的路径（第i个顶点与第j个顶点不仅可以直接邻接，也可以借助其他顶点间接到达）］带来了极大的困难，因而社交网络的矩阵表示法并未被广泛使用。

3. 社交网络的图表示

社交网络分析中最重要的表示方法是图。社交网络与图存在一一对应的关系。图的顶点对应着社交网络中的实体，而边对应着社交网络中实体间的交互关系。

（1）图及其定义

定义1：图G是由顶点集V(G)和连接两个顶点（不要求两个顶点不相同）的边集E(G)构成的二元组。图G可以被记作。

图1-1的顶点集，边集。

图1-1　由4个顶点和6条边构成的图

定义2：如果图G中不存在具有完全相同顶点的两条边，那么称G为简单图。具有一对完全相同的顶点的多条边被称为重边。

如果图的边集为空，那么这样的图称为空图^[4]。对于非空图G，如果G是简单图且图G的边无方向，那么图中任何一条边都可以用无序的顶点对进行唯一的标识。

显然，图1-1的边集。

定义3：如果图G中存在边uv，那么称顶点u和顶点v邻接且互为邻居，边uv与顶点u和顶点v关联。如果边的两个顶点重合，那么称这样的边为圈。

在图1-1中，共有6对顶点互为邻居。

定义4：图的路径是图的边序列，使得，的第二个顶点与的第一个顶点重合；如果路径中，的第一个顶点和的第二个顶点重合，那么称此路径为回路或环。图的通道是图的由顶点和边构成的序列，使得，与顶点和关联。图的迹是序列中没有重复的边的通道。是以u为第一个顶点、v为最后一个顶点的路径。

对于以图表示的社交网络（以下简称“社交图”），图的顶点集对应社交网络的顶点集合，图的边集表示社交网络中顶点的交互关系，因此，社交图被广泛地应用于社交网络分析。

（2）有向图

定义5：对于集合M上的二元关系R，，如果ARB成立，且BRA同时成立，则R在M上是对称的。

在现实生活中，社交关系可以按照对称与否进行划分。比如：两名教授的合作关系是对称的；伴侣之间的恋爱关系是对称的；微博的关注关系可以是非对称的；公司职员间的管理关系是非对称的。对于这些非对称的关系，需要用一个更一般的模型去表示^[5]。

定义6：有向图G是由顶点的集合和有序连接两个顶点（不要求两个顶点不相同）的边的集合构成的二元组。无向图N是由顶点的集合和无序连接两个顶点（不要求两个顶点不相同）的边的集合构成的二元组。

简单有向图G中，任何一条边都可以用有序的顶点对进行唯一的标识。通常把有序顶点对的第一个顶点称为边的尾部，第二个顶点称为边的头部。边的头部被称为尾部的前驱，尾部被称为头部的后继。因此，图G的每条边都是由尾部指向头部的边。

图1-2中有一条从x指向y的边，记作。

社交网络中的对称关系可以用无向图表示，而非对称关系则用有向图表示。微博的关注关系图中，如果用户1关注了用户2，那么图中存在一条由用户1指向用户2的有向边，相反，如果用户2关注了用户1，那么图中存在一条由用户2指向用户1的有向边。另外，如果用户1和用户2互相关注，那么顶点1和顶点2之间同时存在着由用户1指向用户2和由用户2指向用户1的两条有向边。

图1-2　有向图

（3）有权图

在社交图中，人们不仅想知道社交网络中的哪些参与者之间存在关系，同时还想知道其关系的强弱程度。为了解决这一问题，引入了有权图的概念。

定义7：有权图的每一条边都对应着一个实数W，W被称为对应边的权值。

图1-3的边的权值为-1。

图1-3　有权图

权值可以是任何实数，不同场景下的含义各不相同。在城际铁路连通图中，边的权值表示边的两个顶点对应的城市之间的距离；在车流量图中，边的权值表示边对应的路段上的车流量大小；在电路花费图中，边的权值表示对应电路的成本。在社交网络中，有权图的权值通常表示社交联系的紧密程度、情绪的激烈程度和观点的认同程度等。

（4）图的存储

图在计算机中有两种常见的存储方式：邻接矩阵和邻接表。其中，邻接矩阵存储法用一维数组存储图的顶点，用二维数组存储图的边。对于有权图，其邻接矩阵edge的计算公式如下：

　　（1-3）

其中，表示边的权值。

对于无权图，当边存在时，二维数组中的元素，否则，，其公式如下：

　　（1-4）

邻接表是数组与多个链表相结合的存储方法。在邻接表中，一维数组存储图的顶点信息，每个链表存储与对应顶点邻接的所有顶点的信息。具体来说，一维数组包括顶点与指向顶点的第一个邻接顶点（即对应链表的表头）的指针。那么，邻接矩阵和邻接表各自适合存储什么样的图呢？

定义8：图中，，，当时，称G为稀疏图，反之，称G为稠密图。

图，，，G的邻接矩阵所占空间大小为。也就是说，图G的邻接矩阵大小仅与G的顶点数相关。图G的邻接表所占空间大小则为m+n。因此，对于稀疏图，其边数相对于顶点数较少，邻接矩阵的存储方式是一种极大的空间浪费，故通常用邻接表存储稀疏图。而对于稠密图，邻接表与邻接矩阵在存储空间上差别不大，邻接矩阵的存储方式具有易访问和易修改的优点，因而多用邻接矩阵存储稠密图。

1.2　图

本节将介绍图的经典算法——用于解决社交网络中的问题，以及图的结构分析方法——以供读者从结构的角度分析社交图。最后，介绍几种特殊的图，以及这些图在社交网络场景中的应用。

1.2.1　图的经典算法

1. 深度优先搜索（DFS）和广度优先搜索（BFS）算法

如果想查找社交网络中的某个参与者，则可以搜索社交图，若能够搜索到对应的顶点，那么社交网络中存在此参与者，否则，不存在此参与者。如果想知道社交网络中是否存在参与者1到达参与者2的途径，则可以在社交图中搜索参与者1对应的顶点，若从此顶点出发能够搜索到到达参与者2对应顶点的路径，则认为社交网络中存在此途径。

最常见的两种图搜索算式是深度优先搜索（Depth First Search，DFS）和广度优先搜索（Breadth First Search，BFS）。

DFS算法有“不撞南墙不回头”的特点，其在搜索过程中沿着与当前顶点关联的边向下搜索，如果当前顶点的所有邻接顶点都已经被搜索过，那么回溯到上一个被搜索的顶点。重复此操作，直至找到搜索目标。DFS算法的每一次搜索都尽可能地在回溯到上个顶点之前在每个分支上搜索得更深入，因此得名“深度优先搜索”。

BFS算法的思路则是逐个搜索与当前顶点邻接的所有顶点，直到所有邻接顶点都被查询过后，才认为当前的顶点已经被搜索完毕，再继续下个顶点的搜索。

算法1-1　BFS算法

输入：图G，起始顶点u，搜索目标顶点t

输出：BFS结果

1： // S为待搜索顶点队列，R为已搜索顶点集

2：while do

3：  取S中的第一个顶点v进行搜索，将v所有不属于的邻接顶点添加到S中；

4：  将S中的v删除，加入R中；

5：end

2. Kosaraju算法

定义9：图，如果对于任意的都存在一条路径P(u,v)，则称图G是连通的，否则，称G是非连通的。如果G中存在路径P(u,v)，则称u连通到v。

定义10：有向图，如果对于任意的都同时存在路径P(u,v)和路径P(v,u)，则称图G是强连通的。

如果社交图是连通的，那么可以理解为社交图对应的社交网络中的任何两个参与者之间都存在直接或间接认识的途径。

定义11：如果图H满足，且H中边的顶点的分配方式和G一样，那么称H是G的子图。

定义12：有向图G最大的强连通的子图被称为图G的强连通分量。

社交图的强连通分量内任意两者之间都存在相互到达的途径，因此此分量内的人群连接紧密，他们可能拥有共同的兴趣、相似的价值观和类似的成长背景等，因而可以用寻找社交图的强连通分量来发掘社交网络中连接紧密的小团体。

Kosaraju算法需要进行两次DFS，第一次得到有向图的拓扑结构，第二次得到有向图的强连通分量。

算法1-2　Kosaraju算法

输入：有向图G，记录顶点搜索顺序的数组t={}

输出：G的所有连通分量

1：对G进行DFS，在t中记录顶点的搜索顺序；

2：对G进行取反操作（顶点不变，边的方向取反）得到G′；

3：while do

4：  按照t中搜索顺序的逆序对G′进行DFS，把搜索过的顶点从G′和t中删除，直到搜索无法继续进行；// 所有被删除的顶点以及它们之间关联的边组成了G的一个连通分量

5：end

3. 入度表（Kahn）算法

通过寻找有向图的拓扑排序可以确定社交图上是否存在回路。

定义13：拓扑排序是有向无环图的顶点集V的线性序列，满足对于G的每一条有向边，在拓扑排序中，u的顺序都在v之前。

如果能找到有向图对应的拓扑排序，就表示此图中没有环；反之，如果有向图不存在拓扑排序，那么此图中就一定存在回路。通常利用入度表（Kahn）算法来寻找有向图的拓扑排序。

算法1-3　Kahn算法

输入：有向图G，记录拓扑排序的数组S={}

输出：S（图G的拓扑排序）

1：while do //为以v为终点的边数

2：  把不存在任何指向其的边的顶点都加入S中；

3：  从G中删除在步骤2中加入S的顶点，并把从此顶点出发的边也从G中删除；

4：end

4. Dijkstra算法

图上还有很多其他经典算法，如Dijkstra算法、Prim算法、Kruskal算法。虽然这些算法多应用于路径规划、计算机网络时延计算、路由选择、资源优化等场景，但社交网络中的某些问题也可以用这些算法来解决，比如寻找某社交网络中与其他参与者之间关系最淡薄的参与者。

社交网络中参与者之间关系的深浅主要体现在其对其他参与者的影响力大小，也就是说，参与者对其他参与者的影响力越大，其与其他参与者之间的关系越亲密，反之则越淡薄。想要寻找社交网络中与其他参与者关系最淡薄的人，就等价于寻找社交网络中影响力最小的顶点。由此，把社交网络转换成一张有权社交图，边的权值表示社交网络中对应顶点之间连接的边的数量。通常，将所有P(u,v)中权值之和最小的路径称为最短P(u,v)，将此权值称为u到v的最短距离。那么，可以将社交网络中某顶点的影响力表示为其到其他所有顶点的最短距离之和。这样，一个社交网络上的问题就被转化成了计算最短距离的问题，可以用图的Dijkstra算法来求解。

Dijkstra算法是由荷兰计算机科学家Edsger W.Dijkstra于1959年提出的算法。该算法基于一个显而易见的事实：假设v是P(u,z)中的一点，那么最短P(u,z)中，u到v的部分必定是最短的P(u,v)。因此，Dijkstra算法按照路径长度递增次序产生起点到其他所有顶点的最短路径。

算法1-4　Dijkstra算法

输入：有非负权值的图，起始顶点为u，边xy的权值记为，如果边
　　　xy不存在，那么，顶点集

输出：起始顶点u到其他所有顶点的最短距离

1：对于，计算；

2：while do

3：  选择，把对应的添加至S中；

4：  用更新中顶点的dist值；

5：end

5. Prim算法

定义14：如果H满足，且H中边的顶点的分配方式和G一样，那么称H为G的生成子图。

定义15：树是不含有环的连通图。

定义16：如果树T是连通图G的生成子图，那么称T是G的生成树。

定义17：如果生成树T是加权连通图G的各边的权值之和最小的生成树，那么称T是G的最小生成树。

Prim算法和Kruskal算法常用于搜索图的最小生成树。这两种算法都采用了贪心算法，即：求解问题时，总是做出在当前看来最好的选择。换言之，贪心算法解决问题不从整体最优的角度出发，而是把问题拆分成若干个子问题，先对每个子问题寻求最优解，再将若干局部最优解组合成原问题的最优解。

算法1-5　Prim算法

输入：  加权图，最小生成树，其中，（x为起始顶点），

输出：最小生成树H

1：while do

2：  在E中选取权值最小的边uv，其中，；// 如果存在多条边满足前述条件，即有多条相同权值的边，则可任意选取其中之一

3：  将v加入中，uv加入中；

4：end

6. Kruskal算法

Kruskal算法的思路是从具有最小权值的边开始不断扩张树H，直至生成最小生成树。

算法1-6　Kruskal算法

输入：加权图，最小生成树

输出：最小生成树H

1：按照边的权值从小到大测试所有边，如果把当前边加入最小生成树H的边集中，不会使得H中出现环，则把这条测试边加入当前的最小生成树中；否则，将边舍弃；直到H中所有顶点互相连通

1.2.2　图的结构分析

每个社交网络都与社交图一一对应，通过发掘图的结构特征，就可以得到对应的社交网络的结构特点。因此，分析图的结构是社交网络分析的重要手段之一。

1. 社交图顶点的结构分析

度指的是与图上顶点关联的边数。在有向图中，由于边存在方向，因此顶点的度分为出度和入度：顶点的出度等于由此顶点出发的边数，入度则等于指向此顶点的边数。度是最简单的表示顶点与其他顶点的关联程度的变量。一个顶点的度越大，这个顶点与其他顶点的关联越紧密，在社交网络中，此顶点对其他顶点的影响越大，在网络中的地位越重要。这种表示方式虽然简单有效，但是仅仅考虑了顶点间的直接关联，而忽略了整个社交图的结构特征。顶点的度也被称为绝对中心度，为

　　（1-5）

为弥补绝对中心度的局限性，1979年Freeman提出了相对中心度的概念。相对中心度为顶点的绝对中心度与可能的最大绝对中心度的比值。对于一幅有着个顶点的无环无向社交图，其可能的最大绝对中心度为。无向社交图的相对中心度为

　　（1-6）

通常，研究者把有一个度为的顶点和个度为1的顶点的图称为星图，或称为星形耦合网络。图1-4是一个有6个顶点的星图。此星图中，顶点a具有最大绝对中心度。

图1-4　星图

对于无圈的有向图，其可能的最大绝对中心度为，因此有向社交图的相对中心度为

　　（1-7）

绝对中心度与相对中心度都只考虑了顶点与其他顶点的直接联系，而忽略了间接联系。因此，Sabidussi提出了接近中心度的概念。他认为：顶点的重要性应该由其对其他顶点的依赖性来决定。一个顶点越重要，它越容易与其他顶点进行交互；一个顶点越不重要，它与其他顶点的交互越困难，换言之，它与其他顶点的最短距离之和越大。因此，社交图的接近中心度为

　　（1-8）

其中，表示G的顶点v和顶点t之间的最短距离。

对顶点v到其他所有顶点的最短距离进行平均，得到顶点v的平均最短路径：

　　（1-9）

其中，N表示社交图G的顶点总数。

顶点v的平均最短路径只对连通图G有意义，因为如果顶点v与顶点u不连通，那么最短P(u,v)的值为∞。为了得到非连通图的平均最短路径，对进行取倒数处理，得到顶点v的全局效率：

　　（1-10）

越小，顶点v与其他顶点间的信息传播越慢，社交互动越困难。类似于全局效率，可以定义顶点v在社交图的区域H上的局部效率：

　　（1-11）

其中，表示社交图的子图H中的顶点数。

在地铁线路中，不同线路交会的车站被称为交通枢纽站，比如：西直门站是北京地铁2号线、4号线和13号线的交通枢纽站。仿照这个思路，可以用某顶点承载的最短路径数来表示此顶点在社交网络中的重要程度。通常将经过顶点的最短路径数称为顶点v的介数（Betweenness）。

2. 社交图整体的结构分析

上述分析都是基于顶点的社交图结构分析，然而，很多时候，人们关注的重点并不是图上的某个顶点，而是整幅社交图。通常用度分布来刻画社交图的顶点的绝对中心度的分布。度分布可以揭示网络的类型及性质，是网络的重要几何性质。

　　（1-12）

其中，表示图G中度为k的顶点数，N表示图G的顶点总数。

对于一个顶点数有限的完全随机网络，其度分布符合泊松分布。泊松分布的形状以峰值为中心，峰值两侧以指数速度衰减。在这样的网络中，度值比平均值高许多或低许多的顶点，都十分罕见。

科学家们一直想当然地认为现实中的网络都是完全随机的，但1999年无标度网络的提出打破了这种构想：现实世界中的大多数复杂网络（如因特网、万维网和生物新陈代谢网络等）的度分布明显偏离了泊松分布，它们的顶点度分布更符合幂律（Power Law）分布的特征。

幂律分布的曲线有一条长长的尾巴，因此，幂律分布又被称为长尾分布。符合幂律分布的图中，顶点的度往往相差悬殊，极少数顶点的度很大，而绝大多数顶点的度很小，其度范围往往可以跨越几个数量级。比如：在社交网络中，往往少部分人掌握着大多数的社交关系，而其他人的社交关系相当有限。

通常将度分布服从幂律分布的复杂网络称为无标度网络（Scale-Free Network）。与随机网络相反，它是一种高度集中的网络，在这种网络中，度值极大的几个顶点被称为“集散顶点”，它们对整个网络的结构及特性有着很重要的影响。

社交网络的度中心势C用于衡量社交网络的绝对中心度的趋势，其公式为

　　（1-13）

其分子的含义是社交图G中所有顶点的绝对中心度与最大中心度之差的总和，其分母的含义是所有顶点的绝对中心度与最大中心度之差的总和的最大可能值。在具有N个顶点的星图中，中心顶点的绝对中心度为，其他顶点的度为1，因此，所有顶点的绝对中心度与最大中心度之差的总和为，这也是该总和的最大可能值。所以式（1-13）可以转换为

　　（1-14）

1998年，美国康奈尔大学的博士生Duncan Watts和他的导师Steven Strogatz共同发表了一篇名为Collective dynamics of 'small-world' networks的论文。他们认为，复杂网络可以按照两个独立的结构特性进行分类——集聚系数和顶点间的平均路径长度^[6]。集聚系数反映了顶点的邻接顶点间结构的紧密程度，集聚系数越大，此顶点的邻接区域中的顶点连接越亲密，的定义如下：

　　（1-15）

其中，表示社交图上与顶点v邻接的顶点数，表示社交图上与顶点v邻接的顶点之间的边数。

的含义是个顶点之间最大的可能边数。由此，顶点v的集聚系数可以被理解为顶点v的邻接顶点间的实际边数与最大可能边数的比值。集聚系数是能够描述图或网络中的顶点集结成团的程度的系数。显然，的范围介于0～1之间。越接近1，表示这个顶点附近的点越有“抱团”的趋势。

平均路径长度指的是一个网络中两个顶点之间最短距离的平均值，定义顶点到自身的最短距离为0，则社交图的平均路径长度定义为

　　（1-16）

如果去除每个顶点到自身的距离，那么平均路径长度可以被定义为

　　（1-17）

社交网络的密度（Density）则从边数角度衡量社交网络的结构紧密程度，其公式为

　　（1-18）

其中，表示社交图的边数。

一般情况下，关系网中边数越多，顶点间的关系越紧密，信息的传播越快速。

此外，社交网络的大小指社交图中顶点的个数。社交网络的直径指的是社交图中任意两个顶点u和v之间的最短距离。对于非连通图，其直径显然是∞。该值反映了社交网络联系的紧密程度。

3. 社交图层次的结构分析

具有严格组织结构的社交图，如表示公司管理关系的图，往往具有明确的层次性。公司管理制度的存在，使得此类社交网络上信息的传递具有严格的方向，因而社交图呈现出强烈的层次特征。因此，可以用层次度（Hierarchy）来评价社交图的层次性。

社交图的层次度H定义为

　　（1-19）

其中，表示社交图中双向连通的顶点对的数量。

社交图的结构层次性越强，社交关系的方向越明确，双向连通的顶点对越少，层次度H更接近1。

1.2.3　特殊的图

1. k部图

现在的人乐于使用各种社交软件，一个人可能会在多个社交软件上都注册有账号。现有社交图G，G中的顶点表示某人在某社交软件上的账号，比如某人的微信号或某人的豆瓣账号。为了打破各个社交软件间的壁垒，可以把同一个人在不同软件上的账号用边关联起来，比如把表示某人的微信号的顶点与表示其豆瓣账号的顶点相关联。此时，社交图G可以被划分成k个独立集，每个独立集代表一种社交软件。

定义17：如果图G可以被划分为k个互不相交的非空子集，使得每个子集内不存在任何互为邻居的顶点，则这样的图G被称为k部图。如果，那么图G为二部图，如图1-5所示。

图1-5　二部图

除了表示社交关系，k部图也常用于表示资源的分配方式。比如：图G的顶点表示学校的教师或学生，如果老师给某位学生讲过课，则将该老师与该学生相关联。此时，图G为二部图。

2. 同质图、异质图

社交图中每个顶点的特征类型往往相同。但是，在某些情况下，图的顶点并不全是同类型的，顶点需要不同的特征来表达，通常分别用同质图和异质图来表示。

定义18：同质图（Homogeneity）是图中的顶点类型和关系类型都仅有一种的图。异质图（Heterogeneity）是图中的顶点类型或关系类型多于一种的图。

图的另一个概念——同构，与同质名字相似，但需要注意的是，这是两个完全不同的概念。“同构”这一概念只适用于一组图，单独说某张图是同构的是没有任何意义的。

定义19：对于图和图，如果存在一个双射f将映射到，使得对于任何都有对应的，那么图G与图H是同构的。

由于顶点位置的选择不同，不同的人根据同一个邻接矩阵可能画出表面上截然不同的图，但实际上，这些图是同构的。

在有机化学中，分子式相同、结构不同的化合物互为同分异构体，如因碳架不同产生的碳架异构体。由于化学键的能量存在差异，同分异构体之间的化学性质具有明显的差异。然而，在图论中，图的结构决定了图的本质特征，因此，同构的图之间有类似的性质。同构关系是一种等价关系，具有自反、对称和传递的属性。等价关系可以把一个集合划分成一些等价类。相应地，图的同构关系也可以把图集合划分成几个同构类。

3. 超图

在学者合作关系网络中，普通的图虽然能表示作者之间是否存在合作关系，但是不能表示是否有3个及以上的学者同时参与了一次合作，即使关联多个学者的顶点也仅代表两两之间有过合作而非有过共同的合作关系。

为了解决普通的图无法完全刻画真实世界的网络特征的问题，数学家Claude Berge于20世纪60年代提出了一种新的图理论——超图（Hypergraph）理论。在超图中，边被推广为广义的边，即可以和任意个数的顶点相连的超边。下面给出超图的数学定义。

定义20：超图，V是顶点集，E是V的一组非空子集，其元素被称为边或超边。

4. 树

定义21：所有连通分量都是树的非连通图被称为森林。

定义22：树上每一个顶点的子树的个数为这个顶点的度；树上度为0的顶点被称为该树的叶。

图1-6中，薛公的度是1，薛蝌、薛宝琴、薛蟠和薛宝钗是该树的叶。

图1-6　薛家人物关系树

树是图论中最简单的图，也是图的骨架^[7]。除了上述表示人物关系的应用，树还有很多其他应用，如表示文件的目录结构。

1.3　社交网络模型

复杂网络理论兴起于20世纪90年代，是对复杂系统的一种抽象。随着功能越来越强大的计算设备和互联网的迅猛发展，人们逐渐能够收集和处理规模巨大且种类不同的网络数据，因此对复杂网络的研究变得越来越必要。其中，社交网络是复杂网络应用中最直观的例子。本节首先介绍复杂网络中著名的小世界理论，接着在此基础上介绍一些常见的社交网络模型：ER随机网络模型、WS小世界网络模型、BA无标度网络模型。

1.3.1　ER随机网络模型

1. 随机图简介

在了解ER随机网络模型之前，首先需要了解随机图的概念。随机图的“随机”体现在边的分布上。一个随机图是将给定的顶点之间随机地连上边。具体来说，给定一定数量的顶点，随机地将两个顶点之间连上一条边，多次重复后，最终得到一个随机图。由于边的产生可以依赖不同的随机方式，因此就产生了不同的随机图模型。图1-7所示为一个ER随机网络。

图1-7　ER随机网络

2. ER随机网络模型

在图论中，ER随机图是一种网络，因此也被称作ER随机网络模型（Erdős-Rényi model）。ER随机图于1959年被提出，以Paul Erdős和Alfréd Rényi的名字命名。同年，Edward Gilbert独立提出了另一个模型，该模型和ER随机网络模型是两种不同但又密切相关的描述方式。

在ER随机网络模型中，当顶点集数量相同时，具有固定边数的所有图均具有同等的出现概率。在Gilbert引入的模型中，每条边都有固定的出现概率，并与其他边独立。将该模型用于概率方法能证明满足各种属性的图的存在，或者对几乎所有图的属性提供严格的定义。下面分别对这两种模型进行介绍。

ER随机网络模型的第一种描述方式是：给定网络顶点数N，网络中的任意两个顶点以概率p连接，生成的网络全体记为，构成一个概率空间。中的一个图平均有条连边。任意特定顶点的度服从二项分布：

　　（1-20）

特别地，若N很大且p很小，得到其满足泊松分布：

　　（1-21）

ER随机网络模型的第二种描述方式是：给定网络顶点数N和网络的边数M，从构成的所有图的集合中随机选择一个图（不能出现重边和自环）。生成的网络全体记为，构成一个概率空间。

M条连线是从总共条可能的连线中随机选取的，生成的网络全体记为，构成一个概率空间。这样，生成的不同网络的总数为，它们出现的概率相同，服从均匀分布。

3. ER随机网络模型的简单应用

ER随机网络模型与现实世界非常相关。研究表明，在社交媒体平台中，随机选择一个用户作为顶点，与该用户互为好友的用户用边相连，最终得到的网络结构特征类似于随机图。因此，理解ER随机网络模型有助于理解小型社交网络的结构。

此外，人们常利用实际网络与模型的巨大差异来识别社交网络中的虚拟账号和人工智能账号，从而发现网络中的异常情况。ER随机网络模型更直接的商业应用是广告，利用该模型可以发现业务趋势或识别用户特征，从而实现更精准的广告推送。

1.3.2　WS小世界网络模型

20世纪60年代，美国心理学教授Stanley Milgram做了一个著名的连锁信件实验。实验发现，任意两人之间的间隔陌生人数不会超过6个，换句话说，最多通过6个中间人，你就能够认识任何一个陌生人。此现象被称为六度分隔理论（又称小世界理论），它奠定了社交网络的理论基础。

在网络理论中，小世界网络是一类特殊的复杂网络结构，是以小世界理论为基础引出的网络模型。在这种网络中，大部分的顶点彼此并不相连，但绝大部分顶点之间经过少数几步就可到达。小世界网络是Watts和Strogatz在1998年提出的介于完全规则网络与完全随机网络之间的网络模型，即Watts-Strogatz模型。该模型具有高集聚系数和小平均路径长度的特点，是最典型的小世界网络模型。图1-8是经典网络的演变过程。

图1-8　经典网络的演变过程

1. WS小世界网络模型的构建过程

WS小世界网络模型基于一个假设：小世界网络是介于规则网络和随机网络之间的网络。首先开始于规则图形，初始有数量固定的N个顶点，每个顶点有K个最近邻，构成一个规则的一维圆环。然后进行随机化重连，选择网络中的一个顶点，每个顶点的每条边都以概率p随机地选择网络中的边进行重新连接，重新连接的边需要保持该顶点一端不变，将连接的另一端随机换成网络中的另一个顶点，但不能使两个顶点之间有多于一条边。最后，由于最初的NK个连接中每个连接都恰好有一次重连的机会，所以这个过程最后一定会结束。最终得到的网络称为WS小世界网络。

对于上述的构建方式，当p=0时，重连永远不会发生，最后得到的是原来的规则网络，此时网络是具有高集聚系数与较大平均路径长度特性的完全规则网络；当p=1时，所有的连接都被重连了一次，最后得到的是一个完全随机网络，此时网络是具有低集聚系数与较小平均路径长度的完全随机网络。图1-9所示为网络顶点数为20、连接概率为0.9的WS小世界网络。

图1-9　网络顶点数为20、连接概率为0.9的WS小世界网络

2. 疾病传播中的小世界网络

研究者通过研究简易化的疾病传播模型揭示了小世界网络的动力学性质^[6]。现实中的疾病传播通常简化为其中一个人（网络中的一个顶点）被感染，其余人健康。患病者在一段时间后因死亡或被隔离而永久离开网络。在这段时间中，病毒感染者传染引起其余健康个体患病的可能性为p。在接下来的时间中，病毒不断在人群中传播，直到整个群体被感染或者病毒灭亡。最终得出结论：尽管网络中只形成了少量的捷径，小世界网络模型中全体感染所需的时间与随机图被全体感染的时间十分接近，即疾病在小世界网络中迅速传播。

1.3.3　BA无标度网络模型

1. 无标度网络

对比ER随机网络和WS小世界网络可以发现，它们都是一种典型的均匀网络，即度分布函数能用泊松分布曲线来近似表示。小世界网络模型说明在现实中大多数人都拥有差不多规模的社交圈，但是现实的许多网络，比如微博，并不符合均匀网络的分布特性：在该网络结构中，通常微博“大V”的粉丝数巨大，普通用户的粉丝数非常少，不同顶点的入度极其不均匀，这一特征与小世界网络所表现出来的特性极其不同。

Barabási和Albert从数理统计出发，提出了建立无向网络的数学方法，其度分布函数服从幂律分布，由他们提出的方法所建立的无标度网络被称为BA无标度网络模型。

在网络理论中，无标度网络是带有一类特性的复杂网络，其典型特征是网络中的大部分顶点只和很少顶点连接，而有极少的顶点与非常多的顶点连接，这些顶点在网络构建中起到中枢顶点的作用，如图1-10所示。这种无标度网络具有普遍性，很多社交网络都具有无标度网络特征。

图1-10　无标度网络

2. BA无标度网络模型的构建过程^[8]

BA无标度网络模型基于两个假设：一是增长模式，即大多数的现实网络是不断扩大的；二是优先连接模式，即新的顶点在加入时会倾向于与有更多连接的顶点相连。基于这两个假设，BA无标度网络模型的具体构建可以分为如下两步。

（1）增长

网络通常通过添加顶点和边的方式增长，这些增长形成了网络结构特征。BA无标度网络的增长过程是：网络初始顶点数为m₀，在建立网络的每个时间步都有一个顶点加入网络并与当前网络中的m个顶点相连，其中。

（2）优先连接

新顶点加入网络时会选择与m个顶点相连，连接原则为优先考虑度数大的顶点。对于某个原有顶点，将其在原网络中的度数记作，新顶点与其相连的概率为

　　（1-22）

经过t个时间步长后，网络顶点数变为m+t，新增mt条边。3个初始顶点以及3条边组成了BA无标度网络，该网络的演变过程如图1-11所示。

图1-11　无标度网络的演变过程

BA无标度网络模型属于无权网络，即网络中顶点之间只表示是否存在连接，而不用考虑这种连接关系的强弱性。而在现实中，如社会关系网中人与人之间的相识程度、通信网络中干线的带宽等，它们彼此的连接强度是不同的，这种不同显然会影响顶点之间的关系。为了处理这种情况，可以为顶点与顶点之间赋予一定的权值，通过权值来描述这种差异性，即加权网络。

1.4　本章小结

本章首先介绍了社交网络的定义、历史、影响、研究方向等，便于读者全面认识社交网络。为了更好地研究社交网络，本章介绍了3种常见的社交网络形式化表示方式，并进一步介绍了图上的算法与结构等相关知识。考虑到社交网络的复杂和不规则结构，规则网络不能完全呈现具有高度复杂结构的社交网络，因此本章介绍了复杂网络的小世界理论，并在此基础上详细介绍了几种经典的社交网络模型：ER随机网络模型、WS小世界网络模型和BA无标度网络模型。

参考文献

[1] SAJID Y B, MUHAMMAD A. Analysis and mining of online social networks: emerging trends and challenges[J]. Wiley Interdisciplinary Reviews-Data Mining and Knowledge Discovery, 2013, 3(6): 408-444.

[2] DEEPIKA V, DINESH K V. A review on rumour prediction and veracity assessment in online social network[J]. Expert Systems with Applications, 2021, 168(4): 144-208.

[3] TOM G. Collective knowledge systems: where the Social Web meets the Semantic Web[J]. Journal of Web Semantics, 2008, 6(1): 4-13.

[4] WILSON R. Introduction to graph theory[M]. Beijing: World Publishing Corporation, 2010.

[5] WEST B. 图论导引[M]. 2版. 李建中，骆吉洲，译. 北京：机械工业出版社，2020.

[6] WATTS D, STROGATZ S. Collective dynamics of 'small-world' networks[J]. Nature, 1998, 393(6684): 440-442.

[7] 王树禾. 图论[M]. 北京：科学出版社，2009.

[8] BARABASI A-L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.