Index-adaptive Triangle-Based Graph Local Clustering

作     者：Yuan Zhe Wei Zhewei Wen Ji-rong 

作者机构：Renmin University of ChinaBeijing100872China 

出 版 物：《Computers, Materials & Continua》 (计算机、材料和连续体（英文）)

年 卷 期：2023年第75卷第6期

页      面：5009-5026页

核心收录：

学科分类：08[工学] 0714[理学-统计学（可授理学、经济学学位）] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by the Fundamental Research Funds for the Central Universities(No.2020JS005). 

主　　题：Graph local clustering triangle motif sampling method 

摘      要：Motif-based graph local clustering(MGLC)algorithms are gen-erally designed with the two-phase framework,which gets the motif weight for each edge beforehand and then conducts the local clustering algorithm on the weighted graph to output the result.Despite correctness,this frame-work brings limitations on both practical and theoretical aspects and is less applicable in real interactive situations.This research develops a purely local and index-adaptive method,Index-adaptive Triangle-based Graph Local Clustering(TGLC+),to solve the MGLC problem w.***.t.triangle.TGLC+combines the approximated Monte-Carlo method Triangle-based Random Walk(TRW)and deterministic Brute-Force method Triangle-based Forward Push(TFP)adaptively to estimate the Personalized PageRank(PPR)vector without calculating the exact triangle-weighted transition probability and then outputs the clustering result by conducting the standard sweep procedure.This paper presents the efficiency of TGLC+through theoretical analysis and demonstrates its effectiveness through extensive experiments.To our knowl-edge,TGLC+is the first to solve the MGLC problem without computing the motif weight beforehand,thus achieving better efficiency with comparable effectiveness.TGLC+is suitable for large-scale and interactive graph analysis tasks,including visualization,system optimization,and decision-making.