近日，我院张颖教授与悉尼科技大学、新南威尔士大学、香港中文大学、上海交通大学团队合作在我校A+++期刊《VLDB JOURNAL》上发表了题为“Querying historical K-cores in large temporal graphs”的学术论文。浙江工商大学统计与数学学院是本论文通讯作者单位。
通讯作者：张颖
通讯作者单位：浙江工商大学统计与数学学院
论文链接：https://doi.org/10.1007/s00778-025-00903-1
论文内容介绍
k-core作为一种衡量图中紧密连接子结构的基本模型，广泛应用于社交网络分析、社区发现和系统结构分析等领域。然而，在时序图中，随着时间窗口的变化，图的快照结构也发生着改变，传统方法难以高效地完成“在某个历史时间段内，哪些节点属于k-core”的结果查询。本论文首次系统性地研究了在大型时序图中高效查询历史k-core的问题，并提出了一种新颖的索引结构PHC-Index。该结构设计的核心思想是记录每个节点在每个可能的k值下能够成为k-core成员的“核心时间”。通过利用核心数随窗口变化的单调性，PHC-Index仅存储核心时间发生变化的关键时间窗口，从而大幅压缩索引空间。在索引构建方面，论文提出了两种算法：基础算法PHC-Construct和优化算法PHC-Construct*。后者通过局部计算核心时间，避免了全局遍历，将构建时间降至与索引大小成线性关系，显著提升了可扩展性。此外，论文还研究了动态场景下的索引维护问题，提出了PHC-Update和PHC-Update*两种算法，支持在新增边和边过期的情况下高效更新索引。本研究在多个真实时态图数据集上进行了广泛实验，结果显示：PHC-Query 比在线查询方法快一到两个数量级；PHC-Construct* 比基础构建方法快数个数量级，并能处理十亿级别的边；PHC-Index 还能有效加速span-core等其他时序核模型的查询。论文通过DBLP合作网络的案例研究，展示了历史k-core查询在分析研究社区演化中的实际价值，为时序图分析提供了重要工具和思路。
