Small-World Networks

Views:
 
Category: Entertainment
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

Small-World Networks : 

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.

authorStream Live Help