Efficient social graph augmentation schemes for a peer to peer social networking service

For the last several years, it has been a popular research issue to develop an efficient peer to peer social networking service to protect privacy. One of the main problem in a p2p based SNS is that the data may not be available due to the failure of peers. To alleviate this problem, [1] uses many common neighbors between two neighboring nodes so that the data availability can increase. One critical issue is that the data availability depends on the size of common neighbors. In this paper, we propose three graph augmentation schemes to make the number of common neighbors of every link satisfy the given target size, thus the target availability.