Abstract:
Computing the frustration index of a signed graph is a key to solving problems in different fields of research including social networks, physics, material science, and biology. In social networks the frustration index determines network distance from a state of structural balance. Although the definition of frustration index goes back to 1960, an exact algorithmic computation method has not yet been proposed. The main reason seems to be the complexity of computing the frustration index which is closely related to well-known NP-hard problems such as MAXCUT. New quadratic and linear binary programming models are developed to compute the frustration index exactly. Using the Gurobi solver, we evaluate the frustration index on real-world and synthetic datasets. The synthetic data involves Erdős-Rényi networks, Barabási-Albert networks, and specially structured random graphs. We also use well-known datasets from the sociology literature, such as signed networks inferred from students' choice and rejection as well as datasets from the biology literature including gene regulatory networks. We also provide some results on the frustration index of a political network of countries over time. The results show that exact values of the frustration index can be efficiently computed using our suggested optimisation models. We find that most real-world social networks and some biological networks exhibit a relatively low level of frustration which indicates that they are close to balanced.
