skip to main content
10.1145/2684822.2685298acmconferencesArticle/Chapter ViewAbstractPublication PageswsdmConference Proceedingsconference-collections
research-article

Finding Subgraphs with Maximum Total Density and Limited Overlap

Published:02 February 2015Publication History

ABSTRACT

Finding dense subgraphs in large graphs is a key primitive in a variety of real-world application domains, encompassing social network analytics, event detection, biology, and finance. In most such applications, one typically aims at finding several (possibly overlapping) dense subgraphs which might correspond to communities in social networks or interesting events. While a large amount of work is devoted to finding a single densest subgraph, perhaps surprisingly, the problem of finding several dense subgraphs with limited overlap has not been studied in a principled way, to the best of our knowledge. In this work we define and study a natural generalization of the densest subgraph problem, where the main goal is to find at most $k$ subgraphs with maximum total aggregate density, while satisfying an upper bound on the pairwise Jaccard coefficient between the sets of nodes of the subgraphs. After showing that such a problem is NP-Hard, we devise an efficient algorithm that comes with provable guarantees in some cases of interest, as well as, an efficient practical heuristic. Our extensive evaluation on large real-world graphs confirms the efficiency and effectiveness of our algorithms.

References

  1. R. Andersen and K. Chellapilla. Finding dense subgraphs with size bounds. In WAW, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. A. Angel, N. Sarkas, N. Koudas, and D. Srivastava. Dense subgraph maintenance under streaming edge weight updates for real-time story identification. PVLDB, 5(6), 2012. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. A. Angel, N. Sarkas, N. Koudas, and D. Srivastava. Dense subgraph maintenance under streaming edge weight updates for real-time story identification. PVLDB, 5(6), 2012. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. Y. Asahiro, R. Hassin, and K. Iwama. Complexity of finding dense subgraphs. Discr. Ap. Math., 121(1-3), 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. Y. Asahiro, K. Iwama, H. Tamaki, and T. Tokuyama. Greedily finding a dense subgraph. J. Algorithms, 34(2), 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. B. Bahmani, R. Kumar, and S. Vassilvitskii. Densest subgraph in streaming and mapreduce. PVLDB, 5(5), 2012. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. A. Bhaskara, M. Charikar, E. Chlamtac, U. Feige, and A. Vijayaraghavan. Detecting high log-densities: an O(n 1/4) approximation for densest k-subgraph. In STOC, pages 201{210, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. F. Bonchi, F. Gullo, A. Kaltenbrunner, and Y. Volkovich. Core decomposition of uncertain graphs. In KDD, 2014. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. M. Charikar. Greedy approximation algorithms for finding dense components in a graph. In K. Jansen and S. Khuller, editors, APPROX. Springer, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. J. Chen and Y. Saad. Dense subgraph extraction with application to community detection. TKDE, 24(7), 2012. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. W. Cui, Y. Xiao, H. Wang, Y. Lu, and W. Wang. Online search of overlapping communities. In SIGMOD, 2013. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. X. Du, R. Jin, L. Ding, V. E. Lee, and J. H. Thornton, Jr. Migration motif: a spatial - temporal pattern mining approach for financial markets. In KDD, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. E. Fratkin, B. T. Naughton, D. L. Brutlag, and S. Batzoglou. MotifCut: regulatory motifs finding with maximum density subgraphs. In ISMB, 2006.Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. D. Gibson, R. Kumar, and A. Tomkins. Discovering large dense subgraphs in massive graphs. In VLDB, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. A. V. Goldberg. Finding a maximum density subgraph. Technical report, University of California at Berkeley, 1984. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. S. Khot. Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. J. Computing, 36(4), 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. S. Khuller and B. Saha. On finding dense subgraphs. In ICALP, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. M. A. Langston and et al. A combinatorial approach to the analysis of differential gene expression data: The use of graph algorithms for disease prediction and screening. In Methods of Microarray Data Analysis IV. 2005.Google ScholarGoogle ScholarCross RefCross Ref
  19. V. E. Lee, N. Ruan, R. Jin, and C. C. Aggarwal. A survey of algorithms for dense subgraph discovery. In Managing and Mining Graph Data. 2010.Google ScholarGoogle ScholarCross RefCross Ref
  20. C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci., 43(3), 1991.Google ScholarGoogle Scholar
  21. M. Sozio and A. Gionis. The community-search problem and how to plan a successful cocktail party. In KDD, pages 939{948, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. N. Tatti and A. Gionis. Discovering nested communities. In ECML/PKDD (2), 2013.Google ScholarGoogle ScholarCross RefCross Ref
  23. C. Tsourakakis, F. Bonchi, A. Gionis, F. Gullo, and M. Tsiarli. Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees. In KDD, 2013. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. E. Valari, M. Kontaki, and A. N. Papadopoulos. Discovery of top-k dense subgraphs in dynamic graph collections. In SSDBM, 2012. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. N. Wang, J. Zhang, K.-L. Tan, and A. K. H. Tung. On triangulation-based dense neighborhood graph discovery. PVLDB, 4(2), 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Finding Subgraphs with Maximum Total Density and Limited Overlap

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      WSDM '15: Proceedings of the Eighth ACM International Conference on Web Search and Data Mining
      February 2015
      482 pages
      ISBN:9781450333177
      DOI:10.1145/2684822

      Copyright © 2015 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 2 February 2015

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      WSDM '15 Paper Acceptance Rate39of238submissions,16%Overall Acceptance Rate498of2,863submissions,17%

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader