Abstract: With the development of the Internet,rumor information may quickly spread on social networks.Finding the source of rumor can effectively help stop the spread of negative influences,so the source localization problem has great research value.At present,the most effective source localization method is based on observation nodes.But the existing selection of observation nodes has not considered the uniformity of node distribution in the network,and the number of observation nodes is pre-set without reasonably considering the topological characteristics of the graph.This paper studies the strategy of observer nodes placement from two perspectives:node budget threshold and node coverage threshold.Taking into account the activation status of observer nodes and the discriminative distance to the source set,a novel K-differentiation algorithm is proposed,which initially selects the initial observer nodes based on the concept of the doubly-resolving set.Subsequently,an anchor node is chosen to greedily select observer nodes based on a combination of coverage and budget differences to reach the specified thresholds for coverage and budget.The algorithm then addresses two problems related to budget and coverage proposed in this paper when choosing observer nodes for experimentation within the same source localization algorithm.Experiments are conducted in real world social datasets.The proposed algorithm for selecting observer nodes is compared with various alternatives within the same source localization algorithm.The results indicate that the accuracy of source localization and average error distance by our algorithm outperforms other algorithms and achieve excellent results in the large dataset with 5%~10% observer nodes.

Key words: Observer nodes, Social networks, Independent cascade model, Doubly resolving set, Source localization