0
$\begingroup$

Given a distribution over graphs with $n$ nodes having the "scale-free" property, I would like to compute for a pair of vertices $(a,b)$ the probability that they are connected (or more precisely the probability that there is a directed edge from $a$ to $b$).

Is it possible to have such probability distribution ?

Note that the case without the "scale-free" property is not a problem. I can define the probability of having an edge from $a$ to $b$ as $P((a,b))=1/2$ for all $a, b$, $a \neq b$ in the graph.

Thank you.

$\endgroup$
  • $\begingroup$ all graphs have an adjacency matrix. try to reformulate your question. the adjacency matrix properties/ theory is sometimes used to generate scale-free networks. $\endgroup$ – vzn Jun 27 '15 at 18:50
  • 1
    $\begingroup$ 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. $\endgroup$ – François Jun 27 '15 at 20:05
  • 2
    $\begingroup$ 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.. $\endgroup$ – François Jun 30 '15 at 12:33
  • 1
    $\begingroup$ Why do you care so much about generating your graphs by sampling edges independently? $\endgroup$ – Yuval Filmus Jun 30 '15 at 23:06
  • 1
    $\begingroup$ @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. $\endgroup$ – David Richerby Jul 1 '15 at 8:33
2
$\begingroup$

The most popular generative model for scale-free networks is the preferential attachment model of Barabási and Albert. A graph is sampled using an iterative procedure. This is a different sampling procedure than you suggest, since the goal is not only to generate a certain degree sequence, but also to mimic other properties of real-life networks.

If all you're after is a certain degree sequence, you can use MCMC methods; see for example Stanton and Pinar. Such algorithms don't conform to your type of algorithm, however. If you want to use your type of model, you have to decide in advance which vertices will have high degree and which will have low degree, since otherwise you will get a degree distribution which is either roughly Gaussian or roughly Poisson, but definitely no power law.

If all you're after is a certain degree sequence and you really want to use your own generative model, here is one possibility. Use the preferential attachment model, the algorithm of Stanton and Pinar, or any other randomized algorithm to generate a graph $G$. Now your model is: given two vertices $x,y$, if $(x,y) \in G$ then connect $x$ and $y$ with probability $1$, otherwise connect them with probability $0$.

$\endgroup$
  • $\begingroup$ Thanks for your answer. In fact it's the opposite that I would like to have. I don't have a network at the beginning. I can assume a network in which there are nodes without the edges. Then I affect edges between some vertices using probabilities. $\endgroup$ – user7060 Jun 30 '15 at 19:09
  • 1
    $\begingroup$ I gave such an approach in the second paragraph. In preprocessing, you generate a network using a less restricted model. Then you replicate this network using your model. $\endgroup$ – Yuval Filmus Jun 30 '15 at 19:11
  • $\begingroup$ Thanks very much even if I did not understand the last paragraph. In particular the sentence "Now your model is: given two vertices x,y, if (x,y)∈G then connect x and y with probability 1, otherwise connect them with probability 0." $\endgroup$ – user7060 Jul 1 '15 at 8:20
  • $\begingroup$ The thing is that every deterministic graph can be realized in your model. That is, for every graph $G$, we can choose edge probabilities so that you always get $G$. That's the tongue-in-cheek part of my answer. I'm always giving two other generative models. $\endgroup$ – Yuval Filmus Jul 1 '15 at 17:59
  • $\begingroup$ Thanks for your help. Maybe my question has no sense, or I should reformulate it again. $\endgroup$ – user7060 Jul 2 '15 at 8:00
1
$\begingroup$

Your question is fairly unclear and it seems you lack basic understanding in the topic of scale-free networks. Congratulations! You now feel like almost every other PhD student ever. ;)

From how I understand your question, you would like to have a probability distribution over graphs such that you obtain a scale-free graph with high probability from this distribution. There are numerous ways of achieving that, and one of the most popular ones is the Preferential attachment model noted by Yuval.

It seems to me, however, that furthermore, you want to "grasp the individual edge probabilities by hand". Like the Erdos-Renyi random graph model $G(n,p)$, you want to basically know the $p$ for an edge given two nodes $u,v$. This is actually very hard to do for the preferential attachment model! (Though there exist results that do that).

But I have good news for you: This is possible! There are in fact several scale-free network models that give you exact edge probabilities and yet generate a scale-free graph in the end. The most famous one is probably the Chung-Lu Random Graph. The first hit on google seems to give a very good introduction to the topic. Here's the gist of it:

  1. First, for each vertex $i \in \{1, \ldots, n\}$ choose a weight $w_i$ for that vertex. There are several appropriate ways to do this, but if you want something concrete you can use $w_i = \delta \cdot (n/i)^{1/(\beta - 1)}$. This will produce a scale-free network with power-law exponent $\beta$.

  2. Second, connect two nodes with probability $p_{i,j} := \min\{1, \frac{w_i w_j}{\sum_k w_k}\}$

I hope this helps. If you have any further questions, don't hesitate to ask.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I imagine that $\frac{w_iw_j}{\sum w_k}$ can be greater than $1$. No ? What is $\delta$ ? Are the $w_i$ the preferential parameters ? What about the fitness model ? $\endgroup$ – user7060 Jul 3 '15 at 6:40
  • $\begingroup$ If $\beta\leq 3$ then the sum can become larger than $1$. $\delta$ is just some constant, which will in the end adjust the average degree (which is $\Theta(\delta)$). I am not sure what you refer to with "preferential parameters" or "fitness model". This model is different from the preferential attachment. The $w_i$ are the node weights; depending on how you chose them you get different degree sequences. If you choose them like I wrote you obtain a power law (= a scale-free network). $\endgroup$ – HdM Jul 3 '15 at 7:30
  • $\begingroup$ Thanks for your answer. I've seen the fitness model on Wiki (link). In this model $p_{i,j}$ can be computed as $\frac{\delta x_ix_j}{1+\delta x_ix_j}$ where $x_i$, $x_j$ are fitness assigned to nodes $i$ and $j$. Maybe these fitness values are chosen following a power law, I don't know... $\endgroup$ – user7060 Jul 3 '15 at 7:44
  • $\begingroup$ It is a slight variation, but has basically the same properties as my suggestion when you choose (their) $\delta$ to be $1/\sum_k w_k$. There exist many many slight variations on this model. $\endgroup$ – HdM Jul 3 '15 at 13:22
  • $\begingroup$ Thank you very much. Why we have a probability with a max in the model you propose while in the other model the probability calculation is simpler ? $\endgroup$ – user7060 Jul 4 '15 at 13:01

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.