Timeline for Sample a random subgraph from an undirected, unweighted graph, what's the probability of "every two nodes's distance is at least 3 in the subgraph"?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Apr 27 at 4:03 | history | bounty ended | Voyager | ||
| S Apr 27 at 4:03 | history | notice removed | Voyager | ||
| Apr 27 at 3:45 | answer | added | user225256 | timeline score: 2 | |
| Apr 26 at 3:14 | comment | added | Voyager | @MattF. Thanks! I mean $d(i,j)$ in a big graph $G$. | |
| Apr 26 at 2:57 | comment | added | user225256 | Do you mean $d(i,j)$ (the distance between $i$ and $j$ as vertices in the big graph) or $d_S(i,j)$ (the minimum distance between $i$ and $j$ along parts going only through $S$)? Note $d(i,j)\le d_S(i,j)$. | |
| Apr 19 at 15:27 | comment | added | Voyager | @Xi'an Yeah, I see. But I'm sorry I can not provide more details, because that's exactly what I'm seeking for. To be honest, I'm a rookie in this field. I had hoped there are some off-the-shelf results... | |
| Apr 19 at 10:11 | comment | added | Xi'an | The question has no definite answer without specifying the probability distribution behind the sampling mechanism (and possibly a prior on the distribution of edges over the entire graph). | |
| S Apr 19 at 9:43 | history | bounty started | Voyager | ||
| S Apr 19 at 9:43 | history | notice added | Voyager | Draw attention | |
| Apr 17 at 3:06 | comment | added | Voyager | @ThomasLumley Yeah, you're right. Actually, that's exactly what I want to ask. I'm seeking the condition that can make this results hold. | |
| Apr 17 at 3:02 | history | edited | Voyager | CC BY-SA 4.0 |
added 1 character in body
|
| Apr 17 at 3:02 | comment | added | Thomas Lumley | How is your population graph generated? The answer will be quite sensitive to this. | |
| Apr 17 at 3:01 | comment | added | Voyager | It may relate to the concept of 'independent set' in graph theory. | |
| Apr 17 at 2:40 | history | asked | Voyager | CC BY-SA 4.0 |