Finding top-κ answers in node proximity search using distribution state transition graph

Jaehui Park, Sang Goo Lee

Research output: Contribution to journalArticlepeer-review


Considerable attention has been given to processing graph data in recent years. An efficient method for computing the node proximity is one of the most challenging problems for many applications such as recommendation systems and social networks. Regarding large-scale, mutable datasets and user queries, top-κ query processing has gained significant interest. This paper presents a novel method to find top-κ answers in a node proximity search based on the well-κnown measure, Personalized PageRank (PPR). First, we introduce a distribution state transition graph (DSTG) to depict iterative steps for solving the PPR equation. Second, we propose a weight distribution model of a DSTG to capture the states of intermediate PPR scores and their distribution. Using a DSTG, we can selectively follow and compare multiple random paths with different lengths to find the most promising nodes. Moreover, we prove that the results of our method are equivalent to the PPR results. Comparative performance studies using two real datasets clearly show that our method is practical and accurate.

Original languageEnglish
Pages (from-to)714-723
Number of pages10
JournalETRI Journal
Issue number4
StatePublished - Aug 2016


  • Distribution State Transition Graph
  • Graph Search
  • Path Selection Algorithm
  • Personalized PageRank
  • Top-κ Node Proximity Search


Dive into the research topics of 'Finding top-κ answers in node proximity search using distribution state transition graph'. Together they form a unique fingerprint.

Cite this