A local algorithm for finding dense subgraphs

Abstract

We describe a local algorithm for finding subgraphs with high density, according to a measure of density introduced by Kannan and Vinay [1999]. The algorithm takes as input a bipartite graph G, a starting vertex v, and a parameter k, and outputs an induced subgraph of G. It is local in the sense that it does not examine the entire input graph; instead, it adaptively explores a region of the graph near the starting vertex. The running time of the algorithm is bounded by O(Δ k²), which depends on the maximum degree Δ, but is otherwise independent of the graph. We prove the following approximation guarantee: for any subgraph S with k′ vertices and density θ, there exists a set S′ ⊆ S for which the algorithm outputs a subgraph with density Ω(θ/log Δ) whenever v ∈ S′ and k ≥ k′. We prove that S′ contains at least half of the edges in S.

References

1. Andersen, R. 2008. A local algorithm for finding dense subgraphs. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08). 1003--1009.
2. Andersen, R. and Chellapilla, K. 2009. Finding dense subgraphs with size bounds. In Proceedings of the 6th International Workshop on Algorithms and Models for the Web-Graph (WAW'09). 25--37.
3. Andersen, R., Chung, F., and Lang, K. 2006. Local graph partitioning using pagerank vectors. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). 475--486.
4. Andersen, R. and Cioaba, S. M. 2007. Spectral densest subgraph and independence number of a graph. J. Univer. Comput. Sci. 13, 11, 1501--1513.
5. Bilu, Y. and Linial, N. 2004. Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04). 404--412.
6. Charikar, M. 2000. Greedy approximation algorithms for finding dense components in a graph. In Proceedings of the 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX'00).
7. Feige, U., Peleg, D., and Kortsarz, G. 2001. The dense k-subgraph problem. Algorithmica 29, 3, 410--421.
8. Feige, U. and Seltser, M. 1997. On the densest k-subgraph problem. Tech. rep. CS97-16. 1,.
9. Gallo, G., Grigoriadis, M. D., and Tarjan, R. E. 1989. A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18, 1, 30--55.
10. Gibson, D., Kumar, R., and Tomkins, A. 2005. Discovering large dense subgraphs in massive graphs. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05). 721--732.
11. Goldberg, A. 1984. Finding a maximum density subgraph. Tech. rep. UCB CSD 84/71, University of California, Berkeley.
12. Kannan, R. and Vinay, V. 1999. Analyzing the structure of large graphs. Manuscript. http://research.microsoft.com/en-us/um/people/kannan/Papers/webgraph.pdf.
13. Khuller, S. and Saha, B. 2009. On finding dense subgraphs. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP'09). 597--608.
14. Kortsarz, G. and Peleg, D. 1994. Generating sparse 2-spanners. J. Algor. 17, 2, 222--236.
15. Kumar, R., Raghavan, P., Rajagopalan, S., and Tomkins, A. 1999. Trawling the web for emerging cyber-communities. In Proceedings of the 8th World Wide Web Conference (WWW'99). 403--416.
16. Naor, M. and Stockmeyer, L. 1995. What can be computed locally? SIAM J. Comput. 24, 6, 1259--1277.
17. Spielman, D. A. and Teng, S.-H. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC'04). ACM Press, New York, 81--90.
18. Spielman, D. A. and Teng, S.-H. 2008. A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning. CoRR abs/0809.3232.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms