Introducing fractionalization index in Balance theory

In a world which is every day more interconnected and permeated with social relationships (both physical and virtual) modelling such interactions has become an interesting point mostly to achieve a better comprehension of phenomena such as the raise of communities. From a mathematical perspective the general theory of unsigned networks - where nodes are linked one to each others by positive arcs representing the intensity of the links - seems not optimal to describe such situations and signed networks are commonly used in order to take into account also negative interactions (enmity). Referring to Cartwright and Harary's generalization of Heider's theory, the two theories of structural balance and weak balance have been developed in order to investigate the cause of conflicts in networks of individuals whose mutual relationships are characterizable in terms of friendship and hostility. In this regard the structural balance theory postulates that origin of such tensions is related to the presence of negative cycles, meaning that a network is exactly balanced if it has no negative cycles while it is increasingly unbalanced the more the negative cycles are present in the network. Relaxing the hypothesis allowing the network to have "weakly balanced cycles" (i.e. negative cycles with more than one negative link) the weak balance theory instead generalizes the previous one postulating that a network is balanced if it can be exactly partitioned into communities where every within-community link is positive and every between-communities link is negative, while it is increasingly unbalanced the more is the amount of unbalanced cycles. As it is hard to expect that real networks are exactly balanced particularly interesting is determining how far a network is from its balance; in this regard among the various methods introduced in literature one of interest is the frustration index (also known as line index of imbalance) which represents the minimum number of edges to reverse in order to achieve a balanced transformation of the network. Despite its simple derivation though, its computation turns out to be an NP hard problem (which not allows it to be calculated for large networks) and heuristics have been proposed to estimate it in a feasible time. For the case of weakly balanced fully connected networks and supposing the related partition of the network is known though, we prove that the frustration index is related to the fractionalization - a dispersion index well known in literature and vastly used in economy and ecology - by an exact formula. Being that the two indexes are well correlated in the vast majority of the cases two consequences follow: from one hand knowing the network partition we can interpret fractionalization as an easy to compute estimation of the frustration, secondly, we can use frustration to estimate the number of expected communities in community detection algorithms. Aim of this work is to prove these concepts in the cases of fully connected networks, Erdos Renyi networks and quasi weakly balanced networks. For all these cases the exact formula for the frustration index is obtained and demonstrated numerically using artificial networks, moreover for the fully connected case some examples of real networks belonging to economy, politics and etno-linguistic are brought in order to validate the formula. Lastly a novel approach for community detection is proposed and compared with the state of the art for unsigned and signed networks in the case of planted partition graphs.