考虑主题和时间的在线社交网络团体发现算法

李金鹏，曹 宁，张 琪，张文鹏，纪淑娟

(山东科技大学 山东省智慧矿山信息技术重点实验室，山东 青岛 266590)

社区发现是数据挖掘的重点，对于理解用户间的合作和交流等方面有极大帮助。目前已有许多基于图结构的社区发现算法，例如基于聚类的方法[1]、基于密度的方法[2]、基于谱分析的方法[3]、模块度优化的方法[4]等。这些算法都是以静态网络为前提，即所研究的网络是将一段时间内出现的所有节点和边进行聚合而成的。这些方法可以有效挖掘结构上稠密的社区或群组，却忽视了时间维度，可能导致发现的社区与真实社交网络中的社区有所偏差、漏掉社区时序演化规律，从而降低动态复杂网络分析的准确度[5]。演化的社区发现算法及分析越来越受到业界和学界的关注，这是因为随着社交网络的整体规模不断扩张，同时存在节点和链接消失现象，及时发现网络结构的阶段性变化可以更好地体现网络用户的动态交互行为[6]。近几年，人们在静态网络的社区发现方法的基础上提出一些基于动态演化网络的社区发现方法，例如基于两步策略的方法[7-8]、增量聚类法[9-10]、进化聚类法[11-12]等。这些方法一般是按固定时间长度划分快照，对每个快照使用基于静态网络的社区发现方法进行检测，并考虑相邻快照间的变化不断更新社区。然而，将现实网络抽象为某一时间窗口的静态网络仅适用于增加少量节点或边缘的情况[6]。此外，社区的产生原因不同，不同社区生存的周期和活跃时段也不同。例如，有些社区是由于某件事件引起的广泛讨论，议题会随着事件的发生、发展、结束而形成、渐热、渐冷、结束。再如，有些社区是周期性产生的，例如两会的提案讨论、疫情进展等等。然而，现有动态社区划分方法大都忽略了同一快照内不同社区所处的状态可能不同，导致不能挖掘社区讨论议题的周期性特征、事件性社区被划分到多个时间片而被判定为多个社区等情况。

为解决现有研究中存在的上述问题，探讨了同时考虑主题和时间的社交网络中活跃团体的检测方法，考虑社区结构和时间维度，分别挖掘不同主题对应社区下的活跃团体，更合理地对网络中的实体进行划分，以解决目前动态社区发现算法忽视社区内群体演变的问题。由结果能够明显看出某一社区对应的主题是持续性或周期性存在的还是因某种热门事件而仅在短期内存在的，并基于原有的图密度度量方法提出了一个与时间相关的交互度量方法，在真实数据集上的实验结果表明本算法找到的团体是活跃的、在短时间间隔内发生了密集交互的群体。

1 相关工作

寻找稠密子图是图数据挖掘中的一个核心问题，根据挖掘过程中是否考虑了时间维度，将稠密子图挖掘/发现方法分为基于静态图结构和基于动态图结构的挖掘两大类。

在基于静态图结构的稠密子图研究方面，已提出许多不同的方法，例如聚类法[1]、密度子图的方法[2]及基于谱分析的方法[3]等。比较有代表性的工作包括：Newman[13]最早研究社交网络的社区结构，并提出“模块度”这一重要概念；Flake等[14]使用基于最大流/最小割的算法发现的社区内部节点链接比社区外的链接更多；Palla等[15]提出的CPM算法是第一个能发现重叠社区的算法。但这些基于静态图的方法都忽视了时间维度可能存在节点间的隐性关系。因此，一些研究者开始研究基于动态图结构(在静态图结构的基础上增加时间维度)的社区分析方法。

