Common adversaries

In recent news, Canada and Mexico decided to coordinate on trade given the uncertainty faced by the US position on NAFTA. In another news story, an infectious disease physician used a virus to fight back an anti-biotic resistant superbug that was killing her husband. We hear of similar stories of unexpected alliances often. In a slogan: enemies of enemies become friends.

Nations may form alliances to defeat a common adversary (as they are doing presently with ISIS, as depicted in the featured image of this blog). Competing companies may work together to curtail a new disrupting influence in their markets. Gimli and Legolas can team up to battle the forces of Sauron in The Lord of the Rings.

How do we make this folkloric notion mathematically precise? One way is through network science, where we consider nodes and edges between them. Let the agents in the network (countries, companies, etc) be nodes. An edges represents friendship/alliance and rivalry/enmity corresponds to non-edges.  Some of these relationships may be unknown, so if we aren’t sure, then we assume there is a non-edge. In this simplified setting, every node is linked to all others via friendship or rivalry ties.

We explore this setting in the following paper, available on arXiv:

Anthony Bonato, Eva Infeld, Hari Pokhrel, and Pawel Pralat, Common adversaries form alliances: modelling complex networks via anti-transitivity, Preprint 2017.

Closing triads

In a network, a triad consists of three nodes. For example, we could have a virus, a superbug, and a patient.  The patient and virus are adversaries with the superbug, and so become allies in the network.

We may “close” a triad so that nodes with common adversaries become allies.

We may also close triads in other ways. “Friends of friends become friends” would imply that nodes with a common neighbor become friends. We see the latter kind of triad closure often in on-line social networks such as Facebook or Twitter.

The “enemy of enemy become friends” triad closure suggests one way to create new links and form new networks. For example, suppose that for a node x we add another node x’, so that x’ becomes enemies with all of x’s friends. In the language of networks, x’ is adjacent to the nodes in the non-neighbor set of x. In some sense, x’ is like the evil twin of x, with all the opposite friend-enemy relationships. For this reason, we call x’ the anti-clone of x.

A model of enemies and friends

Mathematicians enjoy engineering models that simulate how complex systems behave over time. Network models shed light on hidden mechanisms, can be a predictive tool, and they can lead to new mathematics.

The Iterated Local Anti-Transitivity (or ILAT for short) model duplicates nodes in each time-step by forming anti-clone nodes, and joins them to the parent node’s non-neighbor set. In simpler terms: we double the network by adding anti-clones of every node. Note that none of the anti-clones are adjacent. We repeat this process over discrete time-steps, generating large networks quickly that also have many edges. Provably, the density (that is, ratio of number of edges to the maximum number of possible edges) tends with 0.4 as the number of steps becomes large.

For example, consider the four cycle:

Below is how the ILAT model looks in this case after four time-steps. What we obtain in each time-step is a network with twice as many nodes: from 4 (in the four cycle) to 8, then 16, 32, and 64.

To our initial surprise, the ILAT model generates networks that exhibit familiar properties of complex networks such as densification, small world properties, and bad spectral expansion. I won’t get into the definition of these properties here, but mention are they arise in a variety of real-world, complex networks coming from technology, biology, and the social sciences.

Two emergent properties of the model where simple to prove but startled us. First, there are very short paths connecting nodes: in fact, these paths are length three or less. If we let the model run for many steps, then the average length of these paths tends to 1.6. Further, we can find three nodes who dominate the network, so that any other node is linked to one of the three. Only a small handful of nodes are needed to broadcast in one time-step to the entire network.

Interpretations

As George E.P. Box famously said, “Every model is wrong but some are more useful.” That rings true with many models and certainly with ILAT.

ILAT provides an idealized setting for network formation. In that sense, it is not a realistic model of real-world networks. However, it is fascinating that several emergent properties in networks appear from the model. The presence of 3-element dominating sets suggests the organic appearance of superpower nodes, which have broad influence in the network. Such nodes may emerge naturally in real-world networks owing to a high number of alliances against common adversaries. We certainly see that in networks composed of nations or companies.

The ILAT model also generates graph with short paths, high density, and high clustering of older nodes. This is suggestive that in networks where common adversaries forge alliances, we find tight-knit communities that are well-connected.

Our next step is to test these hypotheses with real empirical data. Stay tuned!

Anthony Bonato