Dense Subgraphs Finding Task

A Dense Subgraphs Finding Task is a subgraphs finding task to find dense subgraphs.

• See: Subgraph, Clique.

---

---

References

2009

• (Andersen & Chellapilla, 2009) ⇒ Reid Andersen, and Kumar Chellapilla. (2009). “Finding Dense Subgraphs with Size Bounds.” In: Proceedings of the 6th International Workshop on Algorithms and Models for the Web-Graph. ISBN:978-3-540-95994-6 doi:10.1007/978-3-540-95995-3_3
  • QUOTE: We consider the problem of finding dense subgraphs with specified upper or lower bounds on the number of vertices. We introduce two optimization problems: the densest at-least-k-subgraph problem (dalks), which is to find an induced subgraph of highest average degree among all subgraphs with at least k vertices, and the densest at-most-k-subgraph problem (damks), which is defined similarly.

2005

• (Gibson et al., 2005) ⇒ David Gibson, Ravi Kumar, and Andrew Tomkins. (2005). “Discovering Large Dense Subgraphs in Massive Graphs.” In: Proceedings of the 31st International Conference on Very large data bases. ISBN:1-59593-154-6
  • QUOTE: We present a new algorithm for finding large, dense subgraphs in massive graphs.

---