2
$\begingroup$

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.

enter image description here

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ I don’t really understand your question. Your walk is well-defined - you described it well enough in the text. What are you missing? $\endgroup$
    – Yuval Filmus
    May 31 '19 at 10:18
  • $\begingroup$ When analyzing the random walk you use the actual graph. $\endgroup$
    – Yuval Filmus
    May 31 '19 at 10:38
  • $\begingroup$ For explanation I have taken graph G with 6 nodes, In reality we do not have whole network view, hence size of the graph is not known(i.e,size of state space of random walk is not known). We can access only one node at a time. So we go for simple random walk starting with an arbitrary node('A' in our case). So what is the size of the initial vector $X_0$(initial distribution) and dimension of transition probability matrix $P_0$. How they are updated when a new neighbor is selected. $\endgroup$
    – user3322017
    May 31 '19 at 10:59
  • 1
    $\begingroup$ When you analyze the algorithm there’s no problem using the actual graph. Only the algorithm doesn’t have access to it - the person trying to understand how the algorithm works on a particular graph does have access to the graph. $\endgroup$
    – Yuval Filmus
    May 31 '19 at 11:00
  • $\begingroup$ I understood what you are saying, I still have a small doubt. Let me read the paper for better understanding and I will get back. Thank you for the comments. $\endgroup$
    – user3322017
    May 31 '19 at 11:13
2
$\begingroup$

While the algorithm doesn't know the graph, when you are analyzing the performance of the algorithm on a graph, you do know the graph.

For a similar example, take the egg dropping puzzle. In this puzzle, the algorithm doesn't know the value of $T$, but when analyzing the algorithm, you are allowed to use the value of $T$; indeed, otherwise it's not clear how you'd ever end up with a running time depending on $T$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.