第四节
动态网络分析方法

无论是文本网络，还是社交网络，在网络分析的过程中，社团结构作为介于宏观网络和微观个体之间的中观结构，其在社团层面所具有的特性是网络层面的特性所不能替代的，忽视社团结构可能会遗漏关键网络特征 。尤其是近年来随着网络数据可得性的增强，具有时间信息的动态网络的社团分析的研究不断增加。时间信息的引入能够以纵向视角重新观察网络的发展，刻画网络演化的模式。因此，本节对动态社团的发现、演化和应用进行了梳理，为网络文本分析提供技术和方向性的参考。

一、动态网络的社团发现

社团结构是复杂网络的拓扑特性之一，发现复杂网络中的社团结构是复杂网络研究的基础性问题 。通常认为，社团结构是指网络中的节点可以被划分为多个分组（Group），组内节点连边相对紧密，组间节点连边相对稀疏 。社团发现（Community Detection）是识别网络中节点群组关系的过程，社团发现往往能够揭示网络更深层次的特征，为理解网络的内部结构和生成机制提供了极具意义的研究视角 。

动态网络（Dynamic Network）是一种处在变化过程中的特殊的演化复杂网络（Evolving Complex Network） ，例如网络节点的加入或移除，或是节点间连边关系的改变，这些变化或许对整个网络结构的影响甚微，但是从动态演化的角度来看，随着时间的推移，细小变化的累积可能最终会导致整个网络及其社团结构特征的改变。

为了实现对动态社团的演化追踪，按照动态网络社团发现算法输入的网络数据类型，纳里梅内·达基切（Narimene Dakiche）等人 ₅ 将算法分为两大类：第一大类是对网络数据按照时间步进行切片，得到一组网络切片序列（Sequence of Snapshots），将其作为输入数据然后进行社团发现分析及演化追踪；第二大类社团发现算法的输入数据是时态网络（Temporal Network），时态网络是通过记录网络中连边随时间移动而产生的变化信息来实现的。具体而言，对于时态网络上的动态社团检测，不需要每次都从零开始对网络进行社团发现，而是根据网络中点与边的变化，对之前已发现的社团进行更新，即时态网络的社团发现是由一个初始的静态社团和对此社团的一系列修改（例如节点的聚集和删除）组成的。但是网络切片序列和时态网络这两种数据类型可以互相转换，时态网络虽然在数据类型上是以“初始网络”和“每个时间点的网络变动”的形式存储，但是其数据反映的还是在每个时间点的网络结构，和网络切片序列所包含的信息是一致的，只是分析单位不同。

综合来看，不同动态社团发现算法最本质的区别在于是否使用历史信息推断当前时刻的社团结构。因此，本书将综合以往学者对社团发现算法的分类方式 ，按照发现当前社团时是否考察网络历史信息这一差异，将动态社团发现算法归纳为独立的社团发现算法（Independent Community Detection）和基于历史的社团发现算法（如图2.2）。

（一）独立社团发现算法

独立社团发现算法针对的是网络切片序列数据，该类算法在对每个时间切片发现社团时，不考虑以往时间切片，因此对于变动较大的动态网络也适用。该算法分为两个阶段。第一阶段：对每一个时间步的网络切片分别进行社团发现。第二阶段：将当前时间切片的社团发现结果与上一时间切片的社团发现结果按照一定的相似性规则进行匹配，从而得出社团的演化过程。该方法将动态网络的社团发现转化为了传统的静态网络社团发现问题，第一阶段可以根据不同的数据背景选择合适的算法，第二阶段可以根据社团的结构（Structural）和社团的语义（Semantic）等维度的相似性指标，匹配不同切片中的社团。该类方法不但可以根据实际网络在两步中选择合适的方法进行组合，而且可以处理重叠和非重叠的社团发现。例如Wang等人 利用节点的结构特征、点权等信息评估出社团内核心节点，然后利用社团的核心节点匹配每个独立切片网络中的社团。孙扬等人 利用经典Louvain算法对每个网络切片划分社团，然后对相邻切片划分的社团两两计算相关矩阵，进而匹配和判别社团演化事件。彼得·布罗德卡（Piotr Bródka）等人 采用“群体演化发现”（Group Evolution Discovery，GED）方法，考虑了社团节点的质量（Social Position）和数量，计算出社团间的包容性（Inclusion），根据此指标匹配相邻网络切片的社团。该类算法的优点是思路简单、灵活，本质是在以往对静态网络社团划分后增加了网络切片的匹配问题，将动态网络的社团发现问题转化为静态网络中的社团匹配问题，能够适用于多种类型的网络。但是此类方法在匹配前后网络切片的社团时，如果相邻切片网络社团发现的结果变化较大，则匹配起来误差大、难度高 ，并且在当前网络切片社团发现的过程中，没有考虑到历史网络的信息，每次都要重新对整个网络进行计算，计算过程存在大量的重复性，计算成本较高。

