Balanced and Unbalanced Triangle Count in Signed Networks

Triangle count is a frequently used network statistic, possessing high computational cost. Moreover, this task gets even more complex in the case of signed networks which consist of unbalanced and balanced triangles. In this work, we propose a fast I ncremental T riangle C ounting (ITC) algorithm for counting all types of triangles, including balanced and unbalanced. The proposed algorithm updates the count of different types of triangles for newly added nodes and edges only instead of recalculating the same triangle multiple times for the entire network repeatedly. Thus, the proposed ITC algorithm also works for dynamic networks. The experimental results show that the proposed method is practically efficient having run time complexity of <tex-math notation="LaTeX">O(m k_max)</tex-math> , where <tex-math notation="LaTeX">m</tex-math> represents the number of edges and <tex-math notation="LaTeX">k_max</tex-math> represents the maximum degree of the given signed network.