In recent years, online social networks have been the target of adversaries
who seek to introduce discord into societies, to undermine democracies and to
destabilize communities. Often the goal is not to favor a certain side of a
conflict but to increase disagreement and polarization. To get a mathematical
understanding of such attacks, researchers use opinion-formation models from
sociology, such as the Friedkin--Johnsen model, and formally study how much
discord the adversary can produce when altering the opinions for only a small
set of users. In this line of work, it is commonly assumed that the adversary
has full knowledge about the network topology and the opinions of all users.
However, the latter assumption is often unrealistic in practice, where user
opinions are not available or simply difficult to estimate accurately.
To address this concern, we raise the following question: Can an attacker sow
discord in a social network, even when only the network topology is known? We
answer this question affirmatively. We present approximation algorithms for
detecting a small set of users who are highly influential for the disagreement
and polarization in the network. We show that when the adversary radicalizes
these users and if the initial disagreement/polarization in the network is not
very high, then our method gives a constant-factor approximation on the setting
when the user opinions are known. To find the set of influential users, we
provide a novel approximation algorithm for a variant of MaxCut in graphs with
positive and negative edge weights. We experimentally evaluate our methods,
which have access only to the network topology, and we find that they have
similar performance as methods that have access to the network topology and all
user opinions. We further present an NP-hardness proof, which was an open
question by Chen and Racz [IEEE Trans. Netw. Sci. Eng., 2021].

通过使用一种新的算法来检测高影响力的用户，即使只知道社交网络的拓扑结构，攻击者仍能在社交网络中激起不和谐，我们证明了这种攻击是可能的。