Knowledge hiding on graph data

Abstract

Çizgelerde anlamlı alt yapılar olan alt çizgeler ve topluluklar, ağ yapılarının daha derinlemesine anlaşılması için önemli bilgiler sağlar. Ancak çizge analiz araçları daha gelişmiş hale geldikçe, bu durum, çizge verilerinden gereğinden fazla bilgi çıkarılması riski gibi yeni bir zorluğu da beraberinde getirir. Böylelikle, bilgi gizleme tekniklerinin araştırılmasına yol açmıştır. Bu tez kapsamında, çizge verilerinin mahremiyetini koruyan teknikler olarak alt çizge gizleme ve topluluk gizleme incelenmektedir. Alt çizge gizleme, işlemsel çizge veritabanındaki hassas alt çizgeleri tanımlamayı ve verilerin yayınlanmasından sonra onların ifşa edilmesini önlemek için veritabanını dönüştürmeyi içerirken, orijinal verileri mümkün olduğunca korur. Topluluk gizleme ise çizgeyi stratejik olarak değiştirerek toplulukların gizlenmesini veya karartılmasını içerir. Kullanıcıların topluluk üyeliği gibi hassas bilgilerinin gizliliğini koruyan topluluk gizlemeye yönelik çalışmalarla birlikte, gizlemeye etkili bir şekilde karşı koyabilecek dayanıklı topluluk tespit algoritmalarına olan ihtiyaç daha da belirgin hale gelir. Bu tezde öncelikle alt çizge gizleme teknikleri incelenmiş ve çeşitli kenar silme tabanlı algoritmalar önerilmiştir. Daha sonra, topluluk gizleme teknikleri araştırılmış ve tekniklerin üç ölçekte kapsamlı bir şekilde ele alınması için bir araştırma yapılmıştır. Ayrıca, klikler kullanılarak küresel topluluk gizleme için bir algoritma önerilmiştir.

Subgraphs and communities, which are meaningful substructures in graphs, provide important information for a deeper understanding of network structures. However, as graph analysis tools become more advanced, this introduces a new challenge, such as the risk of over-mining of knowledge from graph data. Thus, it has led to the investigation of knowledge hiding techniques. Within the scope of this dissertation, as privacy-preserving techniques for graph data, subgraph hiding and community hiding are examined. Subgraph hiding involves identifying sensitive subgraphs in a transactional graph database, and transforming the database to prevent them from being disclosed after publication of data, while preserving the original data as much as possible. Community hiding, on the other hand, involves hiding or obfuscating communities by strategically modifying the graph. With the work on community hiding that protects the privacy of users' sensitive information, such as community membership, the need for robust community detection algorithms that can effectively counter hiding becomes more evident. In this thesis, first subgraph hiding techniques have been examined and various edge deletion-based algorithms have been proposed. Then, community hiding techniques have been investigated, and a research has been conducted to address the comprehensive overview of the techniques at three scales. Further, an algorithm has been offered for global community hiding using cliques.