File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/3132847.3132907
- Scopus: eid_2-s2.0-85037358547
- WOS: WOS:000440845300092
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Maintaining Densest Subsets Efficiently in Evolving Hypergraphs
Title | Maintaining Densest Subsets Efficiently in Evolving Hypergraphs |
---|---|
Authors | |
Keywords | Densest subgraph Dynamic data structure Graph mining |
Issue Date | 2017 |
Publisher | ACM. 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? |
Abstract | In 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 Identifier | http://hdl.handle.net/10722/246612 |
ISBN | |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hu, S | - |
dc.contributor.author | Wu, X | - |
dc.contributor.author | Chan, HTH | - |
dc.date.accessioned | 2017-09-18T02:31:33Z | - |
dc.date.available | 2017-09-18T02:31:33Z | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | Proceedings of the 26th ACM International Conference on Information and Knowledge Management (CIKM'17), Singapore, 6-10 Novermber 2017, p. 929-938 | - |
dc.identifier.isbn | 978-1-4503-4918-5 | - |
dc.identifier.uri | http://hdl.handle.net/10722/246612 | - |
dc.description.abstract | In 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.language | eng | - |
dc.publisher | ACM. The Proceedings' web site is located at https://dl.acm.org/citation.cfm?id=3132847&picked=prox | - |
dc.relation.ispartof | Conference on Information and Knowledge Management, CIKM 2017 Proceedings | - |
dc.subject | Densest subgraph | - |
dc.subject | Dynamic data structure | - |
dc.subject | Graph mining | - |
dc.title | Maintaining Densest Subsets Efficiently in Evolving Hypergraphs | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Chan, HTH: hubert@cs.hku.hk | - |
dc.identifier.authority | Chan, HTH=rp01312 | - |
dc.identifier.doi | 10.1145/3132847.3132907 | - |
dc.identifier.scopus | eid_2-s2.0-85037358547 | - |
dc.identifier.hkuros | 277978 | - |
dc.identifier.spage | 929 | - |
dc.identifier.epage | 938 | - |
dc.identifier.isi | WOS:000440845300092 | - |
dc.publisher.place | New York, NY | - |