In this paper, we study the problem of identifying influential users in mobile social networks. Traditional approaches find these users through centralized algorithms on either friendship or social-contact graphs of all users. However, the computational complexity of these algorithms is known to be very high, making them unsuitable for large-scale networks. We propose a  lightweight  and  distributed  protocol, iWander, to identify influential users through fixed-length  random walks . To the best of our knowledge, we are the first to design a distributed protocol on smartphones that leverages random walks for identifying influential mobile users, although this technique has been used in other areas.   The most attractive feature of  iWander  is its  extremely low  message overhead, which lends itself well to mobile applications. We evaluate the performance of  iWander  for two applications, targeted immunization of infectious diseases and target-set selection for information dissemination. Through extensive simulation studies using a real-world mobility trace, we demonstrate that targeted immunization using  iWander  achieves a comparable performance with a degree-based immunization policy that vaccinates users with large number of contacts first, while consuming only less than 1% of this policy's message overhead. We also show that target-set selection based on iWander outperforms the random and degree-based target-set selections for information dissemination in several scenarios.
['Bo Han', 'Aravind Srinivasan']
Your friends have more friends than you do: identifying influential mobile users through random walks