Generating spatially-aware degree-preserving random graphs? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T17:17:14Z http://mathoverflow.net/feeds/question/116739 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/116739/generating-spatially-aware-degree-preserving-random-graphs Generating spatially-aware degree-preserving random graphs? Douglas S. Stones 2012-12-18T22:43:58Z 2012-12-20T01:40:49Z <p>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).</p> <blockquote> <p><strong>Question</strong>: Is there a random graph model that both</p> <ul> <li>preserves vertex degrees, and</li> <li>accounts for the 3D location of vertices in space (i.e., nearby vertices are more likely to be connected than distant vertices)?</li> </ul> </blockquote> <p>I'd be interested in both directed or undirected graphs (usually they can be adapted to suit, anyway).</p> http://mathoverflow.net/questions/116739/generating-spatially-aware-degree-preserving-random-graphs/116746#116746 Answer by Anthony Quas for Generating spatially-aware degree-preserving random graphs? Anthony Quas 2012-12-19T01:50:09Z 2012-12-20T01:40:49Z <p>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$.</p> <p>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}$. </p> <p>Doing the undirected case seems a bit more subtle...</p> <p>EDIT: Let me expand/change this a bit. For a mathematically interesting model, where you <em>might</em> 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.</p> <p>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')$.</p>