File Download

There are no files associated with this item.

Supplementary

Conference Paper: Maintaining Densest Subsets Efficiently in Evolving Hypergraphs

TitleMaintaining Densest Subsets Efficiently in Evolving Hypergraphs
Authors
Issue Date2017
Citation
ACM Conference on Information and Knowledge Management 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

 

DC FieldValueLanguage
dc.contributor.authorHu, SHUGUANG-
dc.contributor.authorChan, HTH-
dc.date.accessioned2017-09-18T02:31:33Z-
dc.date.available2017-09-18T02:31:33Z-
dc.date.issued2017-
dc.identifier.citationACM Conference on Information and Knowledge Management-
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.relation.ispartofACM Conference on Information and Knowledge Management-
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.hkuros277978-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats