Triangle Centrality

Abstract

Triangle centrality is introduced for finding important vertices in a graph based on the concentration of triangles surrounding each vertex. It has the distinct feature of allowing a vertex to be central if it is in many triangles or none at all. We show experimentally that triangle centrality is broadly applicable to many different types of networks. Our empirical results demonstrate that 30% of the time triangle centrality identified central vertices that differed with those found by five well-known centrality measures, which suggests novelty without being overly specialized. It is also asymptotically faster to compute on sparse graphs than all but the most trivial of these other measures. We introduce optimal algorithms that compute triangle centrality in $O(m\bar{\delta })$ time and $O(m+n)$ space, where $\bar{\delta }\le O(\sqrt{m})$ is the $\text{average degeneracy}$ introduced by Burkhardt, Faber, and Harris (2020). In practical applications, $\bar{\delta }$ is much smaller than $\sqrt{m}$ so triangle centrality can be computed in nearly linear time. On a Concurrent Read Exclusive Write (CREW) Parallel Random Access Machine (PRAM), we give a near work-optimal parallel algorithm that takes $O(\log n)$ time using $O(m\sqrt{m})$ CREW PRAM processors. In MapReduce, we show it takes four rounds using $O(m\sqrt{m})$ communication bits and is therefore optimal. We also derive a linear algebraic formulation of triangle centrality which can be computed in $O(m\bar{\delta })$ time on sparse graphs.

References in corpus (9)

• Community structure in social and biological networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• The structure of scientific collaboration networks
• Why social networks are different from other types of networks
• Counting Triangles in Massive Graphs with MapReduce
• Space-Round Tradeoffs for MapReduce Computations
• Optimal algebraic Breadth-First Search for sparse graphs
• Bounds and algorithms for graph trusses