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

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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).

-

## 1 Answer

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')$.

-

Hmmm, thanks for that.  I see what you're doing there, but this wouldn't preserve vertex in-degrees, which would be a disadvantage. (I'll have to think about whether this would be a significant disadvantage for the application I have in mind.) – Douglas S. Stones Dec 19 at 2:27
I guess you could do what I'm doing (putting weights on edges) and then minimize over configurations that satisfy the degree constraints. My guess is the difficulty with this kind of thing is that you might get mathematically intractable models (although it's probably reasonably easy for computers to simulate it). – Anthony Quas Dec 19 at 2:39
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 27, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9486624598503113, "perplexity_flag": "head"}