I'm studying sampling techniques in online social networks. The assumption is we don't have full access to the network(i.e, we don’t know the size of the network). However crawling is supported, i.e, starting with any arbitrary node we can access its neighbors. Hence we go for random walk(Markov Chain) based crawling techniques as it requires only neighborhood information for any node.
Let's assume we choose simple random walk(SRW) for crawling the network.
In SRW we start with an arbitrary seed node then choose one of the neighbors as new node. At the new node we choose one of its neighbors and this process continues.
Let G be our graph show in above figure, assume graph is large and size of the graph is not known. We go for SRW with node 'A' as initial node.
Since the size of the graph is not known how do we select initial distribution $X_0$(at time 0), and initial transition probabilities $P_0$(at time 0). After time 0 if I choose one of the neighbors(say B), how the transition probabilities $P_1$(at time 1) and distribution $X_1$(at time 1) are calculated.