Real world graphs are massive in size and often prohibitively expensive to analyze. Of the possible solutions, sampling is extracting a representative subgraph from a large graph that faithfully represents the actual graph. The prior research has developed several sampling methods but the samples p roduced by these methods fail to match important properties of the original graph and work poorly in maintaining its topology. We observed that the existing methods do not explore the neighborhood of sampled nodes fairly and hence yield suboptimal samples. In this paper, we introduce a novel approach in which we keep a list of candidate nodes that is populated with all the neighbors of nodes that have been sampled so far. With this approach, we can balance the depth and breadth of graph exploration to produce better samples. We evaluate the effectiveness of our approach using several real world datasets and show that it surpasses the existing state-of-the-art approaches in maintaining the properties of the original graph and retaining its structure. We also calculate Kolmogorov-Smirnov Distance and Jensen-Shannon Distance for quantitative evaluation of our approach.

In the recent years, the P2P file sharing systems have adopted rating systems in the hope to stop the propagation of bad files. In a rating system, users rate files after downloading and a file with positive feedback is considered a good file. However, a dishonest rater can undermine the rating system by giving positive rating to bad files and negative rating to good files. In this paper, we design two filters based on probabilistic models such that the good files with negative feedback are not completely kept out of the system. The first filter is based on the binomial distribution of the ratings of a file, and the second filter considers the confidence of the downloading peer and the difference of positive and negative ratings of a file to calculate the probability to take a risk to download the file or reject it. Our filters only need the ratings of a file and this makes them suitable for popular torrent sharing websites that rank the files using a binary rating system without any information about raters. In addition, we can implement them entirely on the client side without any modification to the content sharing sites.

This paper discusses the design and evaluation of Kistree, a reliable, fault-tolerant and self-configuring constant degree distributed hash table (DHT) for peer-to-peer systems. The Kistree topology can be thought of as log(n) vertically stacked layers or levels. At each level, we divide the whole identifier space into segments to form an n-ary tree structure. The nodes and keys belong to a particular segment at a level in Kistree network depending on the node / key identifier. A node in Kistree contacts with a constant number of nodes at the next level to forward queries. A node also creates a link with a node at the topmost level to get a global view of the system. This way Kistree keeps a constant number of neighbors in the routing table and traverses a logarithmic number of nodes to route a query to its destination. An insert operation stores a key on a number of diverse nodes of a concerned segment. The lookup operation, on the other hand, retrieves a stored key efficiently and reliably. The prototype implementation of Kistree on PeerSim verifies its scalability, reliability and efficiency. The experimental results achieved with a network of 50,000 nodes confirm its self-configurability and ability to route messages even under a high rate of churn.