Reverse Ranking by Graph Structure
Eliav Buchnik, Edith Cohen · 2016
Distances in a network capture relations between nodes and are the basis of centrality, similarity, and influence measures. Often, however, the relevance of a node u to a node v is more precisely measured not by the magnitude of the distance, but by the number of nodes that are closer to v than u. That is, by the rank of u in an ordering of nodes by increasing distance from v. We identify and address fundamental challenges in rank-based graph mining. We first consider single-source computation of reverse-ranks and design a "Dijkstra-like" algorithm which computes nodes in order of increasing approximate reverse rank while only traversing edges adjacent to returned nodes. We then define reverse-rank influence, which naturally extends reverse nearest neighbors influence [Korn and Muthukrishnan 2000] and builds on a well studied distance-based influence. We present near-linear algorithms for greedy approximate reverse-rank influence maximization. The design relies on our single-source algorithm. Our algorithms utilize near-linear preprocessing of the network to compute all-distance sketches. As a contribution of independent interest, we present a novel algorithm for computing these sketches, which have many other applications, on multi-core architectures.
Cited by 3 works. doi:10.1145/2896377.2901458 Open-access PDF
Authors
References
- The Elements of Statistical Learning
- Nearest neighbor pattern classification
- Centrality in social networks conceptual clarification
- Maximizing the spread of influence through a social network
- A Generalization of Sampling Without Replacement From a Finite Universe
- An analysis of approximations for maximizing submodular set functions—I
- A threshold of ln n for approximating set cover
- The Centrality Index of a Graph
- A Mathematical Model for Group Structures
- Wsabie: Scaling up to large vocabulary image annotation