Computer Science – Social and Information Networks
Scientific paper
2011-07-26
Computer Science
Social and Information Networks
Scientific paper
Graph analysis is a critical component of applications such as online social networks, protein interactions in biological networks, and Internet traffic analysis. The arrival of massive graphs with hundreds of millions of nodes, e.g. social graphs, presents a unique challenge to graph analysis applications. Most of these applications rely on computing distances between node pairs, which for large graphs can take minutes to compute using traditional algorithms such as breadth-first-search (BFS). In this paper, we study ways to enable scalable graph processing on today's massive graphs. We explore the design space of graph coordinate systems, a new approach that accurately approximates node distances in constant time by embedding graphs into coordinate spaces. We show that a hyperbolic embedding produces relatively low distortion error, and propose Rigel, a hyperbolic graph coordinate system that lends itself to efficient parallelization across a compute cluster. Rigel produces significantly more accurate results than prior systems, and is naturally parallelizable across compute clusters, allowing it to provide accurate results for graphs up to 43 million nodes. Finally, we show that Rigel's functionality can be easily extended to locate (near-) shortest paths between node pairs. After a one- time preprocessing cost, Rigel answers node-distance queries in 10's of microseconds, and also produces shortest path results up to 18 times faster than prior shortest-path systems with similar levels of accuracy.
Sala Alessandra
Zhao Ben Y.
Zhao Xiaohan
Zheng Haitao
No associations
LandOfFree
Fast and Scalable Analysis of Massive Social Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Fast and Scalable Analysis of Massive Social Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast and Scalable Analysis of Massive Social Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-93043