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 contribution › 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 (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 - , 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	https://link.springer.com/book/10.1007/978-3-030-34223-4 https://wise2019.comp.polyu.edu.hk/

Scopus Subject Areas

Theoretical Computer Science
Computer Science(all)

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.; 20th International Conference on Web Information Systems Engineering, WISE 2019 ; Conference date: 19-01-2020 Through 22-01-2020",

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

url = "https://link.springer.com/book/10.1007/978-3-030-34223-4, https://wise2019.comp.polyu.edu.hk/",

}

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, Hong Kong, 19/01/20. 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 contribution › 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.

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 contribution

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 - 19 January 2020 through 22 January 2020

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