Watts Strogatz Small World Model

Get Complete Project Material File(s) Now! »

Chapter 3 Graph Generation Models

A biological network such as a protein-protein interaction or a synthetic lethal interaction network can be represented as an undirected graph G = (V; E), where V is the set of vertices and E is the set of edges. Vertices in such a graph represent proteins while edges represent interactions between the proteins. Let G have n vertices and m edges. Let N_v be the set of neighbours of a vertex v. Let d_v = jN_v j be the degree of vertex v. Researchers have observed that networks such as the Internet, citation patterns in scienti c papers and some biological networks are scale free.⁶ A network is scale-free, if its degree distribution follows a power law i.e., the probability P (k) that a vertex in the network has degree k is proportional to k for some > 0. A graph generation model is an algorithm or certain steps to follow, so that we may generate graphs with certain properties. The different graph generation models suggested for complex networks such as biological networks that show the scale-free property have been described in the following sections.

Erdos¤-Renyi· Model

Although the Erdos¤-Renyi· model was not initially proposed to explain the evolution or structure of biological networks, we include it since it is a well studied model for the generation of random graphs. An Erdos¤-Renyi· graph G(n; p) is a graph with n vertices such that the probability of having an edge (u; v) in G is p for any vertices u and v in G.²⁶
Although the Erdos¤-Renyi· model is a well studied model, it does not fully capture the features exhibited by biological networks. The presence of many highly connected hubs is a feature that is observed in biological networks. An Erdos¤-Renyi· graph is unlikely to have such a property, since the probability of occurrence of every edge is the same.

Barabasi· Albert Model

Barabasi· and Albert⁶ conjecture that the scale free property of complex networks arises because:

1. the network grows with the addition of more vertices and
2. a new vertex preferentially attaches itself to vertices with high degree.

The propose a growth based model²⁷ in which a new vertex is created at each time step and the newly arrived vertex preferentially attaches itself to existing vertices with higher degree. Therefore in this case vertices with higher degree have a higher probability of connecting to the new vertex. The probability p_v of creating an edge between an existing vertex v and the newly added vertex is
p_v  = (d_v + 1)=(jEj + jV j)
where jEj and jV j are, respectively, the number of edges and vertices currently in the network (counting neither the new vertex nor the other edges that it is incident on).
Due to preferential attachment, a vertex with a higher degree will continue to increase its connectivity at a higher rate, this does explain the presence of hubs in such networks.

 Watts Strogatz Small World Model

The small world model is a graph generating model proposed by Watts and Strogatz.⁹ Graphs which have the small world property have low characteristic path lengths i.e., the average distance between any two vertices in the graph is small and also high clustering coef cient. The algorithm to generate a graph takes as input a regular graph with n vertices with k edges incident on each vertex and a probability p. The algorithm chooses an edge at random with probability p, then one of the end points of the edge is changed to another vertex, again chosen at random.

Eppstein Wang Model

Eppstein and Wang²⁸ proposed a steady state method for generating scale-free networks. A steady state model is not a growth based model i.e., the model does not involve the addition of new vertices or edges. The input to the algorithm is the number of edges m, the number of verices n and a model parameter r. The model starts by generating a graph with n vertices and m edges, by randomly adding edges between the vertices until there are m edges. The algorithm then modi es the initial graph by executing the following sequence of steps r times:

1. Pick a vertex v at random. Repeat this step until d_v > 0
2. Pick an edge (u; v) 2 G at random
3. Pick a vertex x at random.
4. Pick a vertex y proportional to degree of y.
5. If (x; y) is not an edge and if x is not y, then add edge (x; y) to G and remove edge (u; v) from G.

This is a simple model for generating scale-free networks, because it produces a power-law graph without the addition of extra vertices and edges, by evolving the existing graph while maintaining the same number of edges and vertices. Eppstein and Wang simulated the model on graphs with different sizes and different densities, where density = m=n. Each simulation was performed ve times and the model parameter r was chosen to be 107. The degree distribution was observed to converge to a power law distribution as the value of r increased, for many sizes and densities of the graph.

1 Introduction 
1.1 Motivation
1.2 Contributions Of This Thesis
1.3 Readers Guide
2 Properties Of Biological Networks 
2.1 Biological Experiments
2.2 Biological Datasets
2.3 Previous Results
3 Graph Generation Models 
3.1 Erd¨os-R´enyi Model
3.2 Barab´asi Albert Model
3.3 Watts Strogatz Small World Model
3.4 Eppstein Wang Model
4 Betweenness Centrality 
4.1 Denition
4.2 Applications
5 Algorithms For Computing Betweenness Centrality 
5.1 Background
5.2 Brandes Vertex Betweenness Algorithm
5.3 Newman Edge Betweenness Algorithm
6 Results 
6.1 Vertex Betweenness
6.2 Edge Betweenness
6.3 Randomized Analysis
6.4 Random Graphs with Similar Degree Distribution as the Biological Networks
6.5 Further Analysis on Random Graphs
7 Conclusions 
Bibliography
GET THE COMPLETE PROJECT
The Betweenness Centrality Of Biological Networks