论文标题：Index-free triangle-based graph local clustering

期刊：Frontiers of Computer Science

作者：Zhe YUAN , Zhewei WEI , Fangrui LV , Ji-Rong WEN

发表时间：04 Dec 2023

DOI：10.1007/s11704-023-2768-7

近些年来，高阶图局部聚类任务在众多图挖掘任务中表现出良好的场景描述与问题解释能力，在理论研究与实际应用领域受到广泛关注。一般来说，目前主流的高阶图局部聚类算法大多以两阶段的范式作为基础进行设计。该范式首先通过对图上的每条边计算其所包含在的高阶子图实例的数量，在原图基础上构建以之为权重的带权图；其次通过在所构建的带权图上执行标准的图局部聚类算法以得到局部聚类结果。然而，该种方式因引额外引入了繁重的预计算代价，而失去了可扩展性优势，并且难以在大规模实际图上得到应用。

针对大规模高阶图上的图局部聚类问题，中国人民大学魏哲巍教授团队等撰写了研究论文：无需索引的三角形高阶图局部聚类算法。

文章信息

标 题：Index-free triangle-based graph local clustering

引用格式：Zhe YUAN, Zhewei WEI, Fangrui LV, Ji-Rong WEN. Index-free triangle-based graph local clustering. Front. Comput. Sci., 2024, 18(3): 183404

阅读原文：

文章概述

文章旨在提出能够适用于真实大规模图数据的高阶图局部聚类任务，构建了首个无需预先计算高阶图权重矩阵作为后续计算所依赖索引结构的高阶图局部聚类算法，提升了高阶图局部聚类算法的效果与效率，进而提升了其在真实应用场景下的实用性。

技术步骤

基于巧妙设计的具有完全局部性的高阶随机游走采样算子，从种子节点开始进行高效且正确的三角形随机游走并以蒙特卡洛的方式得到各节点相对于种子节点的临近度向量，最后通过标准的遍历优化过程得到局部聚类结果，同时通过一种新颖的可视化形式对算法表现进行展示与比较。

实验结果

大量实验结果表明，基于本文提出的具有完全局部性的高阶蒙特卡洛采样技术，三角形高阶图局部聚类聚类算法能够适用于超大规模图，在保证聚类结果有效性的同时大幅提升可扩展性。

相关内容推荐：

文章精要 | 华东师范大学朱惠彪教授团队：CaIT演算的证明系统 2024 18(2)：182401

文章精要 | 最小和最大度点删除问题在若干特殊图上的参数复杂性 2023 17(4)：174405

文章精要 | 一种面向无线传感器网络中Set k-Cover问题的混合阶局部搜索算法 2023 17(3)：173402

文章精要 | 东北师范大学付治国教授团队：局部全息变换：可解性与困难性 2023 17(2)：172401

CCF 推荐B类期刊； SCI、Ei等收录； 中国科技期刊卓越行动计划梯队类期刊。

IF 4.2

高等教育出版社 北京航空航天大学

共同主办

________________________________________

Frontiers of Computer Science

________________________________________

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；入选“中国科技期刊卓越行动计划项目”。

________________________________________

《前沿》系列英文学术期刊

由教育部主管、高等教育出版社主办的《前沿》（Frontiers）系列英文学术期刊，于2006年正式创刊，以网络版和印刷版向全球发行。系列期刊包括基础科学、生命科学、工程技术和人文社会科学四个主题，是我国覆盖学科最广泛的英文学术期刊群，其中12种被SCI收录，其他也被A&HCI、Ei、MEDLINE或相应学科国际权威检索系统收录，具有一定的国际学术影响力。系列期刊采用在线优先出版方式，保证文章以最快速度发表。

中国学术前沿期刊网

http://journal.hep.com.cn