Heuristic rules
Constructing graphs from genetic encodings
Sci Rep, Jun 24, 2021; DOI: 10.1038/s41598-021-92577-2

We can summarize the scale-free heuristic from the main text, which generated networks with pin=poutk-1, using the pseudocode:

Here “connect” introduces the rule (S)O(D) into the network. For instance, for b = 4 we connect 0000 to XXXX, 000X to XXX0, 00XX to XX00, 0XXX to X000, and XXXX to 0000 (Fig. (Fig.2,2, Main Text). The above code creates a directed network with nodes having equal out- and in-degree, while replacing a ‘0’ with a ‘1’ either in the S or D variable results in a network with separate in-hubs and out-hubs.

Through slight modifications of the heuristic, we can produce scale free networks with alternative γ. For instance, we can use b/2 rules, where we construct D sets as before, but add two Xs to each S set per iteration, resulting in pink-2 and poutk-0.5 (Fig. S2):

In the case of b = 6, this would produce the rules (000000)O(XXXXXX), (0000XX)O(XXXXX0), (00XXXX)O(XXXX00), and (XXXXXX)O(XXX000).

Alternatively, we can use b/3 rules, where we construct D sets as before, but add three Xs to each S set per iteration, resulting in pink-3 and poutk-1/3 (Fig. S3):

In the case of b = 6, this would produce the rules (000000)O(XXXXXX), (000XXX)O(XXXXX0), and (XXXXXX)O(XXXX00).

A simple heuristic for a binary tree of depth b can be implemented on {0,1}b. The binary barcode of a node can determine its depth in the tree: the location of the first ‘1’ in the barcode (first from the left) defines the depth. For instance, in a tree of total depth 4, 0001 is the root of the tree, and 0100 occurs at depth 3 (Fig. S4a). The heuristic consists of a buffer of identities, initialized with the root node. At each step, a barcode is removed from the buffer. A new rule is introduced by using the current barcode as the source set, while the destination set requires removing the first bit of the barcode and adding an X to the end. Then, the two new nodes that are invoked in the destination set are added to the buffer. This process repeats until the destination nodes are selected from the terminal depth (ID starts with ‘1’), at which point the destination nodes are not added to the buffer.

To illustrate, let us again consider a tree with depth b = 4. At initialization, the buffer consists of only the root node, 0001 (Fig. S1a, top). We introduce a rule with source set 0001. The destination set is created by dropping the first ‘0’ from the source node, and adding an ‘X’ at the end: 001X. This results in the rule (0001)O(001X). We then add the two nodes in the destination set to the buffer, which now consists of 0010 and 0011. These will then lead to two new rules: (0010)O(010X) and (0110)O(011X). After introducing these new rules the buffer will consist of 0100, 0101, 0110, and 0111. This will lead to the third set of rules: (0100)O(100X), (0101)O(101X), (0110)O(110X), and (0111)O(111X). However, this step will not place new barcodes in the buffer, as we have reached the final depth (there is 1 as the first bit). Thus, once these rules have been introduced the buffer is empty and the resulting binary tree is now complete (Fig. S4a).

Similar to the binary tree, a genetic rule-based heuristic for generating hierarchical networks relies on a motivated indexing of node identity14. The core module of a hierarchical network is a 5-clique, corresponding to n = 0, which requires at least b = 3 to encode. We label the node at the center ‘000’, and the four nodes on the ‘periphery’ to be ‘1XX’. In this way, the first bit of a 3-bit set corresponds to whether a node is in the center (0) or at the periphery (1). Thus, the n = 0 hierarchical network can be coded with the rules (1XX)O(1XX), which connects the peripheral nodes to each other, and (1XX)O(0XX), which connects the periphery to the center.

The n = 1 hierarchical network is generated by making four copies of the 5-clique, and having the peripheral nodes of the copy connect to the center node of the original (Fig. S4b). This leads to a new definition of core and periphery: a node can be in the ‘core’, or original, clique, or in the peripheral, or copied, cliques, but also a node can be in the center or on the periphery within a clique. In this way, n = 1 can be coded easily with 6 bits, the first of which determine which clique a node is in, and the second of which determine where in the clique the node is present. For instance, 101000 is a central node in a peripheral clique, as the first three bits ‘101’ indicate its peripheral clique status, but ‘000’ as the second three bits corresponds to a central node. Alternatively, 000100 is a peripheral node in the central clique. To wire the system up properly, we introduce a separate clique wiring, as introduced in the previous paragraph, for every possible inner and outer clique in the system, such that we have rules of the type (0001XX)O(0001XX), (1001XX)O(1001XX), (1011XX)O(1011XX), (1101XX)O(1101XX), and (1111XX)O(1111XX), as well as similar rules ending in ‘1XX’ on the source and ‘0XX’ on the destination. Then, each of the nodes that are ‘doubly’ peripheral connects back to the ‘doubly’ central node with rule (1XX1XX)O(000000).

This process can be continued, such that we keep introducing Xs into the rules until Xs are present in the ‘outermost’ 3-bit set. This means that for a hierarchical network of depth n, we get 5n-1 clique-forming rules, 5n-2 rules that generate an n=1 hierarchy, and 5n-k-1 rules that generate a n = k hierarchy. For instance, for an n = 2 hierarchical network (Fig. S4c), we had 52-1=5 clique rules and 52-2=1 n = 2 rules. This process is best illustrated in the supplementary code, which can create hierarchical networks of any depth, such as n = 3 (Fig. S4d), which was not present in the original paper on hierarchical networks14.

The structure of the investigated wiring rules lends itself to a model of homiphilic connectivity, a popular consideration in social networks. Specifically, we aim to connect nodes with similar identities, which can be achieved by placing the same identities on either side of a rule: (010XX)O(010XX). While previously we considered rules where nodes with similar identities share connectivity patterns, we now aim to connect nodes with similar identities to each other. In the language of the wiring rules, until now we focused on rules of the sort (010XX)O(0X01X), where the two sets to be connected may or may not share nodes, while with homiphily rules we consider rules of the form (010XX)O(010XX), where we connect the same two sets of nodes.

Although many possible approaches exist for modeling homiphily, we consider a simple scaling, where we connect all sets of nodes with at least o=b-x overlap in their identities. For instance, (010XX)O(010XX) would represent a rule from o=3, where nodes need at least 3 shared bits to connect. The extremes of this model lie at o=0, where no bits need to be shared, thus we have a fully connected graph, and o=b, where all bits need by shared, thus we have a network with only self loops. The interesting regime lies in 0<o<b, where the networks are expected to densify and have lower path length as o decreases. Simulations confirm these predictions (Fig. S5), and a stereotyped scaling emerges in density, clustering and path length over a number of system sizes.