Heuristic rules

本实验方法提取自研究论文：

Constructing graphs from genetic encodings

**
Sci Rep**,
Jun 24, 2021;
DOI:
10.1038/s41598-021-92577-2

Constructing graphs from genetic encodings

Procedure

We can summarize the scale-free heuristic from the main text, which generated networks with ${p}_{\mathit{in}}={p}_{\mathit{out}}\sim {k}^{-1}$, using the pseudocode:

Here “connect” introduces the rule $(S)\mathbf{O}(D)$ into the network. For instance, for b = 4 we connect 0000 to *XXXX*, 000*X* to *XXX*0, 00*XX* to *XX*00, 0*XXX* to *X*000, 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 $\gamma $. For instance, we can use *b*/2 rules, where we construct D sets as before, but add two *X*s to each S set per iteration, resulting in ${p}_{\mathit{in}}\sim {k}^{-2}$ and ${p}_{\mathit{out}}\sim {k}^{-0.5}$ (Fig. ^{S2}):

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

Alternatively, we can use *b*/3 rules, where we construct D sets as before, but add three *X*s to each S set per iteration, resulting in ${p}_{\mathit{in}}\sim {k}^{-3}$ and ${p}_{\mathit{out}}\sim {k}^{-1/3}$ (Fig. ^{S3}):

In the case of b = 6, this would produce the rules $(000000)\mathbf{O}(XXXXXX)$, $(000XXX)\mathbf{O}(XXXXX0)$, and $(XXXXXX)\mathbf{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. ^{S4}a). 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. ^{S1}a, 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)\mathbf{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)\mathbf{O}(010X)$ and $(0110)\mathbf{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)\mathbf{O}(100X)$, $(0101)\mathbf{O}(101X)$, $(0110)\mathbf{O}(110X)$, and $(0111)\mathbf{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. ^{S4}a).

Similar to the binary tree, a genetic rule-based heuristic for generating hierarchical networks relies on a motivated indexing of node identity^{14}. 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)\mathbf{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. ^{S4}b). 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)\mathbf{O}(0001XX)$, $(1001XX)\mathbf{O}(1001XX)$, $(1011XX)\mathbf{O}(1011XX)$, $(1101XX)\mathbf{O}(1101XX)$, and $(1111XX)\mathbf{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)\mathbf{O}(000000)$.

This process can be continued, such that we keep introducing *X*s into the rules until *X*s are present in the ‘outermost’ 3-bit set. This means that for a hierarchical network of depth n, we get ${5}^{n-1}$ clique-forming rules, ${5}^{n-2}$ rules that generate an n=1 hierarchy, and ${5}^{n-k-1}$ rules that generate a n = k hierarchy. For instance, for an n = 2 hierarchical network (Fig. ^{S4}c), we had ${5}^{2-1}=5$ clique rules and ${5}^{2-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. ^{S4}d), which was not present in the original paper on hierarchical networks^{14}.

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)\mathbf{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)\mathbf{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)\mathbf{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)\mathbf{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.

Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

注意：以上内容是从某篇研究文章中自动提取的，可能无法正确显示。

Q&A

您的问题将发布在Bio-101网站上。我们会将您的问题发送给本研究方案的作者和具有相关研究经验的Bio-protocol成员。我们将通过您的Bio-protocol帐户绑定邮箱进行消息通知。