Optimal Triangle Detection Preventing Duplicates in Large-Scale Graphs

Abstract

During the past decades, the world shifted towards online transactions. From data exchange, service provision to business, users and providers rely on the internet and social networks as a common platform for sharing and trading. In order to ensure an effective and reliable management of these networks and the flow of information within them, it is essential to detect user profiles and communities. In that context, triangle detection is a fundamental task in network analysis, as triangles are the smallest structure in a community. However, identifying triangles in large-scale and dense networks is a heavy and highly time-consuming treatment, due to costly neighborhood intersection computations. Our research aims to optimize intersection computation by minimizing the number of comparisons performed, avoid triangle duplication throughout the detection process and thus reducing the overall computation time. The method we propose, Test With Jumps for triangle detection without duplicates (TWJtr-D), is a refined version of Test With Jumps for triangle detection (TWJtr) algorithm. It optimizes intersection computing between neighbors sorted lists while avoiding redundant comparisons and duplicated triangles. Experimental results, on real-world datasets, demonstrate that TWJtr-D significantly reduces computation time and outperforms state-of-the-art methods which process in a similar pattern. This highlights the efficiency of TWJtr-D for triangle detection in large-scale networks. Future work will upgrade this method to parallel processing to rank its efficiency among algorithms in the same field.