Map represented as a network (rewiring equivalent to application of map)

1 collaborator

WHAT IS IT?

An example of how we can represent a map (function) as a network.

Let f(x,h) = (x + h) mod N With x and h being integer from 0 to N - 1.

We can represent this function by a network. Nodes will be the different values of nubmer x. A directed link from node a to node b will be the function f such that b = f(a).

HOW IT WORKS

Each nodes represent an integer number x from 0 to N - 1 (N = nb-nodes).

At the begining, each node is linked to its direct neighbour (i.e. each node points to its neighbours with value "(x + 1) Modulo N"). Then each link can be seen as the operation "f(x) = (x + 1) modulo N".

The rewiring process is the following: each link is rewired to the 'nb-hop' neighbour (i.e. from a given node, we follow the link until we reach the 'nb-hop'th neighbour).

This rewiring process can be understood as applying the operation "f(x) = (x + 1) modulo N" nb-hop times.

Let 'h = nb-hop' OThe rewiring process corresponds to the operation "f(x,h) = (x + h) modulo N"

Applying the rewiring process 't' times with the same 'h' corresponds to the operation "f(x,h,t) = (x + h^t) modulo N".

Applying the rewiring process once with 'nb-hop = a' and once with 'nb-hop = b' corresponds to the operation "f(x) = (x + (a*b)) Mod N"

HOW TO USE IT

Choose the number of nodes Setup

Choose how to rewire the nodes (i.e. the number of hop)

while true Rewire-once end while

THINGS TO NOTICE

IN GENERAL

For some parameters the network will remain a cycle and the repeated application of the 'rewire' procedure will tend to periodically create the same cycle. For other parameters the network will be disintegrated into smaller cycles (smaller in the sense that they only apply to a sub-set of the original n-nodes)

When nb-hop = 2,

A cycle with 2^x nodes will tend to a fully disconected network (all nodes will be linked with themselves)

A cycle with 3*2^x nodes will tend to 2^x cycles of 3 nodes

A cycle with 5*2^x nodes will tend to 2^x cycles of 5 nodes

...

In general

Applying the rewiring process with nb-hop = 2 gives you two possibilities:

if the number of nodes is even (N mod 2 = 0): then the original cycle is divided into two cycles: all the odd nodes are linked together and all the even nodes are linked together

if the number of nodes is odd (N mod 2 = 1): then the network remains a cycle. Because the node N - 1 (which is even) will be linked with the node 1 (which is odd).

When nb-hop = nb-nodes - 1

Apply the rewiring process 2 times and you have the original cycle again.

Proof:

Let nb-nodes = N Let nb-hop = N - 1 Let 0 <= x <= N - 1

f(x) = (x + N - 1) Mod N = (x - 1) Mod N

f(f(x)) = f((x - 1) Mod N) f(f(x)) = ((x - 1) Mod N + 1) Mod N f(f(x)) = (x + 1 - 1) Mod N f(f(x)) = x Mod N

f(f(x)) = x

When nb-nodes is a prime number

Notice that for a prime number of nodes the cycle remains whatever the parameter nb-hop

THINGS TO TRY

To demonstrate the previous results.

CREDITS AND REFERENCES

One example of such rewiring is given in the following article:

Naoto Kotaoka and Kunihiko Kaneko. Functional Dynamics I: Articulation Process. 1999 arXiv:adap-org/9907006v1 20 jul 1999

Detailed math about the rewiring process are given in appendix of the article for nb-hop = 2

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

breed [ nodes node ] ;; the turtle are called nodes

nodes-own [ current-next-node new-next-node ]

globals [ continue? ]  ;; is it possible to apply the transformation once again 

to setup
  clear-all
  ;; creates all the nodes
  set-default-shape nodes "circle"
  let size-nodes ( 0.75 * max-pxcor / nb-nodes)
  create-nodes nb-nodes [set label who set size size-nodes ]
  ;; show the nodes with a circular layout
  layout-circle sort(turtles) radius
  ;; link the nodes
  init-links
  ;; set up global parameters
  set continue? true
  ;; set simulation time to 0
  reset-ticks
end 

to init-links
  ;; create an ordered cycle between nodes (e.g. 0 -> 1 -> 2 -> 3 ... -> (nb-nodes - 1) -> 0 )
  ask nodes
  [
    set current-next-node turtle ((who + 1) mod count nodes)
    link-nodes
  ]
end 

to apply-transformation
  ;; rewire the links
  if continue?
  [
    ;; we can still apply the transformation
    ask nodes
    [
      ;; compute the new "next-node"
      set new-next-node (get-next-node nb-hop)  ;; get the next n-hop node
    ]
    
    ;; remove the links
    ask links [ die ]
    
    ;; change the current pointer to the next-node by the newly computed one
    ask nodes [ set current-next-node new-next-node ]
    
    ;; link the nodes
    ask nodes [ link-nodes ]
  ]
end 

to link-nodes
  ;; create a link between the node and its current next-node
  ifelse current-next-node != self
  [
    create-link-to current-next-node
    [
      set color [color] of end2
    ]
  ]
  [
    set continue? false
  ]
end 

to-report get-next-node [ n ]
  ;; return the n-hop node (recursive function)
  let result nobody
  ifelse n = 0
  [
    report self
  ]
  [
    set n n - 1
    ask current-next-node [  
        set result get-next-node n
    ]
  ]
  report result
end

There is only one version of this model, created over 12 years ago by julien siebert.

Attached files

File	Type	Description	Last updated
Map represented as a network (rewiring equivalent to application of map).png	preview	Preview for 'Map represented as a network (rewiring equivalent to application of map)'	over 12 years ago, by julien siebert	Download

This model does not have any ancestors.

This model does not have any descendants.

NetLogo