Extracting influential information sources for gossiping

Gossiping or rumor spreading is an effective way of information dissemination, and gossiping-based schemes are promising solutions for many of the next generation networks. Despite the abundant existing works on (high-probability) completion time of gossiping processes, it remains an interesting, important, and largely unaddressed problem how to select the initial information sources for gossiping, so as to maximize the expected spreading or minimize the expected completion time. In this paper, we deal with problems related to selecting influential information sources, which are initially informed nodes in a network for gossiping. The considered problems include the gossip spreading maximization problem (GSMP) and the completion time minimization problem (CTMP). Both problems are conjectured to be at least NP-hard, whereas a greedy algorithm for GSMP is proposed to guarantee an approximation factor of (1-1/e), due to the inherent submodularity property of GSMP. Additionally, based on an all-ordered-pair matrix, three heuristics are proposed for solving CTMP. Throughout the analysis and development, a key observation is that there exists an equivalent view that relates the expected gossiping time to the expected shortest path length in a random weighted directed graph induced by virtual coupon collectors run at each node in the network graph.