Local clustering via approximate heat kernel PageRank with subgraph sampling.

Area of Science:

• Network Science
• Computer Science
• Data Mining

Background:

• Graph clustering is crucial for understanding complex systems but computationally intensive for large graphs.
• Existing methods for heat kernel PageRank (HKPR) approximation often rely on global graph structures, increasing computational cost.
• Efficiently finding local clusters in massive networks remains a significant challenge.

Purpose of the Study:

• To develop an efficient algorithm for approximating the heat kernel PageRank (HKPR) on local subgraphs.
• To reduce the computational burden of graph clustering in large-scale networks.
• To provide a probabilistic guarantee on the approximation error of the HKPR.

Main Methods:

• Developed a novel algorithm for approximating HKPR specifically on local subgraphs.
• Analyzed the computational complexity, demonstrating sublinear dependence on the cluster size.
• Established probabilistic bounds for the approximation errors.

Main Results:

• The proposed algorithm approximates HKPR on local subgraphs efficiently.
• Computational requirements are sublinear with respect to the expected size of the local cluster.
• The approximation error is bounded probabilistically, ensuring reliability.
• Numerical experiments confirm state-of-the-art performance for local clustering.

Conclusions:

• The novel algorithm offers an efficient and accurate method for HKPR approximation in local subgraphs.
• This approach significantly alleviates computational challenges in large-scale graph clustering.
• The method achieves competitive performance, advancing the field of network analysis.