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

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.

• Publication year

  2013

• Venue

  Unknown venue

• Publication date

  2013-08-13

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.2991/ICAISE.2013.13
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Graph Clustering Based on Structural/Attribute Similarities

  2009cited by this paper
• Ranking-based clustering of heterogeneous information networks with star network schema

  2009cited by this paper
• RankClus: integrating clustering with ranking for heterogeneous information network analysis

  2009cited by this paper
• Latent semantic analysis

  2008cited by this paper
• Local Graph Partitioning using PageRank Vectors

  2006cited by this paper
• LinkClus: efficient clustering via heterogeneous semantic links

  2006cited by this paper
• A Random Walks Perspective on Maximizing Satisfaction and Profit

  2005cited by this paper
• Scaling personalized web search

  2003cited by this paper
• Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions

  2003cited by this paper
• An analysis of ontology-based query expansion strategies

  2003cited by this paper
• SimRank: a measure of structural-context similarity

  2002cited by this paper
• Probabilistic Latent Semantic Analysis

  1999cited by this paper
• Fast algorithms for projected clustering

  1999cited by this paper
• CURE: an efficient clustering algorithm for large databases

  1998cited by this paper
• BIRCH: an efficient data clustering method for very large databases

  1996cited by this paper
• Chapter 3 Reversible Markov Chains

  1994cited by this paper
• Efficient and Effective Clustering Methods for Spatial Data Mining

  1994cited by this paper
• Concept based query expansion

  1993cited by this paper
• SLINK: An Optimally Efficient Algorithm for the Single-Link Cluster Method

  1973cited by this paper

• No citing papers are available for this paper.