Timeline for How to uniformly sample vertices from a large graph with given distance from a fixed vertex?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 18, 2019 at 15:43 | history | edited | fuz | CC BY-SA 4.0 |
added 4 characters in body
|
| Oct 18, 2019 at 15:12 | history | edited | fuz | CC BY-SA 4.0 |
notation
|
| Oct 18, 2019 at 13:05 | history | edited | fuz | CC BY-SA 4.0 |
added 175 characters in body
|
| Oct 8, 2019 at 14:07 | vote | accept | fuz | ||
| Jul 22, 2018 at 11:35 | comment | added | MotiNK | Well $S$ is defined by the above procedure. Weighting appropriately within $W$ to achieve $S$ seems very manageable. But weighting with respect to vertices in $V_k$ outside of $W$ (which are of course the majority) is the more difficult part. For example, there may be a node which has a very small number of paths to it, thus the chances of it being included in $W$ are lower than for other nodes. Is this corrected for by the weighting when it DOES make it into $W$? | |
| Jul 22, 2018 at 10:43 | comment | added | fuz | @MotiN Do you mean $S$ by set of vertices chosen by the bootstrap sampling procedure? | |
| Jul 22, 2018 at 10:19 | comment | added | MotiNK | I don't think that $\sum_{v \in W} b(v)^{-1} = 1$ (of course you can reweight). And what happens with vertices not appearing in $W$? The result of your random walks will of course not include a lot of those; I think you really must do a proper calculation to include the probability of a node appearing in $W$ times the chance of it being chosen by the bootstrap sampling procedure. That first probability seems very difficult to me to calculate directly. | |
| Jul 22, 2018 at 10:08 | comment | added | fuz | @MotiN it is $v_i\in V_i$ for all $i$. I have used the same bias values as in your answer, except that I don't lose a factor of $3$ because I am not constrained to actual probabilities. | |
| Jul 22, 2018 at 8:21 | comment | added | MotiNK | As well, I'd really suggest you do a calculation of the probability of selecting a vertex. This is really the only way to know if your algorithm is correct, rather than a gut feeling about it. | |
| Jul 22, 2018 at 7:27 | comment | added | MotiNK | Can you add subscripts to the $C(\dot)$ functions to reflect the $i$ of $V_i$ they are for? it will make things clearer, thank you. | |
| Jul 19, 2018 at 13:22 | history | edited | fuz | CC BY-SA 4.0 |
edited body
|
| Jul 19, 2018 at 12:30 | history | edited | fuz | CC BY-SA 4.0 |
added 5 characters in body
|
| Jul 19, 2018 at 12:13 | history | answered | fuz | CC BY-SA 4.0 |