Generating a weighted random graph with a correlation between degrees per edge and edge weight

Question

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?

Answer 1

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.