File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Finding subgraphs with maximum total density and limited overlap

TitleFinding subgraphs with maximum total density and limited overlap
Authors
Issue Date2015
PublisherACM 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?
AbstractFinding 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 Identifierhttp://hdl.handle.net/10722/214755
ISBN

 

DC FieldValueLanguage
dc.contributor.authorBalalau, OD-
dc.contributor.authorBonchi, F-
dc.contributor.authorChan, HTH-
dc.contributor.authorGullo, F-
dc.contributor.authorSozio, M-
dc.date.accessioned2015-08-21T11:54:16Z-
dc.date.available2015-08-21T11:54:16Z-
dc.date.issued2015-
dc.identifier.citationThe 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.isbn978-1-4503-3317-7-
dc.identifier.urihttp://hdl.handle.net/10722/214755-
dc.description.abstractFinding 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.languageeng-
dc.publisherACM Press.-
dc.relation.ispartofProceedings of the 8th ACM International Conference on Web Search and Data Mining-
dc.titleFinding subgraphs with maximum total density and limited overlap-
dc.typeConference_Paper-
dc.identifier.emailChan, HTH: hubert@cs.hku.hk-
dc.identifier.authorityChan, HTH=rp01312-
dc.description.naturelink_to_OA_fulltext-
dc.identifier.doi10.1145/2684822.2685298-
dc.identifier.scopuseid_2-s2.0-84928713623-
dc.identifier.hkuros247367-
dc.identifier.spage379-
dc.identifier.epage388-
dc.publisher.placeUnited States-
dc.customcontrol.immutablesml 150902-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats