Influence of community structure on misinformation containment in online social networks

摘要

With the emergence of Online Social Networks (OSNs) as an effective medium of information dissemination, its abuse in spreading misinformation has become a great concern to its users. Hence, the misinformation containment problem in various forms has emerged as an important topic of research. In general, given a snapshot of an online social network with a set of misinformed nodes and a budget limiting the maximum number of seed nodes, the goal is to determine a set of seed nodes with the correct information, to contain the misinformation at the earliest. In this paper, we leverage the community structure of the online social network to select the seed nodes statically, independent of the distribution of misinformed nodes for faster misinformation containment with simple one-time computation. We extend the work to include OSNs with overlapped community as well. To the best of our knowledge, so far, ours is the first work where the topology of the OSN has been exploited to combat the spread of misinformation faster. Experiments on real OSNs reveal that the proposed techniques outperform state-of-the-art algorithms significantly in terms of maximum and average infected time, and the point of decline, manifesting the key role of community structure on misinformation containment in a social network. Moreover, the parallel implementations of the proposed algorithms achieve around 10× speed-up over the sequential ones enhancing the scalability of the proposed approach.