Before revision:   The numerical simulations show that the walker finds the marked vertex in O(N^{1/4} \log^{3/4} N) steps  with probability O(1/\log N), for an overall complexity of O(N^{1/4}\log^{7/4}N).
After revision:  The numerical simulations show that the walker finds the marked vertex in O(N^{1/4} \log^{3/4} N) steps , with probability O(1/\log N), for an overall complexity of O(N^{1/4}\log^{7/4}N).