Timeline for scale-free networks and adjacency matrix
Current License: CC BY-SA 3.0
29 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jul 9, 2015 at 10:23 | history | bounty ended | CommunityBot | ||
| S Jul 9, 2015 at 10:23 | history | notice removed | CommunityBot | ||
| Jul 3, 2015 at 1:26 | answer | added | HdM | timeline score: 1 | |
| Jul 1, 2015 at 16:50 | comment | added | vzn | it looks like youve completely reformulated the question. suggest dropping by Computer Science Chat to work out more detail. maybe starting over. there seems to be a real question fighting to get free here. fyi the simple "probability" that any two edges are connected is just the number of edges divided by total possible edges $n^2$, unless there is some other defn wanted. and that does not discriminate the different types of graphs. in other words many non scale free graphs would have exactly the same probabilities and are much easier constructed. so think you probably need to rethink your requirements. | |
| S Jul 1, 2015 at 8:51 | history | bounty started | user7060 | ||
| S Jul 1, 2015 at 8:51 | history | notice added | user7060 | Authoritative reference needed | |
| Jul 1, 2015 at 8:42 | comment | added | user7060 | @DavidRicherby I've read some slides on the subject but it's not clear how to do that. That's why I would like an example. | |
| Jul 1, 2015 at 8:40 | comment | added | David Richerby | @user7060 I don't know if preferential attachment is necessary but, as far as I know, it's the normal way of generating scale-free graphs. But, look, there's a large literature out there about how to do this -- you don't need to make up your own way of doing it. | |
| Jul 1, 2015 at 8:37 | comment | added | user7060 | @DavidRicherby Thanks. That's not possible even without a preferential attachment model ? Look at the second paragraph in the answer below. "you have to decide in advance which vertices will have high degree and which will have low degree". Maybe I can define a probability distribution for the degrees of each vertices ? Not ? I suggest things... Given such a probability distribution, I could include each possible edge independently ? Or that does not work ? | |
| Jul 1, 2015 at 8:33 | comment | added | David Richerby | @user7060 It's impossible to generate a scale free graph by just including each possible edge independently with some probability $p$. That gives a distribution known as $G(n,p)$, which looks nothing like scale-free graphs. For example, $G(n,p)$ graphs are fairly close to regular, whereas scale-free graphs are very far from regular. | |
| Jul 1, 2015 at 8:30 | comment | added | user7060 | @D.W. I've edited the question. | |
| Jul 1, 2015 at 8:28 | history | edited | user7060 | CC BY-SA 3.0 |
deleted 15 characters in body
|
| Jul 1, 2015 at 8:23 | history | edited | user7060 | CC BY-SA 3.0 |
deleted 15 characters in body
|
| Jul 1, 2015 at 8:18 | comment | added | user7060 | @D.W. Thank you. I would like to edit the question appropriately but I don't know the good terminology... I have a not completely constructed network. I just have the nodes without edges. The only property that I want is "scale-free". I would like a probability distribution over the set of all pairs of vertices such that I can compute $P((a,b))=a\ certain\ value$ if an edge exists from $a$ to $b$. I edit my post to write that since the beginning "Given a network..." is ambiguous. | |
| Jul 1, 2015 at 1:51 | comment | added | D.W.♦ | I suspect that what you actually want is something totally different from what the question asks -- I suspect what you actually want is a distribution on graphs with some particular properties. However, that's not what the question currently says. If that's what you want: (a) you need to edit the question drastically to state this, (b) you need to more clearly state what properties you want the distribution to have, and (c) you probably ought to tell us what research you've done and what possibilities you've considered (and if you've rejected them, why). | |
| Jul 1, 2015 at 1:49 | comment | added | D.W.♦ | The question as it is currently stated makes no sense. Given a particular graph, either $a,b$ are connected or they aren't -- there's nothing probabilistic. Maybe you mean "given a distribution over graphs", or "given a *random process" for generating a graph". If so, you should edit the question accordingly -- and you need to tell us how the distribution/random process is specified, as that will dramatically affect the answer to your question. As it stands, the question makes no sense and is not answerable in its current form. | |
| Jun 30, 2015 at 23:06 | comment | added | Yuval Filmus | Why do you care so much about generating your graphs by sampling edges independently? | |
| Jun 30, 2015 at 15:17 | answer | added | Yuval Filmus | timeline score: 2 | |
| Jun 30, 2015 at 14:54 | history | edited | user7060 | CC BY-SA 3.0 |
added 117 characters in body
|
| Jun 30, 2015 at 12:33 | comment | added | François | Or more generally, you are looking for a distribution whose graphs are scale-free with h.p. Indeed I don't think it's possible with edge existence i.i.d.. | |
| Jun 30, 2015 at 12:17 | comment | added | François | @user7060 Ok.. So you are just asking for a probability such that when you generate a random graph where each possible edge is in the graph with this probability, then your graph is scale-free with high probability. I said graph and not adjacency matrix but we don't care, it's the same. I probably have the answer to your question, but please rewrite it clearly first. | |
| Jun 30, 2015 at 11:29 | comment | added | user7060 | @FrançoisGodi No, I don't know how to chose the probability distribution. Generating an adjacency matrix for a random network is easy: I just have to fix a probability of connection, for instance $1/2$, and make coin toss for each pair of vertices. I imagine that for scale-free networks, it isn't as easy as it looks. | |
| Jun 30, 2015 at 11:00 | comment | added | François | @user7060 Can you choose those probabilities or not ? | |
| Jun 29, 2015 at 15:01 | comment | added | user7060 | I would like to generate this matrix only using probabilities.For instance, having t vertices, indexed 1, ..., t, I would like to be able to compute the probability of connection of a vertex i to a vertex j. Then I will be able to generate the matrix of a scale-free network. | |
| Jun 28, 2015 at 4:49 | review | Close votes | |||
| Jul 1, 2015 at 8:53 | |||||
| Jun 27, 2015 at 20:05 | comment | added | François | You are talking about probabilities, thus I assume that you have a distribution over graphs. So are you asking for an adjacency matrix regarding a graph or for a kind of adjacency matrix regarding your distribution ? It's not clear for me. Any way, the adjacency matrix and the graph are isomorph so you can compute both if you can compute one. The complexity for computing the adjacency matrix is at least quadratic in the vertices number, since it's just the matrix size. | |
| Jun 27, 2015 at 19:19 | comment | added | David Richerby | @vzn Yes, all graphs have adjacency matrices. So it makes perfect sense to ask about the adjacency matrices of a particular class of graphs. | |
| Jun 27, 2015 at 18:50 | comment | added | vzn | all graphs have an adjacency matrix. try to reformulate your question. the adjacency matrix properties/ theory is sometimes used to generate scale-free networks. | |
| Jun 27, 2015 at 17:30 | history | asked | user7060 | CC BY-SA 3.0 |