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. / Master of Science
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/35405 |
| Date | 31 October 2005 |
| Creators | Narayanan, Shivaram |
| Contributors | Computer Science, Murali, T. M., Marathe, Madhav V., Vullikanti, Anil Kumar S. |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
| Relation | thesis.pdf |
Page generated in 0.0023 seconds