现有的考虑时间维度的图模型有时间图、动态图、演化图、时变图、交互图等[16]。在此基础上提出了划分团体和社区的方法如两步策略法[7-8]等，主要思想是在网络流的每个快照中检测社区，然后利用相似性度量分析相邻时间片中的社区演化，但没有利用前一个快照的社区信息来推断当前快照的隐藏社区。而基于进化聚类的方法[11-12]则通过引入时间平滑性，在每个时间步中产生局部聚类；或是利用增量聚类的检测算法通过将不断进化的网络转换为流数据来不断更新社区[9-10]。Zhao等[10]提出“完全独立”子图更新策略，将动态社区按照新生社区的诞生以及原有社区的扩张两种方法划分，针对不同的增量类型提出一种增量式算法检测动态进化社交网络中的社区，从而按时态挖掘社区演变过程。Jiao等[17]提出一种基于约束的通用聚类模型，以探索隐藏在时间网络或复杂网络中的社区结构。许宇光等[18]针对动态网络中的社区发现问题，考虑历史网络结构和历史社区结构信息影响的演化，提出一种基于个体稳定度的博弈论方法。Rozenshtein等[19]在交互网络的设置中，研究了动态稠密子图的发现问题，将寻找密集子图的方法与解决覆盖问题的方法进行融合，在交互网络中识别出活动异常频繁的部分，发现在时间上是紧凑的子图。

上述社区发现算法忽视了时间维度的重要性或社区的周期性等特征。为解决以上问题，本研究提出一种融合最大化模块度发现算法[4]及动态稠密子图发现算法[19]的方法。

2 交互网络及动态密集子图定义

在描述算法之前，首先给出交互网络及动态密集子图的定义以及相关符号。

定义1(交互网络)[19]交互网络G=(V,E)由包含n个节点的集合V和包含m条带有时间戳的节点对间的交互边集合E构成，记作V={vi,i∈[1,n]}，E={(u,v,t)}，其中u,v∈V且t∈R。

社交网络中实体间的交互是一个相互作用，本研究认为它是无方向的，一对节点之间可能在不同时间发生多次交互即有多条边，不同节点对之间可能同时发生着多个交互。

定义2(拓扑网络)[19]对于交互网络G=(V,E)，设边集π(E)为不同节点对间至少有一次交互的边集合，π(E)={(u,v)∈V×V|(u,v,t)在某个时刻t存在}。给定交互网络G=(V,E)，网络π(G)=(V,π(E))是一个标准的静态图，交互边没有时间戳，称π(G)为网络G的拓扑网络或G的底层网络。

定义3(诱导交互网络)[19]给定交互网络G=(V,E)和节点子集W⊆V，定义诱导交互网络G(W)=(W,E(W))，E(W)为属于节点子集W的节点间的交互作用E(W)={(u,v,t)∈E|u,v∈W}。

假设所有的交互都发生在持续时间Δ=tM-tm的时间间隔[tM,tm]内，其中包含有多个离散节点，则定义任意一个时间段T=[s,e]⊆[tM,tm]的时间跨度为span(T)=e-s。定义一个时间间隔集合TP为多个不重叠的时间间隔集合，TP=(T1,…,Tk)。TP的时间跨度为k个时间段T的跨度总和，即

定义4(拼接交互网络)[19]给定交互网络G=(V,E)和时间段T=[s,e]，定义拼接交互网络G(T)=(V,E(T))，其中E(T)为发生在时间间隔T内的交互作用，有

E(T)=E([s,e])={(u,v,t)∈E|s≤t≤e}。

基于定义3和定义5给出的诱导交互网络和扩展拼接交互网络，可以得出动态密集子图的两种选择方法[19]，即基于节点子集和基于时间间隔子集的选择。动态密集子图定义如下。

定义6(动态密集子图)[19]动态密集子图可以形式化地表示为G(W,E(TP))，其中W为定义3中节点子集，E(TP)为定义5中定义的TP时间段内的交互边。

动态密集子图的质量度量依赖于静态图中密度的定义。给定静态图H=(V,F)，边集F没有时间戳，则H的密度d(H)定义为：

表1 符号表

(1)

由于增加TP会覆盖更多的边，导致质量分数q(W,TP;G)随着TP跨度的增加而增加，需要对总的时间跨度和时间间隔的数量加以限制。问题转化为在一个交互网络G=(V,E)中求一组节点W⊆V和一组时间间隔TP，让质量分数q(W,TP;G)最大，且时间间隔数量不超过限制预算K，总时间跨度不超过预算B，即|TP|≤K,span(TP)≤B。

3 考虑主题和时间的在线社交网络团体发现算法

在第2节交互网络模型的基础上，本节提出考虑主题和时间因素的在线社交网络团体发现算法—多时间密集子图发现算法(multiple temporal dense subgraph discovery algorithm，MTDSDA)，具体步骤如算法1所示。

