Your Friends Have More Friends Than You Do: Identifying Influential Mobile Users Through Random Walks
In this paper, the authors 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. They propose a lightweight and distributed protocol, iWander, to identify influential users through fixed-length random walks. To the best of their knowledge, they 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.