2015 PantherFastTopKSimilaritySearch

• (Zhang et al., 2015) ⇒ Jing Zhang, Jie Tang, Cong Ma, Hanghang Tong, Yu Jing, and Juanzi Li. (2015). “Panther: Fast Top-k Similarity Search on Large Networks.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783267

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Panther%3A+Fast+Top-k+Similarity+Search+on+Large+Networks
• http://dl.acm.org/citation.cfm?id=2783258.2783267&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; random path; social network; vertex similarity

Abstract

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₂ 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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 PantherFastTopKSimilaritySearch	Jie Tang Hanghang Tong Jing Zhang Juanzi Li Cong Ma Yu Jing			Panther: Fast Top-k Similarity Search on Large Networks				10.1145/2783258.2783267		2015