Amherst College

SURF Program 2020

THE BIG QUESTIONS

Dynamics on Small World Networks

In 1998, Duncan Watts and Steve Strogatz formulated a paper describing a special type of network called the "small world network". According to their research, in such networks the mean shortest distance between nodes increases sufficiently slowly as a function of the number of nodes in the network. Small worlds also have a very high clustering coefficient because they have many clusters.

Small world properties can be found in many real life phenomena such as neural networks in the brain, electric power grids, food webs and popular social networks like Facebook. As such they form an ensemble of robust and important networks and an interesting phenomenon to study.

Wattz and Strogatz explained a rewiring process through which a regular lattice can be turned into a small world or a random network, by changing the probability, p, of rewiring edges. Most of our research centered on how SWN compare to random and regular networks.

The smallworldness of a network can be determined by a small coefficient, sigma. To calculate this, the clustering coefficient and characteristic path length are compared to an equivalent random network of the same average degree. However, this indice performance suffers when the network is large. Thus, the omega indice is a better quantifier of smallworldness. To learn more, click here.

Scale-free networks

A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. A scale-free network is described as any network whose degree distribution follows the power law where P(K) (the proportion of nodes in the network that are connected to k number of nodes) is proportional to k raised to the power of -y, where y > 1, usually between 2 and 3. Examples of scale-free networks are the world-wide web and electronic circuits.

Scale-free networks usually have large hubs, and as the network increases in size, the underlying structure of the network remains the same.

Spatial Networks

Spacial networks are networks in which the nodes and edges are arranged in space according to a certain metric. Examples include lattice graphs and random graphs. In this case, a graph with N nodes will have two nodes connected if the distance between them is smaller than a given value. Power grids and road maps are examples of real life spatial networks.

Read more about scale-free and spatial networks.

Average Temperature and Convergence time

For small networks, the time taken to reach equilibrium is roughly the same if the initial temperature is concentrated on the periphery versus the center of the network.

To understand how long it takes for a network to reach equilibrium, we can find the difference between the largest and the smallest temperature in any given network. That way, even if the network has a disconnect, the temperature difference will still converge to some value. This is shown in figure for a network of 100 nodes, using both the even and odd laplacian. Read more, here.

There are three primary parameter that are taken into consideration when modelling epidemics using graphs.

  • Contagion
  • Strategy
  • Topology

Thus, different graphs respond differently to epidemics. Generally, the more well connected a graph is, the faster the spread of an epidemic. To read more about the different factors used to model epidemics on graphs, click here.

Definiton

An SIR model is an epidemiological model that computes the theoretical number of people infected with a contagious illness in a closed population over time. One of the simplest SIR models is the Kermack-McKendrick model.

Assumptions of the Kermack-McKendrick model

  • Population size is fixed
  • Disease transmission is instantaneous
  • Homogenous population
  • Duration of infectivity synonymous with length of disease period

To learn more click here. To see an SIR model on a SWN stocastichally, go to visualizations.

Definiton

The SIS model assumes that the disease confers no long term / long lasting immunity for infected patients,which allows the disease to obtain a steady state. Infected patients, once recovered, return immediately to the susceptible population.

More information can be found here.

Since many of the graphs found in nature are small worlds, it is important to understand how epidemiology works on such networks, and how it compares to random networks.

We found that, keeping all else constant, increasing probability, p, of rewiring edges lead to a higher peak value of infections and less time to reach that peak value for small world networks. The same behavior was exhibited by random networks. To read more, click here.

3-min Flash Talk

Summer 2020 REU Presentation