0
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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.) $\endgroup$
    – Douglas S. Stones
    Commented Dec 19, 2012 at 2:27
  • $\begingroup$ 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). $\endgroup$
    – Anthony Quas
    Commented Dec 19, 2012 at 2:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .