Open Access iconOpen Access

ARTICLE

crossmark

Index-adaptive Triangle-Based Graph Local Clustering

Zhe Yuan*, Zhewei Wei, Ji-rong Wen

Renmin University of China, Beijing, 100872, China

* Corresponding Author: Zhe Yuan. Email: email

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

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


Cite This Article

Y. Zhe, W. Zhewei and W. Ji-rong, "Index-adaptive triangle-based graph local clustering," Computers, Materials & Continua, vol. 75, no.3, pp. 5009–5026, 2023.



cc This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 460

    View

  • 321

    Download

  • 2

    Like

Share Link