Abstract: Several real-world problems including network influence maximization, rank aggregation, etc. can be posed as problems that output a good ranking of a set of items. We introduce a unifying algorithmic framework based on a novel notion called rank refinement of monotonic set functions to tackle such problems. We prove that under very mild monotonicity assumptions the proposed algorithm converges to a stable ranking. We show that IMRank, a highly scalable influence maximization algorithm can be derived as a special case of our framework. By careful choice of the monotonic set functions, we derive novel generalizations of IMRank that balances the influence and diversity of the top-ranked nodes without compromising on scalability. We provide extensive experimental analysis on both synthetic data-sets based on stochastic block models and large scale real-world data-sets to demonstrate the efficacy of the proposed framework.
Authors: Prateek Yadav and Arun Rajkumar (IIT Madras)