Locating Multi-Sources in Social Networks With a Low Infection Rate

ABSTRACT

With the development of modern technology, numerous economic losses are incurred by various spreading phenomena. Thus, it is of great significance to identify the initial sources triggering such phenomena. The investigation of source localization in social networks has gained substantial attention and become a popular topic of study. For practical spreading phenomena on social networks, the infection rates are relatively low. Hence, a high uncertainty of spreading trace might be incurred, which further incurs the reduction of localization accuracy obtained through existed source localization methods, especially the observer-based ones. Aiming to solve the source localization problem with a low infection rate, we propose a novel localization algorithm, i.e., path-based source identification (PBSI). First, a small number of nodes are selected and designated as observers. After the propagation process triggered by sources, we can obtain a snapshot. Later, a label is assigned to represent whether a node is infected or not, and observers are supposed to record the paths through which nodes are successfully infected. Based on source centrality theory, observers make the labels flow in the direction recorded during the label iteration process, which ensures the labels of nodes in the direction of the source increase gradually. Extensive experiments indicate that the proposed PBSI can handle source localization problems for both single and multi-source scenarios with better performance than that of state-of-the-art algorithms under different propagation models.