  Network growth models that embody principles such as preferential attachment
and local attachment rules have received much attention over the last decade.
Among various approaches, random walks have been leveraged to capture such
principles. In this paper we consider the No Restart Random Walk (NRRW) model
where a walker builds its graph (tree) while moving around. In particular, the
walker takes s steps (a parameter) on the current graph. A new node with degree
one is added to the graph and connected to the node currently occupied by the
walker. The walker then resumes, taking another s steps, and the process
repeats. We analyze this process from the perspective of the walker and the
network, showing a fundamental dichotomy between transience and recurrence for
the walker as well as power law and exponential degree distribution for the
network. More precisely, we prove the following results: i) for s=1 the random
walk is transient and the degree of every node is bounded from above by a
geometric distribution. ii) for s even the random walk is recurrent and the
degree of non-leaf nodes is bounded from below by a power law distribution with
exponent decreasing in s. We also provide a lower bound for the fraction of
leaves in the graph, and for s=2 our bound implies that the fraction of leaves
goes to one as the graph size goes to infinity. NRRW exhibits an interesting
mutual dependency between graph building and random walking that is
fundamentally influenced by the parity of s. Understanding this kind of coupled
dynamics is an important step towards modeling more realistic network growth
processes.