（二）基于历史的社团发现算法

基于历史的社团发现算法，包括针对网络切片序列数据的增量社团挖掘（Incremental Community Detection）、同步社团挖掘（Simultaneous Community Detection）和基于时态网络作为输入数据的动态社团发现算法。

增量社团挖掘算法在一定程度上兼顾了以往时刻网络切片的信息，适合处理网络结构相对比较稳定的动态网络。该类算法认为，在社团结构的动态演化中，一定时间间隔内出现剧烈改变的可能性很小，因此当前时刻的网络社团结构，一定程度上是依赖于前一时刻甚至前几个时刻中的社团结构。例如，何嘉林和陈端兵 将当前时刻网络切片中和上一时刻切片中连边情况相同的节点，按照一定的规则，压缩为一个新节点并替换原有节点，然后对改造后的网络切片采用Blondel算法划分社团，最后再将压缩节点还原。尚家兴等人 借助机器学习的方法，增加了分类器来判断网络中新增节点或连边有变化的节点及其邻居节点是否需要重新划分社团，从而只通过对局部的修改便能得到当前网络切片的社团发现结果，降低了算法的时间复杂度。赵中英等人 首先检测网络初始状态下的社团结构，然后在后续时刻查找网络的增量，根据新增节点的类型（例如新增节点构成了完全独立的联通集团，或是新增节点被包含在以往某个社团内等），决定社团结果的更新策略，同时该算法还引入了边权的时间衰退效应，以调整历史信息对当前网络社团发现的影响程度。王志晓等人 提出了面向重叠社团发现的DOCET算法，同样是借助核心节点和拓扑结构，根据在时序网络切片中的增量变化更新节点社团发现结果。

同步社团发现算法是针对所有时刻的网络切片同时进行社团发现算法，其基本思想是通过耦合网络检测社团结构。例如通过在不同时刻网络切片中耦合相同节点之间的边，将所有的时间切片重新建构为一个新的网络，也就是将所有的时间切片之间通过加边的方式绑定为一个单独的网络，然后在此网络上进行经典的社团发现算法 。托马斯·艾诺（Thomas Aynaud）和让-卢·纪尧姆（Jean-Loup Guillaume） 通过新定义一个平均模块度来修改Louvain算法，以达到在网络切片中识别出长期存在的社团的目标。比瓦斯·米特拉（Bivas Mitra）等人 在引文网络数据中，按照作者文章发布时间和引用等关系，重新建构出一个合并网络，实现了对不同时刻网络关系的耦合，最后利用静态社团发现算法实现在合并网络中识别社团结构。虽然这类算法依旧需要先采用切片的方式切割数据，并且在建构不同切片网络的关联上计算成本高于前两类算法，但是其优点是在社团发现时所有时刻的切片被同时考虑，社团划分结果的一致性得到最大限度地保留。

