File(s) under permanent embargo
Contextual community search over large social networks
conference contribution
posted on 2019-01-01, 00:00 authored by L Chen, C Liu, K Liao, Jianxin LiJianxin Li, R ZhouCommunity search on attributed networks has recently attracted great deal of research interest. However, most of existing works require query users to specify some community structure parameters. This may not be always practical as sometimes a user does not have the knowledge and experience to decide the suitable parameters. In this paper, we propose a novel parameter-free contextual community model for attributed community search. The proposed model only requires a query context, i.e., a set of keywords describing the desired matching community context, while the community returned is both structure and attribute cohesive w.r.t. the provided query context. We theoretically show that both our exact and approximate contextual community search algorithms can be executed in worst case polynomial time. The exact algorithm is based on an elegant parametric maximum flow technique and the approximation algorithm that significantly improves the search efficiency is analyzed to have an approximation factor of 1/3. In the experiment, we use six real networks with ground-truth communities to evaluate the effectiveness of our contextual community model. Experimental results demonstrate that the proposed model can find near ground-truth communities. We also test both our exact and approximate algorithms using eight large real networks to demonstrate the high efficiency of the proposed algorithms.
History
Event
IEEE Computer Society. Conference (35th : 2019 : Macao, China)Series
IEEE Computer Society ConferencePagination
88 - 99Publisher
Institute of Electrical and Electronics EngineersLocation
Macao, ChinaPlace of publication
Piscataway, N.J.Publisher DOI
Start date
2019-04-08End date
2019-04-11ISSN
1084-4627ISBN-13
9781538674741Language
engPublication classification
E1 Full written paper - refereedCopyright notice
2019, IEEEEditor/Contributor(s)
[Unknown]Title of proceedings
ICDE 2019 : Proceedings of the 2019 IEEE 35th International Conference on Data EngineeringUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC