Penetrating a Social Network: The Follow-back Problem Fanyu Que, Krishnan Rajagopalan, Tauhid Zaman (Submitted on 8 Apr 2018) arXiv:1804.02608 [cs.SI] (or arXiv:1804.02608v1 [cs.SI] for this version)

“Modern threats have emerged from the prevalence of social networks. Hostile actors, such as extremist groups or foreign governments, utilize these networks to run propaganda campaigns with different aims. For extremists, these campaigns are designed for recruiting new members or inciting violence. For foreign governments, the aim may be to create instability in rival nations. Proper social network counter-measures are needed to combat these threats. Here we present one important counter-measure: penetrating social networks. This means making target users connect with or follow agents deployed in the social network. Once such connections are established with the targets, the agents can influence them by sharing content which counters the influence campaign. In this work we study how to penetrate a social network, which we call the follow-back problem. The goal here is to find a policy that maximizes the number of targets that follow the agent. We conduct an empirical study to understand what behavioral and network features affect the probability of a target following an agent. We find that the degree of the target and the size of the mutual neighborhood of the agent and target in the network affect this probability. Based on our empirical findings, we then propose a model for targets following an agent. Using this model, we solve the follow-back problem exactly on directed acyclic graphs and derive a closed form expression for the expected number of follows an agent receives under the optimal policy. We then formulate the follow-back problem on an arbitrary graph as an integer program. To evaluate our integer program based policies, we conduct simulations on real social network topologies in Twitter. We find that our polices result in more effective network penetration, with significant increases in the expected number of targets that follow the agent.”