Degree-Based triangle classification algorithm for graph data
Haixia Deng, Shihu Liu · 2025
Triangle classification is essential in graph analysis, such as for effectively detecting communities, evaluating clusters, and quantifying connection density. While traditional algorithms focus on counting, they often miss structural nuances critical for deeper insights. This paper introduces a degree-based triangle classification algorithm that combines efficient traversal with structural classification. The algorithm initiates traversal from the maximum degree node, recursively exploring neighbors to identify triangles through common connections. Found triangles are classified into four types based on the node degrees relative to the graph’s average degree, enabling fine-grained structural analysis. The traversal prioritizes unvisited maximum degree neighbors, switching to new maximum degree central nodes when local exploration concludes. Extensive experiments across twelve real-world and four synthetic datasets demonstrate the proposed algorithm’s superiority over four existing algorithms in both efficiency and structural interpretability.