Towards Maximum Independent Sets on Massive Graphs

Yu  Liu; Jiaheng Lu; Hua  Yang; Xiaokui  Xiao; Zhewei  Wei

Towards Maximum Independent Sets on Massive Graphs

Yu Liu, Jiaheng Lu, Hua Yang, Xiaokui Xiao, Zhewei Wei

Tietojenkäsittelytieteen osasto

Tutkimustuotos: Artikkelijulkaisu › Artikkeli › Tieteellinen › vertaisarvioitu

Abstrakti

Graph, maximum independent set

Alkuperäiskieli	englanti
Lehti	Proceedings of the VLDB Endowment
Vuosikerta	8
Numero	13
Sivut	2122-2133
Sivumäärä	12
ISSN	2150-8097
Tila	Julkaistu - 2015
OKM-julkaisutyyppi	A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä, vertaisarvioitu

Lisätietoja

Maximum independent set (MIS) is a fundamental problem in graph
theory and it has important applications in many areas such as social
network analysis, graphical information systems and coding
theory. The problem is NP-hard, and there has been numerous studies
on its approximate solutions. While successful to a certain
degree, the existing methods require memory space at least linear
in the size of the input graph. This has become a serious concern in
view of the massive volume of today’s fast-growing graphs.
In this paper, we study the MIS problem under the semi-external
setting, which assumes that the main memory can accommodate
all vertices of the graph but not all edges. We present a greedy
algorithm and a general vertex-swap framework, which swaps vertices
to incrementally increase the size of independent sets. Our
solutions require only few sequential scans of graphs on the disk
file, thus enabling in-memory computation without costly random
disk accesses. Experiments on large-scale datasets show that our
solutions are able to compute a large independent set for a massive
graph with 59 million vertices and 151 million edges using a commodity
machine, with a memory cost of 469MB and a time cost of
three minutes.

Tieteenalat

113 Tietojenkäsittely- ja informaatiotieteet

Pääsy asiakirjaan

p2122_luLopullinen julkaistu versio, 360 KB

Muut tiedostot ja linkit

Siteeraa tätä

@article{52c3640766ef47dc921521ec42d451fa,

title = "Towards Maximum Independent Sets on Massive Graphs",

abstract = "Graph, maximum independent set",

keywords = "113 Computer and information sciences",

author = "Yu Liu and Jiaheng Lu and Hua Yang and Xiaokui Xiao and Zhewei Wei",

note = "Maximum independent set (MIS) is a fundamental problem in graph theory and it has important applications in many areas such as social network analysis, graphical information systems and coding theory. The problem is NP-hard, and there has been numerous studies on its approximate solutions. While successful to a certain degree, the existing methods require memory space at least linear in the size of the input graph. This has become a serious concern in view of the massive volume of today{\textquoteright}s fast-growing graphs. In this paper, we study the MIS problem under the semi-external setting, which assumes that the main memory can accommodate all vertices of the graph but not all edges. We present a greedy algorithm and a general vertex-swap framework, which swaps vertices to incrementally increase the size of independent sets. Our solutions require only few sequential scans of graphs on the disk file, thus enabling in-memory computation without costly random disk accesses. Experiments on large-scale datasets show that our solutions are able to compute a large independent set for a massive graph with 59 million vertices and 151 million edges using a commodity machine, with a memory cost of 469MB and a time cost of three minutes. ",

year = "2015",

language = "English",

volume = "8",

pages = "2122--2133",

journal = "Proceedings of the VLDB Endowment",

issn = "2150-8097",

publisher = "VLDB Endowment",

number = "13",

}

TY - JOUR

T1 - Towards Maximum Independent Sets on Massive Graphs

AU - Liu, Yu

AU - Lu, Jiaheng

AU - Yang, Hua

AU - Xiao, Xiaokui

AU - Wei, Zhewei

N1 - Maximum independent set (MIS) is a fundamental problem in graph theory and it has important applications in many areas such as social network analysis, graphical information systems and coding theory. The problem is NP-hard, and there has been numerous studies on its approximate solutions. While successful to a certain degree, the existing methods require memory space at least linear in the size of the input graph. This has become a serious concern in view of the massive volume of today’s fast-growing graphs. In this paper, we study the MIS problem under the semi-external setting, which assumes that the main memory can accommodate all vertices of the graph but not all edges. We present a greedy algorithm and a general vertex-swap framework, which swaps vertices to incrementally increase the size of independent sets. Our solutions require only few sequential scans of graphs on the disk file, thus enabling in-memory computation without costly random disk accesses. Experiments on large-scale datasets show that our solutions are able to compute a large independent set for a massive graph with 59 million vertices and 151 million edges using a commodity machine, with a memory cost of 469MB and a time cost of three minutes.

PY - 2015

Y1 - 2015

N2 - Graph, maximum independent set

AB - Graph, maximum independent set

KW - 113 Computer and information sciences

UR - http://www.vldb.org/pvldb/vol8/p2122-lu.pdf

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

M3 - Article

SN - 2150-8097

VL - 8

SP - 2122

EP - 2133

JO - Proceedings of the VLDB Endowment

JF - Proceedings of the VLDB Endowment

IS - 13

ER -