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.

Improve this question
$\endgroup$
18
  • $\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
    Commented Jun 27, 2015 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
    Commented Jun 27, 2015 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
    Commented Jun 30, 2015 at 12:33
  • 1
    $\begingroup$ Why do you care so much about generating your graphs by sampling edges independently? $\endgroup$
    – Yuval Filmus
    Commented Jun 30, 2015 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
    Commented Jul 1, 2015 at 8:33

2 Answers 2

Reset to default
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$.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Jun 30, 2015 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
    Commented Jun 30, 2015 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
    Commented Jul 1, 2015 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
    Commented Jul 1, 2015 at 17:59
  • $\begingroup$ Thanks for your help. Maybe my question has no sense, or I should reformulate it again. $\endgroup$
    – user7060
    Commented Jul 2, 2015 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.

Improve this answer
$\endgroup$
6
  • $\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
    Commented Jul 3, 2015 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
    Commented Jul 3, 2015 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
    Commented Jul 3, 2015 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
    Commented Jul 3, 2015 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
    Commented Jul 4, 2015 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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