Using Robust Graph Clustering to Detect Fake News

错误信息和假新闻在从暴力到促进种族主义等多个层面上对社会构成威胁。当今时代和社交网络的兴起助长了错误信息的迅速传播。部分原因是，阻止假新闻是一件微妙的事情：决定一条信息是否是假新闻通常需要人为干预，这对于大型（社交）网络来说不是一个可扩展的解决方案。因此，似乎有必要依靠算法来做出决策，或者至少在决策过程中提供帮助。该项目的目标是开发一个算法框架，以帮助防止假新闻传播。我们的目标是使用最新进展的层次图聚类来实现这一目标。要了解为什么这是有希望的，请考虑我们的两个应用程序之一：维基百科。维基百科依靠世界各地的用户来编辑条目的内容，以建立一个包含所有知识分支信息的百科全书。不可避免的是，有些编辑是不正确的-有意或无意的。特别是当条款有争议时（例如，接种疫苗，等等）。结果往往是所谓的“编辑战争”爆发，用户开始一遍又一遍地更改有争议的信息。在这些编辑的过程中，维基百科可以被用作错误信息和宣传的武器。维基百科管理员用来防止这种情况的主要工具是限制编辑范围。我们的目标是在编辑大战发生之前预测哪些文章应该受到限制，以避免错误信息的传播。为了实现这一点，我们建议使用层次图聚类算法。将问题框架为层次图聚类问题是很自然的：请注意，我们将关注的应用程序，Twitter和维基百科，都是图。在维基百科的例子中，这个图的节点是文章，如果一篇文章链接到另一篇文章，则存在从一篇文章到另一篇文章的有向边。层次结构源于文章所属的类别。例如，关于巴拉克奥巴马和唐纳德特朗普的文章都受到限制。两人都属于“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.