Hybrid mobile content delivery systems improve performance of wide-area networks by combining both wide-area and local-area communications. In hybrid content delivery, service providers send data packets first to a small number of selected users (e.g., those with good channel quality) and then these mobile users help forward the packets to others (e.g., those with poor channel quality). The central theme of our work is to identify the initial target set composed of influential mobile users (i.e., individuals with high centrality in their social-contact graphs) and thus improve the efficiency of hybrid mobile content distribution.

We first present two centralized algorithms for this target-set selection problem. The greedy algorithm has a provable performance guarantee, due to the submodularity of the underlying information dissemination function. The heuristic algorithm exploits the regularity of human mobility and is more practical than the greedy algorithm. We then propose a lightweight and distributed protocol to identify these influential users through random-walk sampling. This distributed protocol leverages random-walk probe messages to sample mobile users and estimates their centrality based on how many times they are visited by the probe messages. This protocol has low communication and computation overhead and lends itself well to mobile content delivery. We verify the effectiveness of these approaches through extensive trace-driven simulation studies using real-world mobility traces.