Oregon State University

Calendar

Calendars

Event Details

MS Final Examination – Theresa Migler-VonDollen


Thursday, June 20, 2013 12:00 PM - 2:00 PM

Decomposing a Network by Density
In the analysis of networks, certain network properties are of particular interest, including average path length, degree distribution, degree of clustering, assortativity, and betweenness centrality. In this paper we introduce a new analytical property of networks: the density signature. This signature comes from a decomposition of the vertices of the network. The density decomposition that yields the density signature is obtained by partitioning the vertices based on their indegrees given an egalitarian orientation of the network. An egalitarian orientation is an assignment of direction to the edges of the network such that the indegree is shared as equally as possible amongst the vertices given the topology of the network. We call these partitions rings.

We find that our density decomposition and signature provide unique insight into the structure of real networks. We use this property to analyze how well random networks model real networks. We find that the most commonly studied random networks don't have interesting density signatures. However, real networks do have interesting density signatures. We also find that, within the rings of the density decomposition, the clustering coefficient is higher than the clustering coefficient of the entire network, suggesting that the structure of the density decomposition illuminates clustering qualities of the network. We also find that with the density decomposition there is one ring that will always contain the vertices of the densest subnetwork of the network. Finally, we find that vertices are connected through the decompositions in a predictable way.

Major Advisor: Glencora Borradaile
Committee: Prasad Tadepalli
Committee: Eduardo Cotilla-Sanchez 


Kelley Engineering Center (campus map)
1003
Nicole Thompson
1 541 737 3617
Nicole.Thompson at oregonstate.edu
Sch Elect Engr/Comp Sci
This event appears on the following calendars: