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

DOI10.1002/net.21907arXiv1611.09030OpenAlexW2978911227MaRDI QIDQ6068535

Andrew J. Mason, Mark C. Wilson, Samin Aref

Publication date: 13 November 2023

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.09030

zbMATH Keywords

optimizationsigned graphfrustration indexbinary programmingbalance theorysigned networks0-1 integer linear programmingline index of balance

Mathematics Subject Classification ID

Computer science (68-XX) Operations research, mathematical programming (90-XX)

Related Items (5)

Information spreading with relative attributes on signed networks ⋮ Nodal domain theorems for \(p\)-Laplacians on signed graphs ⋮ Resolvability of Hamming Graphs ⋮ Bounds for the extremal eigenvalues of gain Laplacian matrices ⋮ Characterizing attitudinal network graphs through frustration cloud

Cites Work

• Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
• Frustration and isoperimetric inequalities for signed graphs
• Separator-based data reduction for signed graph balancing
• Correlation clustering
• Optimal 2-constraint satisfaction via sum-product algorithms
• The multi-multiway cut problem
• Efficient solutions for special zero-one programming problems
• Balanced decompositions of a signed graph
• Weakly bipartite graphs and the max-cut problem
• Evaluating balancing on social networks through the efficient solution of correlation clustering problems
• Computing the line index of balance using integer programming optimisation
• The maximum balanced subgraph of a signed graph: applications and solution approaches
• Computing the bipartite edge frustration of fullerene graphs
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
• Correlation clustering in general weighted graphs
• A derivation of a measure of relative balance for social structures and a characterization of extensive ratio systems
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A Spectral Algorithm for Computing Social Balance
• Measuring partial balance in signed networks
• Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets
• Powers of tensors and fast matrix multiplication
• A Local-Search 2-Approximation for 2-Correlation-Clustering
• On the power of unique 2-prover 1-round games
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• Correlation clustering with a fixed number of clusters
• Edge-Deletion Problems
• Signed graphs for portfolio analysis in risk management

This page was built for publication: A modeling and computational study of the frustration index in signed networks