Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

First some preamble:

Let A be a set of unordered elements, and let A' and A'' be subsets of A, where |A'| = |A''| = k. It’s given that as k approaches |A|, for every x in A' there is an increased probability of finding x in A''. That is, as k approaches |A|, |A' ∩ A''| approaches |A|.

On to the issue at hand:

Let’s say we have two different graphs G1 and G2, each with n vertices labeled 1 through n, and each with a set of non-random edges.* Let B be the set of vertices from G1, and C be the set of vertices from G2. Order B and C by vertex degree. Let B' and C' be subsets of B and C respectively, where |B'| = |C'| = k, and where subset elements are taken from their respective supersets from left to right (see example below), such that as k approaches n, B' and C' will tend to include vertices of lesser and lesser degree.

Here’s a general example of the subset selection process: B = {1,4,2,5,3} C = {4,2,3,1,5}

k = 1 -> B' = {1}, C' = {4}

k = 2 -> B' = {1,4}, C' = {4,2}

k = 3 -> B' = {1,4,2}, C' = {4,2,3}

k = 4 -> B' = {1,4,2,5}, C' = {4,2,3,1}

k = n -> B' = {1,4,2,5,3}, C' = {4,2,3,1,5}

If I were to plot k vs |B' ∩ C'|, the shape of the curve would be attributable both to the effect of increasing k, as described in my preamble, but ALSO, and especially, to the effect of the ordering. In this case, the ordering by degree. How do I determine the significance of this ordering?

*By non-random edges I mean that the connectivity of the respective graphs is determined by some other factor. In my real-world case, these graphs represent brain connectivity at different intervals of time. Connected nodes represent highly correlated activity between neurons.

share|cite|improve this question
If the arrangements of edges in the two graphs are independent (and it sounds like they are), then the ordering by degree of the two vertex sets should be essentially equivalent to ordering the vertices at random. So I'm not sure there should be any significance to ordering by degree. Or am I misunderstanding your question? – Mike Spivey Sep 1 '11 at 1:37
Good point. For the data I'm actually working with they're not independent. In fact, they're graphs of brain networks taken from fMRI at different times. I'll fix my post. – Narwe Sep 1 '11 at 1:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.