Fast Algorithms for Intimate-Core Group Search in Weighted Graphs

Longxu Sun; Xin Huang; Rong Hua Li; Jianliang Xu

doi:10.1007/978-3-030-34223-4_46

Fast Algorithms for Intimate-Core Group Search in Weighted Graphs

Longxu Sun^*, Xin Huang, Rong Hua Li, Jianliang Xu

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

2 Citations (Scopus)

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 (Electronic)	9783030342234
ISBN (Print)	9783030342227
DOIs	https://doi.org/10.1007/978-3-030-34223-4_46
Publication status	Published - 29 Oct 2019
Event	20th International Conference on Web Information Systems Engineering, WISE 2019 - Hongkong, Hong Kong Duration: 26 Nov 2019 → 30 Nov 2019

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
City	Hongkong
Period	26/11/19 → 30/11/19

Scopus Subject Areas

Theoretical Computer Science
General Computer Science

User-Defined Keywords

Community search
Graph mining
K-core
Weighted graphs

Access to Document

10.1007/978-3-030-34223-4_46

Cite this

Sun, L., Huang, X., Li, R. H., & Xu, J. (2019). Fast Algorithms for Intimate-Core Group Search in Weighted Graphs. In R. Cheng, N. Mamoulis, Y. Sun, & X. Huang (Eds.), Web Information Systems Engineering – WISE 2019 - 20th International Conference, Proceedings (pp. 728-744). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11881 LNCS). Springer. https://doi.org/10.1007/978-3-030-34223-4_46

Sun, Longxu ; Huang, Xin ; Li, Rong Hua et al. / Fast Algorithms for Intimate-Core Group Search in Weighted Graphs. Web Information Systems Engineering – WISE 2019 - 20th International Conference, Proceedings. editor / Reynold Cheng ; Nikos Mamoulis ; Yizhou Sun ; Xin Huang. Springer, 2019. pp. 728-744 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{65f69a2135c945b2bab3f9f6af85c0ca,

title = "Fast Algorithms for Intimate-Core Group Search in Weighted Graphs",

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.",

keywords = "Community search, Graph mining, K-core, Weighted graphs",

author = "Longxu Sun and Xin Huang and Li, {Rong Hua} and Jianliang Xu",

note = "Funding information: This work is supported by the NSFC Nos. 61702435, 61772346, U1809206, RGC Nos. 12200917, 12200817, and CRF C6030-18GF. Publisher copyright: {\textcopyright} Springer Nature Switzerland AG 2019; 20th International Conference on Web Information Systems Engineering, WISE 2019 ; Conference date: 26-11-2019 Through 30-11-2019",

year = "2019",

month = oct,

day = "29",

doi = "10.1007/978-3-030-34223-4_46",

language = "English",

isbn = "9783030342227",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "728--744",

editor = "Reynold Cheng and Nikos Mamoulis and Yizhou Sun and Xin Huang",

booktitle = "Web Information Systems Engineering – WISE 2019 - 20th International Conference, Proceedings",

}

Sun, L, Huang, X, Li, RH & Xu, J 2019, Fast Algorithms for Intimate-Core Group Search in Weighted Graphs. in R Cheng, N Mamoulis, Y Sun & X Huang (eds), Web Information Systems Engineering – WISE 2019 - 20th International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11881 LNCS, Springer, pp. 728-744, 20th International Conference on Web Information Systems Engineering, WISE 2019, Hongkong, Hong Kong, 26/11/19. https://doi.org/10.1007/978-3-030-34223-4_46

Fast Algorithms for Intimate-Core Group Search in Weighted Graphs. / Sun, Longxu; Huang, Xin; Li, Rong Hua et al.
Web Information Systems Engineering – WISE 2019 - 20th International Conference, Proceedings. ed. / Reynold Cheng; Nikos Mamoulis; Yizhou Sun; Xin Huang. Springer, 2019. p. 728-744 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11881 LNCS).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Fast Algorithms for Intimate-Core Group Search in Weighted Graphs

AU - Sun, Longxu

AU - Huang, Xin

AU - Li, Rong Hua

AU - Xu, Jianliang

N1 - Funding information: This work is supported by the NSFC Nos. 61702435, 61772346, U1809206, RGC Nos. 12200917, 12200817, and CRF C6030-18GF. Publisher copyright: © Springer Nature Switzerland AG 2019

PY - 2019/10/29

Y1 - 2019/10/29

N2 - 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.

AB - 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.

KW - Community search

KW - Graph mining

KW - K-core

KW - Weighted graphs

UR - http://www.scopus.com/inward/record.url?scp=85076980964&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-34223-4_46

DO - 10.1007/978-3-030-34223-4_46

M3 - Conference proceeding

AN - SCOPUS:85076980964

SN - 9783030342227

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 728

EP - 744

BT - Web Information Systems Engineering – WISE 2019 - 20th International Conference, Proceedings

A2 - Cheng, Reynold

A2 - Mamoulis, Nikos

A2 - Sun, Yizhou

A2 - Huang, Xin

PB - Springer

T2 - 20th International Conference on Web Information Systems Engineering, WISE 2019

Y2 - 26 November 2019 through 30 November 2019

ER -

Sun L, Huang X, Li RH, Xu J. Fast Algorithms for Intimate-Core Group Search in Weighted Graphs. In Cheng R, Mamoulis N, Sun Y, Huang X, editors, Web Information Systems Engineering – WISE 2019 - 20th International Conference, Proceedings. Springer. 2019. p. 728-744. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-34223-4_46

Fast Algorithms for Intimate-Core Group Search in Weighted Graphs

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this