Computing the Line Index of Balance Using Integer Programming Optimisation

Samin Aref (), Andrew J. Mason and Mark C. Wilson
Additional contact information
Samin Aref: University of Auckland
Andrew J. Mason: University of Auckland
Mark C. Wilson: University of Auckland

A chapter in Optimization Problems in Graph Theory, 2018, pp 65-84 from Springer

Abstract: Abstract An important measure of signed graphs is the line index of balance which has applications in many fields. However, this graph-theoretic measure was underused for decades because of the inherent complexity in its computation which is closely related to solving NP-hard graph optimisation problems like MAXCUT. We develop new quadratic and linear programming models to compute the line index of balance exactly. Using the Gurobi integer programming optimisation solver, we evaluate the line index of balance on real-world and synthetic datasets. The synthetic data involves Erdős-Rényi graphs, Barabási-Albert graphs, and specially structured random graphs. We also use well-known datasets from the sociology literature, such as signed graphs inferred from students’ choice and rejection, as well as datasets from the biology literature including gene regulatory networks. The results show that exact values of the line index of balance in relatively large signed graphs can be efficiently computed using our suggested optimisation models. We find that most real-world social networks and some biological networks have a small line index of balance which indicates that they are close to balanced.

Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-94830-0_3

Ordering information: This item can be ordered from
http://www.springer.com/9783319948300

DOI: 10.1007/978-3-319-94830-0_3

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().