  SimRank is a similarity measure between vertices in a graph, which has become
a fundamental technique in graph analytics. Recently, many algorithms have been
proposed for efficient evaluation of SimRank similarities. However, the
existing SimRank computation algorithms either overlook uncertainty in graph
structures or is based on an unreasonable assumption (Du et al). In this paper,
we study SimRank similarities on uncertain graphs based on the possible world
model of uncertain graphs. Following the random-walk-based formulation of
SimRank on deterministic graphs and the possible worlds model of uncertain
graphs, we define random walks on uncertain graphs for the first time and show
that our definition of random walks satisfies Markov's property. We formulate
the SimRank measure based on random walks on uncertain graphs. We discover a
critical difference between random walks on uncertain graphs and random walks
on deterministic graphs, which makes all existing SimRank computation
algorithms on deterministic graphs inapplicable to uncertain graphs. To
efficiently compute SimRank similarities, we propose three algorithms, namely
the baseline algorithm with high accuracy, the sampling algorithm with high
efficiency, and the two-phase algorithm with comparable efficiency as the
sampling algorithm and about an order of magnitude smaller relative error than
the sampling algorithm. The extensive experiments and case studies verify the
effectiveness of our SimRank measure and the efficiency of our SimRank
computation algorithms.
