Use Network

Use Network preview image

1 collaborator

Default-person Kyosuke Tanaka (Author)

Tags

social networks 

Tagged by Kyosuke Tanaka almost 8 years ago

Model group MAM-2016 | Visible to everyone | Changeable by everyone
Model was written in NetLogo 6.0-M6 • Viewed 793 times • Downloaded 51 times • Run 0 times
Download the 'Use Network' modelDownload this modelEmbed this model

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)


WHAT IS IT?

This model explores how network structure and agent choice of routing influence the observed average steps between a message origin and target. In terms of network structure, the model produces two types of networks:

  • a random network (default), and

  • a small-world network.

Speaking of agent rounting choice, the model has four different choice heuristics (See details on HOW TO USE IT):

  • random (default)

  • local search

  • homophilious search and

  • preferential attachment search.

The "actual" average path length (observed) means how many steps take until messages are reached, while the average path length (expected) can be conceptually calculated as the average possible shortest path between pairs of agents. However, research shows the actual paths are longer than computed expected shortest paths in real human practice due to the fact that people choose not shortest path once in two choices (Killworth et al., 2006). This model shows this phenomenon and the mechanisms of why this is the case.

HOW IT WORKS

In the model, two agents are set up: (1) nodes who circulate a message and (2) a message who is circulated by nodes. Also, nodes have links, which create paths to other nodes.

When you press the SETUP button (See also the Choose Network Model):

  • Create NUMBER nodes and NUMBER of directed links for each nodes - either randomly or in a small-world way (the SMALL-WORLD switch)
  • Default is a circle layout
  • One message is randomly set up on a node
  • One target is randomly set up on another node
  • Calculate the number of paths unavailable between pairs of nodes as NUMBER-OF-UNCONNECTED

Each tick (GO or GO ONCE):

  • The message moves to a new location via a link
  • A link becomes thicker as a mark of usage of the route
  • Repeat the aforementioned processes until the message reaches or becoming one of the two conditions: (1) INCOMPLETES: When the ROUTE-LIMITS switch is on, nodes often exhaust their paths as a result that the message comes back them again and again. When nodes have no usable paths, STOP. (2) DEADEND: When not all nodes have avaiable access to every other node (i.e., NUMBER-OF-UNCONNECTED is not 0), the message can suddenly go a DEADEND path and can't get out to reach to the target. If so, it adds NUMBER-OF-DEADEND and STOP.

Once the message is reached:

  • It counts as one session and adds NUMBER OF SESSIONS
  • Re-setup a message and target at a random node, respecively
  • If there is no path available between a randomly setup message and target, the case is recorded as UNREACHABLE-PAIRS

HOW TO USE IT

This models provides a experimental setting for a small-world experiment. Changing the switches and sliders helps you understand how observed path lengths are emerged.

  • ROUTE-LIMITS: This gives constrains on use of links (paths). If the switch is on, agents can't use the same path twice.

  • SMALL-WORLD: This switch changes the network setting from a random to a small-world network (shorter path length and high clustering coefficient). Using REWIRING PROBABILITY, change the likelihood of rewiring links to create a small-world network.

  • NUMBER-OF-NODES: This gives you a control for creating how many nodes are in a network.

  • NUMBER-OF-LINKS: This determines how many links each node can hold.

  • SEARCH-STRATEGY: This chooser allows you to test how different cognitive strategies work in message delivery: (1) random search: All links agents hold have a equal chance to be chose, (2) local search: First, agents look at their local neighbors. If no neighbors are the target, they pass a message to furthest link-neighbor or one of local neighbors if they don't have further link-neighbor, (3) homophilious search: Based on target's gender, agents determine which contact they will send. If the target is female, agents are more likely to choose female contact than male one, and (4) preferential attachment: Agents prefer to send a message to the highest in-link neighbors)

THINGS TO NOTICE

You see a similarity and difference in terms of observed and expected average path length and the freqency distribution of path lengths. In particular, look at an observed line or bar (red) and an expected line or bar (gray) in the plots. How do their shapes differ?

Also, if you turn ROUTE-LIMITS on, what is the NUMBER-OF-INCOMPLETES? What is the successful chain rate? What is the incomplete rate? You can calculate the imcomplete rate as follows: (NUMBER-OF-INCOMPLETES + NUMBER-OF-DEADEND) / (SESSIONS - UNREACHABLE PAIRS).

THINGS TO TRY

First, you should try to switch between a random network and small-world network, and see how observed path lengths change.

Second, use the SEARCH-STRATEGY chooser. The different search strategies return different results of observed path lengths.

Third, using the ROUTE-LIMITS switch, see how a message is circulated within a network. Particularly, no route limit condition is barely able to be observed in the reality. Compared to no route limit condition, see how much the route limit condition chages observed path lengths.

