Efficient computation of a near-maximum independent set over evolving graphs

Weiguo Zheng; Qichen Wang; Jeffrey Xu Yu; Hong Cheng; Lei Zou

doi:10.1109/ICDE.2018.00083

Efficient computation of a near-maximum independent set over evolving graphs

Weiguo Zheng, Qichen Wang, Jeffrey Xu Yu, Hong Cheng, Lei Zou

Department of Computer Science

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

10 Citations (Scopus)

Abstract

Most existing algorithms computing the maximum independent set (MIS) or independent set (IS) are designed for handling static graphs, which may not be practicable as many networks are dynamically evolving over time. In this paper, we study the MIS/IS problem in evolving graphs by considering graph update operations: vertex/edge addition and vertex/edge deletion. Instead of computing the MIS/IS of the updated graph from scratch, we propose a baseline algorithm that finds the MIS/IS at time t i+1 based on the MIS/IS at time ti. Due to the hardness of computing an exact MIS, we develop an efficient constant-Time algorithm LSTwo to return a high-quality (large-size) independent set. Then we design a lazy search algorithm which produces higher-quality independent sets. To improve the time efficiency further, we devise the conditional besieging and k-petal based methods to reduce the search space. Extensive experimental studies over large-scale graphs confirm the effectiveness and efficiency of our proposed algorithms.

Original language	English
Title of host publication	Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018
Publisher	IEEE
Pages	869-880
Number of pages	12
ISBN (Electronic)	9781538655207
ISBN (Print)	9781538655214
DOIs	https://doi.org/10.1109/ICDE.2018.00083
Publication status	Published - 16 Apr 2018
Event	34th IEEE International Conference on Data Engineering, ICDE 2018 - Paris, France Duration: 16 Apr 2018 → 19 Apr 2018 https://ieeexplore.ieee.org/xpl/conhome/8476188/proceeding

Publication series

Name	Proceedings - IEEE International Conference on Data Engineering (ICDE)
ISSN (Print)	1063-6382
ISSN (Electronic)	2375-026X

Conference

Conference	34th IEEE International Conference on Data Engineering, ICDE 2018
Country/Territory	France
City	Paris
Period	16/04/18 → 19/04/18
Internet address	https://ieeexplore.ieee.org/xpl/conhome/8476188/proceeding

Scopus Subject Areas

Information Systems
Information Systems and Management
Hardware and Architecture

User-Defined Keywords

Evolving graph
greedy algorithm
independent set
maximum independent set

Access to Document

10.1109/ICDE.2018.00083

Cite this

@inproceedings{cf6acfeff4d449a7baadb257d49d4760,

title = "Efficient computation of a near-maximum independent set over evolving graphs",

abstract = "Most existing algorithms computing the maximum independent set (MIS) or independent set (IS) are designed for handling static graphs, which may not be practicable as many networks are dynamically evolving over time. In this paper, we study the MIS/IS problem in evolving graphs by considering graph update operations: vertex/edge addition and vertex/edge deletion. Instead of computing the MIS/IS of the updated graph from scratch, we propose a baseline algorithm that finds the MIS/IS at time t i+1 based on the MIS/IS at time ti. Due to the hardness of computing an exact MIS, we develop an efficient constant-Time algorithm LSTwo to return a high-quality (large-size) independent set. Then we design a lazy search algorithm which produces higher-quality independent sets. To improve the time efficiency further, we devise the conditional besieging and k-petal based methods to reduce the search space. Extensive experimental studies over large-scale graphs confirm the effectiveness and efficiency of our proposed algorithms.",

keywords = "Evolving graph, greedy algorithm, independent set, maximum independent set",

author = "Weiguo Zheng and Qichen Wang and {Xu Yu}, Jeffrey and Hong Cheng and Lei Zou",

note = "Funding Information: This work was substantially supported by grants from the Research Grant Council of the Hong Kong Special Administrative Region, China [Project No.: CUHK 14205617] and [Project No.: CUHK 14221716]. Lei Zou was supported by NSFC under grant 61622201 and 61532010. Publisher Copyright: {\textcopyright} 2018 IEEE.; 34th IEEE International Conference on Data Engineering, ICDE 2018 ; Conference date: 16-04-2018 Through 19-04-2018",

year = "2018",

month = apr,

day = "16",

doi = "10.1109/ICDE.2018.00083",

language = "English",

isbn = "9781538655214",

series = "Proceedings - IEEE International Conference on Data Engineering (ICDE)",

publisher = "IEEE",

pages = "869--880",

booktitle = "Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/8476188/proceeding",

}

