TY - JOUR
T1 - Gateway finder in large graphs
T2 - Problem definitions and fast solutions
AU - Tong, Hanghang
AU - Papadimitriou, Spiros
AU - Faloutsos, Christos
AU - Yu, Philip S.
AU - Eliassi-Rad, Tina
N1 - Funding Information:
Acknowledgments This material is based upon work supported by the National Science Foundation under Grants No. IIS1017415, IIS 0905215, and DBI-0960443. Research was sponsored by the Defense Threat Reduction Agency under contract No. HDTRA1-10-1-0120 and by the Army Research Laboratory under Cooperative Agreement Number W911NF-09-2-0053. It is continuing through participation in the Anomaly Detection at Multiple Scales (ADAMS) program sponsored by the U.S. Defense Advanced Research Projects Agency (DARPA) under Agreements No. W911NF-11-C-0200 and W911NF-11-C-0088. This work is also partially supported by an IBM Faculty Award and Google Mobile 2014 Program. The content of the information in this document does not necessarily reflect the position or the policy of the Government, and no official endorsement should be inferred. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation, or other funding parties.
PY - 2012/6
Y1 - 2012/6
N2 - 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.
AB - 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.
KW - Gateway
KW - Graph mining
KW - Scalability
KW - Social network
KW - Sub-modularity
UR - http://www.scopus.com/inward/record.url?scp=84861454556&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84861454556&partnerID=8YFLogxK
U2 - 10.1007/s10791-012-9190-3
DO - 10.1007/s10791-012-9190-3
M3 - Article
AN - SCOPUS:84861454556
SN - 1386-4564
VL - 15
SP - 391
EP - 411
JO - Information Retrieval
JF - Information Retrieval
IS - 3-4
ER -