动态信息网关键技术的研究进展

2022-11-05王芯蕊

智能计算机与应用 2022年10期

王芯蕊，高宏

（哈尔滨工业大学计算机科学与技术学院，哈尔滨 150001）

0 引言

随着信息技术和互联网的发展，诸如社交网络、生物医疗等各个领域产生了大量的数据。作为一种常见的数据组织形式，信息网在真实世界中广泛存在。信息网由众多的对象以及这些对象间的联系组成。例如，在微博等社交信息网中，用户是对象，用户之间的朋友关系是对象间的联系。在豆瓣等影评信息网中，用户、影片都是对象，一个用户评价了一部影片，就产生了用户与影片之间的联系。在中国知网等文献信息网中，作者、会议、论文都是对象，一个作者发表了一篇论文、一篇论文被一个会议收录，都是对象之间产生的联系。对信息网的分析研究具有重要的实际意义和广阔的应用前景，例如在社交信息网中，通过对具有共同兴趣爱好的用户进行聚类，可以为用户推荐新的朋友。又如在文献信息网中，通过对作者发表的论文、论文所属的会议等信息进行分析，可以评估出作者的学术影响力。

在真实世界中，信息网上的对象和联系常常随着时间的推移不断发生变化。如在社交信息网中，可能有新的用户开始加入使用社交应用，也可能有用户选择注销账户，用户之间的朋友关系更是不断发展变化。又如在文献信息网中，每年有众多会议、期刊收录大量论文，论文工作背后的科研团队也在不断发展、更迭。这里将对象和联系随时间变化的信息网称为动态信息网。

随着大数据时代的到来，动态信息网上的对象和联系不仅规模越来越大，其随时间更新变化的频率也越来越高。以社交信息网为例，由字节跳动公布的数据分析报告显示，截止2020年8月，抖音日活跃用户数突破6亿，相比于2020年1月时4亿的日活跃用户数，7个月内涨幅高达50%，平均每秒新增约11个日活跃用户。图1展示了2019年TikTok每月的视频下载量，每次下载可以认为是TikTok用户之间的一次互动联系，由图1可以看出随着时间的推移，TikTok用户之间的互动总是非常地频繁，并且互动数量不断变化。

图1 2019年TikTok每月视频下载量Fig.1 TikTok video downloads by month in 2019

由于动态信息网在各种现实应用中普遍存在，近年来，动态信息网受到了越来越多的关注。目前对于动态信息网关键技术的研究主要集中在社区探测和社区搜索、离群点探测、影响力最大化、链接预测。本文详细介绍了这些关键技术的概念、发展及其在动态信息网上的研究进展，然后讨论了动态信息网关键技术研究仍然面临的挑战，以及未来可能的研究方向。

1 动态信息网关键技术研究现状

1.1 社区探测和社区搜索

社区探测的目的在于识别网络中所有的社区。

在信息网中，传统的社区定义是一些相互之间紧密联系的对象组成的集合。根据这个定义，文献［2］采用基于图划分的方法，自顶向下将图划分成多个簇，使得簇内的顶点间边数尽可能大，而簇与簇之间的顶点间边数尽可能小，最终满足划分要求所得到的每个簇对应了一个社区。文献［3］提出了被广泛用于图聚类和社区探测的SCAN算法，该算法自底向上地将拥有足够多的共同邻居的顶点聚类到同一个簇，每个簇对应一个社区，SCAN算法还可以识别出连接多个簇的中心点（hub）以及离群点。值得注意的是，在真实的信息网中，常常存在一个对象属于多个社区的情形，这就产生了一系列发现重叠社区的算法。上述所有社区探测的研究工作都只考虑了静态信息网。

近年来，动态信息网上的社区探测问题也受到了广泛的关注。文献［5］提出了基于博弈论的方法在动态社交网上进行社区探测。文献［6］利用被改进的标签传播算法在动态社交网上探测有重叠的社区。一般地，动态社区探测的主要难点在于，不仅需要保证每个当前时刻网络聚类结果的质量，而且需要考虑社区随时间的推移所发生的动态变化（如扩大、缩小、消亡等）。

社区探测从整个网络的宏观角度，对静态或者动态网络中所有的顶点进行划分或者聚类等操作，找到网络中所有的社区。但是，从整个网络探测的所有社区的数目可能非常庞大，而且这些社区从更细致的角度看可能各不相同，具有各种不同的特点。为此，研究者们又提出了社区搜索问题，旨在找到网络中一些符合给定查询条件的社区，这样一来，就可以从更细致的角度提供以用户为中心的、个性化的社区搜索服务。

