Truss decomposition in massive networks
The k-truss is a type of cohesive subgraphs proposed recently for the study of networks. While the problem of computing most cohesive subgraphs is NP-hard, there exists a polynomial time algorithm for computing k-truss. Compared with k-core which is also efficient to compute, k-truss represents the...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Language: | English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/98773 http://hdl.handle.net/10220/13430 http://dl.acm.org/citation.cfm?id=2311909 |
| _version_ | 1811688624812457984 |
|---|---|
| author | Wang, Jia Cheng, James |
| author2 | School of Computer Engineering |
| author_facet | School of Computer Engineering Wang, Jia Cheng, James |
| author_sort | Wang, Jia |
| collection | NTU |
| description | The k-truss is a type of cohesive subgraphs proposed recently for the study of networks. While the problem of computing most cohesive subgraphs is NP-hard, there exists a polynomial time algorithm for computing k-truss. Compared with k-core which is also efficient to compute, k-truss represents the "core" of a k-core that keeps the key information of, while filtering out less important information from, the k-core. However, existing algorithms for computing k-truss are inefficient for handling today's massive networks. We first improve the existing in-memory algorithm for computing k-truss in networks of moderate size. Then, we propose two I/O-efficient algorithms to handle massive networks that cannot fit in main memory. Our experiments on real datasets verify the efficiency of our algorithms and the value of k-truss. |
| first_indexed | 2024-10-01T05:35:10Z |
| format | Conference Paper |
| id | ntu-10356/98773 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:35:10Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/987732020-05-28T07:41:34Z Truss decomposition in massive networks Wang, Jia Cheng, James School of Computer Engineering Very Large Data Base Endowment (2012) DRNTU::Engineering::Computer science and engineering The k-truss is a type of cohesive subgraphs proposed recently for the study of networks. While the problem of computing most cohesive subgraphs is NP-hard, there exists a polynomial time algorithm for computing k-truss. Compared with k-core which is also efficient to compute, k-truss represents the "core" of a k-core that keeps the key information of, while filtering out less important information from, the k-core. However, existing algorithms for computing k-truss are inefficient for handling today's massive networks. We first improve the existing in-memory algorithm for computing k-truss in networks of moderate size. Then, we propose two I/O-efficient algorithms to handle massive networks that cannot fit in main memory. Our experiments on real datasets verify the efficiency of our algorithms and the value of k-truss. 2013-09-09T08:19:16Z 2019-12-06T19:59:31Z 2013-09-09T08:19:16Z 2019-12-06T19:59:31Z 2012 2012 Conference Paper https://hdl.handle.net/10356/98773 http://hdl.handle.net/10220/13430 http://dl.acm.org/citation.cfm?id=2311909 en © 2012 VLDB Endowment |
| spellingShingle | DRNTU::Engineering::Computer science and engineering Wang, Jia Cheng, James Truss decomposition in massive networks |
| title | Truss decomposition in massive networks |
| title_full | Truss decomposition in massive networks |
| title_fullStr | Truss decomposition in massive networks |
| title_full_unstemmed | Truss decomposition in massive networks |
| title_short | Truss decomposition in massive networks |
| title_sort | truss decomposition in massive networks |
| topic | DRNTU::Engineering::Computer science and engineering |
| url | https://hdl.handle.net/10356/98773 http://hdl.handle.net/10220/13430 http://dl.acm.org/citation.cfm?id=2311909 |
| work_keys_str_mv | AT wangjia trussdecompositioninmassivenetworks AT chengjames trussdecompositioninmassivenetworks |