Networks -- Robin Koytcheff, April 6, 2004

<p>

Recently, statistical physicists have been interested in accurately 
modeling real-world networks (i.e., graphs). However, many of these 
attempts have considered one or at most a handful of network features 
such as degree distribution or mean distance. Over the summer (as part 
of the VIGRE program), my research group developed a technique for 
determining which models best simulate certain real-world networks. 
It involved using a new "words" method, in which words are constructed 
out of operators on the adjacency matrix of a graph. These words correspond 
to walks in the graph and thus to subgraphs to some extent. Each word 
evaluates to a scalar for a given graph and can be considered as a 
feature of the network, giving high-dimensional data for a real network 
or an implementation of a model. We then used Support Vector Machines 
(a technique from machine learning) to classify this high-dimensional 
data. A key advantage of this technique is that important features 
are not selected a priori as in many models. Our final results were 
classifications of real networks according to which of a number of 
the models from the literature best simulated them.