摘要
本文提出了一个新的模型(α, β, T)-core,用于在时间双向图上寻找凝聚子图。时间双向图中,不同实体之间的关系随着时间的推移而变化。为了提高查询效率,本文提出了顶点分区和时间分区的历史索引(VH-Index和TH-Index),并进一步提出了时间交集索引(TH*-Index)。实验结果表明,本文提出的模型和算法在多个真实数据集上表现出色。
什么是时间双向图
时间双向图(Temporal Bipartite Graph)是指在图中存在两类不同的顶点集合,并且这些顶点之间的关系(边)随着时间的推移而变化。每条边都有一个时间戳,表示该边在特定时间发生。时间双向图可以用于建模许多现实世界的应用场景,如用户-商品购买关系、作者-论文发表关系等。
时间双向图的构成
-
顶点集合:
- 上层顶点集(U):表示一种类型的实体。例如,在用户-商品购买网络中,上层顶点可以表示用户。
- 下层顶点集(L):表示另一种类型的实体。例如,在用户-商品购买网络中,下层顶点可以表示商品。
-
边集合(E):
- 边连接上层顶点和下层顶点,表示两种实体之间的关系。例如,用户购买商品。在时间双向图中,边带有时间戳,表示这种关系发生的时间。
举例说明
我们以一个简化的用户-商品购买网络为例,其中:
- 顶点集U表示用户
- 顶点集L表示商品
- 边表示用户在某一时间购买某一商品
- 每条边都有一个时间戳,表示购买时间
假设有以下用户和商品:
- 用户U: {Alice, Bob, Carol}
- 商品L: {Book, Pen, Notebook}
时间双向图的边集可以如下表示:
-
(Alice, Book, 2024-01-01): 表示Alice在2024年1月1日购买了Book
-
(Bob, Pen, 2024-01-03): 表示Bob在2024年1月3日购买了Pen
-
(Alice, Notebook, 2024-01-05): 表示Alice在2024年1月5日购买了Notebook
-
(Carol, Book, 2024-01-06): 表示Carol在2024年1月6日购买了Book
-
(Bob, Notebook, 2024-01-07): 表示Bob在2024年1月7日购买了Notebook
研究背景
在许多现实世界的应用中,例如作者-论文网络、用户-物品网络等,不同实体之间的关系可以自然地表示为双向图。双向图由两类顶点和连接它们的边组成,这些边只在不同类别的顶点之间存在。在时间双向图中,边不仅连接不同类别的顶点,还带有时间戳,表示这种关系在某一特定时间发生或存在。随着时间的推移,这些关系会发生变化,形成时间双向图。传统的凝聚子图(密集子图)模型没有考虑时间维度,因此无法捕捉关系的动态变化。为了弥补这一不足,本文提出了时间双向图上的(α, β, T)-core模型。
研究问题
本文研究的问题是在时间双向图上找到满足给定度约束的最大子图。具体来说,给定时间窗口T=[ts, te],以及度约束α和β,目标是找到一个子图,使得在该时间窗口内,上层和下层顶点的度分别至少为α和β。
主要贡献
- 提出新的凝聚子图模型(α, β, T)-core:该模型结合了时间维度,能够捕捉关系的动态变化。
- 设计了高效的索引结构:包括顶点分区历史索引(VH-Index)、时间分区历史索引(TH-Index)和时间交集索引(TH*-Index),以提高查询效率。
- 开发了高效的构建和查询算法:提出了顺序和并行算法,用于高效构建时间交集索引。
- 实验验证:在10个真实数据集上进行了大量实验,验证了模型和算法的有效性和效率。
预备知识
本文使用了一些基本的数学符号和定义:
- 时间双向图G(V, E):V表示顶点集,E表示带有时间戳的边集。
- U(G)和L(G):分别表示上层和下层顶点集。
- 快照G[ts, te]:表示在时间窗口[ts, te]内的子图。
- 度和邻居:顶点u在图G中的度表示为deg(u, G),邻居集表示为N(u)。
索引的基本思想
-
顶点分区历史索引(VH-Index):
- 基本思想:存储每个顶点在不同时间窗口内的状态,以便快速检索满足(α, β, T)-core条件的顶点。
- 实现方式:对于每个顶点u,VH-Index存储所有可能的(α, β, T)-core组合的时间窗口。
-
时间分区历史索引(TH-Index):
- 基本思想:通过按时间存储顶点,减少查询过程中需要访问的顶点数量。
- 实现方式:TH-Index按时间分区存储顶点,将每个时间窗口内的(α, β, T)-core顶点集合存储在一起。
-
时间交集索引(TH-Index)*:
- 基本思想:结合VH-Index和TH-Index的优点,既减少存储空间,又提高查询效率。
- 实现方式:通过存储代表性的时间点,减少冗余信息的存储,并在查询时进行交集计算。
索引的构建
-
顶点分区历史索引(VH-Index):
- 步骤:
- 对于每个顶点u和每个可能的α、β组合,计算u在不同时间窗口内的状态。
- 存储每个顶点在不同时间窗口内的状态,以便快速查询。
- 构建算法:
- 通过对图进行多次遍历,依次计算每个顶点在各个时间窗口内的(α, β, T)-core状态,并将这些状态存储在VH-Index中。
- 步骤:
-
时间分区历史索引(TH-Index):
-
步骤:
- 按时间窗口对图进行分割,计算每个时间窗口内的(α, β, T)-core顶点集合。
- 存储这些顶点集合,以便快速查询。
-
构建算法:
-
对于每个时间窗口,计算(α, β, T)-core,并将结果存储在相应的时间分区中。
-
-
-
时间交集索引(TH-Index)*:
- 步骤:
- 选取代表性的时间点,计算这些时间点内的(α, β, T)-core。
- 存储这些代表性时间点的结果,减少冗余信息。
- 在查询时,通过这些代表性时间点进行交集计算,快速得到查询结果。
- 构建算法:
- 通过逐步增加时间窗口的大小,计算并存储代表性时间点的(α, β, T)-core,并将结果存储在TH*-Index中。
- 步骤:
查询
-
基于顶点分区历史索引(VH-Index)的查询:
-
步骤:
- 根据查询参数α、β和时间窗口T=[ts, te],在VH-Index中查找每个顶点u的状态。
- 通过二分搜索找到满足条件的时间窗口,收集符合条件的顶点。
-
算法
def query_vh_index(VH_Index, alpha, beta, ts, te):result = set()for vertex in VH_Index:time_windows = VH_Index[vertex][alpha][beta]for window in time_windows:if window.start >= ts and window.end <= te:result.add(vertex)return result
-
-
基于时间分区历史索引(TH-Index)的查询:
- 步骤:
- 根据查询参数α、β和时间窗口T=[ts, te],在TH-Index中查找相应时间窗口内的顶点集合。
- 通过二分搜索找到符合条件的顶点集合,返回结果。
- 算法:
def query_th_index(TH_Index, alpha, beta, ts, te):result = set()for t in range(ts, te + 1):if TH_Index[alpha][beta][t]:result.update(TH_Index[alpha][beta][t])return result
-
步骤:
- 根据查询参数α、β和时间窗口T=[ts, te],分别在TH*-Index的前向索引和后向索引中查找符合条件的顶点集合。
- 计算前向索引和后向索引的交集,得到最终结果。
-
算法:
def query_th_star_index(TH_Star_Index, alpha, beta, ts, te):forward_result = set()backward_result = set()# 查询前向索引for t in range(ts, TH_Star_Index.max_time):if TH_Star_Index.forward[alpha][beta][t]:forward_result.update(TH_Star_Index.forward[alpha][beta][t])# 查询后向索引for t in range(te, -1, -1):if TH_Star_Index.backward[alpha][beta][t]:backward_result.update(TH_Star_Index.backward[alpha][beta][t])# 计算交集return forward_result.intersection(backward_result)
实验结果
-
实验设置:实验在10个真实数据集上进行,评估模型和算法的性能。
-
结果分析:结果表明,提出的模型和算法在不同数据集上的表现优异,查询效率和索引构建时间均有显著提升。
图7展示了不同数据集上构建TH*-Index的内存使用情况和时间成本。黑色柱状图表示原始图的大小,白色柱状图表示TH*-Index的大小,折线图(带三角形标记)表示构建TH*-Index所需的时间。可以观察到,大多数情况下,TH*-Index的大小显著大于原始图的大小,这表明索引构建会增加内存开销。同时,构建TH*-Index的时间随数据集大小的增加而显著增加,尤其是在较大的数据集(如RU)上,构建时间超过了10^5秒。尽管构建TH*-Index需要较大的内存和时间成本,但它显著提高了查询效率,特别是在需要频繁查询的大规模时间双向图上。因此,对于这些场景,构建TH*-Index是值得的,而在较小数据集或查询频率较低的场景下,则需要权衡索引构建的必要性。
结论
本文提出了第一个适用于时间双向图的凝聚子图模型(α, β, T)-core,并设计了高效的索引结构和算法。通过大量实验验证,本文提出的方法在实际应用中具有很高的效率和实用性。未来的研究方向可以包括进一步优化索引结构和算法,以处理更大规模的时间双向图。此外,可以探索该模型在更多实际应用中的潜力,例如社交网络中的社区检测、电子商务中的推荐系统、以及生物网络中的功能模块识别等。这些应用可以利用本文提出的模型和算法,来有效地分析和挖掘数据中的动态关系,从而提供更有价值的见解和服务。
论文地址:https://www.researchgate.net/publication/382506975_Querying_Historical_Cohesive_Subgraphs_Over_Temporal_Bipartite_Graphs