Weighted and Directed Graph Approaches

Source Title: Security, Privacy, and Anonymization in Social Networks: Emerging Research and Opportunities

DOI: 10.4018/978-1-5225-5158-4.ch006

Abstract

It is interesting to look at the types of social networks that are directed or weighted, or social networks with the combination of both. In many cases, the relationship between vertices may be quantifiable (weighted) or asymmetrical (directed). In this chapter, the authors first introduce the concept of weighted social networks and present an anonymization algorithm for these networks called the anonymity generalization algorithm. After that, they discuss k-anonymous path privacy and introduce the MSP algorithm. Next, the authors introduce the (k1, k2)-shortest path privacy and a (k1, k2)-shortest path privacy algorithm. Then they introduce directed weighted social networks and present the k-multiple paths anonymization on PV+NV (KMPPN). Also, the authors present a technique to convert directed networks into undirected networks. Finally, the authors present the linear property preserving anonymization approach for social networks.

Chapter Preview

Top

Under this section, we will look at the various anonymization approaches proposed for undirected weighted social networks alone. The weight on edges can represent degree of friendship, trustworthiness, behaviour, etc. We will consider directed weighted social networks as a different section later. As stated in the introductory chapters, a weighted social network graph is one where the edges between vertices have quantifiable weights associated with them. It is given by where is the set of nodes, is the set of edges and is the matrix of weights associated with the edges such that is the weight in edge that connects nodes and .