A method to calculate structural holes by triangle counting

Structural hole theory reveals the influence of individual positional differences in social networks on their access to information and resources. At the same time, it is also significant for understanding information dissemination, knowledge sharing and innovation processes in social networks. Generally, some metrics, such as effective size, constraint and betweenness centrality, are used to approximately estimate the structural holes of vertices. In this paper, based on the definition of structural hole, we propose an accurate method to calculate the number of structural holes (NSH) by triangle counting. The method’s computational complexity depends only on the number of vertices, making it suitable for large-scale dense graphs. Furthermore, based on the proposed method, we design an edge-addition strategy to improve traffic efficiency. Simulation results show that our strategy is efficient.