File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/3385416
- Scopus: eid_2-s2.0-85088451713
- WOS: WOS:000583626600002
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Fully Dynamic Approximate k-Core Decomposition in Hypergraphs
Title | Fully Dynamic Approximate k-Core Decomposition in Hypergraphs |
---|---|
Authors | |
Keywords | Core values dynamic network hypergraphs |
Issue Date | 2020 |
Publisher | Association for Computing Machinery, Inc. The Journal's web site is located at http://tkdd.cs.uiuc.edu |
Citation | ACM Transactions on Knowledge Discovery from Data, 2020, v. 14 n. 4, p. article no. 39 How to Cite? |
Abstract | In this article, we design algorithms to maintain approximate core values in dynamic hypergraphs. This notion has been well studied for normal graphs in both static and dynamic setting. We generalize the problem to hypergraphs when edges can be inserted or deleted by an adversary.
We consider two dynamic scenarios. In the first case, there are only insertions; and in the second case, there can be both insertions and deletions. In either case, the update time is poly-logarithmic in the number of nodes, with the insertion-only case boasting a better approximation ratio. We also perform extensive experiments on large real-world datasets, which demonstrate the accuracy and efficiency of our algorithms. |
Persistent Identifier | http://hdl.handle.net/10722/290739 |
ISSN | 2023 Impact Factor: 4.0 2023 SCImago Journal Rankings: 1.303 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | SUN, B | - |
dc.contributor.author | Chan, TH | - |
dc.contributor.author | Sozio, M | - |
dc.date.accessioned | 2020-11-02T05:46:26Z | - |
dc.date.available | 2020-11-02T05:46:26Z | - |
dc.date.issued | 2020 | - |
dc.identifier.citation | ACM Transactions on Knowledge Discovery from Data, 2020, v. 14 n. 4, p. article no. 39 | - |
dc.identifier.issn | 1556-4681 | - |
dc.identifier.uri | http://hdl.handle.net/10722/290739 | - |
dc.description.abstract | In this article, we design algorithms to maintain approximate core values in dynamic hypergraphs. This notion has been well studied for normal graphs in both static and dynamic setting. We generalize the problem to hypergraphs when edges can be inserted or deleted by an adversary. We consider two dynamic scenarios. In the first case, there are only insertions; and in the second case, there can be both insertions and deletions. In either case, the update time is poly-logarithmic in the number of nodes, with the insertion-only case boasting a better approximation ratio. We also perform extensive experiments on large real-world datasets, which demonstrate the accuracy and efficiency of our algorithms. | - |
dc.language | eng | - |
dc.publisher | Association for Computing Machinery, Inc. The Journal's web site is located at http://tkdd.cs.uiuc.edu | - |
dc.relation.ispartof | ACM Transactions on Knowledge Discovery from Data | - |
dc.rights | ACM Transactions on Knowledge Discovery from Data. Copyright © Association for Computing Machinery, Inc. | - |
dc.rights | ©ACM, YYYY. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in PUBLICATION, {VOL#, ISS#, (DATE)} http://doi.acm.org/10.1145/nnnnnn.nnnnnn | - |
dc.subject | Core values | - |
dc.subject | dynamic network | - |
dc.subject | hypergraphs | - |
dc.title | Fully Dynamic Approximate k-Core Decomposition in Hypergraphs | - |
dc.type | Article | - |
dc.identifier.email | Chan, TH: hubert@cs.hku.hk | - |
dc.identifier.authority | Chan, TH=rp01312 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/3385416 | - |
dc.identifier.scopus | eid_2-s2.0-85088451713 | - |
dc.identifier.hkuros | 318367 | - |
dc.identifier.volume | 14 | - |
dc.identifier.issue | 4 | - |
dc.identifier.spage | article no. 39 | - |
dc.identifier.epage | article no. 39 | - |
dc.identifier.isi | WOS:000583626600002 | - |
dc.publisher.place | United States | - |
dc.identifier.issnl | 1556-4681 | - |