EXTENDING THE MODEL

Try to change the number of message propagation. The current model is set one message at a time. However, circulating multiple messages is a reasonable scenario in the reality. For doing so, you may require to change some other procedures.

It is also possible to implement a memory for each agents, for instance, using the LevelSpace extension. This extension may enable to test how agents become better or worse at routing over time.

NETLOGO FEATURES

This model uses the NW extension to calculate path length, clustering coefficient and in-degree centrality for each node. However, for the average path length, it doesn't use the NW extension, but it returns the same result as a command of nw:mean-path-length in the NW extension.

RELATED MODELS

This model is based on Stanley Milgram's small-world experiment:

  • Milgram, S. (1967). The Small World Problem, Psychology Today, 2: 60-67.

  • Travers, J., & Milgram, S. (1969). An experimental study of the small world problem. Sociometry, 425-443.

In terms of the expected emergence patterns for this model:

  • Killworth, P. D., McCarty, C., Bernard, H. R., & House, M. (2006). The accuracy of small world chains in social networks. Social networks, 28(1), 85-96.

Also, this model extensively refers to in Models Library:

CREDITS AND REFERENCES

This model is developed by Kyosuke Tanaka at Northwestern University. If you have any questions or want to use this model not in your own use, please email at kyosuke [at] u.northwestern.edu.

Comments and Questions

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

Click to Run Model

extensions [
  nw
]

breed [nodes node]
breed [messages message]

messages-own [
  location ;;holds a node in which a message is
]

nodes-own[
  ;; Use Net
  target ;;target as a message destination
  ;; this RECEIVDED is not used well in this implementation
  ;; But this is useful to see which node is "actually used as a "hub"
  received ;;if a node received, add 1
  ;; Choose Net
  distance-to-other-nodes   ;; list of distances of this node to other turtles
  ;; Local Search
  localset ;; holds a local agentset
  ;; Homophily
  gender ;; gender to either 0 "male" or 1 "female"
]

links-own [
  used ;;if a message went through a link, add 1
]

globals [
  ;; Use Net
  origin ;;holds a starting node
  current-location ;; holds a node where a message is currently
  next-location ;; owns a node where a message goes next
  target-node ;;holds a target node
  unreachable ;;holds true/false
  number-of-unreachable ;;counts unreachable cases
  steps ;;holds count of steps
  steps-record ;;holds a list of steps per session
  min-pl-record ;; holds a list of min path length per session
  min-pl ;; holds min distance between the origin and target
  number-of-sessions ;;owns the count of sessions
  incomplete ;;holds the number of imcomplete cases
  incomplete-case ;;holds true/false
  deadend ;;holds true/false
  number-of-deadend ;;counts deadend cases
  actual-average-pl ;; average path length of the network
  number-of-neighbors ;; holds [out-link-neighbors] of location
  ;; Choose Net
  average-path-length ;; average path length of the network
  pl-list ;; list of distances of this node to other turtles
  unconnected ;; holds the number of unconnected pairs
  connected ;; holds the number of connected pairs
]

;;;;;;;;;;;;;;;;;;;;;
;; Setup Procedure ;;
;;;;;;;;;;;;;;;;;;;;;

to setup
  clear-all
  set-default-shape nodes "circle"
  create-nodes number-of-nodes [set color blue]
  ask nodes [
    create-links-to n-of number-of-links other nodes
    set target one-of other nodes
    set received 0
    set gender random 2 ;; set gender to either 0 "male" or 1 "female"
  ]
  layout
  message-setup
  ask target-node [
    set color red
  ]
  ask nodes [
    set localset (min-n-of 4 other nodes [distance myself]) ;; holds a turtles-own variable
  ]
  local-search
  link-setup
  ask origin [
    ifelse nw:distance-to target = False [
    set min-pl 0 ][
    set min-pl nw:distance-to target]
  ]
  set number-of-sessions 0
  set unreachable false
  set incomplete 0
  unreachable-setup
  set steps-record []
  set min-pl-record []
  ;; Choose Net
  find-path-lengths
  find-connected-pairs
  path-length-list
  find-average
  reset-ticks
end 

;;circle layout

to layout
  layout-circle (sort nodes) max-pxcor - 1
end 

