BASSET: Scalable gateway finder in large graphs

Hanghang Tong; Spiros Papadimitriou; Christos Faloutsos; Philip S. Yu; Tina Eliassi-Rad

doi:10.1007/978-3-642-13672-6_43

BASSET: Scalable gateway finder in large graphs

Hanghang Tong, Spiros Papadimitriou, Christos Faloutsos, Philip S. Yu, Tina Eliassi-Rad

National Center for Supercomputing Applications (NCSA)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Given a social network, who is the best person to introduce you to, say, Chris Ferguson, the poker champion? Or, given a network of people and skills, who is the best person to help you learn about, say, wavelets? The goal is to find a small group of 'gateways': persons who is close enough to us, as well as close enough to the target (person, or skill) or, in other words, are crucial in connecting us to the target. The main contributions are the following: (a) we show how to formulate this problem precisely; (b) we show that it is sub-modular and thus it can be solved near-optimally; (c) we give fast, scalable algorithms to find such gateways. Experiments on real data sets validate the effectiveness and efficiency of the proposed methods, achieving up to 6,000,000x speedup.

Original language	English (US)
Title of host publication	Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings
Pages	449-463
Number of pages	15
Edition	PART 2
DOIs	https://doi.org/10.1007/978-3-642-13672-6_43
State	Published - 2010
Event	14th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2010 - Hyderabad, India Duration: Jun 21 2010 → Jun 24 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 2
Volume	6119 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	14th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2010
Country/Territory	India
City	Hyderabad
Period	6/21/10 → 6/24/10

Keywords

Gateway
Graph-Mining
Scalability
Sub-modularity

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-3-642-13672-6_43

Library availability

Discover UIUC Full Text

Cite this

Tong, H., Papadimitriou, S., Faloutsos, C., Yu, P. S., & Eliassi-Rad, T. (2010). BASSET: Scalable gateway finder in large graphs. In Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings (PART 2 ed., pp. 449-463). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6119 LNAI, No. PART 2). https://doi.org/10.1007/978-3-642-13672-6_43

BASSET: Scalable gateway finder in large graphs. / Tong, Hanghang; Papadimitriou, Spiros; Faloutsos, Christos et al.
Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings. PART 2. ed. 2010. p. 449-463 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6119 LNAI, No. PART 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Tong, H, Papadimitriou, S, Faloutsos, C, Yu, PS & Eliassi-Rad, T 2010, BASSET: Scalable gateway finder in large graphs. in Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 6119 LNAI, pp. 449-463, 14th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2010, Hyderabad, India, 6/21/10. https://doi.org/10.1007/978-3-642-13672-6_43

Tong H, Papadimitriou S, Faloutsos C, Yu PS, Eliassi-Rad T. BASSET: Scalable gateway finder in large graphs. In Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings. PART 2 ed. 2010. p. 449-463. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). doi: 10.1007/978-3-642-13672-6_43

Tong, Hanghang ; Papadimitriou, Spiros ; Faloutsos, Christos et al. / BASSET : Scalable gateway finder in large graphs. Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings. PART 2. ed. 2010. pp. 449-463 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).

@inproceedings{b047060ec1d240c8b6747dd76706175b,

title = "BASSET: Scalable gateway finder in large graphs",

abstract = "Given a social network, who is the best person to introduce you to, say, Chris Ferguson, the poker champion? Or, given a network of people and skills, who is the best person to help you learn about, say, wavelets? The goal is to find a small group of 'gateways': persons who is close enough to us, as well as close enough to the target (person, or skill) or, in other words, are crucial in connecting us to the target. The main contributions are the following: (a) we show how to formulate this problem precisely; (b) we show that it is sub-modular and thus it can be solved near-optimally; (c) we give fast, scalable algorithms to find such gateways. Experiments on real data sets validate the effectiveness and efficiency of the proposed methods, achieving up to 6,000,000x speedup.",

keywords = "Gateway, Graph-Mining, Scalability, Sub-modularity",

author = "Hanghang Tong and Spiros Papadimitriou and Christos Faloutsos and Yu, {Philip S.} and Tina Eliassi-Rad",

year = "2010",

doi = "10.1007/978-3-642-13672-6_43",

language = "English (US)",

isbn = "3642136710",

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

number = "PART 2",

pages = "449--463",

booktitle = "Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings",

edition = "PART 2",

note = "14th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2010 ; Conference date: 21-06-2010 Through 24-06-2010",

}

TY - GEN

T1 - BASSET

T2 - 14th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2010

AU - Tong, Hanghang

AU - Papadimitriou, Spiros

AU - Faloutsos, Christos

AU - Yu, Philip S.

AU - Eliassi-Rad, Tina

PY - 2010

Y1 - 2010

N2 - Given a social network, who is the best person to introduce you to, say, Chris Ferguson, the poker champion? Or, given a network of people and skills, who is the best person to help you learn about, say, wavelets? The goal is to find a small group of 'gateways': persons who is close enough to us, as well as close enough to the target (person, or skill) or, in other words, are crucial in connecting us to the target. The main contributions are the following: (a) we show how to formulate this problem precisely; (b) we show that it is sub-modular and thus it can be solved near-optimally; (c) we give fast, scalable algorithms to find such gateways. Experiments on real data sets validate the effectiveness and efficiency of the proposed methods, achieving up to 6,000,000x speedup.

AB - Given a social network, who is the best person to introduce you to, say, Chris Ferguson, the poker champion? Or, given a network of people and skills, who is the best person to help you learn about, say, wavelets? The goal is to find a small group of 'gateways': persons who is close enough to us, as well as close enough to the target (person, or skill) or, in other words, are crucial in connecting us to the target. The main contributions are the following: (a) we show how to formulate this problem precisely; (b) we show that it is sub-modular and thus it can be solved near-optimally; (c) we give fast, scalable algorithms to find such gateways. Experiments on real data sets validate the effectiveness and efficiency of the proposed methods, achieving up to 6,000,000x speedup.

KW - Gateway

KW - Graph-Mining

KW - Scalability

KW - Sub-modularity

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

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

U2 - 10.1007/978-3-642-13672-6_43

DO - 10.1007/978-3-642-13672-6_43

M3 - Conference contribution

AN - SCOPUS:79956301922

SN - 3642136710

SN - 9783642136719

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

SP - 449

EP - 463

BT - Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings

Y2 - 21 June 2010 through 24 June 2010

ER -

BASSET: Scalable gateway finder in large graphs

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this