Presentation By
Rohan Railkar Small-World Networks

Small-World Graphs :

Small-World Graphs Most nodes are NOT neighbours of each other; but most nodes can be reached from every other by a small number of steps
Random graphs: (i)small mean shortest path & (ii)small clustering coefficient
Small-World graphs: (i)small mean shortest paths & (ii)high clustering coefficient
These two are the necessary & sufficient characteristics of small-world graphs

Properties of Small-World Networks :

Properties of Small-World Networks Consist of considerable number of cliques & subgraphs that are few edges shy of clique
Over abundance of “hubs”
Fat-tailed distribution- enriched degree-distribution at higher values of distribution
Power law distribution is a small-world network
Also, other topologies can be small-world if they satisfy the two properties

Examples of SW Networks :

Examples of SW Networks Social networks: Milgram’s famous Small-World experiment, social influence network, Six degrees of Kevin Bacon, Erdõs number & XING- 5/6 degrees of separation from most members (a functioning large small-world network that can be viewed and analyzed by anyone)
Business networks: power grids, road-maps, flight networks, railroads
Natural networks: foodchains, neural network of the worm C. Elegans, network of interacting proteins & transcriptional networks consisting of genes

Construction of SW Graph :

Construction of SW Graph Preferential Attachment- new nodes are added to a pre-existing network, and connected to each of the original nodes with a probability proportional to the number of connections each of the original nodes already had
Statistically, this method will generate a power-law distributed small-world network (i.e. a scale-free network)

Pros & cons of SW networks :

Pros & cons of SW networks In dynamic systems; enhanced signal-propagation speed, computational power & synchronizability
Viral infections spread more easily & rapidly in SW networks (computers as well as biological/social networks)
Deletion of peripheral node does not cause dramatic increase in mean shortest path or dramatic decrease in clustering coefficient
Vice versa in case of deletion of a hub node, i.e. SW networks are vulnerable to targeted attacks on hubs
Random networks cannot be targeted for catastrophic failure, but deletion any node in random graph always causes a slight but significant increase in mean-shortest path length

Simple model of SW network :

Simple model of SW network SW network systems are highly clustered like regular lattices & have characteristic small mean-short path lengths like random graphs
In 1998, Watts & Strogatz proposed that a simple model for SW network can created by interpolation between regular lattice and random graph
“Random rewiring” procedure is followed

Rewiring technique :

Rewiring technique Regular ring lattice: n vertices, k edges per vertex, each edge is rewritten with probability p
L(p) characteristic path length & C(p) clustering coefficient
Graph has many vertices with sparse connections but not too sparse so that the graph becomes disconnected,
Specifically, n » k » ln(n) » 1
In a regular lattice, large C is associated with large L and small C is associated with small L
But over a finite interval of p, L(p) is almost as small as Lrandom yet C(p) » Crandom – Small-World

Rewiring (contd.) :

Rewiring (contd.) As p is increased, there is non-linear immediate drop in L(p) as a few links are rewired, i.e. short-cuts are introduced
On the contrary, drop in C(p) is very small & usually undetectable
This typical behaviour is observed when rewired edges connect those vertices that were originally far apart
When (i) film actors, (ii) power grid & (iii) neural network of C.Elegans are compared with corresponding random graphs with same n & k, the basic SW properties of L = Lrandom & C » Crandom are observed

Functional significance :

Functional significance Taking an example of a infectious disease; r the probability that a node is infected in unit time for which its neighbour is infected & is to be quarantined
rhalf decreases rapidly for small p
For infections able to infect entire population, T(p) time required for global infection resembles the L(p) curve
SW properties can be used to draw many important inferences for varied problems like cellular automata, iterative multi-player Prisoner’s dilemma & coupled phased oscillators

References :

References “Collective Dynamics of Small-World Networks” – Duncan J. Watts & Steven H. Strogatz; Nature vol. 393 (June’ 98); MacMillan Pub. Ltd.
Wikipedia.Org

Thank you. :

Thank you.

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

Send to Blogs and Networks

Processing ....

Premium member

Use HTTPs

HTTPS (Hypertext Transfer Protocol Secure) is a protocol used by Web servers to transfer and display Web content securely. Most web browsers block content or generate a “mixed content” warning when users access web pages via HTTPS that contain embedded content loaded via HTTP. To prevent users from facing this, Use HTTPS option.