Exploring communities in large profiled graphs
Given a graph G and a vertex q∈G, the community search (CS) problem aims to efficiently find a subgraph of G whose vertices are closely related to q. Communities are prevalent in social and biological networks, and can be used in product advertisement and social event recommendation. In this paper,...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/140797 |
| _version_ | 1826118780342763520 |
|---|---|
| author | Chen, Yankai Fang, Yixiang Cheng, Reynold Li, Yun Chen, Xiaojun Zhang, Jie |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Chen, Yankai Fang, Yixiang Cheng, Reynold Li, Yun Chen, Xiaojun Zhang, Jie |
| author_sort | Chen, Yankai |
| collection | NTU |
| description | Given a graph G and a vertex q∈G, the community search (CS) problem aims to efficiently find a subgraph of G whose vertices are closely related to q. Communities are prevalent in social and biological networks, and can be used in product advertisement and social event recommendation. In this paper, we study profiled community search (PCS), where CS is performed on a profiled graph. This is a graph in which each vertex has labels arranged in a hierarchical manner. Extensive experiments show that PCS can identify communities with themes that are common to their vertices, and is more effective than existing CS approaches. As a naive solution for PCS is highly expensive, we have also developed a tree index, which facilitates efficient and online solutions for PCS. |
| first_indexed | 2024-10-01T04:49:05Z |
| format | Journal Article |
| id | ntu-10356/140797 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:49:05Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | ntu-10356/1407972020-06-02T04:13:04Z Exploring communities in large profiled graphs Chen, Yankai Fang, Yixiang Cheng, Reynold Li, Yun Chen, Xiaojun Zhang, Jie School of Computer Science and Engineering Engineering::Computer science and engineering Community Search Social Networks Given a graph G and a vertex q∈G, the community search (CS) problem aims to efficiently find a subgraph of G whose vertices are closely related to q. Communities are prevalent in social and biological networks, and can be used in product advertisement and social event recommendation. In this paper, we study profiled community search (PCS), where CS is performed on a profiled graph. This is a graph in which each vertex has labels arranged in a hierarchical manner. Extensive experiments show that PCS can identify communities with themes that are common to their vertices, and is more effective than existing CS approaches. As a naive solution for PCS is highly expensive, we have also developed a tree index, which facilitates efficient and online solutions for PCS. MOE (Min. of Education, S’pore) 2020-06-02T04:13:04Z 2020-06-02T04:13:04Z 2018 Journal Article Chen, Y., Fang, Y., Cheng, R., Li, Y., Chen, X., & Zhang, J. (2019). Exploring communities in large profiled graphs. IEEE Transactions on Knowledge and Data Engineering, 31(8), 1624-1629. doi:10.1109/tkde.2018.2882837 1041-4347 https://hdl.handle.net/10356/140797 10.1109/TKDE.2018.2882837 2-s2.0-85057366751 8 31 1624 1629 en IEEE Transactions on Knowledge and Data Engineering © 2018 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: https://doi.org/10.1109/TKDE.2018.2882837 |
| spellingShingle | Engineering::Computer science and engineering Community Search Social Networks Chen, Yankai Fang, Yixiang Cheng, Reynold Li, Yun Chen, Xiaojun Zhang, Jie Exploring communities in large profiled graphs |
| title | Exploring communities in large profiled graphs |
| title_full | Exploring communities in large profiled graphs |
| title_fullStr | Exploring communities in large profiled graphs |
| title_full_unstemmed | Exploring communities in large profiled graphs |
| title_short | Exploring communities in large profiled graphs |
| title_sort | exploring communities in large profiled graphs |
| topic | Engineering::Computer science and engineering Community Search Social Networks |
| url | https://hdl.handle.net/10356/140797 |
| work_keys_str_mv | AT chenyankai exploringcommunitiesinlargeprofiledgraphs AT fangyixiang exploringcommunitiesinlargeprofiledgraphs AT chengreynold exploringcommunitiesinlargeprofiledgraphs AT liyun exploringcommunitiesinlargeprofiledgraphs AT chenxiaojun exploringcommunitiesinlargeprofiledgraphs AT zhangjie exploringcommunitiesinlargeprofiledgraphs |