RETRIEVING TOP WEIGHTED TRIANGLES IN GRAPHS

Abstract

Many network analysis tasks use pattern counting in graphs as a fundamental primitive, and there are several ways to scale sub-graph counting to large graphs. Although existing scalable methods for pattern mining are built for unweighted graphs, many real-world networks have a concept of the strength of connection between nodes, which is frequently described by a weighted graph. Here, using the generalised mean of the triangle's edge weights, Authors create deterministic and random sampling methods that make it quick to identify the 3-cliques (triangles) with the largest weight. For instance, one of our suggested algorithms may, in a reasonable amount of time on a commodity server, discover the top 1000 weighted triangles of a weighted graph with billions of edges, which is orders of magnitude faster than existing "fast" enumeration techniques.