Open Access

ARTICLE

Index-adaptive Triangle-Based Graph Local Clustering

by Zhe Yuan^*, Zhewei Wei, Ji-rong Wen

Renmin University of China, Beijing, 100872, China

* Corresponding Author: Zhe Yuan. Email:

Computers, Materials & Continua 2023, 75(3), 5009-5026. https://doi.org/10.32604/cmc.2023.038531

Received 16 December 2022; Accepted 23 February 2023; Issue published 29 April 2023

Abstract

Motif-based graph local clustering (MGLC) algorithms are generally 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 framework 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.r.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 knowledge, 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.

---

Keywords

---