The Spanning Tree based Approach for Solving the Shortest Path Problem in Social Graphs

4

 

Atlas+

 ALGORITHM 

DESCRIPTION 

The  following  section  describes  the  changes  in  the 

Atlas

  algorithm  that  improve  its  accuracy.  The 

improvement is based on the large value of the 

local 

clustering coefficient

.  After  that,  properties  of  the 

new algorithm, 

Atlas

+, are analyzed, and according 

to them, two versions of 

Atlas

+ are suggested. 

The  tree  construction  phase  of 

Atlas

+  is  taken 

from  the 

Atlas

  algorithm  as  is. 

K

  most  popular 

vertices  are  selected  as  starting  vertices,  but  the 

breadth-first search with random tie-break is used as 

edge  selection  strategy.  BFS  with  random  tie-break 

has  been  selected  because  it  allows  isolated  tree 

construction.