@incollection{aref2018computing,
  title={Computing the line index of balance using integer programming optimisation},
  author={Aref, Samin and Mason, Andrew J and Wilson, Mark C.},
  booktitle={Optimization Problems in Graph Theory},
  pages={65-84},
  year={2018},
  publisher={Springer, Cham},
  keywords={network science, computation, graphs},
  url_Paper={https://arxiv.org/abs/1710.09876},
  abstract={An important measure of signed graphs is the line index of balance which
has several 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\H{o}s-R\'{e}nyi graphs, Barab\'{a}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 small line index of balance which indicates that they are
close to balanced.}
}

{"_id":"W3r52Mv8JMgvv6cuQ","bibbaseid":"aref-mason-wilson-computingthelineindexofbalanceusingintegerprogrammingoptimisation-2018","author_short":["Aref, S.","Mason, A. J","Wilson, M. C."],"bibdata":{"bibtype":"incollection","type":"incollection","title":"Computing the line index of balance using integer programming optimisation","author":[{"propositions":[],"lastnames":["Aref"],"firstnames":["Samin"],"suffixes":[]},{"propositions":[],"lastnames":["Mason"],"firstnames":["Andrew","J"],"suffixes":[]},{"propositions":[],"lastnames":["Wilson"],"firstnames":["Mark","C."],"suffixes":[]}],"booktitle":"Optimization Problems in Graph Theory","pages":"65-84","year":"2018","publisher":"Springer, Cham","keywords":"network science, computation, graphs","url_paper":"https://arxiv.org/abs/1710.09876","abstract":"An important measure of signed graphs is the line index of balance which has several 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 small line index of balance which indicates that they are close to balanced.","bibtex":"@incollection{aref2018computing,\n title={Computing the line index of balance using integer programming optimisation},\n author={Aref, Samin and Mason, Andrew J and Wilson, Mark C.},\n booktitle={Optimization Problems in Graph Theory},\n pages={65-84},\n year={2018},\n publisher={Springer, Cham},\n keywords={network science, computation, graphs},\n url_Paper={https://arxiv.org/abs/1710.09876},\n abstract={An important measure of signed graphs is the line index of balance which\nhas several applications in many fields. However, this graph-theoretic\nmeasure was underused for decades because of the inherent complexity in\nits computation which is closely related to solving NP-hard graph\noptimisation problems like MAXCUT. We develop new quadratic and linear\nprogramming models to compute the line index of balance exactly. Using\nthe Gurobi integer programming optimisation solver, we evaluate the line\nindex of balance on real-world and synthetic datasets. The synthetic\ndata involves Erd\\H{o}s-R\\'{e}nyi graphs, Barab\\'{a}si-Albert graphs,\nand specially structured random graphs. We also use well known datasets\nfrom the sociology literature, such as signed graphs inferred from\nstudents' choice and rejection as well as datasets from the biology\nliterature including gene regulatory networks. The results show that\nexact values of the line index of balance in relatively large signed\ngraphs can be efficiently computed using our suggested optimisation\nmodels. We find that most real-world social networks and some biological\nnetworks have small line index of balance which indicates that they are\nclose to balanced.}\n}\n\n","author_short":["Aref, S.","Mason, A. J","Wilson, M. C."],"key":"aref2018computing","id":"aref2018computing","bibbaseid":"aref-mason-wilson-computingthelineindexofbalanceusingintegerprogrammingoptimisation-2018","role":"author","urls":{" paper":"https://arxiv.org/abs/1710.09876"},"keyword":["network science","computation","graphs"],"metadata":{"authorlinks":{}}},"bibtype":"incollection","biburl":"https://drive.google.com/uc?export=download&id=1NEXsxwRAx2CWt43v0y0jyZdP1LdOS_xF","dataSources":["yx9ivfGLzvFNsg4LH","QdFdNQZBZSvbPbp7t","o2FBsFrZMS3PxguCG","SjBh38uzaGjRinwq8","M2T285kj8vXfTkGDx","2zimNJgtWEiEM2L3J","TAyBmAZAcnenc4YET","BCqQErP8wgW48bwvt","YjweTJPHHEQ85Pems"],"keywords":["network science","computation","graphs"],"search_terms":["computing","line","index","balance","using","integer","programming","optimisation","aref","mason","wilson"],"title":"Computing the line index of balance using integer programming optimisation","year":2018}