Densest Subgraph in Streaming and MapReduce

Details Densest Subgraph in Streaming and MapReduce Densest Subgraph in Streaming and MapReduce

2012-01-31

arxiv.org/abs/1201.6567v1

Proceedings of the VLDB Endowment (PVLDB), Vol. 5, No. 5, pp. 454-465 (2012)

Computer Science

Databases

VLDB2012

Scientific paper

The problem of finding locally dense components of a graph is an important primitive in data analysis, with wide-ranging applications from community mining to spam detection and the discovery of biological network modules. In this paper we present new algorithms for finding the densest subgraph in the streaming model. For any epsilon>0, our algorithms make O((log n)/log (1+epsilon)) passes over the input and find a subgraph whose density is guaranteed to be within a factor 2(1+epsilon) of the optimum. Our algorithms are also easily parallelizable and we illustrate this by realizing them in the MapReduce model. In addition we perform extensive experimental evaluation on massive real-world graphs showing the performance and scalability of our algorithms in practice.

Affiliated with

Also associated with

No associations

Rating

Densest Subgraph in Streaming and MapReduce 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 Densest Subgraph in Streaming and MapReduce, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Densest Subgraph in Streaming and MapReduce will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-57196