| Random graphs and small world networks |
Experiment with the Watts-Strogatz small world model. See how different amounts of random rewiring affect the shortest path and clustering coefficient of the network:
Watts-Strogatz Small World NetLogo model |  |
Vary the average degree in the classic Erdos-Renyi random graph model. Is there a critical average degree at which a giant component emerges?
Giant Component Model (model is part of the standard NetLogo models library) | |
| Growing networks: |
Each node that joins the network has to decide what other node(s) it will attach to. It can do this purely at random, or it may prefer nodes who have more connections. Vary this preference and see the effect on the growing network.
Random and preferential attachment NetLogo model
| |
| Community structure: |
Use the Girvan-Newman betweenness clustering algorithm to discover community structure in the linking patterns of political blogs.
Betweenness clustering using Guess
| |
Find out how community structure can affect opinion formation.
Opinion formation on a toy network (NetLogo)
| |
| Diffusion: |
Start with a simple Erdos-Renyi random graph, and figure out how the density of the network affects the speed of diffusion.
Diffusion in an Erdos Renyi graph (NetLogo)
| |
Next, take a growing network, with and without preferential attachment. See how the tendency of new nodes to attach to well connected nodes influences the rate of spread:
Diffusion in randomly and preferentially grown networks (NetLogo)
| |
Find out how random rewiring affects the probability that an infection persists in the network using an SIS (susceptible-infected-susceptible) model.
Diffusion in a small world (NetLogo)
| |
Sometimes whether an opinion diffuses or not depends on the initial location where it is formed, and also whether one is dealing with simple contagion (each of your friends "infects" you with constant probability at each time point) or complex contagion (you need to hear it from at least two friends to adopt an opinion). This model is set up as a two-player game. Choose nodes in a small social network such that your opinion wins out.
Simple and complex contagion (NetLogo)
| |
| Information retrieval: |
Having high PageRank means that not only do others link to you, but those others are themselves linked to. Experiment by varying the teleportation probability in applying PageRank to a small network.
PageRank on a small network (Guess)
| |
Use LexRank, a PageRank based algorithm, to summarize text. This demo was written by Patrick Jordan based on the algorithm by Gunes Erkan and Dragomir Radev:
Text summarization using LexRank
| |
| Resilience: |
Many real world networks are scale free. See how the Gnutella peer-to-peer filesharing network holds up to random node failure and targeted attack on the highest degree nodes.
Testing the resilience of a Gnutella network (Guess)
| |
Study percolation on a regular lattice. Is there a critical threshold for the percentage of active nodes at which the lattice percolates (i.e. there is a giant component)?
Percolation on a square lattice (NetLogo)
| |
| Network games: |
Play a game of coordination on a small world topology. Each nodes tries to pick a different color than each of its neighbors.
Graph coloring in a small world topology (NetLogo)
| |
Play the iterated prisoners'' dilemma game on different topologies (model created by Ed Baskerville):
Game strategies and different topologies (NetLogo)
| |
| Search in networks: |
Find your way around on Kleinberg's small world lattice
Search in a small world (NetLogo)
| |