Large-scale, networked systems such as the World Wide Web or Online Social Networks (OSNs) can be represented as graphs where nodes represent individual entities (e.g., web pages or users), and directed or undirected edges represent relations between these entities (e.g., interaction or friendship between users). Characterizing the connectivity structure of such a graph, in particular at scale, often provides deeper insight into the corresponding networked system and has motivated many researchers to analyze graph representations of large networked systems. It is often very useful to obtain a coarse view of the connectivity structure of a huge graph that shows a few major tightly connected components or regions of the graph along with the inter- and intra-region connectivity. Such a regional view also enables a natural top-down approach to the analysis of large graphs, where one first examines the regional connectivity of a huge graph and then zooms in to individual regions to explore their structure in further detail. However, capturing a regional view of a huge graph is a non-trivial task that existing tools and techniques are not able to achieve. While many techniques exist for graph clustering, graph partitioning, and community detection, these approaches do not work well for discovering coarse regional views in very large graphs. These methods usually scale poorly, force regions to have similar size, or find communities that are too small. For example, existing techniques (e.g., Louvain) are likely to identify tens of thousands of communities in the structure of a large OSN that is still too complex for high-level analysis to determine the full picture of inter-community connectivity. WalkAboutis technique to infer a coarse view of connectivity in very large graphs; that is, identify well-connected "regions" with different edge densities and determine the corresponding inter- and intra- region connectivity. We leverage the transient behavior of many short random walks (RW) on a large graph that is assumed to have regions of varying edge density but whose structure is otherwise unknown. The key idea is that as RWs approach the mixing time of a region, the ratio of the number of visits by all RWs to the degree for nodes in that region converges to a value proportional to the average node degree in that region. Leveraging this indirect sign of connectivity enables our proposed framework to effectively scale with graph size. If individual regions in a graph have a different average degrees, we can use the visit-to-degree ratio across visited nodes to identify the regions and their corresponding nodes. Using this indirect sign of connectivity enables this framework to scale with graph size. We leverage this phenomenon in our proposed framework and address practical considerations.
Empirical Analysis
In our empirical evaluation, we apply WalkAbout to three major OSNs: Flickr, Twitter and Google+. Compared to Louvain, the gold standard for scalable community detection, WalkAbout runs faster and finds larger, coarser regions. Most communities discovered by Louvain can be mapped to a single one of WalkAbout’s regions, suggesting that WalkAbout is providing a higher-level view of the network than Louvain. Finally, we analyze the regions in Flickr and show that different regions discovered by WalkAbout correspond to different interest groups, providing a meaningful coarse view of this OSN.
Please read more about this research here
Publications
R. Motamedi, R. Rejaie, Daniel Lowd, Walter Willinger, and Roberto Gonzalez, “Inferring Coarse Views of Connectivity in Very Large Graphs”, paper ACM Conference on Online Social Networks (COSN), Dublin, Ireland, October 2014