Gateway finder in large graphs: Problem definitions and fast solutions

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

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


Given a graph, how to find a small group of 'gateways', that is a small subset of nodes that are crucial in connecting the source to the target? For instance, 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? We formally formulate this problem in two scenarios: Pair-Gateway and Group-Gateway. For each scenario, we show that it is sub-modular and thus it can be solved near-optimally. We further give fast, scalable algorithms to find such gateways. Extensive experimental evaluations on real data sets demonstrate the effectiveness and efficiency of the proposed methods.

Original languageEnglish (US)
Pages (from-to)391-411
Number of pages21
JournalInformation Retrieval
Issue number3-4
StatePublished - Jun 2012
Externally publishedYes


  • Gateway
  • Graph mining
  • Scalability
  • Social network
  • Sub-modularity

ASJC Scopus subject areas

  • Information Systems
  • Library and Information Sciences


Dive into the research topics of 'Gateway finder in large graphs: Problem definitions and fast solutions'. Together they form a unique fingerprint.

Cite this