Skip Navigation

Document Information

A Multi-Resolution Approach to Characterize the Connectivity Structure and Evolution of Large Graphs
Soheil Jamshidi
Committee: Reza Rejaie (chair), Daniel Lowd, Hank Childs
Directed Research Project(Jun 2016)
Keywords: Graph evolution, Social network analysis

Graphs are widely used to represent the structure of large networked systems such as Online Social Networks (OSN). These graphs have a large number of evolving nodes (i.e., users) and edges (i.e., relationships). It is important to have practical methods to capture and characterize the connectivity structure and evolution patterns of such networks to gain insights about the corresponding system. However, existing techniques for graph analysis have limited scalability, offer limited insight about graph structure, and often do not capture the graph evolution.

In this study, we present a new multi-resolution method to characterize the connectivity features and evolution of large graphs. The main idea is to divide the graph into a manageable number of meaningful elements and characterize inter and intra-element connectivity. We focus on the subgraphs of high degree nodes, i.e., core nodes, and identify the community of core nodes, i.e., core communities, as the main elements of the graph. This method allows us to perform the following analysis:
  1. spatial analysis to determine how the size of core subgraph affects the number and characteristics of core communities which control the resolution of our analysis,
  2. temporal analysis to characterize the evolution patterns of the core communities over time, and
  3. spatiotemporal analysis to relate the spatial and temporal analysis. We use 14 snapshots of Google+ OSN to illustrate the capabilities of our approach.