Models of interaction network

This protocol is extracted from research article:

Optimal network topology for responsive collective behavior

**
Sci Adv**,
Apr 3, 2019;
DOI:
10.1126/sciadv.aau0999

Optimal network topology for responsive collective behavior

Procedure

To study the effect of the number of neighbors on the collective frequency response, we have considered a set of network topologies including 1D and 2D regular periodic lattices (i.e., a ring and a mesh), connected caveman model graphs (*34*), and regular random graphs.

We have chosen these models because they feature a fairly regular structure—minimizing the effect of the leader’s location—and they allow a fine control of the degree of the agents from *k* = 2 or 4 up to an all-to-all connectivity (*k* = *N*). They are also guaranteed to be connected and thus have *H*^{2}(ω = 0) = *N* for any *k*, with the exception of the random regular graph at low degrees (*k* ≲ log *N*) (*35*). All these models provide unweighted, undirected interaction networks without self-loops.

*Regular lattice*. These networks are constructed by placing the agents in a regular square grid embedded in an Euclidean *d*-dimensional periodic space (a ring for *d* = 1 and a torus for *d* = 2) and connecting each node to its *k* nearest neighbors on the grid. This structure guarantees that all nodes have the same centrality and degree, and we can set the leader arbitrarily as the first agent without loss of generality.

For the 1D ring, the degree can be any even value between 2 and *N*. For the 2D mesh, only multiples of 4 are valid degrees.

*Caveman model*. The connected caveman graph is composed of *n* complete subgraphs with *k* + 1 nodes, where one edge from each cluster is modified so that it connects neighboring clusters (*34*). Note that the number of nodes is *N* = (*k* + 1)*n* and the average degree is *k* (there are *n* nodes with a degree of *k* + 1 and another *k* with *k* – 1; the rest have a degree of *k*).

We choose the number of agents *N* to be a highly composite number (such as 720, 840, or 1260) to have a high resolution on the possible values of the degree *k* while keeping *N* constant.

*Regular random networks*. Last, we consider the case of regular random graphs, i.e., graphs randomly sampled from all the possible *k*-regular graphs with *N* nodes. The graphs sampled are expected to be less structured than the lattices or caveman graphs, typically having significantly lower diameter and clustering coefficient. The frequency response of random networks presented in Fig. 2 is obtained by averaging over 100 samples for each frequency.

Note: The content above has been extracted from a research article, so it may not display correctly.

Q&A

Your question will be posted on the Bio-101 website. We will send your questions to the authors of this protocol and Bio-protocol community members who are experienced with this method. you will be informed using the email address associated with your Bio-protocol account.