Network Bipartitioning In The Anti-Communicability Euclidean Space

Abstract

We define the anti-communicability function for the nodes of a simple graph as the nondiagonal entries of exp (-A). We prove that it induces an embedding of the nodes into a Euclidean space. The anti-communicability angle is then defined as the angle spanned by the position vectors of the corresponding nodes in the anti-communicability Euclidean space. We prove analytically that in a given k-partite graph, the anti-communicability angle is larger than 90{degrees} for every pair of nodes in different partitions and smaller than 90{degrees} for those in the same partition. This angle is then used as a similarity metric to detect the "best" k-partitions in networks where certain level of edge frustration exists. We apply this method to detect the "best" k-partitions in 15 real-world networks, finding partitions with a very low level of "edge frustration". Most of these partitions correspond to bipartitions but tri- and pentapartite structures of real-world networks are also reported.