  We study random walk on complex networks with transition probabilities which
depend on the current and previously visited nodes. By using an absorbing
Markov chain we derive an exact expression for the mean first passage time
between pairs of nodes, for a random walk with a memory of one step. We have
analyzed one particular model of random walk, where the transition
probabilities depend on the number of paths to the second neighbors. The
numerical experiments on paradigmatic complex networks verify the validity of
the theoretical expressions, and also indicate that the flattening of the
stationary occupation probability accompanies a nearly optimal random search.