Algorithm1：考虑主题的和时间因素的在线社交网络团体发现算法(MTDSDA)

Input:交互网络G，合并阈值φ

Output: 多个子图Gi(Wj,E(TPj))

Process:

1:交互网络G生成拓扑图π(G)；

2:利用Louvain算法将π(G)划分为n个社区，同时得到每个社区的交互图；

3:For每一个社区i的交互图do:

4: 获得社区时间总跨度作为最大预算值B，总天数作为间隔数最大预算值K；

5:Forbin (1,B)do:

6:Forkin (1,K)do:

7:TP0←初始时间间隔，即能覆盖所有数据的时间间隔；

8:j←0;

9:While(收敛条件；j←j+1)do:

10: 用给定的TPj找出最活跃的节点集Wj+1；

11: 用Wj+1找出最活跃的m个时间段集合TPj+1，m的值小于等于预算k，且时间段长度之和小于预算b；

12: 如果时间段之间相隔小于等于阈值φ，则将其合并，返回x个活跃时期;

13:endWhile

14:if找到的节点集在时间和结构上形成多个有明显界限的社区组织then

15: 拆分社区i为x个群体，并加入到n个社区中，求得它们的最优解，总数为n-1+x，并结束当前社区;

16:endif

17:return最优Gi(Wj,E(TPj));

18：endFor

19:endFor

20:endFor

算法1的过程为：

1) 将带有时间戳的交互网络G转为拓扑网络π(G)(如图1)，使用Louvain算法[4]将拓扑网络划分为n个社区并得到每个社区的交互图，社区内的节点代表彼此联系密切的社交个体，属于相同的主题(譬如参与某一热门新闻的讨论)，但可能在不同的活跃时期内讨论。直观地说，活跃时期可以由同一主题下多个相邻的交互频繁的时间段组成，其间相隔的时间很短，而如果交互频繁的时间段没有其他邻近的时间段，也可以将其视作活跃时期，如图2所示，时间序列8～53和98～126为两个活跃时期。

图1 交互网络的处理

图2 活跃时期示例

2) 利用每个社区的交互图查找其中的紧密团体，也就是发现动态密集子图(步骤7～13)。其中，步骤10是在给定的一组时间间隔集合中找到最优的一组节点集，则问题转化为在静态图上寻找稠密子图的问题，本研究使用Charikar的线性时间算法[2]来求解这一问题。步骤11的目的是利用稠密子图中的节点集寻找最优时间间隔集合，找出节点集之间交互最密集的时间间隔集，可以视为双预算下的最大覆盖问题，即给定预算B、K，使质量分数q(W,TP;G)最大。使用标准贪婪算法求解该问题，选择每单位成本包含元素最多的集合，最大化公式为：

(2)

使用标准贪婪算法是为了求得最大质量分数q(W,TP;G)。While循环不能确保质量分数增加，但是如果达到收敛条件：步骤11得到的时间间隔集内的节点集包含步骤10得到的节点集，则可以终止循环，获得近似最优解[19]。步骤12是对原始的发现动态稠密子图迭代算法[19]的改进，将挖掘交互密集时间段改为挖掘活跃时期。现实社交网络中实体间的交互频率有高有低，挖掘活跃时期更符合实际情况，不同的活跃时期意味着该主题下的社区是由不同时期的群体组成的。当算法找到一组时间间隔集合后，需要判断这些时间间隔是否相隔很短，如果小于合并阈值φ则将其合并为一个活跃时期。

3) 生成挖掘社区中的动态密集子图。考虑到虽然一个社区中得到的紧密团体可能不止一个，虽然参与的主题相同，但可能不在同一个活跃时期参与，故将其分开(步骤14～16)。每个社区得到的团体在不同的B和K下得到的结果不同，算法最后仅返回d(H)最大的解。

4 实验与结果分析

4.1 实验数据

使用文献[19]中提供的两个真实数据集来验证本算法的有效性。Facebook数据集是Facebook New Orleans regional从2006年5—8月的数据。Students数据集是加利福尼亚大学在线社区从2004年6月27日—10月26日的学生活动日志数据。表2是实验数据的统计特征，其中,|V|为节点数，|π(E)|为拓扑网络的边数，|E|为交互次数，|TP|表示数据集的时间跨度，d(π(G))表示拓扑网络的密度。

