††††††††††††† METHODS FOR CHARACTERIZING MASSIVE NETWORKS

 

Brian Cloteaux

In Collaboration with Isabel Beichl and Francis Sullivan

 

A type of data of increasing importance in information technology is one that is based not on floating point values but rather on connections between objects which can be modeled as massive graphs or networks. These complex systems arise in many areas such as the power grid, the Internet, communications and transportation networks, situations where resources are delivered through restricted channels and where reliability is crucial. The size of these objects makes exact measurement impossible. We are in the process of building novel computational tools to generate meaningful statistics about real networks that will characterize these networks and yield measures of reliability.

 

We have developed Monte Carlo methods based on sequential importance sampling to count the number of spanning trees of a graph along with all sub-forests with k edges for each k. There already exists a method to count all spanning trees of a graph, which uses the determinant of a particular matrix. This is impractical for the size of network we are measuring. However, it has allowed us to test our methods on smaller data.† We have also tested our method on examples for which the determinant method cannot be used, the autonomous systems (AS) level data of the Internet.† This is a graph with 24566 nodes and 102946 edges obtained from the UCLA database.

 

We have used this information to compare the results with a random graph having the same degree sequence as the original data. The random graph with a given degree sequence was generated by a program written by one of us based on the Blitzstein-Diaconis method. The object was to determine the validity of results obtained by generating random graphs that are "similar" to actual data. The random graph approach to modeling real data is widely used by some research groups. Our preliminary conclusion is the unsurprising but important one - random graphs don't capture important details contained in real data.

 

Author Information

††††††††††† †Name:††††††††††††††††††††††† Brian Cloteaux

††††††††††† Mentorís name:††††††††††† Isabel Beichl

††††††††††† Division:†††††††††††††††††††††† Mathematical and Computational Sciences Division (891)

††††††††††† Laboratory:††††††††††††††††† ITL

††††††††††† Room/Building: †††††††††† B153/225

††††††††††† Mail Stop:††††††††††††††††††† 8910

††††††††††† Telephone #:††††††††††††††† 301-975-5264

††††††††††† Fax #:††††††††††††††††††††††††† 301-975-3553

††††††††††† Email:††††††††††††††††††††††††† brian.cloteaux@nist.gov

††††††††††† Sigma Xi:†††††††††††††††††††† not a member

††††††††††† Category:†††††††††††††††††††† Mathematics