Abstract
The notion of node similarity is useful in many real-world applications. Many existing similarity measurements such as SimRank and its variants have been proposed. Among these measurements, most capture the structural information of a graph only, and thus they are not suitable for graphs with additional label information. We propose a new similarity measurement called LSimRank which measures the similarities among nodes by using both the structural information and the label information of a graph. Extensive experiments on datasets verify that LSimRank is superior over SimRank and other variants on labeled graphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
NDCG and precision are two commonly used metrics in top-k query problems. However, these two metrics cannot be used here, since they need the ground-truth rank of nodes which does not exist in our case.
References
Konect datasets: The koblenz network collection. http://konect.uni-koblenz.de
Technical report: LSimRank: Node similarity in a labeled graph. https://www.dropbox.com/sh/19il4hol726ltic/AABsMjX-28wJN4IlYArJS6yYa?dl=0
Antonellis, I., Molina, H.G., Chang, C.C.: Simrank++: query rewriting through link analysis of the click graph. Proc. VLDB Endowment 1(1), 408–421 (2008)
Arora, A., Sachan, M., Bhattacharya, A.: Mining statistically significant connected subgraphs in vertex labeled graphs. In: SIGMOD, pp. 1003–1014 (2014)
Chen, H.-H., Giles, C.L.: Ascos++: an asymmetric similarity measure for weighted networks to address the problem of simrank. ACM Trans. Knowl. Discov. Data (TKDD) 10(2), 15 (2015)
Conte, A., Ferraro, G., Grossi, R., Marino, A., Sadakane, K., Uno, T.: Node similarity with q-grams for real-world labeled networks. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1282–1291. ACM (2018)
Fogaras, D., Rácz, B.: Scaling link-based similarity search. In: Proceedings of the 14th International Conference on World Wide Web, pp. 641–650. ACM (2005)
Jeh, G., Widom, J.: Simrank: a measure of structural-context similarity. In: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 538–543. ACM (2002)
Jiang, M., Fu, A.W.-C., Wong, R.C.-W.: Reads: a random walk approach for efficient and accurate dynamic simrank. Proc. VLDB Endowment 10(9), 937–948 (2017)
Jin, R., Lee, V.E., Hong, H.: Axiomatic ranking of network role similarity. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 922–930. ACM (2011)
Leskovec, J., Krevl, A.: Snap datasets: standford large network dataset collection (2016). http://snap.standford.edu/data
Liben-Nowell, D., Kleinberg, J.: The link-prediction problem for social networks. J. Am. Soc. Inf. Sci. Technol. 58(7), 1019–1031 (2007)
Lin, D., et al.: An information-theoretic definition of similarity. In: Icml, vol. 98, pp. 296–304. Citeseer (1998)
Liu, Y., Zheng, B., He, X., Wei, Z., Xiao, X., Zheng, K., Lu, J.: Probesim: scalable single-source and top-k simrank computations on dynamic graphs. Proc. VLDB Endowment 11(1), 14–26 (2017)
Rothe, S., Schütze, H.: Cosimrank: a flexible & efficient graph-theoretic similarity measure. In: Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), vol. 1, pp. 1392–1402 (2014)
Shao, Y., Cui, B., Chen, L., Liu, M., Xie, X.: An efficient similarity search framework for simrank over large dynamic graphs. Proc. VLDB Endowment 8(8), 838–849 (2015)
Shi, C., Kong, X., Huang, Y., Philip, S.Y., Wu, B.: Hetesim: a general framework for relevance measure in heterogeneous networks. IEEE Trans. Knowl. Data Eng. 26(10), 2479–2492 (2014)
Song, J., Luo, X., Gao, J., Zhou, C., Wei, H., Uniwalk, J.X.Y.: Unidirectional random walk based scalable simrank computation over large graph. IEEE Trans. Knowl. Data Eng. 30(5), 992–1006 (2018)
Spirin, N., Han, J.: Survey on web spam detection: principles and algorithms. ACM SIGKDD Explor. Newsletter 13(2), 50–64 (2012)
Sun, Y., Han, J., Yan, X., Yu, P.S., Wu, T.: Pathsim: meta path-based top-k similarity search in heterogeneous information networks. Proc. VLDB Endowment 4(11), 992–1003 (2011)
Tian, B., Xiao, X.: Sling: a near-optimal index structure for simrank. In: Proceedings of the 2016 International Conference on Management of Data, pp. 1859–1874. ACM (2016)
Xiong, Y., Zhu, Y., Philip, S.Y.: Top-k similarity join in heterogeneous information networks. IEEE Trans. Knowl. Data Eng. 27(6), 1710–1723 (2014)
Youngmann, B., Milo, T., Somech, A.: Boosting simrank with semantics. In: EDBT, pp. 37–48 (2019)
Yu, W., Lin, X., Zhang, W., Chang, L., Pei, J.: More is simpler: effectively and efficiently assessing node-pair similarities based on hyperlinks. Proc. VLDB Endowment 7(1), 13–24 (2013)
Zhao, P., Han, J., Sun, Y.: P-rank: a comprehensive structural similarity measure over information networks. In: Proceedings of the 18th ACM Conference on Information and Knowledge Management, pp. 553–562. ACM (2009)
Zhou, Y., Cheng, H., Yu, J.X.: Graph clustering based on structural/attribute similarities. Proc. VLDB Endowment 2(1), 718–729 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Wu, Y., Fu, A.WC., Long, C., Chen, Z. (2020). LSimRank: Node Similarity in a Labeled Graph. In: Wang, X., Zhang, R., Lee, YK., Sun, L., Moon, YS. (eds) Web and Big Data. APWeb-WAIM 2020. Lecture Notes in Computer Science(), vol 12317. Springer, Cham. https://doi.org/10.1007/978-3-030-60259-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-030-60259-8_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-60258-1
Online ISBN: 978-3-030-60259-8
eBook Packages: Computer ScienceComputer Science (R0)