File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/3038912.3052619
- Scopus: eid_2-s2.0-85050609589
- WOS: WOS:000461544900027
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Large Scale Density-friendly Graph Decomposition via Convex Programming
Title | Large Scale Density-friendly Graph Decomposition via Convex Programming |
---|---|
Authors | |
Issue Date | 2017 |
Publisher | International World Wide Web Conferences Steering Committee. |
Citation | Proceedings of the 26th International Conference on World Wide Web (WWW '17), Perth, Australia, 3-7 April 2017, p. 233-242 How to Cite? |
Abstract | Algorithms for finding dense regions in an input graph have proved to be effective tools in graph mining and data analysis. Recently, Tatti and Gionis [WWW 2015] presented a novel graph decomposition (known as the locally-dense decomposition) that is similar to the well-known k-core decomposition, with the additional property that its components are arranged in order of their densities. Such a decomposition provides a valuable tool in graph mining. Unfortunately, their algorithm for computing the exact decomposition is based on a maximum-flow algorithm which cannot scale to massive graphs, while the approximate decomposition defined by the same authors misses several interesting properties. This calls for scalable algorithms for computing such a decomposition. In our work, we devise an efficient algorithm which is able to compute exact locally-dense decompositions in real-world graphs containing up to billions of edges. Moreover, we provide a new definition of approximate locally-dense decomposition which retains most of the properties of an exact decomposition, for which we devise an algorithm that can scale to real-world graphs containing up to tens of billions of edges. Our algorithm is based on the classic Frank-Wolfe algorithm which is similar to gradient descent and can be efficiently implemented in most of the modern architectures dealing with massive graphs. We provide a rigorous study of our algorithms and their convergence rates. We conduct an extensive experimental evaluation on multi-core architectures showing that our algorithms converge much faster in practice than their worst-case analysis. Our algorithm is even more efficient for the more specialized problem of computing a densest subgraph. |
Persistent Identifier | http://hdl.handle.net/10722/245440 |
ISBN | |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Danisch, M | - |
dc.contributor.author | Chan, HTH | - |
dc.contributor.author | Sozio, M | - |
dc.date.accessioned | 2017-09-18T02:10:46Z | - |
dc.date.available | 2017-09-18T02:10:46Z | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | Proceedings of the 26th International Conference on World Wide Web (WWW '17), Perth, Australia, 3-7 April 2017, p. 233-242 | - |
dc.identifier.isbn | 978-1-4503-4913-0 | - |
dc.identifier.uri | http://hdl.handle.net/10722/245440 | - |
dc.description.abstract | Algorithms for finding dense regions in an input graph have proved to be effective tools in graph mining and data analysis. Recently, Tatti and Gionis [WWW 2015] presented a novel graph decomposition (known as the locally-dense decomposition) that is similar to the well-known k-core decomposition, with the additional property that its components are arranged in order of their densities. Such a decomposition provides a valuable tool in graph mining. Unfortunately, their algorithm for computing the exact decomposition is based on a maximum-flow algorithm which cannot scale to massive graphs, while the approximate decomposition defined by the same authors misses several interesting properties. This calls for scalable algorithms for computing such a decomposition. In our work, we devise an efficient algorithm which is able to compute exact locally-dense decompositions in real-world graphs containing up to billions of edges. Moreover, we provide a new definition of approximate locally-dense decomposition which retains most of the properties of an exact decomposition, for which we devise an algorithm that can scale to real-world graphs containing up to tens of billions of edges. Our algorithm is based on the classic Frank-Wolfe algorithm which is similar to gradient descent and can be efficiently implemented in most of the modern architectures dealing with massive graphs. We provide a rigorous study of our algorithms and their convergence rates. We conduct an extensive experimental evaluation on multi-core architectures showing that our algorithms converge much faster in practice than their worst-case analysis. Our algorithm is even more efficient for the more specialized problem of computing a densest subgraph. | - |
dc.language | eng | - |
dc.publisher | International World Wide Web Conferences Steering Committee. | - |
dc.relation.ispartof | International Conference on World Wide Web (WWW), 2017 | - |
dc.title | Large Scale Density-friendly Graph Decomposition via Convex Programming | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Chan, HTH: hubert@cs.hku.hk | - |
dc.identifier.authority | Chan, HTH=rp01312 | - |
dc.identifier.doi | 10.1145/3038912.3052619 | - |
dc.identifier.scopus | eid_2-s2.0-85050609589 | - |
dc.identifier.hkuros | 276468 | - |
dc.identifier.spage | 233 | - |
dc.identifier.epage | 242 | - |
dc.identifier.isi | WOS:000461544900027 | - |
dc.publisher.place | Geneva, Switzerland | - |