Zheng, W, Wang, Q, Xu Yu, J, Cheng, H & Zou, L 2018, Efficient computation of a near-maximum independent set over evolving graphs. in Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018. Proceedings - IEEE International Conference on Data Engineering (ICDE), IEEE, pp. 869-880, 34th IEEE International Conference on Data Engineering, ICDE 2018, Paris, France, 16/04/18. https://doi.org/10.1109/ICDE.2018.00083

Efficient computation of a near-maximum independent set over evolving graphs. / Zheng, Weiguo; Wang, Qichen; Xu Yu, Jeffrey et al.
Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018. IEEE, 2018. p. 869-880 (Proceedings - IEEE International Conference on Data Engineering (ICDE)).

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

TY - GEN

T1 - Efficient computation of a near-maximum independent set over evolving graphs

AU - Zheng, Weiguo

AU - Wang, Qichen

AU - Xu Yu, Jeffrey

AU - Cheng, Hong

AU - Zou, Lei

N1 - Funding Information: This work was substantially supported by grants from the Research Grant Council of the Hong Kong Special Administrative Region, China [Project No.: CUHK 14205617] and [Project No.: CUHK 14221716]. Lei Zou was supported by NSFC under grant 61622201 and 61532010. Publisher Copyright: © 2018 IEEE.

PY - 2018/4/16

Y1 - 2018/4/16

N2 - Most existing algorithms computing the maximum independent set (MIS) or independent set (IS) are designed for handling static graphs, which may not be practicable as many networks are dynamically evolving over time. In this paper, we study the MIS/IS problem in evolving graphs by considering graph update operations: vertex/edge addition and vertex/edge deletion. Instead of computing the MIS/IS of the updated graph from scratch, we propose a baseline algorithm that finds the MIS/IS at time t i+1 based on the MIS/IS at time ti. Due to the hardness of computing an exact MIS, we develop an efficient constant-Time algorithm LSTwo to return a high-quality (large-size) independent set. Then we design a lazy search algorithm which produces higher-quality independent sets. To improve the time efficiency further, we devise the conditional besieging and k-petal based methods to reduce the search space. Extensive experimental studies over large-scale graphs confirm the effectiveness and efficiency of our proposed algorithms.

AB - Most existing algorithms computing the maximum independent set (MIS) or independent set (IS) are designed for handling static graphs, which may not be practicable as many networks are dynamically evolving over time. In this paper, we study the MIS/IS problem in evolving graphs by considering graph update operations: vertex/edge addition and vertex/edge deletion. Instead of computing the MIS/IS of the updated graph from scratch, we propose a baseline algorithm that finds the MIS/IS at time t i+1 based on the MIS/IS at time ti. Due to the hardness of computing an exact MIS, we develop an efficient constant-Time algorithm LSTwo to return a high-quality (large-size) independent set. Then we design a lazy search algorithm which produces higher-quality independent sets. To improve the time efficiency further, we devise the conditional besieging and k-petal based methods to reduce the search space. Extensive experimental studies over large-scale graphs confirm the effectiveness and efficiency of our proposed algorithms.

KW - Evolving graph

KW - greedy algorithm

KW - independent set

KW - maximum independent set

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

U2 - 10.1109/ICDE.2018.00083

DO - 10.1109/ICDE.2018.00083

M3 - Conference proceeding

AN - SCOPUS:85057104712

SN - 9781538655214

T3 - Proceedings - IEEE International Conference on Data Engineering (ICDE)

SP - 869

EP - 880

BT - Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018

PB - IEEE

T2 - 34th IEEE International Conference on Data Engineering, ICDE 2018

Y2 - 16 April 2018 through 19 April 2018

ER -

Efficient computation of a near-maximum independent set over evolving graphs

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this