Spotting significant changing subgraphs in evolving graphs

Zheng Liu; Jeffrey Xu Yu; Yiping Ke; Xuemin Lin; Lei Chen

doi:10.1109/ICDM.2008.112

Spotting significant changing subgraphs in evolving graphs

Zheng Liu^*, Jeffrey Xu Yu, Yiping Ke, Xuemin Lin, Lei Chen

^*Corresponding author for this work

Department of Computer Science and Engineering

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

27 Citations (Scopus)

Abstract

Graphs are popularly used to model structural relationships between objects. In many application domains such associal networks, sensor networks and telecommunication, graphs evolve over time. In this paper, we study a new problem of discovering the subgraphs that exhibit significant changes in evolving graphs. This problem is challenging since it is hard to define changing regions that are closely related to the actual changes (i.e., additions/deletions of edges/nodes) in graphs. We formalize the problem, and design an efficient algorithm that is able to identify the changing subgraphs incrementally. Our experimental results on real datasets show that our solution is very efficient and the resultant subgraphs are of high quality.

Original language	English
Title of host publication	Proceedings - 8th IEEE International Conference on Data Mining, ICDM 2008
Pages	917-922
Number of pages	6
DOIs	https://doi.org/10.1109/ICDM.2008.112
Publication status	Published - 2008
Event	8th IEEE International Conference on Data Mining, ICDM 2008 - Pisa, Italy Duration: 15 Dec 2008 → 19 Dec 2008

Publication series

Name	Proceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)	1550-4786

Conference

Conference	8th IEEE International Conference on Data Mining, ICDM 2008
Country/Territory	Italy
City	Pisa
Period	15/12/08 → 19/12/08

Access to Document

10.1109/ICDM.2008.112

Cite this

@inproceedings{ce7a1ae126224455a3209ae08b9ee873,

title = "Spotting significant changing subgraphs in evolving graphs",

abstract = "Graphs are popularly used to model structural relationships between objects. In many application domains such associal networks, sensor networks and telecommunication, graphs evolve over time. In this paper, we study a new problem of discovering the subgraphs that exhibit significant changes in evolving graphs. This problem is challenging since it is hard to define changing regions that are closely related to the actual changes (i.e., additions/deletions of edges/nodes) in graphs. We formalize the problem, and design an efficient algorithm that is able to identify the changing subgraphs incrementally. Our experimental results on real datasets show that our solution is very efficient and the resultant subgraphs are of high quality.",

author = "Zheng Liu and Yu, \{Jeffrey Xu\} and Yiping Ke and Xuemin Lin and Lei Chen",

year = "2008",

doi = "10.1109/ICDM.2008.112",

language = "English",

isbn = "9780769535029",

series = "Proceedings - IEEE International Conference on Data Mining, ICDM",

pages = "917--922",

booktitle = "Proceedings - 8th IEEE International Conference on Data Mining, ICDM 2008",

note = "8th IEEE International Conference on Data Mining, ICDM 2008 ; Conference date: 15-12-2008 Through 19-12-2008",

}

Liu, Z, Yu, JX, Ke, Y, Lin, X & Chen, L 2008, Spotting significant changing subgraphs in evolving graphs. in Proceedings - 8th IEEE International Conference on Data Mining, ICDM 2008., 4781201, Proceedings - IEEE International Conference on Data Mining, ICDM, pp. 917-922, 8th IEEE International Conference on Data Mining, ICDM 2008, Pisa, Italy, 15/12/08. https://doi.org/10.1109/ICDM.2008.112

Spotting significant changing subgraphs in evolving graphs. / Liu, Zheng; Yu, Jeffrey Xu; Ke, Yiping et al.
Proceedings - 8th IEEE International Conference on Data Mining, ICDM 2008. 2008. p. 917-922 4781201 (Proceedings - IEEE International Conference on Data Mining, ICDM).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - Spotting significant changing subgraphs in evolving graphs

AU - Liu, Zheng

AU - Yu, Jeffrey Xu

AU - Ke, Yiping

AU - Lin, Xuemin

AU - Chen, Lei

PY - 2008

Y1 - 2008

N2 - Graphs are popularly used to model structural relationships between objects. In many application domains such associal networks, sensor networks and telecommunication, graphs evolve over time. In this paper, we study a new problem of discovering the subgraphs that exhibit significant changes in evolving graphs. This problem is challenging since it is hard to define changing regions that are closely related to the actual changes (i.e., additions/deletions of edges/nodes) in graphs. We formalize the problem, and design an efficient algorithm that is able to identify the changing subgraphs incrementally. Our experimental results on real datasets show that our solution is very efficient and the resultant subgraphs are of high quality.

AB - Graphs are popularly used to model structural relationships between objects. In many application domains such associal networks, sensor networks and telecommunication, graphs evolve over time. In this paper, we study a new problem of discovering the subgraphs that exhibit significant changes in evolving graphs. This problem is challenging since it is hard to define changing regions that are closely related to the actual changes (i.e., additions/deletions of edges/nodes) in graphs. We formalize the problem, and design an efficient algorithm that is able to identify the changing subgraphs incrementally. Our experimental results on real datasets show that our solution is very efficient and the resultant subgraphs are of high quality.

UR - https://www.webofscience.com/wos/woscc/full-record/WOS:000264173600107

UR - https://openalex.org/W2127765405

UR - https://www.scopus.com/pages/publications/67049162766

U2 - 10.1109/ICDM.2008.112

DO - 10.1109/ICDM.2008.112

M3 - Conference Paper published in a book

SN - 9780769535029

T3 - Proceedings - IEEE International Conference on Data Mining, ICDM

SP - 917

EP - 922

BT - Proceedings - 8th IEEE International Conference on Data Mining, ICDM 2008

T2 - 8th IEEE International Conference on Data Mining, ICDM 2008

Y2 - 15 December 2008 through 19 December 2008

ER -

Spotting significant changing subgraphs in evolving graphs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this