Balanced and Unbalanced Triangle Count in Signed Networks

IEEE Transactions on Knowledge and Data Engineering, vol. 35, pp. 12491–12496

Abstract

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 fastIncrementalTriangleCounting (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$O(m k_{{\max}})$, where$m$represents the number of edges and$k_{{\max}}$represents the maximum degree of the given signed network.

Authors 3

1. Aikta Arya

   Indian Institute of Technology Roorkee

   Affiliation as printed

   Department of Computer Science and Engineering, Indian Institute of Technology, Roorkee, Uttarakhand, India

2. Pradumn Kumar Pandey

   Indian Institute of Technology Roorkee

   Affiliation as printed

   Department of Computer Science and Engineering, Indian Institute of Technology, Roorkee, Uttarakhand, India

3. Akrati Saxena Aachen Leiden Institute of Advanced Computer Science

   Leiden University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science, Leiden University, Leiden, CA, The Netherlands