SNA EXP5
Name:- Jatin Pareek
SAPID:- 60019210026
ROLLNO:- T013
Branch:- CSE(ICB)
1. Introduction
The Watts-Strogatz (WS) model is a well-known framework in network science, used to
generate small-world networks. It was introduced by Duncan J. Watts and Steven H. Strogatz
in 1998. Small-world networks are characterized by a combination of high clustering (nodes
tend to be highly connected to their neighbors) and short average path lengths (there are
relatively few steps between any two randomly chosen nodes). These networks are seen in
various real-world systems, such as social networks, biological networks, and communication
systems.
2. The Watts-Strogatz Model
The Watts-Strogatz model creates networks with the following properties:
n: The number of nodes in the network.
k: Each node is initially connected to k nearest neighbors (this can be seen as a ring-
lattice structure where each node is connected to its k nearest neighbors).
p: The probability of rewiring each edge in the network. A rewired edge connects to a
random node in the network instead of its original neighbor, introducing randomness
and reducing the average path length.
The WS model proceeds as follows:
1. Start with a regular ring lattice where each node is connected to k neighbors.
2. Rewire each edge with probability p. If an edge is rewired, it is connected to a
randomly chosen node, breaking the regular structure and creating randomness in the
network.
3. The result is a small-world network where clustering is high (nodes tend to have many
of their neighbors connected to each other) and the average path length is short (the
number of steps between two randomly chosen nodes is small).
3. Key Parameters
n (Number of Nodes): This is the total number of nodes in the network. The size of
the network influences the overall connectivity and the average path length.
k (Number of Nearest Neighbors): Each node in the network is initially connected
to k nearest neighbors. This parameter defines the density of the initial network and
determines the average degree of each node.
p (Rewiring Probability): This controls the degree of randomness in the network.
When p=0, the network is a regular ring-lattice, with each node connected only to its k
nearest neighbors. As p increases, more edges are rewired, introducing randomness
and reducing clustering.
4. Clustering Coefficient
The clustering coefficient of a node measures the extent to which the node’s neighbors are
connected to each other. The clustering coefficient of a network is the average of the
clustering coefficients of all nodes. In the case of the Watts-Strogatz model, this coefficient
tends to remain high even as p increases, meaning that local neighborhoods are still highly
interconnected even in the presence of randomness.
Clustering Coefficient Formula: For any node i, the clustering coefficient C_i is
calculated as:
Ci=2×number of triangles involving inumber of connected triplets of neighbors of iC_
i = \frac{2 \times \text{number of triangles involving } i}{\text{number of connected
triplets of neighbors of } i}Ci
=number of connected triplets of neighbors of i2×number of triangles involving i The
clustering coefficient for the whole network is the average of C_i for all nodes.
5. Network Visualization
Visualization plays a crucial role in understanding the structure and properties of a network.
For the Watts-Strogatz model, visualizing the network helps to see the regular lattice
structure at low p values and the more random structure as p increases. The layout of nodes
can be adjusted using different algorithms to better represent the network's topological
features.
6. Practical Implementation
In the implementation of the Watts-Strogatz model, the following steps are performed:
1. Network Generation: The networkx library in Python is used to generate a Watts-
Strogatz graph using the watts_strogatz_graph() function, with specified values of
n, k, and p.
2. Clustering Coefficient Calculation: The average clustering coefficient of the
network is computed using the average_clustering() function from networkx.
3. Visualization: The matplotlib library is used to plot the generated network, with
options to customize the layout and appearance of the nodes and edges.
Explanation of the Code
1. Parameters: The number of nodes n, the number of nearest neighbors k, and the
rewiring probability p are defined at the beginning.
2. Network Generation: The Watts-Strogatz network is generated using the
watts_strogatz_graph() function from the networkx library.
3. Clustering Coefficient: The average_clustering() function computes the average
clustering coefficient of the network.
4. Network Visualization: The spring_layout() function is used to position the
nodes, and nx.draw() is used to render the network with customized colors and node
sizes.
7. Results and Discussion
The clustering coefficient of the network provides insight into how interconnected the
neighbors of nodes are. In a Watts-Strogatz small-world network, as the rewiring probability
p increases, the average path length decreases, and the network becomes more "random."
However, the clustering coefficient remains relatively high even at higher values of p, a key
feature of small-world networks.
Visualization of the network provides an intuitive understanding of how node connections
evolve as the network transitions from a regular structure (low p) to a random network (high
p). The layout and appearance of the network can be adjusted to highlight different
properties, such as node degree or community structure.
8. Conclusion
The Watts-Strogatz model is a fundamental tool in network science that successfully captures
the small-world phenomena observed in many real-world networks. It combines the
advantages of both regular lattices and random graphs, showing high clustering and short
path lengths. The model has widespread applications in various domains, from social
networks to biological systems. By implementing and analyzing the Watts-Strogatz model,
we gain valuable insights into the structure and behavior of complex systems.
