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.

We consider the enumeration of walks on the nonnegative lattice $\mathbb{N}^{d},$ with steps defined by a set $\mathcal{S}\subset \{-1, 0, 1\}^d\backslash\{{0}\}$. Previous work in this area has established asymptotics for the number of walks in certain families of models by applying the techniques of analytic combinatorics in several variables (ACSV), where one encodes the generating function of a lattice path model as the diagonal of a multivariate rational function. Melczer and Mishna obtained asymptotics when the set of steps $\mathcal{S}$ is symmetric over every axis; in this setting one can always apply the methods of ACSV to a multivariate rational function whose set of singularities is a smooth manifold (the simplest case). Here we go further, providing asymptotics for models with generating functions that must be encoded by multivariate rational functions having nonsmooth singular sets. In the process, our analysis connects past work to deeper structural results in the theory of ACSV. One application is a closed form for asymptotics of models defined by step sets that are symmetric over all but one axis. As a special case, we apply our results when $d=2$ to give a rigorous proof of asymptotics conjectured by Bostan and Kauers; asymptotics for walks returning to boundary axes and the origin are also given.

This paper concerns the recently introduced concept of Legislation Networks, with an application focus on the New Zealand legislation network. Legislation networks have some novel features which make them an excellent test case for new network science tools. We develop several such networks, compute relevant centrality measures, and apply community detection algorithms. We study the relationship between the legislation network measures and legal/political factors.

Slinko and White, (2008) have recently introduced a new model of coalitional manipulation of voting rules under limited communication, which they call safe strategic voting. The computational aspects of this model were first studied by Hazon and Elkind, (2010), who provide polynomial-time algorithms for finding a safe strategic vote under k-approval and the Bucklin rule. In this paper, we answer an open question of Hazon and Elkind, (2010) by presenting a polynomial-time algorithm for finding a safe strategic vote under the Borda rule. Our results for Borda generalize to several interesting classes of scoring rules.

Abstract We consider the problem of constructing networks with as many nodes as possible, subject to upper bounds on the degree and broadcast time. This paper includes the results of an extensive empirical study of broadcasting in small regular graphs using a stochastic search algorithm to approximate the broadcast time. Significant improvements on known results are obtained for cubic broadcast networks. © 2002 Wiley Periodicals, Inc.