0

I would like to generate using a single, coherent mathematical formalism a weighted random graph, either a small-wolrd or a scale free graph, with a probabilistic distribution of weights and vertex properties, s.t. vertices with similar properties have a higher probability of being connected and at that being strongly connected.

How should I go about this?

Piotr Sokol
  • 185

1 Answers1

2

Here's a suggestion that I've come up with:

Let $v_i$ be a vertex of the graph,$e_{ij}$ be an edge between vertex $i$ and $j$.

Lets call your vertex properties $\theta_i$ for the vector of properties for vertex $i$. You will need to define a metric $d_{ij}$ between two property vectors such that if $d_{ij}>d_{ik}$ implies vertex $i$ is more similar to $k$ than $j$. An example of such a metric could be the euclidean distance between two property vectors $\theta_i,\theta_j$.

Generative Model:

  1. Let $e_{ij}\sim Ber(p_{ij})$ ($0$=not included, $1$=included in graph)
  2. Choose a function $s_p(d)$ that is symmetric about $0$ and bounded between $0$ and $p_{max}$, such that $s_p(0)=p_{max}$ is the unique maximum of the function.
  3. Set $p_{ij} = s_p(d_{ij})$
  4. Similarly, define a function $s_w(d)$ that is symmetric about $0$ and bounded between $0$ and $w_{max}$, such that $s_w(0)=w_{max}$ is the unique maximum of the function.
  5. Set $w_{ij} = s_w(d_{ij})+\varepsilon_{ij}$, where $\varepsilon_{ij}$ is a random variate with $E[\varepsilon_{ij}]=0\;\;Var[\varepsilon_{ij}]=g(d_{ij})$ for some function $g(\cdot)$ (possibly constant)

Now, just generate the actual values of $e_{ij}$ from their respective Bernoulli distributions and assign the associated weight to the ones that are included in the graph.

Anyway, just one idea...lots of possibilities out there give your general formulation.

  • I was thinking along the same lines. I do have question though - intuitively this method will not ensure that the distribution of edges per node will follow that of a scale free or small world net, right? That property, is perhaps less important to me, but I'm sure there's a way to specify that in the generative model. I was also thinking about starting with the Watts-Strogatz/preferential attachment algorithm and assigning in a correlated fashion $\theta_i$ values within clique of some size. – Piotr Sokol Sep 03 '14 at 14:35
  • @PiotrSokol I purposely left the functions undefined, as graph theory is not my specialty...I was just offering a quantitative framework. –  Sep 03 '14 at 14:41
  • This answers my question that I just added in the comment - it describes how to get SF networks with a fitness metric. Taken together, I can generate the network I described above, thanks! – Piotr Sokol Sep 03 '14 at 17:09