Adaptive crawling with cautious users

In Online Social Networks (OSNs), privacy issue is a growing concern as more and more users are sharing their candid personal information and friendships online. One simple yet effective attack aims at private user data is to use socialbots to befriend the users and crawl data from users who accept the attackers' friend requests. With the attackers involving, individual users' preference and habit analysis is available, hence it is easier for the attackers to trick the users and befriend them. To better protect private information, some cautious, high-profile users may refer to their friends' decisions when receiving a friend request. The aim for this paper is to analyze the vulnerability of OSN users under this attack, in a more realistic setting that the high profile users having a different friend request acceptance model. Specifically, despite the existing probabilistic acceptance models, we introduce a deterministic linear threshold acceptance model for the cautious users such that they will only accept friend requests from users sharing at least a certain number of mutual friends with them. The model makes the cautious users harder to befriend with and complicates the attack. Although the new problem with multiple acceptance models is non-submodular and has no performance guarantee in general, we introduce the concept of adaptive submodular ratio and establish an approximation ratio under certain conditions. In addition, our results are also verified by extensive experiments in real-world OSN data sets.