Extending TWJ for Triangles Detection in Large Graphs

In light of social networks' expansion and the ever-increasing number of subscribers who daily sign up to them. Detecting and counting triangles of subscribers in these networks are the basis of community detection. This detection is expressed as the computation of intersections between neighbors' subscribers lists. However, it remains very cumbersome and time-consuming to perform intersection operations. The significant detection cost is due to the fact that, until now, the treatment of intersections has been approached naively. Indeed, each element in the sorted neighborhood list of two neighboring vertices (listel and list2) in the network is compared one by one until one of the lists is exhausted. Given large-scale context, this results in a very high complexity of |liste1| + |liste2|. In this paper, we introduce a new technique for triangle detection. This approach aims to optimize intersection computing through minimizing the number of comparisons skipping the neighbors of one list that have no chance appearing in the second one, and thus making the triangle detection in large-scale networks more efficient.