Graph based local risk estimation in large scale online social networks

Online Social Networks (OSNs) have become extremely popular in recent years, leading to the presence of huge volumes of users' personal information on the Internet. This increases the need for efficient and effective measures helping users to judge their direct contacts so as to avoid friendship with malicious users that could misuse their personal information. At this purpose, in this paper we propose a risk measure, called local risk factor, having as a key idea the fact the malicious users in OSNs (aka attackers) show some common features on the topology of their social graphs, which is different from those of legitimate users. This consideration brought us to design a set of features defined based on attacker activity patterns. To prove the effectiveness of the proposed risk measure, we run several experiments on a real OSN dataset (i.e., Orkut social network) with more than 3 million vertices and 117 million edges, by injecting synthetic fake users according to different settings and showing how the proposed measures can indeed help in their detection.