Valence and interactions in judicial voting.

The collective statistics of voting on judicial courts present hints about their inner workings. Many approaches for studying these statistics, however, assume that judges' decisions are conditionally independent: a judge reaches a decision based on the case at hand and his or her personal views. In reality, judges interact. We develop a minimal model that accounts for judge bias, depending on the context of the case, and peer interaction. We apply the model to voting data from the US Supreme Court. We find strong evidence that interaction is an important factor across natural courts from 1946 to 2021. We also find that, after accounting for interaction, the recovered biases differ from highly cited ideological scores. Our method exemplifies how physics and complexity-inspired modelling can drive the development of theoretical models and improved measures for political voting. This article is part of the theme issue 'A complexity science approach to law and governance'.

Message passing on networks with loops.

Message passing is a fundamental technique for performing calculations on networks and graphs with applications in physics, computer science, statistics, and machine learning, including Bayesian inference, spin models, satisfiability, graph partitioning, network epidemiology, and the calculation of matrix eigenvalues. Despite its wide use, however, it has long been recognized that the method has a fundamental flaw: It works poorly on networks that contain short loops. Loops introduce correlations that can cause the method to give inaccurate answers or to fail completely in the worst cases. Unfortunately, most real-world networks contain many short loops, which limits the usefulness of the message-passing approach. In this paper we demonstrate how to rectify this shortcoming and create message-passing methods that work on any network. We give 2 example applications, one to the percolation properties of networks and the other to the calculation of the spectra of sparse matrices.

Inference, Model Selection, and the Combinatorics of Growing Trees.

One can often make inferences about a growing network from its current state alone. For example, it is generally possible to determine how a network changed over time or pick among plausible mechanisms explaining its growth. In practice, however, the extent to which such problems can be solved is limited by existing techniques, which are often inexact, inefficient, or both. In this Letter, we derive exact and efficient inference methods for growing trees and demonstrate them in a series of applications: network interpolation, history reconstruction, model fitting, and model selection.

Heterogeneous message passing for heterogeneous networks.

Message passing (MP) is a computational technique used to find approximate solutions to a variety of problems defined on networks. MP approximations are generally accurate in locally treelike networks but require corrections to maintain their accuracy level in networks rich with short cycles. However, MP may already be computationally challenging on very large networks and additional costs incurred by correcting for cycles could be prohibitive. We show how the issue can be addressed. By allowing each node in the network to have its own level of approximation, one can focus on improving the accuracy of MP approaches in a targeted manner. We perform a systematic analysis of 109 real-world networks and show that our node-based MP approximation is able to increase both the accuracy and speed of traditional MP approaches. We find that, compared to conventional MP, a heterogeneous approach based on a simple heuristic is more accurate in 81% of tested networks, faster in 64% of cases, and both more accurate and faster in 49% of cases.

Belief propagation for permutations, rankings, and partial orders.

Many datasets give partial information about an ordering or ranking by indicating which team won a game, which item a user prefers, or who infected whom. We define a continuous spin system whose Gibbs distribution is the posterior distribution on permutations, given a probabilistic model of these interactions. Using the cavity method, we derive a belief propagation algorithm that computes the marginal distribution of each node's position. In addition, the Bethe free energy lets us approximate the number of linear extensions of a partial order and perform model selection between competing probabilistic models, such as the Bradley-Terry-Luce model of noisy comparisons and its cousins.

Belief propagation for networks with loops.

Belief propagation is a widely used message passing method for the solution of probabilistic models on networks such as epidemic models, spin models, and Bayesian graphical models, but it suffers from the serious shortcoming that it works poorly in the common case of networks that contain short loops. Here, we provide a solution to this long-standing problem, deriving a belief propagation method that allows for fast calculation of probability distributions in systems with short loops, potentially with high density, as well as giving expressions for the entropy and partition function, which are notoriously difficult quantities to compute. Using the Ising model as an example, we show that our approach gives excellent results on both real and synthetic networks, improving substantially on standard message passing methods. We also discuss potential applications of our method to a variety of other problems.

Improved mutual information measure for clustering, classification, and community detection.

The information theoretic measure known as mutual information is widely used as a way to quantify the similarity of two different labelings or divisions of the same set of objects, such as arises, for instance, in clustering and classification problems in machine learning or community detection problems in network science. Here we argue that the standard mutual information, as commonly defined, omits a crucial term which can become large under real-world conditions, producing results that can be substantially in error. We derive an expression for this missing term and hence write a corrected mutual information that gives accurate results even in cases where the standard measure fails. We discuss practical implementation of the new measure and give example applications.

Thresholding normally distributed data creates complex networks.

Network data sets are often constructed by some kind of thresholding procedure. The resulting networks frequently possess properties such as heavy-tailed degree distributions, clustering, large connected components, and short average shortest path lengths. These properties are considered typical of complex networks and appear in many contexts, prompting consideration of their universality. Here we introduce a simple model for correlated relational data and study the network ensemble obtained by thresholding it. We find that some, but not all, of the properties associated with complex networks can be seen after thresholding the correlated data, even though the underlying data are not "complex." In particular, we observe heavy-tailed degree distributions, a large numbers of triangles, and short path lengths, while we do not observe nonvanishing clustering or community structure.

Mixing patterns and individual differences in networks.

We study mixing patterns in networks, meaning the propensity for nodes of different kinds to connect to one another. The phenomenon of assortative mixing, whereby nodes prefer to connect to others that are similar to themselves, has been widely studied, but here we go further and examine how and to what extent nodes that are otherwise similar can have different preferences. Many individuals in a friendship network, for instance, may prefer friends who are roughly the same age as themselves, but some may display a preference for older or younger friends. We introduce a network model that captures this behavior and a method for fitting it to empirical network data. We propose metrics to characterize the mean and variation of mixing patterns and show how to infer their values from the fitted model, either using maximum-likelihood estimates of model parameters or in a Bayesian framework that does not require fixing any parameters.

Balance in signed networks.

We consider signed networks in which connections or edges can be either positive (friendship, trust, alliance) or negative (dislike, distrust, conflict). Early literature in graph theory theorized that such networks should display "structural balance," meaning that certain configurations of positive and negative edges are favored and others are disfavored. Here we propose two measures of balance in signed networks based on the established notions of weak and strong balance, and we compare their performance on a range of tasks with each other and with previously proposed measures. In particular, we ask whether real-world signed networks are significantly balanced by these measures compared to an appropriate null model, finding that indeed they are, by all the measures studied. We also test our ability to predict unknown signs in otherwise known networks by maximizing balance. In a series of cross-validation tests we find that our measures are able to predict signs substantially better than chance.

Efficient method for estimating the number of communities in a network.

While there exist a wide range of effective methods for community detection in networks, most of them require one to know in advance how many communities one is looking for. Here we present a method for estimating the number of communities in a network using a combination of Bayesian inference with a novel prior and an efficient Monte Carlo sampling scheme. We test the method extensively on both real and computer-generated networks, showing that it performs accurately and consistently, even in cases where groups are widely varying in size or structure.