近日，威廉希尔智能计算研究团队针对大规模图中的紧密子图挖掘问题取得重要突破，相关论文成果发表于计算机国际顶级期刊IEEE Transaction on Computers（CCF推荐A类期刊）、计算机数据库领域国际顶级期刊The VLDB Journal（CCF推荐A类期刊）和计算机数据库领域国际顶级会议IEEE International conference on Data Engineering (CCF推荐A类会议)。三项研究成果均以公司博士研究生罗琦为第一署名作者、以威廉希尔亚洲公司为第一署名单位、在威廉希尔成秀珍教授和于东晓教授共同指导下完成。

论文“Exploring Truss Maintenance in Fully Dynamic Graphs: A Mixed Structure-Based Approach”发表于计算机国际顶级期刊IEEE Transaction on Computers。挖掘紧密子图是图分析中的一个基本问题，良好的紧密子图不仅要保证内聚性还要考虑计算效率，紧密子图k-truss完美平衡了结构紧密性和计算效率。该研究聚焦于全动态图中k-truss的维护问题，创新性地提出了全动态情况下可批量处理的混合结构，避免了重新分解计算的低效性。实现了只需要小范围遍历图的局部更新算法，并且算法可以并行执行。该研究有效解决了全动态图下紧密子图k-truss维护的批处理问题。

图1 混合结构示例。混合结构由三角形边集不相交的点集和边集组成

论文“Towards Maintenance of Hypercores in Large-Scale Dynamic Hypergraphs”发表于数据库领域顶级期刊The VLDB Journal。超图中的一条超边不仅仅只包含两个顶点，超边包含任意的顶点数使得超图中hypercore的计算和维护需要大量成本。该研究聚焦于大规模动态超图中hypercore的计算问题，以研究高效的精确hypercore维护方法。该研究提出了顶点与超边的core值关联更新的创新方法，实现了hypercore局部遍历更新算法，显著减少了动态超图下hypercore的更新时间。并且该研究通过一个索引结构加速遍历超图使得算法效率进一步提升。该研究解决了动态超图中紧密子图hypercore维护的难题。

图2 超图和hypercore示例

论文“Finer-Grained Engagement in Hypergraphs”被数据库领域顶级会议IEEE International Conference on Data Engineering接收。超图分析面临稀疏性、复杂性和动态性等挑战，传统的紧密子图指标在超图中均无法有效衡量紧密子图的内聚性。该研究聚焦于超图中紧密子图计算问题，创新性地提出了基于超图顶点的engagement一种全新的紧密子图指标(k, h)-core，并提出线性时间内的分解算法。此外，通过提出(k, h)-core的局部属性，该研究实现了在动态超图中更新(k, h)-core的高效维护算法，避免了从头分解造成的大量冗余计算。该研究解决了超图中有效紧密子图模型的设计和计算的难题。

图3 超图中三种类型的cores

IEEE Transactions on Computers创办于1952年，由IEEE计算机协会出版，是计算机方向的顶级刊物，是中国计算机学会（CCF）推荐的A类国际学术期刊。IEEE Transaction on Computers涵盖了计算机设计、系统、架构、硬件等各个方面的研究课题。

The VLDB Journal是计算机数据库领域的国际顶级期刊，是中国计算机学会（CCF）推荐的A类国际学术期刊。该期刊涵盖了信息系统架构、信息技术以及新型数据库应用开发的研究课题。

IEEE International Conferenceon Data Engineering是计算机数据库领域的国际顶级会议，是中国计算机学会（CCF）推荐的A类国际学术会议。该会议聚焦于数据密集型系统和应用的设计、构建、管理和评估的研究课题。

（ 图文/罗琦   审核/于东晓   责任编辑/徐慧   供稿单位：威廉希尔）