Publication Type
Conference Proceeding Article
Version
acceptedVersion
Publication Date
5-2024
Abstract
What is the widest community in which a person exercises a strong impact? Although extensive attention has been devoted to searching communities containing given individuals, the problem of finding their unique communities of influence has barely been examined. In this paper, we study the novel problem of Characteristic cOmmunity Discovery (COD) in attributed graphs. Our goal is to identify the largest community, taking into account the query attribute, in which the query node has a significant impact. The key challenge of the COD problem is that it requires evaluating the influence of the query node over a large number of hierarchically structured communities. We first propose a novel compressed COD evaluation approach to accelerate the influence estimation by eliminating redundant computations for overlapping communities. Then, we further devise a local hierarchical reclustering method to alleviate the skewness of hierarchical communities generated by global clustering for a specific query attribute. Extensive experiments confirm the effectiveness and efficiency of our solutions to COD: they find characteristic communities better than existing community search methods by several quality measures and achieve up to 25 x speedups against well-crafted baselines.
Discipline
Databases and Information Systems | Numerical Analysis and Scientific Computing
Research Areas
Data Science and Engineering
Publication
2024 IEEE 40th International Conference on Data Engineering (ICDE): Utrecht, May 13-16: Proceedings
First Page
2834
Last Page
2847
ISBN
9798350317152
Identifier
10.1109/ICDE60146.2024.00221
Publisher
IEEE Computer Society
City or Country
Los Alamitos, CA
Citation
NIU, Yudong; LI, Yuchen; KARRAS, Panagiotis; WANG, Yanhao; and LI, Zhao.
Discovering personalized characteristic communities in attributed graphs. (2024). 2024 IEEE 40th International Conference on Data Engineering (ICDE): Utrecht, May 13-16: Proceedings. 2834-2847.
Available at: https://ink.library.smu.edu.sg/sis_research/9335
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1109/ICDE60146.2024.00221
Included in
Databases and Information Systems Commons, Numerical Analysis and Scientific Computing Commons
