With increased connectivity, ease of use and free access, social networks have become the go-to platform for information interchange. Recently, however, a surge in misinformation dissemination has been witnessed on these platforms. Works exist which assume a particular standardized epidemiological model (SI, SIR, SIRS, etc.) to determine the sources of misinformation dissemination. However, this assumption becomes impractical in real world settings and, little or no works are present which determine the sources of misinformation without relying heavily on such underlying epidemiological models. In this paper, we attempt to fill in this gap by presenting a resource optimized strategy of deploying a minimum number of "detection sensors" on a social network, in order to uniquely identify a user, if they were to disseminate misinformation. We show that by monitoring the social media content of a small subset of users, the platform can still uniquely identify a user, if they were to engage in misinformation dissemination. We utilize the mathematical notion of Identifying Codes to solve our problem. As the computation of the optimal solution is NP-Complete, we provide a polynomial time approximation algorithm and two minimal algorithms. Finally, we highlight the significant resource reduction and scalability achieved by our approaches, by utilizing various real world anonymous Facebook datasets.

PDF