Investigating the fine grained structure of networks

In this thesis I explore a novel representation for characterizing a graph's fine grained structure. The key idea is that this structure can be represented as a distribution of the structural features of subgraphs. I introduce a set of such structural features and use them to compute representations for a variety of graphs, demonstrating their use in qualitatively describing fine structure. I then demonstrate the utility of this representation with quantitative techniques for computing graph similarity and graph clustering. I show that similarity judged using this representation is significantly different from judgements using full graph structural measures. I find that graphs from the same class of networks, such as email correspondence graphs, can differ significantly in their fine structure across the institutions whose relations they model, but also find examples of graphs from the same institutions across different time periods that share a similar fine structure.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2010

Author dc:creator

• Macindoe, Owen

Advisor dc:contributor.advisor

• Whitman Richards.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/60103

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/60103