首页|Index-free triangle-based graph local clustering
Index-free triangle-based graph local clustering
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NETL
NSTL
万方数据
Motif-based graph local clustering(MGLC)is a popular method for graph mining tasks due to its various applications.However,the traditional two-phase approach of precomputing motif weights before performing local clustering loses locality and is impractical for large graphs.While some attempts have been made to address the efficiency bottleneck,there is still no applicable algorithm for large scale graphs with billions of edges.In this paper,we propose a purely local and index-free method called Index-free Triangle-based Graph Local Clustering(TGLC*)to solve the MGLC problem w.r.t.a triangle.TGLC*directly estimates the Personalized PageRank(PPR)vector using random walks with the desired triangle-weighted distribution and proposes the clustering result using a standard sweep procedure.We demonstrate TGLC*'s scalability through theoretical analysis and its practical benefits through a novel visualization layout.TGLC*is the first algorithm to solve the MGLC problem without precomputing the motif weight.Extensive experiments on seven real-world large-scale datasets show that TGLC*is applicable and scalable for large graphs.
graph local clusteringtriangle motifindex-freesampling methodvisualization
Zhe YUAN、Zhewei WEI、Fangrui LV、Ji-Rong WEN
展开 >
The Country and Area Studies Academy,Beijing Foreign Studies University,Beijing 100089,China
Gaoling School of Artificial Intelligence,Renmin University of China,Beijing 100872,China
Fundamental Research Funds for the Central Universities
NETL
NSTL
万方数据
