Influenced node discovery in a temporal contact network based on common nodes

Verification is the only way to make sure if a node is influenced or not because of the uncertainty of information diffusion in the temporal contact network. In the previous methods, only $ N $ influenced nodes could be found for a given number of verifications $ N $. The target of discovering influenced nodes is to find more influenced nodes with the limited number of verifications. To tackle this difficult task, the common nodes on the temporal diffusion paths is proposed in this paper. We prove that if a node $ v $ is confirmed as the influenced node and there exist common nodes on the temporal diffusion paths from the initial node to the node $ v $, these common nodes can be regarded as the influenced nodes without verification. It means that it is possible to find more than $ N $ influenced nodes given $ N $ verifications. The common nodes idea is applied to search influenced nodes in the temporal contact network, and three algorithms are designed based on the idea in this paper. The experiments show that our algorithms can find more influenced nodes in the existence of common nodes.