Generating spatially-aware degree-preserving random graphs?

2012-12-18T22:43:58Z

In the study of biological neural networks, researchers sometimes compare hypotheses vs. a degree-preserving random null model. One major criticism against this approach is that connections in neural networks are greatly affected by their location in 3D Euclidean space (whereas the null model isn't).

Question: Is there a random graph model that both

preserves vertex degrees, and

accounts for the 3D location of vertices in space (i.e., nearby vertices are more likely to be connected than distant vertices)?

I'd be interested in both directed or undirected graphs (usually they can be adapted to suit, anyway).

Answer by Anthony Quas for Generating spatially-aware degree-preserving random graphs?

2012-12-19T01:50:09Z

I can make you a directed model! Let's specify the out-degree of each vertex: $o_x$ is the out-degree of vertex $x$.

Choose yourself an increasing function $F(d)$ that encodes a distance penalty. For each pair of vertices $x$ and $y$, let $A_{xy}=F(\|x-y\|)U_{xy}$. The edges leaving vertex $x$ are then the $\vec{xy}$ corresponding to the $o_x$ smallest values of $A_{xy}$.

Doing the undirected case seems a bit more subtle...

EDIT: Let me expand/change this a bit. For a mathematically interesting model, where you might be able to prove something, you could look at a Gibbs probability distribution. You define an "energy" for each legal configuration (i.e. subgraph of $G$ satisfying the degree constraints). Then, based on the hypothesis that high energy states are unlikely, you assign them low probability.

More specifically, a reasonable approach would be to define the energy of a configuration $\xi$ to be $\Phi(\xi)=\sum_{e\in E(\xi)}F(\|e\|)$. If you let $\Lambda$ be the set of all legal configurations, then the Gibbs measure is defined by $\mathbb P(\xi)=e^{-\Phi(\xi)}/\sum_{\zeta\in\Lambda}e^{-\Phi(\zeta)}$. (The normalization, which is sometimes called the partition function, $Z(\Lambda)$, there makes this a probability measure). The reason that Gibbs measures are nice is that the multiplicative properties of the exponential function ($e^{a+b}=e^ae^b$) lead to some independence properties of the measure you've constructed. For example it's easy to see that if $\xi$ and $\xi'$ are 2 configurations that agree except that $\xi$ contains edges $ab$ and $cd$, while $\xi'$ contains edges $ac$ and $bd$, there's an easily calculated relationship between $\mathbb P(\xi)$ and $\mathbb P(\xi')$.

Generating spatially-aware degree-preserving random graphs? - MathOverflow

Generating spatially-aware degree-preserving random graphs?

Answer by Anthony Quas for Generating spatially-aware degree-preserving random graphs?