随着社区搜索问题的产生，由传统的社区定义扩展出了一系列新的社区模型，如基于核（该子图内的每个顶点至少有个邻居）的社区、基于（该子图中的每条边至少被包含在这个子图的（2）个三角形中）的社区、基于准团的社区、基于加权最稠密子图的社区、以及具有影响力的社区等。

此外，因为核模型中每个顶点的核数可以用来度量用户在社区中的参与度，所以基于核的社区模型在实际中应用广泛，并被进一步扩展定义许多新的社区模型。类似地，因为一个三角形反映了3个对象间稳定的联系，所以的值越大，说明该子图内的成员间的关系越稳定，于是，可以反映社区内部成员间联系的稳定程度的社区模型也得到了广泛使用和扩展。

上述部分工作研究了动态网络上的社区搜索问题。这些工作主要考虑的是如何设计在线算法及时计算出动态网络上每个当前时刻的社区搜索结果。

1.2 离群点探测

离群点作为经典的数据挖掘问题，相关研究已经开展了几十年，其最基本的定义是由文献［12］提出的：离群点是这样一种观察点，即明显偏离于其他观察点的行为，以至于认为这些点与其他正常点是由不同机制产生的。

由于数据类型的不同，离群点探测的方法也各有不同。例如，一种常用的离群点探测方法是基于聚类的，这种方法将离群点归为聚类分析的附加产物，也就是说，在对所有数据点执行聚类操作后，那些不属于任何簇的点就是离群点。其他常用的方法还有基于统计学的方法、基于神经网络的方法等等。

针对不同类型的数据，离群点的定义可能会发生一些扩展和变化。例如，文献［13］研究了图流上的离群点探测，输入的图流是一个个图对象（称图流中所有图的顶点的集合为基本顶点域，而每个图对象的顶点集是基本顶点域的一个子集）。图中不寻常的关系是指在图的各区域（即密集、连通子结构，通过顶点划分获得）之间很少出现的起到桥接作用的边，离群点是包含了这些不寻常的桥接边的图对象。

近年来，一些研究工作开始关注信息网上社区离群点的探测。文献［14］进行社区探测后，把那些不属于任何社区的对象作为社区离群点。文献［15］在静态信息网上研究了如何探测那些与其所在社区内的其他成员具有明显不同的行为模式的社区离群点。

此外，因为信息网中的一个对象常常属于多个社区，文献［16］提出静态信息网上的社区分布离群点探测问题，给定信息网上的所有社区，并且已知每个对象属于哪些社区，先通过在各个对象的社区分布矩阵上进行联合非负矩阵分解以发现所有的频繁社区分布模式、即社区中大多数对象普遍具有的社区分布模式，然后计算每个对象的社区分布模式到与其最近的频繁社区分布模式的距离作为该对象的离群点得分，最后那些离群点得分最大的对象被作为社区分布离群点输出。类似地，文献［17-18］研究了在动态信息网的2张或多张快照上，动态社区分布模式与其所在社区内的大部分成员有所不同的社区分布离群点的探测问题。另外，文献［19］进一步将少量具有影响力、可能改变社区未来构成的重要社区分布离群点从所有的社区分布离群点中分离了出来。

1.3 影响力最大化

给定一个网络，以及一个参数，影响力最大化旨在找到一个由个顶点构成的种子集合，从而最大化整个网络的影响力传播，亦即最大化整个网络中被种子集合所影响的所有顶点的总数。

影响力最大化问题是NP-难的，文献［20］中将影响力最大化问题形式化为离散型最优化问题，并且通过分析目标函数的次模性，基于蒙特卡罗模拟方法，给出了一个具有（11）近似比的贪心算法求解影响力最大化问题。其中，是自然对数的底，≈2718。具体地，该方法进行轮贪心选择，每轮都寻找一个具有最大影响力的顶点加入种子集合。在每轮贪心选择中，使用多次蒙特卡罗模拟来估计每个顶点的影响力。

现有的关于静态信息网上影响力最大化问题的解决方法主要分为4类：基于模拟的方法、基于子图的方法、基于概要的方法和基于启发式的方法。文献［20］是采用基于模拟的方法的典型代表。但是由于蒙特卡罗模拟需要很多的时间，所以文献［20］中的贪心算法扩展性不好，对于大规模网络的适用性并不好。为此，文献［21］在保证达到文献［20］中贪心算法的结果质量的情况下，采用早期终止技术CELF减少了一些不必要的模拟，但是CELF的最坏时间复杂性仍然没有得到改善。基于子图的方法是使用蒙特卡罗模拟生成少量原始网络的子图，然后重复利用这些子图估计每个顶点的影响力。基于概要的方法则是通过蒙特卡罗模拟为选中的顶点建立概要，概要中包含了能达到的所有顶点的集合，称为的逆可达集，最后根据建立的概要解决影响力最大化问题。可见，基于子图和基于概要的方法也是以蒙特卡罗模拟为基础。为了避免进行蒙特卡罗模拟，研究者们提出了一系列基于启发式的方法。虽然基于启发式的方法具有更好的扩展性，但是结果质量却有所削减。实际上，目前众多求解影响力最大化问题的算法都无法同时兼顾可扩展性和结果质量。

