File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Appears in Collections:
Conference Paper: Effective and Efficient Community Search
Title | Effective and Efficient Community Search |
---|---|
Authors | |
Issue Date | 2017 |
Citation | Workshop on Mobility Analytics for Spatio-temporal and Social Data (MATES 2017), co- located with VLDB 2017, Munich, Germany, 28 August - 1 September 2017 How to Cite? |
Abstract | Given a graph G and a vertex q ∈ G, the community search query returns a subgraph of G that contains vertices related to q. Communities, which are prevalent in attributed graphs such as social networks and knowledge bases, can be used in emerging applications such as product advertisement and setting up of social events. In this talk, we investigate the attributed community query (or ACQ), which returns an attributed community (AC) for an attributed graph. The AC is a subgraph of G, which satisfies both structure cohesiveness (i.e., its vertices are tightly connected) and keyword cohesiveness (i.e., its vertices share common keywords). The AC enables a better understanding of how and why a community is formed (e.g., members of an AC have a common interest in music, because they all have the same keyword “music”). An AC can be “personalized”; for example, an ACQ user may specify that an AC returned should be related to some specific keywords like “research”and “sports”. To enable efficient AC search, we develop the CL-tree index structure and three algorithms based on it. We evaluate our solutions on four large graphs, namely Flickr, DBLP, Tencent, and DBpedia. Our results show that ACs are more effective and efficient than existing community retrieval approaches. Moreover, an AC contains more precise and personalized information than that of existing community search and detection methods.
We further generalize the keyword –based attributed graphs to spatial-based attributed graphs, in which each vertex has a location, and study the spatial-aware community (SAC) search problem. An SAC is a community with high structure cohesiveness and spatial cohesiveness. The structure cohesiveness mainly measures the social connections within the community, while the spatial cohesiveness focuses on the closeness among their geo-locations. We propose two exact algorithms, and three efficient approximation algorithms. Our experiments show that SAC search achieves higher effectiveness than the state-of-the-art CD and CS algorithms. |
Description | Session 1 - KeynoteTalk 1 |
Persistent Identifier | http://hdl.handle.net/10722/255187 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cheng, CK | - |
dc.date.accessioned | 2018-06-28T09:57:07Z | - |
dc.date.available | 2018-06-28T09:57:07Z | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | Workshop on Mobility Analytics for Spatio-temporal and Social Data (MATES 2017), co- located with VLDB 2017, Munich, Germany, 28 August - 1 September 2017 | - |
dc.identifier.uri | http://hdl.handle.net/10722/255187 | - |
dc.description | Session 1 - KeynoteTalk 1 | - |
dc.description.abstract | Given a graph G and a vertex q ∈ G, the community search query returns a subgraph of G that contains vertices related to q. Communities, which are prevalent in attributed graphs such as social networks and knowledge bases, can be used in emerging applications such as product advertisement and setting up of social events. In this talk, we investigate the attributed community query (or ACQ), which returns an attributed community (AC) for an attributed graph. The AC is a subgraph of G, which satisfies both structure cohesiveness (i.e., its vertices are tightly connected) and keyword cohesiveness (i.e., its vertices share common keywords). The AC enables a better understanding of how and why a community is formed (e.g., members of an AC have a common interest in music, because they all have the same keyword “music”). An AC can be “personalized”; for example, an ACQ user may specify that an AC returned should be related to some specific keywords like “research”and “sports”. To enable efficient AC search, we develop the CL-tree index structure and three algorithms based on it. We evaluate our solutions on four large graphs, namely Flickr, DBLP, Tencent, and DBpedia. Our results show that ACs are more effective and efficient than existing community retrieval approaches. Moreover, an AC contains more precise and personalized information than that of existing community search and detection methods. We further generalize the keyword –based attributed graphs to spatial-based attributed graphs, in which each vertex has a location, and study the spatial-aware community (SAC) search problem. An SAC is a community with high structure cohesiveness and spatial cohesiveness. The structure cohesiveness mainly measures the social connections within the community, while the spatial cohesiveness focuses on the closeness among their geo-locations. We propose two exact algorithms, and three efficient approximation algorithms. Our experiments show that SAC search achieves higher effectiveness than the state-of-the-art CD and CS algorithms. | - |
dc.language | eng | - |
dc.relation.ispartof | Mobility Analytics for Spatio-temporal and Social Data (MATES 2017), co- located with VLDB 2017 | - |
dc.title | Effective and Efficient Community Search | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Cheng, CK: ckcheng@cs.hku.hk | - |
dc.identifier.authority | Cheng, CK=rp00074 | - |
dc.identifier.hkuros | 275528 | - |