|
|||||
|
|
Gateway finder in large graphs: problem definitions and fast solutions |
|
| Authors: | Hanghang Tong Spiros Papadimitriou Christos Faloutsos Philip S Yu Tina Eliassi-Rad |
| Institution: | 1. IBM T.J. Watson Research Center, Yorktown, NY, USA 2. Google Inc, Mountain View, CA, USA 3. Carnegie Mellon University, Pittsburgh, PA, USA 4. University of Illinois at Chicago, Chicago, IL, USA 5. Rutgers University, Newark, NJ, USA |
| Abstract: | 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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |