More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks

Summary: Introduces SimRank*, extending SimRank beyond equal-length incoming paths to eliminate zero-similarity cases while retaining a simple closed form and comparable O(Knm) computation. Edge-concentration clustering further reduces runtime using a practical sparse-graph heuristic. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h009c3ca295395268
Venue: VLDB
Year: 2014
Pagerank: 0.00010043754
Overall Rank: 1,626 | 89.07%
DOI: 10.14778/2732232.2732234

Incoming Non-self Citations Over Time

Authors

1. Weiren Yu (National ICT Australia; University of New South Wales)
2. Xuemin Lin (East China Normal University; University of New South Wales)
3. Wenjie Zhang (University of New South Wales)
4. Lijun Chang (University of New South Wales)
5. Jian Pei (Simon Fraser University)

BibTeX Citation

@article{yu_vldb14,
        title = {{More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks}},
        author = {Yu, Weiren and Lin, Xuemin and Zhang, Wenjie and Chang, Lijun and Pei, Jian},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {1},
        pages = {13--24},
        doi = {10.14778/2732232.2732234},
        url = {https://doi.org/10.14778/2732232.2732234},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,222	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011463714
1,400	Scalable Similarity Search for SimRank	2014	SIGMOD	0.00010776946
2,345	Efficient Partial-Pairs SimRank Search on Large Networks	2015	VLDB	8.6034897e-05
4,031	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB	6.84057e-05
4,150	Efficient Top-K SimRank-based Similarity Join	2015	VLDB	6.7794413e-05
4,303	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB	6.6772109e-05
4,941	SLING: A Near-Optimal Index Structure for SimRank	2016	SIGMOD	6.3454989e-05
5,098	Remember Where You Came From: On The Second-Order Random Walk Based Proximity Measures	2017	VLDB	6.2741304e-05
5,945	Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs	2020	VLDB	5.9384932e-05
6,581	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD	5.7445028e-05
7,986	ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs	2018	VLDB	5.4123815e-05
8,379	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD	5.3432239e-05
9,492	DISK: A Distributed Framework for Single-Source SimRank with Accuracy Guarantee	2021	VLDB	5.1708619e-05
9,628	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB	5.1476979e-05
10,493	PJsim: Towards Precise and Scalable Graph Similarity	2026	SIGMOD	4.9793485e-05
12,098	SimTab: Accuracy-Guaranteed SimRank Queries through Tighter Confidence Bounds and Multi-Armed Bandits	2020	VLDB	4.9793485e-05
12,316	NED: An Inter-Graph Node Metric Based On Edit Distance	2017	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
375	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.00019628745
666	Accuracy Estimate and Optimization Techniques for SimRank Computation	2008	VLDB	0.00014985082
788	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00013980547
4,785	LinkClus: Efficient Clustering via Heterogeneous Semantic Links	2006	VLDB	6.4150472e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,031	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB
2	4,785	LinkClus: Efficient Clustering via Heterogeneous Semantic Links	2006	VLDB
3	1,864	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB
4	1,400	Scalable Similarity Search for SimRank	2014	SIGMOD
5	9,628	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB
6	666	Accuracy Estimate and Optimization Techniques for SimRank Computation	2008	VLDB
7	6,752	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB
8	8,471	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD
9	4,150	Efficient Top-K SimRank-based Similarity Join	2015	VLDB
10	2,345	Efficient Partial-Pairs SimRank Search on Large Networks	2015	VLDB