ERWD: A Measure for Nearest-Neighbor Search in Undirected Graph

DOI

10.2991/icaise.2013.13How to use a DOI?

Keywords

Similarity measure, random walk distance, Relationship Strength

Abstract

Finding nearest neighbors in graph plays an increasingly important role in various applications, such as graph clustering, query expansion, recommendation system, etc. To tackle this problem, we need compute the most “similar” k vertices for the given vertex. One popular class of similarity measures is based on random walk approach on graphs. However, these measures consider each co-occurrence frequency of two vertices is equivalent, means that each occurrence of two vertices is not differentiated, and the influence of the vertices have not been considered enough. In this paper, we proposed an effective distance measure based on random walk distance, called ERWD, for nearest-neighbor search in undirected graph. The Relationship Strength (RS) of two vertices, which affects ERWD, is proposed firstly, and a model for measuring RS is established according to their structural characteristics and influences of the vertices. Extensive experimental results demonstrate the effectiveness of ERWD through comparison with the common random walk distance.

Copyright

© 2013, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Junyin Wei
AU  - Binghui Qi
AU  - Mingxi Zhang
PY  - 2013/08
DA  - 2013/08
TI  - ERWD: A Measure for Nearest-Neighbor Search in Undirected Graph
BT  - Proceedings of the 2013 The International Conference on Artificial Intelligence and Software Engineering (ICAISE 2013)
PB  - Atlantis Press
SP  - 54
EP  - 58
SN  - 1951-6851
UR  - https://doi.org/10.2991/icaise.2013.13
DO  - 10.2991/icaise.2013.13
ID  - Wei2013/08
ER  -