Using Robust Graph Clustering to Detect Fake News

从暴力到宣传种族主义，错误信息和假新闻在多个层面上对社会构成威胁。现代社会和社交网络的兴起促成了错误信息的迅速传播。在一定程度上，这是因为阻止假新闻是一件微妙的事情：决定一条信息是否为假新闻往往需要人工干预，这对于大型(社交)网络来说不是一个可扩展的解决方案。因此，似乎有必要依靠算法来做出决策，或者至少在决策过程中提供帮助。这个项目的目标是开发一个算法框架，以帮助防止假新闻的传播。我们的目标是使用层次图聚类的最新进展来实现这一点。要了解这为什么很有前景，请考虑我们的两个应用程序之一：维基百科。维基百科依靠世界各地的用户编辑文章的内容，以建立一个包含所有知识分支信息的百科全书。不可避免的是，有些编辑是不正确的-有意无意的。这尤其发生在文章具有争议性的时候(例如，政客、疫苗接种等)。其结果往往是所谓的“编辑大战”爆发，用户开始一遍又一遍地更改有争议的信息。在这些编辑过程中，维基百科可能被用作错误信息和宣传的武器。维基百科管理员防止这种情况的主要工具是将编辑限制在有限的用户范围内。我们的目标是在编辑战发生之前预测哪些文章应该被限制，以避免错误信息的传播。为了实现这一点，我们建议使用分层图聚类算法。将问题框架化为分层图聚类问题是很自然的：请注意，我们将关注的应用程序Twitter和Wikipedia都是图。在维基百科的例子中，这个图的节点是文章，如果一篇文章链接到另一篇文章，那么从一篇文章到另一篇文章就有一条有向边。层级结构源于文章所属的类别。例如，有关巴拉克·奥巴马和唐纳德·特朗普的文章都是受限的。两人都属于“21世纪美国总统”这一类别，而后者又是“美国总统”的一部分。事实证明，所有关于总统的文章都是受限的，这说明了潜在等级制度的影响。该项目由两部分组成。在第一部分中，我们的目标是在更一般的环境下分析图聚类算法，目的是找到实际相关算法(如Louvain算法)的可证明的保证和局限性。在第二部分中，我们的目标是将这些结果应用于错误信息和假新闻的发现。

Misinformation and fake news are a threat to society on numerous levels ranging from violence to the promotion of racism. The modern era and the rise of social networks have contributed to a rapid spread of misinformation. Partly, this is due to the fact that stopping fake news is a delicate matter: deciding whether a piece of information is fake news often requires human intervention, which is not a scalable solution for large (social) networks. It seems therefore necessary to rely on algorithms to make decisions or to at least help in the decision process.The goal of this project is to develop an algorithmic framework to help prevent fake news from spreading. We aim to use recent advances in hierarchical graph clustering to achieve this. To see why this is promising consider one of our two applications: Wikipedia. Wikipedia relies on users world-wide to edit the content of articles in order to build an encyclopaedia that contains information on all branches of knowledge. It is inevitable that some of the edits are factually incorrect --- intentionally or unintentionally. This occurs in particular when the articles are contentious (e.g., politicians, vaccination, etc.). The result is often that so-called 'edit-wars' break out and users start changing contested information over and over. In the process of these edits, Wikipedia can be used a weapon of misinformation and propaganda. The main tool used by the Wikipedia admins to prevent this is to restrict the editing to a limited range of users.Our goal is to predict which articles should be restricted before edit-wars take place in order to avoid the spread of misinformation. To achieve this, we propose to use hierarchical graph clustering algorithms.Framing the problem as a hierarchical graph clustering problem is natural: Note that the applications we will focus on, Twitter and Wikipedia, are both graphs. In the case of Wikipedia, the nodes of this graph are the articles and there is a directed edge from one article to another if one article links to the other. The hierarchical structure stems from the categories the article belongs to. For example, the articles on Barack Obama and Donald Trump are both restricted. Both belong to the category "21st-century Presidents of the United States" which in turn is part "Presidents of the United States". It turns out all articles concerning presidents are restricted, illustrating the influence of the underlying hierarchy. The project consists of two parts. In the first part, we aim to analyse graph clustering algorithms in more general settings with the aim of finding provable guarantees and limitations of practically relevant algorithms such as the Louvain algorithm. In the second part, we aim to apply these results to finding misinformation and fake news.