Networks

A modeling and computational study of the frustration index in signed networks

Journal Article

Abstract Computing the frustration index of a signed graph is a key step toward solving problems in many fields including social networks, political science, physics, chemistry, and biology. The frustration index determines the distance of a network from a state of total structural balance. Although the definition of the frustration index goes back to the 1950s, its exact algorithmic computation, which is closely related to classic NP‐hard graph problems, has only become a focus in recent years. We develop three new binary linear programming models to compute the frustration index exactly and efficiently as the solution to a global optimization problem. Solving the models with prioritized branching and valid inequalities in Gurobi, we can compute the frustration index of real signed networks with over 15 000 edges in less than a minute on inexpensive hardware. We provide extensive performance analysis for both random and real signed networks and show that our models outperform all existing approaches by large factors. Based on resolution time, algorithm output, and effective branching factor we highlight the superiority of our models to both exact and heuristic methods in the literature.

Related Topics

Related Publications

Related Content

Site Footer

Address:

This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on StatisticsViews.com are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and StatisticsViews.com express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.