Title page for ETD etd-10162005-200707

Type of Document

Master's Thesis

Author

Narayanan, Shivaram

Author's Email Address

shivaram@vt.edu

URN

etd-10162005-200707

Title

The Betweenness Centrality Of Biological Networks.

Degree

Master of Science

Department

Computer Science

Advisory Committee

Advisor Name	Title
Murali, T. M.	Committee Chair
Marathe, Madhav V.	Committee Member
Vullikanti, Anil Kumar S.	Committee Member

Keywords

Betweenness centrality
Vertex Betweenness
Edge Betweenness
Power law
Biological networks

Date of Defense

2005-09-16

Availability

unrestricted

Abstract

In the last few years, large-scale experiments have generated genome-wide protein interaction networks for many organisms including Saccharomyces cerevisiae (baker's yeast), Caenorhabditis elegans (worm) and Drosophila melanogaster (fruit fly). In this thesis, we examine the vertex and edge betweenness centrality measures of these graphs. These measures capture how "central" a vertex or an edge is in the graph by considering the fraction of shortest paths that pass through that vertex or edge. Our primary observation is that the distribution of the vertex betweenness centrality follows a power law, but the distribution of the edge betweenness centrality has a Poisson-like distribution with a very sharp spike. To investigate this phenomenon, we generated random networks with degree distribution identical to those of the protein interaction networks. To our surprise, we found out that the random networks and the protein interaction networks had almost identical distribution of edge betweenness. We conjecture that the "Poisson-like" distribution of the edge betweenness centrality is the property of any graph whose degree distribution satisfies power law.

Files

Filename		Size	Approximate Download Time (Hours:Minutes:Seconds)
Filename		Size	28.8 Modem	56K Modem	ISDN (64 Kb)	ISDN (128 Kb)	Higher-speed Access
	thesis.pdf	1.07 Mb	00:04:57	00:02:32	00:02:13	00:01:06	00:00:05