ANO NIMOS: AN LP-BASED APPROACH FOR ANONYMIZING WEIGHTED SOCIAL NETWORK GRAPHS

ANO´NIMOS: AN LP-BASED APPROACH FOR ANONYMIZING WEIGHTED SOCIAL NETWORK GRAPHS

The increasing popularity of social networks has initiated a fertile research area in information extraction and data mining. Anonymization of these social graphs is important to facilitate publishing these data sets for analysis by external entities. Prior work has concentrated mostly on node identity anonymization and structural anonymization. But with the growing interest in analyzing social networks as a weighted network, edge weight anonymization is also gaining importance. We present Ano´nimos, a Linear Programming-based technique for anonymization of edge weights that preserves linear properties of graphs. Such properties form the foundation of many important graph-theoretic algorithms such as shortest paths problem, k-nearest neighbors, minimum cost spanning tree, and maximizing information spread. As a proof of concept, we apply Ano´nimos to the shortest paths problem and its extensions, prove the correctness, analyze complexity, and experimentally evaluate it using real social network data sets. Our experiments demonstrate that Ano´nimos anonymizes the weights, improves k-anonymity of the weights, and also scrambles the relative ordering of the edges sorted by weights, thereby providing robust and effective anonymization of the sensitive edge-weights. We also demonstrate the composability of different models generated using Ano´nimos, a property that allows a single anonymized graph to preserve multiple linear properties.

Existing System:

If we consider that edge weights are inverse of “trustworthiness” (smaller weights correspond to higher trust in the relation), then the k Nearest Neighbors (kNN) query at a particular vertex returns the k most trusted users associated with the queried user, and the single source shortest paths tree provides the most trusted paths within the community which might be used for communicating while minimizing chances of a leak. We focus on the problem of anonymization of edge weights in a social graph.

Proposed System:

We propose Ano´nimos, a technique for edge weight anonymization of graph structured data that preserves linear properties by expressing them as a system of inequalities formulated as an LP problem.
. We use Ano´nimos to develop models for different variants of the shortest paths problem. We also demonstrate the composability of the models by composing the models of the single source shortest paths trees to construct the model for all pairs shortest paths. Ano´nimos therefore has the ability to preserve multiple linear properties in a single anonymized graph. We further optimize the models that considerably reduce the complexity of the models.
. We prove the correctness of the proposed models, provide a thorough analysis of the complexity of the proposed models, and present the results of experiments on real social network graphs that validate this analysis and evaluate the extent of anonymization.

Software Requirements:
.Net
Front End – ASP.Net
Language – C#.Net
Back End – SQL Server
Windows XP
Hardware Requirements:
RAM : 512 Mb
Hard Disk : 80 Gb
Processor : Pentium IV

FUTURE ENHANCEMENT:
We would like to extend Ano´nimos for other applications such as graph clustering, information spread modeling, etc., which also rely on linear combinations of edge weights. It is also of interest to study the complexity and the effectiveness of various measures of privacy, their interrelation, statistical behavior, and worst case guarantees.

Comments are closed.