STUDENT PROJECTS

Introduction

Small World Networks:
Small world networks, first introduced by D. J. Watts and S. H. Strogatz in “Collective Dynamics of ‘Small-World’ Networks” [1], represent a connection topology that straddles randomness and regularity. Because this system exhibits properties of both random and regular systems, small- world networks are capable of accurately representing many real world systems, including the power grid in the Western United States, the spread of communicable diseases throughout a community, and the dynamics of social networking in a business environment.

In quantifying the transformation between regular and small-world networks, we must first define a network size, N, and a small-world probability, p. N represents the number of units in the system, while p represents the number of units that will have connections cut and then reattached at random. This probability p is a key factor in discriminating between regular, small-world, and random systems.

Each unit, or node, has four neighbors in the regular system. Let i represent the unit number of interest. In a regular, one-dimensional system, i’s neighbors are i-2, i-1, i+1, and i+2 for 2 < i <= N-2. For the endpoints, the system wraps around in a circular fashion, as depicted in Figure 1. Following Watts and Strogatz’s reasoning, we define the system’s characteristic path length, L(p), and clustering coefficient, C(p), as follows. Let d(i, j) be the length (in edges) of the shortest path between two units i, j in the system. The characteristic path length is the average of d(i, j) over all pairs (i, j) of units in the system. Let v be the number of neighbors assigned to a given unit i. Then c = v(v-1)/2 is the maximum possible number of edges between this set of neighbors – in other words, if all the neighbors of unit i are also neighbors of each other, the number of edges, or connections, between this set of neighbors is c. The clustering coefficient, C(p), is the ratio between the actual number of edges between each set of neighbors and the maximum number c, averaged over all units in the system. In a regular network, where the small-world probability p = 0, C(p) and L(p) are both at a maximum. In a small-world network, where 0 < p < 1, C(p) remains high, while L(p) is low, as depicted in Figure 2. This means that they behave like regular networks locally, but exhibit random features globally. [2]

Critical Sensitivity:
The earth’s crust can be treated as a regular, two-dimensional network. In simulations using this model, critical sensitivity is a term which is applied to a system that demonstrates a large change in energy released per broken unit near a catastrophic transition (see Figure 3). The simulation of interest to this author is called the Cluster Mean Field (CMF) model, in which the stress of broken units is redistributed evenly over neighboring intact clusters such that the stress on each node in an intact cluster is the same. Using this model, Xia et al. were able to exhibit evidence of critical sensitivity in the earth’s crust. [3]

Critical sensitivity may useful in predicting when earthquakes are most likely to occur. Thus, if small world networks could also be shown to exhibit critical sensitivity, this idea could be used to predict systems that can be represented as such. In other words, if the concept of critical sensitivity can be applied to small-world or scale-free networks, decidedly unpredictable systems – like the stock market – could become somewhat predictable.

To begin the simulation, Xia et al. randomly assign an initial strength σ_ci to each unit N using a Weibull distribution function with a mean of 1 and a modulus 2, denoted h(σ_c). The system is described by the damage pattern, X = {xi, i = 1, 2, … N}, where x = 0 indicates an intact unit and x = 1 indicates a broken unit, the stress pattern Σ = {σ_i, i = 1, 2, … N}, and the initial strength pattern Σ_c={σ_ci, i = 1, 2, … N}. For an intact unit, x = 0, while x=1 indicates that the unit is broken, and σ_i is the stress on the unit at the time of measurement. Each unit breaks when the stress σ_i is greater than the initial strength of the unit. The program iterates, redistributing the stress from broken units according to the Cluster Mean Field Model and re-computing the number of units broken until the number broken is equal to N. For each unit broken, the energy released to the system (given by E=σ_i², where σ_i is the stress on the broken unit) is recorded. [3]

Transforming a regular network into a small-world network

To test for critical sensitivity in small world networks, we first wrote a program in C++ that transformed the regular, one-dimensional network into a one-dimensional small-world network. To do this, we first created a symmetric N x N matrix, where N is the number of units in our system. As illustrated in Figure 4(a), each row was assigned to one unit, and entries of 1 indicated a connection between that row’s unit and the unit corresponding to the column number, while 0’s indicated that there was no connection between the two. For each connection, we generated a random number. If this number was less than or equal to the p value of the system, that connection was broken (the entry was placed with a zero), and a new random number was generated. This new random number represented a new connection, and conditions were placed such that a unit could not be connected with itself, or be reunited with the unit it was previously associated with. As depicted in Figure 4(b), the transformed matrix is similar to the regular network matrix and is necessarily symmetric, but has a few irregularities.

To ensure that the network we created was indeed a small world network, we modified a program for calculating the characteristic path length and clustering coefficients for various p values, and averaged over several trials. To calculate L(p), our program systematically chose two units, and determined the shortest path length between them by cycling through one unit’s system of neighbors and finding the minimum number of neighbors it had to go through to reach the second unit. After this had been computed for each pair in the network, we averaged all the values. To determine C(p), we computed the number of shared neighbors between two units for all pairs in the system, and averaged these values.

Testing for critical sensitivity

After creating the small-world network, we then assigned an initial strength i to each unit using a random number x and the Weibull distribution function, given by h(x) = 2x*exp(-x²). We followed the procedure Xia et al. used for testing for critical sensitivity: the program generated initial stress values randomly, and if the initial stress was greater than the initial strength for any unit i, it let x_i become 1. It then computed the energy released for each broken unit, and recorded this value and the corresponding number of broken units in an output file. After recording the energy release, it redistributed the stress of the broken unit to the neighboring intact clusters by increasing the stress by the total stress of the broken unit divided by the number of intact units in the neighboring clusters. Because the system was small-world rather than regular, we used the symmetric matrix we created to keep track of the locations of the neighboring intact clusters.

Results

As shown in Figure 5, L(p) and C(p) followed the same trend presented by Watts and Strogatz [1], as expected. Because of this agreement with the Watts-Strogatz model, we concluded that our program successfully created a small-world network. The irregularities in the L(p) curve are most likely due to the small number of units we used for this test, but for our purposes, N = 330 was sufficient for this test.

In order to test our CMF simulation, we began taking energy release data for a regular network (for p = 0). These tests did not allow us to conclude that our program was effective, as the point at which critical sensitivity was reached in Xia et al.’s research was more defined for a network composed of the same number of units. [3] In our case, we can see a relative increase in the energy released just before 100 units have been broken, as shown in Figure 6, but we would need time to perform more tests to ensure that the simulation is behaving as expected.

Because we were unable to establish the effectiveness of our simulation for a regular system, we could not draw any definite conclusions about whether or not critical sensitivity occurs in small world systems.

With more time and programming expertise, this question may be answerable, and in fact could be extendable to similar network models. Because these models are widely applicable to physical, economical, and social networks, a greater understanding of their behavior under stress would provide insight into systems that are macroscopically difficult to predict.