Message-ID: <1702667071.137.1611490156381.JavaMail.root@wiki.cns.iu.edu> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_136_1923917271.1611490156380" ------=_Part_136_1923917271.1611490156380 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html Watts-Strogatz Small World

# Watts-Strogatz Small World

=20

From Wikipedia

=20
###### Pros & Cons
=20

It is a well known model, whose properties are by now quite well underst= ood. It can be used to generate networks of any size. The degree distributi= on is Poissonian for any value of the rewiring probability (except in the e= xtreme case of rewiring probability zero, for which all nodes have equal de= gree), the clustering coefficient is tunable.

=20
###### Applications
=20

It is usually studied to explore networks with tunable values for the av= erage shortest path between pairs of nodes and the clustering coefficient. = Networks with small values for the average shortest path and large values f= or the clustering coefficient are supposed to simulate social networks.

= =20
###### Implementation De= tails
=20

The algorithm requires three inputs: the number of nodes of the network,= the number k of initial neighbors of each node on the two sides of the net= work (the initial configuration is a ring of nodes) and the probability of = rewiring the edges (which is a real number between 0 and 1). The network is= built following the original prescription of Watts and Strogatz, i.e. by s= tarting from a ring of nodes each connected to the k nodes to their right/l= eft and by rewiring each edge with the specified probability.
The algor= ithm runs in a time O(kn), where n is the number of nodes of the network.=20

###### Usage Hints
=20

As an exercise, one could try to build a small world network with 1000 n= odes, 10 initial neighbors per side and a rewiring probability of 0.01. Aft= er the network file has been produced, one could select it and apply on it = the two algorithms on the average shortest path and the clustering coeffici= ent, to verify that the former is small and the latter is still relatively = large.

=20
###### Acknowledgements
= =20

The algorithm was implemented and documented by S. Fortunato, integrated= by S. Fortunato and W. Huang. For the description we acknowledge Wikipedia= .

=20
###### References
=20

Watts, D.J., Strogatz, S.H.(1998) Collective dynamics of 'small-world' networks. Nature 393:440-442= .

=20