File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/2684822.2685298
- Scopus: eid_2-s2.0-84928713623
- WOS: WOS:000485486900046
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Finding subgraphs with maximum total density and limited overlap
Title | Finding subgraphs with maximum total density and limited overlap |
---|---|
Authors | |
Issue Date | 2015 |
Publisher | ACM Press. |
Citation | The 8th ACM International Conference on Web Search and Data Mining (WSDM 2015), Shanghai, China, 31 January-6 February 2015. In Conference Proceedings, 2015, p. 379-388 How to Cite? |
Abstract | Finding dense subgraphs in large graphs is a key primitive in a variety of real-world application domains, encompass-ing 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 in-teresting 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 to-tal 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. Copyright © 2015 ACM. |
Persistent Identifier | http://hdl.handle.net/10722/214755 |
ISBN | |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Balalau, OD | - |
dc.contributor.author | Bonchi, F | - |
dc.contributor.author | Chan, HTH | - |
dc.contributor.author | Gullo, F | - |
dc.contributor.author | Sozio, M | - |
dc.date.accessioned | 2015-08-21T11:54:16Z | - |
dc.date.available | 2015-08-21T11:54:16Z | - |
dc.date.issued | 2015 | - |
dc.identifier.citation | The 8th ACM International Conference on Web Search and Data Mining (WSDM 2015), Shanghai, China, 31 January-6 February 2015. In Conference Proceedings, 2015, p. 379-388 | - |
dc.identifier.isbn | 978-1-4503-3317-7 | - |
dc.identifier.uri | http://hdl.handle.net/10722/214755 | - |
dc.description.abstract | Finding dense subgraphs in large graphs is a key primitive in a variety of real-world application domains, encompass-ing 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 in-teresting 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 to-tal 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. Copyright © 2015 ACM. | - |
dc.language | eng | - |
dc.publisher | ACM Press. | - |
dc.relation.ispartof | Proceedings of the 8th ACM International Conference on Web Search and Data Mining | - |
dc.title | Finding subgraphs with maximum total density and limited overlap | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Chan, HTH: hubert@cs.hku.hk | - |
dc.identifier.authority | Chan, HTH=rp01312 | - |
dc.description.nature | link_to_OA_fulltext | - |
dc.identifier.doi | 10.1145/2684822.2685298 | - |
dc.identifier.scopus | eid_2-s2.0-84928713623 | - |
dc.identifier.hkuros | 247367 | - |
dc.identifier.spage | 379 | - |
dc.identifier.epage | 388 | - |
dc.identifier.isi | WOS:000485486900046 | - |
dc.publisher.place | United States | - |
dc.customcontrol.immutable | sml 150902 | - |