Designing threshold networks with given structural and dynamical properties

The threshold model can be used to generate random networks of arbitrary size with given local properties such as the degree distribution, clustering, and degree correlation. We summarize the properties of networks created using the threshold model and present an alternative deterministic construction. These networks are threshold graphs and therefore contain a highly compressible layered structure and allow computation of important network properties in linear time. We show how to construct arbitrarily large, sparse, threshold networks with (approximately) any prescribed degree distribution or Laplacian spectrum. Control of the spectrum allows careful study of the synchronization properties of threshold networks including the relationship between heterogeneous degrees and resistance to synchrony.

Figure 1

(Color online) Some threshold networks and corresponding creation sequences. (a) Star with representation $S=10001$. (b) Complete graph $K_5$ with representation $S=11111$. (c) Network with representation $S=10101$. (d) Network with representation $S=10000101$. The creation sequence consists of dominating 1 nodes and isolated 0 nodes and is read from left to right. In (a) one dominating node is connected to four isolated nodes, one of which, appearing first in $S$, is technically both dominating and isolated and by convention denoted 1.

Figure 2

(Color online) Two representations of a threshold network with the compact creation sequence $C=(2,4,3,6,5,1,1)$. Top: layer-cake depiction of the network showing the structure of the network by different node types. The layers are numbered from bottom to top with the isolated nodes (small squares) on the left and the dominating nodes (small circles) on the right. Ovals represent complete subgraphs for the surrounded nodes while rectangles are groups of isolated nodes that are not connected to each other. Lines between the node group outlines mean that all nodes in each group are connected to all nodes in the other group. Bottom: a two-dimensional layout of the network.

Figure 3

(Color online) The degree distribution $P\left(k\right)$ for a threshold network that is approximately Gaussian. The threshold network was generated as described in the text with the degree distribution given by $n_k=a{e}^{-{[(k-c)∕w]}^2}$ for $k=1,\dots ,20$, $a=1000$, $c=10$, and $w=4$.

Figure 4

(Color online) The degree distribution $P\left(k\right)$ for a threshold network that is approximately a power law. The threshold network was generated as described in the text with the degree distribution given by $n_k=a{k}^{-2.5}$ for $k=1,\dots ,20$ and $a=2000$.

Figure 5

(Color online) The Ferrer diagram for the degree sequence (6,4,2,2,2,1,1). Each column has a number of squares to match the degree of a node. Because this degree sequence represents a threshold network, the spectrum for the Laplacian can be obtained by counting squares in each row to get (7,5,2,2,1,1,0).

Figure 6

The matrix of column eigenvectors of the Laplacian for the network shown in Fig. 2. Blank entries indicate zero value. Boxes have been placed around the entries describing groups of identical nodes. Eigenvalues for each eigenvector appear at the bottom of each column. Below them are the degree and node type for nodes in the group identified by the eigenvector. Notice that dominating nodes have degree one less than the corresponding eigenvalue while for isolated nodes the spectrum and degree are equal.

Figure 7

(Color online) The phase difference of coupled oscillators vs time for a network with the dynamics given by $u_i=-u_i+\sigma {\sum }_{j=1}^N{L}_{ij}(u_j^3-u_j^5∕2)$ and $\sigma =0.01855$. The system is started from an initially synchronized state with a small random perturbation applied to all nodes. The instantaneous phase is estimated using a Hilbert transform of the time signals [39]. (a) A 100-node threshold model with weights randomly selected from a power-law distribution with exponent $\gamma =-2.5$ and with threshold $\theta =3$. The eigenvalue ratio is $r={\lambda }_N∕{\lambda }_2=100∕33\approx 3.0$. (b) The same network as (a) but with three nodes added so that the creation sequence ends in 101. This change makes the synchronized state unstable. The eigenvalue ratio in (b) is $r={\lambda }_N∕{\lambda }_2=103∕1=103$.