Title: Comparing networks using their fine structure

Authors: Owen Macindoe; Whitman Richards

Addresses: CSAIL – 32-G585, Massachusetts Institute of Technology, Cambridge, MA 02139, USA. ' CSAIL – 32-G585, Massachusetts Institute of Technology, Cambridge, MA 02139, USA

Abstract: We introduce a novel technique for characterising networks using the structure of their sub-graphs, which we call the network|s fine structure. To judge the similarities between networks we use the earth mover|s distance between the distributions of features of their constituent sub-graphs. This technique is an abstraction of graph edit-distance. Given these similarity measures we explore their use in hierarchical clustering on several networks derived from a variety of sources including social interaction data.

Keywords: social network analysis; network comparison; graph similarity; social computing; social networking; sub-graphs; similarity measures; hierarchical clustering; social interaction data; social networks.

DOI: 10.1504/IJSCCPS.2011.043605

International Journal of Social Computing and Cyber-Physical Systems, 2011 Vol.1 No.1, pp.79 - 97

Available online: 28 Oct 2011 *