The New Kind of Science book defines a network system as a collection of nodes with various connections between these nodes, and rules that specify how these connections should change from one step to the next. In this article, I explore different ways to enumerate the instructions that make up the rules for a two-link(up and down) network system. The instructions specify how the connections coming out of each node should be rerouted depending on the structure of the network around that node.
​
Two-link network system means there are two connections that come out of each node. And in this setup, one connection is always going above while the other is always going below. In the rules as we will see later, the “above” connection is represented as 1 and the “below” connection as 2.

Rule properties

Rule specifications:
◼
  • {
    a
    1
    ,
    a
    2
    , ...,
    a
    d
    }  instruction
    • ◼
  • instruction: { M, N }. M and N are of type list which can be single or nested lists of integer values
    • ◼
  • M is instruction for up link
    • ◼
  • N is instruction for down link
    • ◼
  • a
    1
    is the number of distinct neighbour nodes up to distance 1
    • ◼
  • a
    2
    is the number of distinct neighbour nodes up to distance 2
    • ◼
  • a
    d
    is the number of distinct neighbour nodes up to distance d
    • Example:
    rule: { 1, 1 } -> { { 1 }, { 2 } }
    rules for a network: {{ 1 }  {{ 2 }, { 1 }}, { 2 }  {{ 1 }, {{ 1 }, { 2 }}}}
    Neighbour number parsing:
    ◼
  • Given current node i, if distinct neighbour numbers for this node is {2, 3} and the instruction is { { 2, 1 }, { 1 } }, then the up link from this node take instructions to follow as {2, 1} and the down link uses instruction {1}.

    • Rule Enumeration

    The network structure rules are classified based on how far a node can connect to its neighbours(distances) and cases each distance-rules have. The cases are chosen based on the local pairs of all possible neighbour numbers for distance. For example: Let d > 0 be the distance.
    If d = 2, then all local pairs will be(we will see later how this is computed):
    { { 1, 1 }, { 1, 2 }, { 1 , 3 }, { 1, 4 }, { 2, 1 }, { 2, 2 }, { 2, 3 }, { 2, 4 } }

    Link instructions for distance d in base 6: Why base 6?

    Instructions are encoded with two item(for a two-link network system), 1 for up link and 2 for down link. That is {1, 2}. There are only 6 possible selection from this:
    d == 1 = { { 1 }, { 2 }, {{ 1 }, { 1 }}, {{ 2 }, { 1 }}, {{ 1 }, { 2 }}, {{ 2 }, { 2 }}}
    d > 1 = { { 1 }, { 2 }, { 1, 1 }, { 2, 1 }, { 1, 2 }, { 2, 2 } }
    which are then mapped to their specific base digits as:
    d == 1 = { 0 -> { 1 }, 1 -> { 2 }, 2 -> { { 1 }, { 1 } }, 3 -> { { 1 }, { 2 }}, 4 -> { { 2 }, { 1 } }, 5 -> { { 2 }, { 2 } } }
    d > 1 = { 0 -> { 1 }, 1 -> { 2 }, 2 -> { 1, 1 }, 3 -> { 1, 2 }, 4 -> { 2, 1 }, 5 -> { 2, 2 } }

    Combining cases into a single rule index

    If you have C distinct “cases” for local pairs (see above), then each rule is a product of C up-down pairs. Power 2 is used because we have two links (up and down).
    TotalRules(d) =
    C
    
    2
    (
    d
    6
    )
    
    =
    d2C
    6

    Rule Index(Code) selection

    Let k be the total number of rules for distance d :
    k = TotalRules(d)
    The index is then chosen from the range 0...(k -1)

    Function(s) definitions

    GetDistanceDRules[k_Integer, d_integer]
    k rule index
    d distance/depth

    Enumeration procedure

    ◼
  • Step 0: Define values
    • ◼
  • d = 1
    • ◼
  • cases = {{1}, {2}}
    • ◼
  • c = Length[cases] = 2
    • ◼
  • base =
    2d
    6
    • ◼
  • TotalRules(d) =
    c
    base
    =
    2
    base
    = 1296
    • ◼
  • Let index(k) be a value between 0 and 1296. I.e., k = 219
    • ◼
  • Step 1: Compute case index
    • ◼
  • index_case = IntegerDigits[k, base, c] = IntegerDigits[219, 36, 2]
    • ◼
  • {6, 3}
    • ◼
  • Step 2: Compute up and down decoded
    • ◼
  • size =
    d
    6
    • ◼
  • up = Quotient[index_case, size] = Quotient[6, 6] = {1, 0}
    • ◼
  • down = Mod[index_case, size] = Mod[3, 6] = {0, 3}
    • ◼
  • Step 3: Compute the link mapping
    • ◼
  • If up/down code is not in the range 0...5 (see link instructions above), then compute finally with base 6, otherwise get the instructions from the mapping: { 0 -> { 1 }, 1 -> { 2 }, 2 -> { { 1 }, { 1 } }, 3 -> { { 1 }, { 2 }}, 4 -> { { 2 }, { 1 } }, 5 -> { { 2 }, { 2 } } }.
    • ◼
  • All values for {1, 0}, and {0, 3} are in range 0...5. Hence the rule instruction, by replacement function, becomes:
    • ◼
  • {1, 0} = { { 2 }, { 1 } }
    • ◼
  • {0, 3} = { { 1 }, { { 1 }, { 2 } } }
    • ◼
  • Step 4: Assign instructions to specific cases
    • ◼
  • Case {1}  { { 2 }, { 1 } }
    • ◼
  • Case {2}  { { 1 }, { { 1 }, { 2 } } }
    • ◼
  • Final output rules:
    • ◼
  • {{1}  { { 2 }, { 1 } }, { { 1 }, { { 1 }, { 2 } } } }

    • Distance one rules

    Possible rules:
    In[]:=
    d=1;
    In[]:=
    cases=TuplesTableRange1,
    i
    2
    ,{i,d}
    Out[]=
    {{1},{2}}
    In[]:=
    c=Length[cases]
    Out[]=
    2
    In[]:=
    2*d*c
    6
    Out[]=
    1296
    In[]:=
    k=219;
    In[]:=
    rules=GetDistanceDRules[k,d]
    Out[]=
    {{1}{{2},{1}},{2}{{1},{{1},{2}}}}
    In[]:=
    TableDisplay[rules,k]
    Out[]=
    Rule Index: 219
    Configuration
    Up Link
    Down Link
    {1}
    {2}
    {1}
    {2}
    {1}
    {{1},{2}}
    Different k
    In[]:=
    rulesa=GetDistanceDRules[1288,d]
    Out[]=
    {{1}{{{2},{2}},{{2},{2}}},{2}{{{2},{1}},{{2},{1}}}}
    In[]:=
    TableDisplay[rulesa,1288]
    Out[]=
    Rule Index: 1288
    Configuration
    Up Link
    Down Link
    {1}
    {{2},{2}}
    {{2},{2}}
    {2}
    {{2},{1}}
    {{2},{1}}

    Distance 2 rules

    In[]:=
    d2=2;
    In[]:=
    cases2=TuplesTableRange1,
    i
    2
    ,{i,d2}
    Out[]=
    {{1,1},{1,2},{1,3},{1,4},{2,1},{2,2},{2,3},{2,4}}
    In[]:=
    c2=Length[cases2]
    Out[]=
    8
    In[]:=
    2*d2*c2
    6
    Out[]=
    7958661109946400884391936
    In[]:=
    k2=9652665412472289834238;
    In[]:=
    rules2=GetDistanceDRules[k2,d2]
    Out[]=
    {{1,1}{{1},{2}},{1,2}{{{1,2},{1,1}},{{1,2},{1,2}}},{1,3}{{2,1},{{1,1},{1,2}}},{1,4}{{{1,1},{1}},{{2,1},{1,2}}},{2,1}{{{2,1},{2,1}},{{1,1},{2,1}}},{2,2}{{{2},{2,2}},{{2,1},{2,1}}},{2,3}{{{2,2},{1}},{{2},{1,2}}},{2,4}{{{2,1},{1,2}},{{2,2},{2,1}}}}
    In[]:=
    TableDisplay[rules2,k2]
    Out[]=
    Rule Index: 9652665412472289834238
    Configuration
    Up Link
    Down Link
    {1,1}
    {1}
    {2}
    {1,2}
    {{1,2},{1,1}}
    {{1,2},{1,2}}
    {1,3}
    {2,1}
    {{1,1},{1,2}}
    {1,4}
    {{1,1},{1}}
    {{2,1},{1,2}}
    {2,1}
    {{2,1},{2,1}}
    {{1,1},{2,1}}
    {2,2}
    {{2},{2,2}}
    {{2,1},{2,1}}
    {2,3}
    {{2,2},{1}}
    {{2},{1,2}}
    {2,4}
    {{2,1},{1,2}}
    {{2,2},{2,1}}

    Distance 3 rules

    Concluding Remarks

    ◼
  • Rule-space size grows extremely fast as the distance increases. We saw this with distance 3 which has a large number of rules.
    • ◼
  • Code for evolving Network Systems using this rules

    • References

    1
    .
    Stephen Wolfram, A New Kind Of Science, Wolfram Media (2002). ISBN: 1-57955-008-8
    2
    .
    Kate L. Morrow,1 Todd Rowland,2 and Christopher M. Danforth (2009), “Dynamic structure of networks updated according to simple, local rules”. 10.1103/PhysRevE.80.016103

    CITE THIS NOTEBOOK

    Enumerating local rewriting rules for two-link network systems​
    by Brian A. Mboya​
    Wolfram Community, STAFF PICKS, March 20, 2025
    ​https://community.wolfram.com/groups/-/m/t/3420775