表2 真实数据集的特征

4.2 实验设置和评价指标

通过实验将本算法的结果与动态稠密子图发现算法GA算法[19]在参数B分别取值1、7和K分别取值1、5、7时的结果进行对比。对于本算法得到的多个社区而言，每个社区的情况和存在的时间跨度不同，不能对所有社区施加相同的约束B和K。因此在实验中对每个社区施加的时间跨度约束B从1到7、时间间隔数约束K从1到10，每个社区仅返回d(H)最大的解。GA算法的参数B和K分别取1～7和1～10的整数值。

动态稠密子图发现算法找到的是一个最稠密的子图，而本算法则是找到了多个社区下的稠密子图。在传统的概念中一般用公式(1)作为衡量在社区中发现的子图是否稠密的标准，但是本算法在时间维度上将实体间在不同时间的交互考虑进来，基于公式(1)提出度量标准：

(3)

其中，|E|表示发现的交互图在不同时间的所有交互边数，d(G)体现了交互的频繁程度。

4.3 实验结果与分析

表3和表4分别是MTDSDA算法和GA算法[19]在Facebook和Students数据集上的结果对比。由于本算法求得的是多个团体，首先对每个团体用公式(3)得到计算结果d(g)，然后将所有子图合并后再利用公式(3)得到总图的d(G)，与GA算法进行比较。表3中团体编号1.1、1.2及1.3是对社区1的划分，表示同属于一个社区下的不同活跃时期。由于篇幅原因，GA算法仅给出参数B分别取值1、3、5、7和K分别取值1、3、5、7、10的结果。

表3 Facebook数据集上的实验比较

表4 Students数据集上的实验比较

由表3和表4可以观察到：在一定范围内，随着B和K增大，GA算法子图的d(H)和d(G)基本上呈变大的趋势，这是因为时间预算越大所覆盖的交互边越多。本算法同样符合这个规律，且仅需相对较小的B和K就能达到对应团体的d(H)最大值，而GA算法并没有划分社区和时期，将整个数据集中交互频繁的多个时段看作一个虚拟时段，因而需要很大的预算才能挖掘出所有交互活跃的实体。

相较于GA算法，虽然本算法得到的团体d(H)相对较小，但d(G)评价指标有明显的提高，符合本研究猜想。因为GA算法是为了求得交互网络中的动态稠密子图即寻找最活跃的群体，实质上在社交网络中只求解一个社区，即使考虑时间维度，重点仍是在静态图上求解所有节点中参与不同交互最多的群体，即交互是不重复的。本算法则考虑了社交网络的结构，不同的节点由于参与的主题不同，在当前主题下参与的次数肯定是多次的，即交互是多次的，符合现实实际。

图3和图4给出了本算法分别在Facebook和Students数据集上的发现结果。从图3～4可以看出，群体多以事件性话题或新闻等因素引发产生，而同主题对应的社区在不同时段可能存在多个团体。若某一主题下存在多个团体，则认为该主题是持续性的或周期性的，该主题下的社区成员在热度下降一段时期后又开始频繁交互。

图3 Facebook不同主题下的团体在时间上的分布

图4 Students不同主题下的团体在时间上的分布

5 总结

在社区发现工作中，现有的研究大多致力于探索具有密集连接节点的邻域结构，而忽视了时间维度这一重要因素。为了有效地利用社交网络的时间维度与结构信息，提出了一种考虑主题和时间的多时间密集子图发现算法，可在社交网络平台中发现不同社区下的团体。算法将社交网络建模为交互网络，然后使用图划分方法，将交互网络中的节点划分为多个不同的社区，最后使用考虑活跃时期的动态稠密子图算法从得到的社区中挖掘团体。为了验证本算法是符合现实逻辑的，提出了新的度量准则，并在Facebook和Students数据集上进行实验，实验结果显示本算法优于GA算法，验证了其有效性。

本研究工作对社交网络进行了分析，在这个过程中交互信息被考虑在内，以更准确地描述社区及网络中的动态现象。对社区的划分是基于实体更倾向于参与某个主题的交互这一实际情况，下一步将考虑实体被划分到参与过的多个主题下的社区，以此来完善动态密集结构的发现可能。