基于时态网络的动态社团发现算法，不需要对网络进行切片，而是在每次网络中节点和边发生变化后，根据一定的规则，更新和调整节点的社团划分结果，保证了动态网络社团的连续性。李静永等人 通过考察时态网络中边的变化，在每一个时刻对变动边所连接的点重新评估社团，根据点的所有邻居所属于的社团情况判定该点的新社团，评估机制非常简单。朱利奥·罗塞蒂（Giulio Rossetti）等人 基于时态网络提出了Tiles算法，根据每个时刻网络中的变化，对网络使用标签传播（Label Propagation）的思想重新评估变化相关的节点及其邻居节点的社团关系。阮（Nam P. Nguyen）等人 针对时态网络中的重叠社团发现问题提出了AFOCS算法，该算法在初始时会识别网络中内部密度大于一定程度的小社团，并将高度重合的紧密社团合并，在此基础之上再根据时态网络的实时变化更新节点的社团划分结果。苏阿德·布德布扎（Souâad Boudebza）等人 基于派系过滤（Clique Percolation）和标签传播的方法提出了OLCPM算法，先发现网络中的核心社团，再通过标签传播标注外围节点，该算法在处理网络中的变化时，会根据是节点还是边的变化，按照不同的规则更新社团结果。该类算法虽然能保证社团发现的连贯性，但是时态网络要面临的网络变动量是巨大的，所以基于时态网络的社团发现算法很难在每一步更新时使用较为复杂的算法。除此之外，由于每一步的社团结果都是建立在前一步的结果之上，该类算法不能保证最终得到的社团发现结果是全局角度的最佳结果。

整体而言，基于历史的社团发现算法更适用于结构相对稳定的动态网络，能够较好地利用前一时刻甚至前几个时刻网络切片中的历史信息，保持社团的连贯性。该类算法虽然比独立的社团发现算法在社团划分这一步更复杂，但是该类算法将前一时刻的结果作为输入数据来识别当前时刻的社团，避免了不同时刻网络切片间的社团匹配的问题。与此同时，在大规模网络中，该类算法能够有效降低计算成本，更适合当前大数据环境下的在线社会网络的研究。

社团发现结果的稳定性和可靠性会影响后续对于动态社团演化事件的判定和预测。因此，在社团发现阶段，应该尽可能地保证结果的稳定性和可靠性。需要注意的是，在动态网络的社团发现算法中，如果使用切片数据，在将网络按照时间窗口的切分时，切片策略会直接影响到后期社团发现和演化的研究结果。时间窗口切分方式可以分为按照等时间长度切分，按照每个时间窗口具有等量的关系数进行切分，以及根据数据的具体背景按照任意长度进行切分。斯坦尼斯瓦夫·萨加诺夫斯基（Stanisław Saganowski）等人 指出网络切片可以分为互斥的（Disjoint）、重叠的（Overlapping）和累积的（Increasing），在切分网络过程中，应该注意：（1）对于变化较快较大的网络，建议采用重叠的时间窗口，通常采用30%的偏移量以保证能获取到足够的时间窗之间的连续事件（例如连边变化）；（2）窗口大小应该和实际数据的背景相结合；（3）如果研究的对象是持续存在的社团，建议采用累积的时间窗口，尽量保存网络的持续性和增长性的事件；（4）在处理相对稠密并且节点间的关系会反复出现的网络时，可以尝试使用互斥的时间窗口来降低计算量；（5）在设计时间窗口的类型和大小时，可以通过多次尝试以达到最佳的切分结果。

二、动态社团演化

社团的动态发展是网络科学尤其是社交网络分析的一个重要领域，关注的是特定群体如何随时间变化 。例如在知识网络中，社团的动态发展意味着知识领域的演化，可以代表甚至预示着知识领域的发展方向。如表2.1所示，格格利·帕拉（Gergely Palla）等人 将网络演化事件总结为生长（Growth）、萎缩（Contraction）、合并（Merging）、分裂（Splitting）、出生（Birth）和死亡（Death）。这一归纳被许多学者沿用 ，也有学者对此模型进行了进一步的补充。例如，雷米·卡扎贝特（Rémy Cazabet）和朱利奥·罗塞蒂（Giulio Rossetti） 提出了社团的复活（Resurgence）；艾蒂安·盖尔·塔赫纳（Etienne Gael Tajeuna）等人 都使用了社团的持续（Continue/Stable）这一概念；卡维·卡德霍达·穆罕默德·莫萨费里（Kaveh Kadkhoda Mohammadmosaferi）和哈桑·纳德里（Hassan Naderi）将社团演化过程进一步细化，新增了合并且增长（Merge and Grow）、部分合并（Partial Merge）、部分合并且增长（Partial Merge and Grow）、分裂且增长（Divide and Grow）和部分存活且生长（Partial Survive and Grow） 。

