■ Efficient and timely misinformation blocking under varying cost constraints

Abstract.

Online Social Networks (OSNs) constitute one of the most important communication channels and are widely utilized as news sources. Information spreads widely and rapidly in OSNs through the word-of-mouth effect. However, it is not uncommon for misinformation to propagate in the network. Misinformation dissemination may lead to undesirable effects, especially in cases where the non-credible information concerns emergency events. Therefore, it is essential to timely limit the propagation of misinformation. Towards this goal, we suggest a novel propagation model, namely the Dynamic Linear Threshold (DLT) model, that effectively captures the way contradictory information, i.e., misinformation and credible information, propagates in the network. The DLT model considers the probability of a user alternating between competing beliefs, assisting in either the propagation of misinformation or credible news. Based on the DLT model, we formulate an optimization problem that under cost constraints aims in identifying the most appropriate subset of users to limit the spread of misinformation by initiating the propagation of credible information. We prove that our suggested approach achieves an approximation ratio of 1-1/e and demonstrate by experimental evaluation that it outperforms its competitors.

BibTex Entry.

@article{LITOU201719,
title = "Efficient and timely misinformation blocking under varying cost constraints",
journal = "Online Social Networks and Media",
volume = "2",
pages = "19 - 31",
year = "2017",
issn = "2468-6964",
doi = "https://doi.org/10.1016/j.osnem.2017.07.001",
url = "http://www.sciencedirect.com/science/article/pii/S2468696417300113",
author = "Iouliana Litou and Vana Kalogeraki and Ioannis Katakis and Dimitrios Gunopulos",
keywords = "Misinformation blocking, Social networks, Emergency events",
abstract = "Online Social Networks (OSNs) constitute one of the most important communication channels and are widely utilized as news sources. Information spreads widely and rapidly in OSNs through the word-of-mouth effect. However, it is not uncommon for misinformation to propagate in the network. Misinformation dissemination may lead to undesirable effects, especially in cases where the non-credible information concerns emergency events. Therefore, it is essential to timely limit the propagation of misinformation. Towards this goal, we suggest a novel propagation model, namely the Dynamic Linear Threshold (DLT) model, that effectively captures the way contradictory information, i.e., misinformation and credible information, propagates in the network. The DLT model considers the probability of a user alternating between competing beliefs, assisting in either the propagation of misinformation or credible news. Based on the DLT model, we formulate an optimization problem that under cost constraints aims in identifying the most appropriate subset of users to limit the spread of misinformation by initiating the propagation of credible information. We prove that our suggested approach achieves an approximation ratio of 1−1/e and demonstrate by experimental evaluation that it outperforms its competitors."
}