Multi-resolution analysis of connectivity and evolution in huge graphs
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
Coarser resolution; smaller number of components which are more stable and easier to comprehend.
Finer resolution of each component can be examined to learn more details of each component.
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.