近几年来，动态信息网上的影响力最大化问题的研究热度仍在攀升。文献［25］将动态信息网刻画成一系列静态信息网的快照，并连续地为每张快照求解种子集合。文献［26］设计了实时全动态的索引数据结构对动态信息网进行影响力分析，其方法适用于网络中对象和联系随时间增加或减少、以及传播概率频繁更新的情形。文献［27］采用图压缩技术，提出高效的算法找到一个种子集合，以最大化动态信息网上一个时间窗口内由该种子集合所影响的所有不同顶点的总数。

此外，与影响力最大化问题相对应的，一些工作研究了如何限制谣言在动态信息网上的传播。具体地，通过识别一些知道真相的用户，使得谣言传到该用户处就停止继续往下传播。文献［28］给定一些谣言发起者的集合，输出个知道真相的用户，使得整个网络中被谣言影响的用户总数最少。考虑到以前的工作认为谣言开始传播和某些用户知道真相是同时发生的，忽略了谣言的传播具有时间延迟性，也忽略了一些谣言的传播是有截止时间的，超过截止时间将不再传播，于是，文献［29］研究了在存在传播延迟的情况下，识别top个知道真相的用户，以最小化网络中在谣言传播截止时间前被谣言影响的用户总数的问题。

1.4 链接预测

链接预测是指预测未来可能出现的对象之间的新联系。链接预测可以用于朋友推荐、市场分析、商业智能等多个领域。因此，近年来，链接预测问题得到了各方面的关注和重视。

基于顶点相似性度量的方法常用于链接预测问题，具体地，预测2个顶点之间可能会产生一条边（或称一个链接），如果这2个顶点足够相似。另外，通过有监督的学习方法对信息网上的边进行分类以及采用其它一些机器学习的方法进行建模也可以处理链接预测问题。文献［30］基于图嵌入（Graph Embedding）方法，提出了知识图谱上的链接预测算法，用于填补知识图谱中未知的链接信息。文献［31］利用改进了的深度图卷积网络研究异构信息网上的链接预测问题。此外，因为图卷积网络只能用于简单图上的链接预测，文献［32］提出了神经超链接预测器NHP以及相应的2个变体NHP-U和NHP-D，用于超图上的链接预测。文献［33］考虑到在快速演化的图流上，因为边是随时间逐渐到达的，内存中无法一次性维护完整的图结构，因而提出了动态在线链接预测算法来解决图流上的链接预测问题。

目前，已经有很多工作研究了动态信息网上的链接预测问题。文献［34］通过整合时间信息、社区结构信息和顶点中心性度量，给出了一个全新的动态信息网上的链接预测模型。文献［35］提出了一个时序潜在空间模型用于动态信息网上的链接预测，该模型假设每个用户都位于一个未被观察到的潜在空间，并且在潜在空间表示中，相似用户之间更有可能发生交互，该模型允许每个用户随着网络结构的演化而逐渐移动其在潜在空间中的位置。

2 挑战与展望

目前关于动态信息网关键技术的研究仍然面临着很多挑战。首先，动态信息网上仍然存在着大量十分重要、实用的关键问题，但却被以往的研究工作所忽略，发现这些问题并给出合理的形式化定义是一个重要挑战。其次，真实世界中的动态信息网常常规模庞大、并且具有很高的数据演化速率，很多的关键问题都是复杂而难解的。因此，恰当地选取合适的数据结构来维护动态信息网上的数据，与此同时建立合理的模型有效地刻画动态信息网上对象和联系的不同动态行为特征是非常有必要的。此外，设计出适用于大规模、更新频繁的动态信息网的时空高效的关键技术，有效地解决这些问题也是很具有挑战性的。

关于未来可能的研究方向，第一，可以考虑利用压缩、采样、并行等方法设计出适用于真实世界中包含着数以亿计的对象和联系的大规模动态信息网的若干关键技术。第二，可以关注更加复杂但同样普遍存在的动态信息网（如动态异构信息网、动态超图信息网等）的关键技术研究。