Hiding in Social Networks

Internet oraz media społecznościowe spowodowały ogromny wzrost zainteresowania metodami analizy sieci społecznych. Coraz bardziej zaawansowane narzędzia służą do analizy naszych powiązań z innymi ludźmi.Rodzi to poważne obawy związane z prywatnością. Mając to na uwadze, rozważamy następujące pytanie: Czy członek lub grupa członków sieci społecznej może aktywnie zarządzać swoimi połączeniami tak, aby uniknąć wykrycia przez narzędzia analizy sieci społecznych? Odpowiedź na to pytanie pozwoliłaby użytkownikom Internetu lepiej chronić swoją prywatność, grupom aktywistów lepiej ukrywać swoją działalność, a agencjom bezpieczeństwa lepiej rozumieć w jaki sposób organizacje terrorystyczne i kryminalne mogą unikać wykrycia.W tej pracy rozważamy ukrywanie się przed trzema różnymi narzędziami analizy sieci społecznych. Po pierwsze, badamy jak pojedynczy węzeł lub ich grupa może uniknąć wykrycia przez miary centralności (ang. centrality measures), wciąż pozostając zdolnym do brania udziału w działalności sieci. Po drugie, analizujemy jak grupa węzłów może uniknąć zidentyfikowania przez algorytmy wykrywania społeczności (ang. community detection algorithms). Po trzecie wreszcie, badamy jak można ukryć istnienie określonej krawędzi w sieci przed algorytmami przewidywania połączeń (ang. link prediction algorithms).Analizujemy złożoność obliczeniową rozważanych zagadnień oraz udowadniamy, że większość z nich to problemy NP-trudne. Tym niemniej prezentujemy również wielomianowe rozwiązania heurystyczne, które okazują się efektywne w praktyce. Nasze algorytmy testujemy na szeregu różnych sieci, tak prawdziwych, jak i wygenerowanych losowo.

The Internet and social media have fuelled enormous interest in social network analysis. New tools continue to be developed and used to analyse our personal connections. This raises privacy concerns that are likely to exacerbate in the future. With this in mind, we ask the question: Can individuals or groups actively manage their connections to evade social network analysis tools? By addressing this question, the general public may better protect their privacy, oppressed activist groups may better conceal their existence, and security agencies may better understand how terrorists escape detection.In this dissertation we consider hiding from three different types of social network analysis tools. First, we study how both an individual and a group of nodes can evade analysis utilizing centrality measures, without compromising ability to participate in network's activities. In the second study, we investigate how a community can avoid being identified by a community detection algorithm as a closely cooperating group of nodes. In the third study, we analyse how a presence of a particular edge in a network can be hidden from link prediction algorithms.For considered problems we analyse their computational complexity and prove that they are usually NP-hard.However, we also provide polynomial-time heuristic solutions that turn out to be effective in practice. We test our algorithms on a number of real-life and artificially generated network datasets.