实际上，社团演化事件通常只是为了描述网络切片中社团的一些发展状态，并不适合用来描述精细时间粒度下的网络复杂动态 。在具体的判定过程中，阈值的设定会严重影响演化结果的判定，例如，很多算法通过计算相邻网络切片中各个社团间的相似性，来决定两个社团是否匹配。具体而言，假若 t 时刻的两个社团各自流失了小部分节点，这些节点在 t +1时刻组成了新社团，如果判定社团匹配的相似性阈值设置较高，则新社团会被判定为出生（Birth），反之该社团将被视为由前一时刻两个社团部分合并（Partial Merge）而来。

探究网络的社团结构及其演化过程，有助于认识和发现实际网络中事物的关联和发展规律。合作行为建立了个体之间的关联网络，个体与所在社团内外其他个体的合作行为，推动了社团和网络结构的动态演化 。阿提拉·瓦尔加（Attila Varga） 建立了1950—2018年Web of Science中SCI期刊引文网络，发现学科之间的距离越来越短，学科之间的交叉现象更加明显。查克雷什·辛格（chakresh singh）和希瓦库玛·约拉德（Shivakumar Jolad） 通过建立印度物理学家1970—2013年间的合作网络，追踪合作社团的规模变动，探究了印度物理学家与外国物理学家在不同期刊上的合作关系，并找出了每个时期最有影响力的作者。马丁·阿兹米勒（Martin Atzmueller）等人 研究了面对面接触网络中群体形成和演化，描述了在一个会议过程中个体交流群组的演化，并发现群组规模的分布在茶歇，会议和空闲时间差异明显。齐金山等人 发现，社会网络中节点的出现和消失频繁程度会影响社团稳定性以及社团结构的演化。社团结构的演化作为动态网络中的重要特性，对于网络的生存发展和网络中信息的传播等都具有重要的研究价值。但是目前关于动态社团的研究中，更多集中于如何提出更有效的动态社团发现算法，对社团演化问题关注还不足够。实际上，无论是引文网络，还是社交网络，随着数据可得性的提高，对网络性质和特征的探究还可以被进一步挖掘。

对当前时刻社团结构的分析和对下一时刻结构的预测，是社团演化研究的主要目标 。许多学者致力于提出可靠性和可行性更强的社团演化预测算法，例如纳吉汗·伊尔汗（Nagehan Ilhan） 提出一种特征子集提取算法，能够通过检测网络和社团的特征，匹配不同时间网络切片的社团，并寻找出能有效预测社团演化的最少特征。在动态网络社团演化预测的问题中，社团的生命周期是一个重要话题，例如S.卡蒂卡（S. Karthika）和吉萨（Geetha R） 提出了Communalyzer算法，能够检测网络的局部社团和全局社团，并且以维基百科的用户数据为例，使用该算法刻画了社交网络中社团的出生、合并、增长、缩减、分裂和死亡的生命周期。格格利·帕拉等人 利用派系过滤算法（Cluster Percolation Method，CPM）划分了科学家合作网络和通话网络，探究了社团的稳定性与社团生存能力的关联，该研究发现规模大的社团如果社团内的变动较大则能维持更长的生命周期，而规模小的社团则需要更高的稳定性才能维持更长的生命周期。马克·戈德堡（Mark Goldberg）等人 发现，在社团演化过程中，社团的早期状态对社团的生命周期影响显著，早期密集、小型、稳定的社团可以生存更久。当前社交网络、线上问答平台，电商网络等平台用户关系数据的可得性不断增强，其网络的社团结构也更加清晰，对动态网络社团演化的预测，无论是关注社团的演化方向还是生命周期，在当前的信息环境下，都具有极高的应用价值。

综上所述，本章探讨了传统在线知识传播在理论和方法层面取得的成果及存在的问题，进而探讨了计算传播学视角下的在线知识传播研究路径的可能性和必要性。最后，本章重点介绍并评述了计算传播学视角下的在线知识传播研究两种重要研究方法——网络文本分析方法和动态网络分析方法。在后续章节中，本书将利用上述研究方法，分别探究在线知识传播的疆域、结构与机制。 aMClSf60aVYyiXP/11g/QA/ysBAiDlvusHE7B6TiyEoPlBybRNB/xeSAXBhEW3l8