Estimating similarity between vertices is a fundamental issue in network analysis across various domains, such as social networks and biological networks. Methods based on common neighbors and structural contexts have received much attention. However, both categories of methods are difficult to scale up to handle large networks (with billions of nodes). In this paper, we propose a sampling method that provably and accurately estimates the similarity between vertices. The algorithm is based on a novel idea of random path. Specifically, given a network, we perform R random walks, each starting from a randomly picked vertex and walking T steps. Theoretically, the algorithm guarantees that the sampling size R = O(2ε −2 log 2 T ) depends on the error-bound ε, the confidence level (1 − δ), and the path length T of each random walk. We perform extensive empirical study on a Tencent microblogging network of 1,000,000,000 edges. We show that our algorithm can return top-k similar vertices for any vertex in a network 300× faster than the state-of-the-art methods. We also use two applications-identity resolution and structural hole spanner finding-to evaluate the accuracy of the estimated similarities. Our results demonstrate that the proposed algorithm achieves clearly better performance than several alternative methods. Figure 1: Example of top-k similarity search across networks and performance comparison. (a) Top-k similarity search across two disconnected networks; (b) Efficiency comparison of Panther and several comparison methods on a Tencent subnetwork of 443,070 vertices and 5,000,000 edges; and (c) Accuracy performance when applying Panther++ to identity resolution [11], an important application in social network. Please refer to § 4 for definitions of all the comparison methods in (b) and (c). tion of structural patterns, we extend the proposed algorithm by augmenting each vertex with a vector of structure-based features. The resultant algorithm is referred to as Panther++. Panther++ is not only able to estimate similarity between vertices in a connected network, but also capable of estimating similarity between vertices from disconnected networks. Figure 1(a) shows an example of topk similarity search across two disconnected networks, where v4, v6 and v5 are top-3 similar vertices to v0. We evaluate the efficiency of the methods on a microblogging network from Tencent. 1 Figure 1(b) shows the efficiency comparison of Panther, Panther++, and several other methods. Clearly, our methods are much faster than the comparison methods. Panther++ achieves a 300× speed-up over the fastest comparison method on a Tencent subnetwork of 443,070 vertices and 5,000,000 edges. Our methods are also scalable. Panther is able to return top-k similar vertices for all vertices in a network with 51,640,620 vertices and 1,000,000,000 edges. On average, it only need 0.0001 second to perform top-k search for each vertex. We also evaluate the estimation capability of Panther++. Specifically, we use identity resolution and top-k structural hole spanner finding, two important applications in social networks, to evaluate the accuracy of the estimated similarities. Figure 1(c) shows the accuracy performance of Panther++ and several alternative methods for identity resolution. Panther++ achieves clearly better performance than several alternative methods. All codes and datasets used in this paper are publicly available. 2
Zhang et al. REF design a sampling method to accelerate the proximity computation based on the concept of random path.
Panther: Fast Top-k Similarity Search on Large Networks
KDD '15
Computer Science