Multi-resolution analysis of connectivity and evolution in huge graphs

Soheil Jamshidi Researcher:  
Soheil Jamshidi

Graphs are used in different domains to represent the structure of networked systems. Topology of the Internet, connectivity of users in large online social networks (OSN) such as Twitter and Google+ and also biological networks are a few examples of these domains. These graphs not only have huge number of nodes, but also evolve with time. For example, in an online social network, new users may join the network and build relationship with other users which will add more nodes and also edges to the system. On the other hand, current users may end some of their relationships as a response to real world events or even deactivate their accounts. So nodes and edges may reduce over time. Characterizing such huge graphs provides insight about the structure of the system. Furthermore, since they are inherently evolving as nodes and edges are added or removed, characterizing such changes also illustrates how these systems evolve over time. Having millions of nodes and billions of edges forces us to use scalable and efficient methods to explore the graphs and characterize the structure and the way they are changing. Therefore, instead of focusing on single nodes, we need to have a coarser view of the graph to be able to analyze the inter connectivity of higher level components and track their changes as graph evolves.

Key Idea : Examining the connectivity structure of the graph at multiple resolutions

We consider three resolutions from coarse to fine as follows: Region -> Community -> Node.
Each graph consists of a few regions where each regions is composed of many communities, and each community has a collection of nodes
Region view
Region View
Coarser resolution; smaller number of components which are more stable and easier to comprehend.
Community view
Community View
Finer resolution of each component can be examined to learn more details of each component.
Node view
Edge View
Having millions of nodes and edges, it's complicated to get any useful information about the graph structure.

Tools, Dataset and Methodology

We are working on 14 snapshots of Google+ social network which contains the network structure and also the user attributes.