Abstract
Community search that finds query-dependent communities has been studied on various kinds of graphs. As one instance of community search, intimate-core group search over a weighted graph is to find a connected k-core containing all query nodes with the smallest group weight. However, existing state-of-the-art methods start from the maximal k-core to refine an answer, which is practically inefficient for large networks. In this paper, we develop an efficient framework, called local exploration k-core search (LEKS), to find intimate-core groups in graphs. We propose a small-weighted spanning tree to connect query nodes, and then expand the tree level by level to a connected k-core, which is finally refined as an intimate-core group. We also design a protection mechanism for critical nodes to avoid the collapsed k-core. Extensive experiments on real-life networks validate the effectiveness and efficiency of our methods.
Original language | English |
---|---|
Title of host publication | Web Information Systems Engineering – WISE 2019 - 20th International Conference, Proceedings |
Editors | Reynold Cheng, Nikos Mamoulis, Yizhou Sun, Xin Huang |
Publisher | Springer |
Pages | 728-744 |
Number of pages | 17 |
ISBN (Print) | 9783030342227 |
DOIs | |
Publication status | Published - 29 Oct 2019 |
Event | 20th International Conference on Web Information Systems Engineering, WISE 2019 - , Hong Kong Duration: 19 Jan 2020 → 22 Jan 2020 https://link.springer.com/book/10.1007/978-3-030-34223-4 https://wise2019.comp.polyu.edu.hk/ |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 11881 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 20th International Conference on Web Information Systems Engineering, WISE 2019 |
---|---|
Country/Territory | Hong Kong |
Period | 19/01/20 → 22/01/20 |
Internet address |
Scopus Subject Areas
- Theoretical Computer Science
- Computer Science(all)
User-Defined Keywords
- Community search
- Graph mining
- K-core
- Weighted graphs