Material Detail

Denser than the Densest Subgraph: Extracting Optimal Quasi-Cliques with Quality Guarantees

Denser than the Densest Subgraph: Extracting Optimal Quasi-Cliques with Quality Guarantees

This video was recorded at 19th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), Chicago 2013. Finding dense subgraphs is an important graph-mining task with many applications. Given that the direct optimization of edge density is not meaningful, as even a single edge achieves maximum density, research has focused on optimizing alternative density functions. A very popular among such functions is the average degree, whose maximization leads to the well-known densest-subgraph notion. Surprisingly enough, however, densest subgraphs are typically large graphs, with small edge density and large diameter. In this paper, we define a novel density function, which gives subgraphs of much higher quality than densest subgraphs: the graphs found by our method are compact, dense, and... Show More

Quality

  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material

Comments

Log in to participate in the discussions or sign up if you are not already a MERLOT member.