论文标题
关于社交网络中多数幻想的复杂性
On the Complexity of Majority Illusion in Social Networks
论文作者
论文摘要
当大多数网络节点属于某种类型时，大多数幻觉发生在社交网络中，但是每个节点的邻居大多属于其他类型，因此产生错误的看法，即幻觉，多数类型与实际类型不同。从系统工程的角度来看，我们想设计算法以检测并至关重要的是纠正这种不良现象。在本文中，我们启动了社交网络中多数幻觉的计算研究，为其发生和回避提供了复杂性结果。也就是说，我们表明，确定是否可以标记一个网络，以使多数幻觉存在，以及通过添加网络的添加或删除网络删除幻觉的问题，是NP完整的问题。
Majority illusion occurs in a social network when the majority of the network nodes belong to a certain type but each node's neighbours mostly belong to a different type, therefore creating the wrong perception, i.e., the illusion, that the majority type is different from the actual one. From a system engineering point of view, we want to devise algorithms to detect and, crucially, correct this undesirable phenomenon. In this paper we initiate the computational study of majority illusion in social networks, providing complexity results for its occurrence and avoidance. Namely, we show that identifying whether a network can be labelled such that majority illusion is present, as well as the problem of removing an illusion by adding or deleting edges of the network, are NP-complete problems.