to go
  if any? messages with [location = target-node][
    set steps number-of-steps
    set steps-record lput number-of-steps steps-record
    set min-pl-record lput min-pl min-pl-record
    set number-of-sessions number-of-sessions + 1
    target-resetup
  ]
  unreachable-setup
  if unreachable = true [
    set unreachable false
    set number-of-unreachable number-of-unreachable + 1
    set steps 0
    set steps-record lput 0 steps-record ;; tentatively assign 0 but INF should be more appropriate...
    set min-pl-record lput 0 min-pl-record
    set number-of-sessions number-of-sessions + 1
    target-resetup
  ]
  wrong-choice
  if deadend = true [
    set deadend false
    set number-of-deadend number-of-deadend + 1
    set steps 0
    set steps-record lput 0 steps-record;; tentatively assign 0 but INF should be more appropriate...
    set min-pl-record lput 0 min-pl-record
    set number-of-sessions number-of-sessions + 1
    target-resetup
  ]
  ask links [
    set thickness 0
    ask links with [used >= 1]
      [set thickness 0.3]
  ]
  message-procedure
  tick
end 

;;;;;;;;;;;;;;;;;;;;;;;
;; Use Net procedure ;;
;;;;;;;;;;;;;;;;;;;;;;;

;;mesasge procedure

to message-procedure
  ask messages [
    if not any? [out-link-neighbors] of location [
      stop
    ]
    set current-location location
    ;set upper limits of passing messages through links
    ifelse route-limits? [
      ;; 1 as an arbitrary limit
      let out-link-node [my-out-links with [(used < 1) and (self != myself)]] of current-location
      ifelse  count out-link-node > 1 ;;count out-link-node = number-of-links
      [set number-of-neighbors turtle-set [end2] of out-link-node
        if search-strategy = "random-search"
        [set next-location one-of number-of-neighbors] ;[out-link-neighbors] of location]
        if search-strategy = "local-search"
        [ls-strategy]
        if search-strategy = "homophilious-search"
        [homophily]
        if search-strategy = "preferential-attachment"
        [preferential]
      ]
      ;; if running out of available links a node can use, end the session
      [ifelse count out-link-node = 0
        [set incomplete incomplete + 1
        set incomplete-case true
        stop]
        [set next-location one-of turtle-set [end2] of out-link-node]
      ]
    ][
    set number-of-neighbors [out-link-neighbors] of current-location
      if search-strategy = "random-search"
      [set next-location one-of number-of-neighbors] ;[out-link-neighbors] of location]
      if search-strategy = "local-search"
      [ls-strategy]
      if search-strategy = "homophilious-search"
      [homophily]
      if search-strategy = "preferential-attachment"
      [preferential]
    ]
    let new-location next-location
    ;; change the thickness of the link as a message moves
    ask [out-link-to new-location] of location [set thickness 0.3 set used used + 1]
    face new-location ;; not strictly necessary, but improves the visuals a bit
    move-to new-location
    set location new-location
    ask location [
      set received received + 1 ;; increase received
    ]
  ]
  if incomplete-case = true [
    set number-of-sessions number-of-sessions + 1
    set incomplete-case false
    target-resetup
  ]
end 


;;new round setup

to target-resetup
  ask nodes [
    set target one-of other nodes
    ;set received 0
    set color blue
  ]
  ask messages [die]
  message-setup
  ask target-node [
    set color red
  ]
  link-setup
  ;unreachable-setup
  ask origin [
    ifelse nw:distance-to target = False [
    set min-pl 0 ][
    set min-pl nw:distance-to target]
  ]
  reset-ticks
end 

;;procedure for target

to message-setup
  create-messages 1 [ ;; TO DO: replace 1 to a slider
    set color orange
    set location one-of nodes
    set origin location
    set target-node [target] of location
    move-to location
  ]
end 

;;link weight

to link-setup
  ask links [
    set used 0
    set thickness 0
    ;ask links with [used >= 1]
      ;[set thickness 0.3]
  ]
end 

;;detect an unreachable case

to unreachable-setup
  ;;an empty means no path b/w the origin and target exists
  if empty? [nw:path-to target-node] of origin [
    set unreachable true
  ]
end 

;;critical mistakes of route choices
;;where a path to the target becomes no longer avaiable

to wrong-choice
  ask messages [
    ask location [
      if empty? nw:path-to target-node [
        set deadend true
      ]
    ]
  ]
end 

;; average simulated path length

to-report calculate-average
  let avg-pl filter [? != 0] steps-record
  set actual-average-pl (sum avg-pl) / (length avg-pl)
  report actual-average-pl
end 

to-report unreachable-pairs
  report number-of-unreachable
end 

to-report number-of-steps
  report ticks
end 

to-report sessions
  report number-of-sessions
end 

to-report incompletes
  report incomplete
end 

;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Choose Net procedure ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;

to path-length-list
  set pl-list []
  foreach sort nodes [
    let x [distance-to-other-nodes] of ?
    set pl-list sentence pl-list x
  ]
end 

;; calculate the number of unconnected pairs and connected pairs

