File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.14778/3401960.3401962
- Scopus: eid_2-s2.0-85091157256
- WOS: WOS:000573962300002
Supplementary
- Citations:
- Appears in Collections:
Article: KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs
Title | KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs |
---|---|
Authors | |
Issue Date | 2020 |
Publisher | Association for Computing Machinery. The Journal's web site is located at http://vldb.org/pvldb/ |
Citation | Proceedings of the VLDB Endowment, 2020, v. 13 n. 10, p. 1628-1640 How to Cite? |
Abstract | The problem of finding densest subgraphs has received increasing attention in recent years finding applications in biology, finance, as well as social network analysis. The k-clique densest subgraph problem is a generalization of the densest subgraph problem, where the objective is to find a subgraph maximizing the ratio between the number of k-cliques in the subgraph and its number of nodes. It includes as a special case the problem of finding subgraphs with largest average number of triangles (k = 3), which plays an important role in social network analysis. Moreover, algorithms that deal with larger values of k can effectively find quasi-cliques. The densest subgraph problem can be solved in polynomial time with algorithms based on maximum flow, linear programming or a recent approach based on convex optimization. In particular, the latter approach can scale to graphs containing tens of billions of edges. While finding a densest subgraph in large graphs is no longer a bottleneck, the k-clique densest subgraph remains challenging even when k = 3. Our work aims at developing near-optimal and exact algorithms for the k-clique densest subgraph problem on large real-world graphs. We give a surprisingly simple procedure that can be employed to find the maximal k-clique densest subgraph in large-real world graphs. By leveraging appealing properties of existing results, we combine it with a recent approach for listing all k-cliques in a graph and a sampling scheme, obtaining the state-of-the-art approaches for the aforementioned problem. Our theoretical results are complemented with an extensive experimental evaluation showing the effectiveness of our approach in large real-world graphs. |
Persistent Identifier | http://hdl.handle.net/10722/301338 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | SUN, B | - |
dc.contributor.author | Danisch, M | - |
dc.contributor.author | Chan, TH | - |
dc.contributor.author | Sozio, M | - |
dc.date.accessioned | 2021-07-27T08:09:37Z | - |
dc.date.available | 2021-07-27T08:09:37Z | - |
dc.date.issued | 2020 | - |
dc.identifier.citation | Proceedings of the VLDB Endowment, 2020, v. 13 n. 10, p. 1628-1640 | - |
dc.identifier.uri | http://hdl.handle.net/10722/301338 | - |
dc.description.abstract | The problem of finding densest subgraphs has received increasing attention in recent years finding applications in biology, finance, as well as social network analysis. The k-clique densest subgraph problem is a generalization of the densest subgraph problem, where the objective is to find a subgraph maximizing the ratio between the number of k-cliques in the subgraph and its number of nodes. It includes as a special case the problem of finding subgraphs with largest average number of triangles (k = 3), which plays an important role in social network analysis. Moreover, algorithms that deal with larger values of k can effectively find quasi-cliques. The densest subgraph problem can be solved in polynomial time with algorithms based on maximum flow, linear programming or a recent approach based on convex optimization. In particular, the latter approach can scale to graphs containing tens of billions of edges. While finding a densest subgraph in large graphs is no longer a bottleneck, the k-clique densest subgraph remains challenging even when k = 3. Our work aims at developing near-optimal and exact algorithms for the k-clique densest subgraph problem on large real-world graphs. We give a surprisingly simple procedure that can be employed to find the maximal k-clique densest subgraph in large-real world graphs. By leveraging appealing properties of existing results, we combine it with a recent approach for listing all k-cliques in a graph and a sampling scheme, obtaining the state-of-the-art approaches for the aforementioned problem. Our theoretical results are complemented with an extensive experimental evaluation showing the effectiveness of our approach in large real-world graphs. | - |
dc.language | eng | - |
dc.publisher | Association for Computing Machinery. The Journal's web site is located at http://vldb.org/pvldb/ | - |
dc.relation.ispartof | Proceedings of the VLDB Endowment | - |
dc.rights | Proceedings of the VLDB Endowment. Copyright © Association for Computing Machinery. | - |
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.title | KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs | - |
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.14778/3401960.3401962 | - |
dc.identifier.scopus | eid_2-s2.0-85091157256 | - |
dc.identifier.hkuros | 323566 | - |
dc.identifier.volume | 13 | - |
dc.identifier.issue | 10 | - |
dc.identifier.spage | 1628 | - |
dc.identifier.epage | 1640 | - |
dc.identifier.eissn | 2150-8097 | - |
dc.identifier.isi | WOS:000573962300002 | - |
dc.publisher.place | United States | - |