"Taxonomies of Networks from Community Structure"

Well, this paper has certainly taken a while to finally appear in final form. The project started in December 2007 as Stephen Reid's senior thesis project from the winter 2008 term. We put the first version of the just-published paper on the arXiv preprint server in June 2010. Here are more details.

Title: Taxonomies of Networks from Community Structure

Authors: Jukka-Pekka Onnela, Daniel J. Fenn, Stephen Reid, Mason A. Porter, Peter J. Mucha, Mark D. Fricker, and Nick S. Jones

Abstract: The study of networks has become a substantial interdisciplinary endeavor that encompasses myriad disciplines in the natural, social, and information sciences. Here we introduce a framework for constructing taxonomies of networks based on their structural similarities. These networks can arise from any of numerous sources: They can be empirical or synthetic, they can arise from multiple realizations of a single process (either empirical or synthetic), they can represent entirely different systems in different disciplines, etc. Because mesoscopic properties of networks are hypothesized to be important for network function, we base our comparisons on summaries of network community structures. Although we use a specific method for uncovering network communities, much of the introduced framework is independent of that choice. After introducing the framework, we apply it to construct a taxonomy for 746 networks and demonstrate that our approach usefully identifies similar networks.We also construct taxonomies within individual categories of networks, and we thereby expose nontrivial structure. For example, we create taxonomies for similarity networks constructed from both political voting data and financial data. We also construct network taxonomies to compare the social structures of 100 Facebook networks and the growth structures produced by different types of fungi.



And as an extra note, this paper includes the following line: "Moreover, the Louvain and simulated-annealing algorithms are much more popular than spectral algorithms in investigations of community structure [14] (and life is short), so we only compare results using the Louvain and simulated-annealing algorithms for the remainder of this appendix."

Update (9/23/12): Nick Jones has now described this paper on the blog he writes for his research group.