to find-connected-pairs
  set connected 0
  set unconnected 0
  let i 0 ;;holds a target turtle number
  let node-count count nodes
  foreach sort nodes[
    ask ? [
      while [ i < node-count ]
      [ifelse ? = node i ;;if a turtle is the same as i, skip it
        [set i i + 1]
        [ifelse empty? nw:path-to node i ;;since if there is no path from a turtle to i, return an empty list
          [
            set i i + 1
            set unconnected unconnected + 1
          ]
          [set i i + 1
            set connected connected + 1]
        ]
      ]
    ]
   set i 0 ;;set the default again
  ]
end 

;; calculate distance from turtles to other turtles only if they are connected with each other

to find-path-lengths
  ask nodes
  [
    set distance-to-other-nodes filter [is-number? ?] [[nw:distance-to myself] of myself] of other nodes
  ]
end 

;; average path length

to find-average
  set average-path-length (sum [sum distance-to-other-nodes] of nodes) / (connected)
end 

to-report avg-path-length
  report average-path-length
end 

to-report unreachable-path
  report unconnected
end 

;; calculate global clustering coefficient

to-report clustering-coefficient
  let closed-triplets sum [ nw:clustering-coefficient * count my-links * (count my-links - 1) ] of nodes
  let triplets sum [ count my-links * (count my-links - 1) ] of nodes
  report closed-triplets / triplets
end 

;; local search implementation of small-world networks

to local-search
  if small-world? [
    ask links [die]
    ask nodes [
      ;; if NUMBER of links are below 4, use n-of for localset since localset includes 4 neighbors
      ifelse number-of-links <= 4 [
        create-links-to n-of number-of-links localset
        if (random-float 1) < rewiring-probability [
          let rewire one-of other nodes with [ (self != myself) and (localset != myself) ]
          ask one-of links [ die ]
          create-link-to rewire
        ]
      ]
      [create-links-to localset
        create-links-to n-of (number-of-links - 4) other nodes with [ (self != myself) and (localset != myself) ]
      ]
    ]
  ]
end 

;;;;;;;;;;;;;;;
;; Cognition ;;
;;;;;;;;;;;;;;;

;; local search strategy

to ls-strategy
  ;; this procedure gives local knowledge of who is the target to nodes
  ;; but nodes don't hold any knowledge of long nodes which are not in their local set
  ;; If nodes hold long nodes and they don't find the target in their localset, then they send a message to a long node
  ask nodes [
    let l1 sort-on [who] [localset] of current-location
    let l2 sort-on [who] number-of-neighbors
    let long-node filter [? != l1] l2
    ifelse member? [target] of origin number-of-neighbors [
    ifelse member? [target] of origin [localset] of current-location [
      set next-location [target] of origin][
        ;; since some nodes don't rewire, make sure whether nodes have links with long-distant nodes
        ifelse empty? long-node[
          set next-location one-of number-of-neighbors][
          set next-location item random length long-node long-node
      ]
    ]
    ][ifelse empty? long-node[
          set next-location one-of number-of-neighbors][
          set next-location item random length long-node long-node
          ]
    ]
  ]
end 

;; homophily search

to homophily
  ;; A node holding a message prefers to send the same gender neighbor as target's gender
  ;; if they don't have any neighbor's gender same as target's, then they randomly choose next destination in their link neighbors
  ask nodes [
    ifelse any? number-of-neighbors with [gender = [gender] of target-node] [
      ;; a 70 percent chance to choose a contact whose gender is the same as target
      ;; Otherwise, follow the random choice procedure
      ;; this random implementation is not parcilarly something I'm not proud of...
      ;; 70 is an abtraral number, but it works both with & without route limits
      ifelse random 99 < 70 [set next-location one-of number-of-neighbors with [gender = [gender] of target-node]][
        set next-location one-of number-of-neighbors]
    ][set next-location one-of number-of-neighbors
    ]
  ]
end 

;; preferential attachment search

to preferential
  ;; nodes look at maximum indegree neighbor as their next message destination
  ask nodes [
    set next-location max-one-of number-of-neighbors [count [in-link-neighbors] of self ]
  ]
end 

There are 5 versions of this model.

Uploaded by When Description Download
Kyosuke Tanaka almost 8 years ago Add descriptions on Info tab Download this version
Kyosuke Tanaka almost 8 years ago Tiny change Download this version
Kyosuke Tanaka almost 8 years ago Implement search strategies, clean up the code and add descriptions on Info tab Download this version
Kyosuke Tanaka almost 8 years ago created new plots and combined it with part of choose network Download this version
Kyosuke Tanaka almost 8 years ago Initial upload Download this version

Attached files

File Type Description Last updated
Use Network.png preview preview image almost 8 years ago, by Kyosuke Tanaka Download

This model does not have any ancestors.

This model does not have any descendants.