File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Maintaining Densest Subsets Efficiently in Evolving Hypergraphs

TitleMaintaining Densest Subsets Efficiently in Evolving Hypergraphs
Authors
Issue Date2017
PublisherACM. The Proceedings' web site is located at https://dl.acm.org/citation.cfm?id=3132847&picked=prox
Citation
Proceedings of the 26th ACM International Conference on Information and Knowledge Management (CIKM'17), Singapore, 6-10 Novermber 2017, p. 929-938 How to Cite?
AbstractIn this paper we study the densest subgraph problem, which plays a key role in many graph mining applications. The goal of the problem is to find a subset of nodes that induces a graph with maximum average degree. The problem has been extensively studied in the past few decades under a variety of different settings. Several exact and approximation algorithms were proposed. However, as normal graph can only model objects with pairwise relationships, the densest subgraph problem fails in identifying communities under relationships that involve more than 2 objects, e.g., in a network connecting authors by publications. We consider in this work the densest subgraph problem in hypergraphs, which generalizes the problem to a wider class of networks in which edges might have different cardinalities and contain more than 2 nodes. We present two exact algorithms and a near-linear time r-approximation algorithm for the problem, where r is the maximum cardinality of an edge in the hypergraph. We also consider the dynamic version of the problem, in which an adversary can insert or delete an edge from the hypergraph in each round and the goal is to maintain efficiently an approximation of the densest subgraph. We present two dynamic approximation algorithms in this paper with amortized poly(r/epsilon log n) update time, for any epsilon > 0. For the case when there are only insertions, the approximation ratio we maintain is r(1+epsilon), while for the fully dynamic case, the ratio is r^2(1+epsilon). Extensive experiments are performed on large real datasets to validate the effectiveness and efficiency of our algorithms.
Persistent Identifierhttp://hdl.handle.net/10722/246612
ISBN

 

DC FieldValueLanguage
dc.contributor.authorHu, S-
dc.contributor.authorWu, X-
dc.contributor.authorChan, HTH-
dc.date.accessioned2017-09-18T02:31:33Z-
dc.date.available2017-09-18T02:31:33Z-
dc.date.issued2017-
dc.identifier.citationProceedings of the 26th ACM International Conference on Information and Knowledge Management (CIKM'17), Singapore, 6-10 Novermber 2017, p. 929-938-
dc.identifier.isbn978-1-4503-4918-5-
dc.identifier.urihttp://hdl.handle.net/10722/246612-
dc.description.abstractIn this paper we study the densest subgraph problem, which plays a key role in many graph mining applications. The goal of the problem is to find a subset of nodes that induces a graph with maximum average degree. The problem has been extensively studied in the past few decades under a variety of different settings. Several exact and approximation algorithms were proposed. However, as normal graph can only model objects with pairwise relationships, the densest subgraph problem fails in identifying communities under relationships that involve more than 2 objects, e.g., in a network connecting authors by publications. We consider in this work the densest subgraph problem in hypergraphs, which generalizes the problem to a wider class of networks in which edges might have different cardinalities and contain more than 2 nodes. We present two exact algorithms and a near-linear time r-approximation algorithm for the problem, where r is the maximum cardinality of an edge in the hypergraph. We also consider the dynamic version of the problem, in which an adversary can insert or delete an edge from the hypergraph in each round and the goal is to maintain efficiently an approximation of the densest subgraph. We present two dynamic approximation algorithms in this paper with amortized poly(r/epsilon log n) update time, for any epsilon > 0. For the case when there are only insertions, the approximation ratio we maintain is r(1+epsilon), while for the fully dynamic case, the ratio is r^2(1+epsilon). Extensive experiments are performed on large real datasets to validate the effectiveness and efficiency of our algorithms.-
dc.languageeng-
dc.publisherACM. The Proceedings' web site is located at https://dl.acm.org/citation.cfm?id=3132847&picked=prox-
dc.relation.ispartofConference on Information and Knowledge Management, CIKM 2017 Proceedings-
dc.titleMaintaining Densest Subsets Efficiently in Evolving Hypergraphs-
dc.typeConference_Paper-
dc.identifier.emailChan, HTH: hubert@cs.hku.hk-
dc.identifier.authorityChan, HTH=rp01312-
dc.identifier.doi10.1145/3132847.3132907-
dc.identifier.hkuros277978-
dc.identifier.spage929-
dc.identifier.epage938-
dc.publisher.placeNew York, NY-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats