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。

从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的顶点集，边集。

定义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的两条有向边。

（3）有权图

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

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

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

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

（4）图的存储

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

　　（1-3）

其中，表示边的权值。

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

　　（1-4）

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

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

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