Fast top-k similarity search in large dynamic attributed networks

作者：

Highlights：

• A similarity search algorithm for attributed networks that combines the structure similarity and the attribute similarity into one single metric.

• A single-source path sampling procedure for sampling single source paths, which is efficient and have a theoretic bound on the sample size.

• Two dynamic updating schemes for maintaining similarity scores in response to batches of updates of nodes, edges and attributes.

• Experimental results show that our proposed method achieves better convergence performance, runs faster than Panther.

摘要

•A similarity search algorithm for attributed networks that combines the structure similarity and the attribute similarity into one single metric.•A single-source path sampling procedure for sampling single source paths, which is efficient and have a theoretic bound on the sample size.•Two dynamic updating schemes for maintaining similarity scores in response to batches of updates of nodes, edges and attributes.•Experimental results show that our proposed method achieves better convergence performance, runs faster than Panther.

论文关键词：Similarity search,Top-k search,Attributed network,Path sampling,Random walk

论文评审过程：Received 26 November 2018, Revised 4 December 2018, Accepted 2 July 2019, Available online 11 July 2019, Version of Record 11 July 2019.

论文官网地址：https://doi.org/10.1016/j.ipm.2019.102074