Mixing
Measure of subgraph isomorphisms
$begingroup$
I have a "big" (biological) finite graph $Gamma = (V, E)$ and a set of subsets of vertices $S = {gamma(t)}_{t in mathcal T}$ (with a given function $gamma : mathcal T to mathcal P(V)$ where $|V| simeq 18,000$ and $|mathcal T| simeq 12,500$). I am interested in the different subgraphs induced by the $gamma(t)$ modulo isomorphisms. I claim that in my case, the number of different non-isomorphic subgraphs is clearly higher than expected if they were uniformly distributed among $V$. To do this, I sample uniformly selected subsets of $V$ (of the same size as the $gamma(t)$ subsets) and look at the number of non-isomorphic subgraphs I end up with, and then repeat this step a lot of times to have an idea of the distribution of the number of non-isomorphic subgraphs under the uniform sampling.
However I need to have a statistical measure on this. So what I did was approximating the probability distribution mentioned right above and use Chebyshev's inequality to infer an upper bound that is used as a $p$-value. This gives me what I expect (i.e. a very low $p$-value).
My first question is: is this method valid in any way? and my second question is: how can I measure the "density" of isomorphisms?
What I mean by "density of isomorphisms" is a scalar value (hopefully normalized so between 0 and 1) that will represent somehow how much of isomorphisms can be found within my subgraphs. The only thing I have been able to come up with so far is based on Shannon entropy (yeah computer science background here):
$$H(S) = frac 1{log |S|}sum_{s in S/simeq}frac {|s|}{|S|}logfrac {|s|}{|S|},$$
where $S/simeq$ is the set of isomorphism classes and $frac 1{log |S|}$ is there to normalize the value. But again I have no idea if this can get me somewhere in the statistical analysis of my results.
graph-theory graph-isomorphism
asked Jan 8 at 13:12
BermudesBermudes
15713
$endgroup$
add a comment |
$begingroup$
I have a "big" (biological) finite graph $Gamma = (V, E)$ and a set of subsets of vertices $S = {gamma(t)}_{t in mathcal T}$ (with a given function $gamma : mathcal T to mathcal P(V)$ where $|V| simeq 18,000$ and $|mathcal T| simeq 12,500$). I am interested in the different subgraphs induced by the $gamma(t)$ modulo isomorphisms. I claim that in my case, the number of different non-isomorphic subgraphs is clearly higher than expected if they were uniformly distributed among $V$. To do this, I sample uniformly selected subsets of $V$ (of the same size as the $gamma(t)$ subsets) and look at the number of non-isomorphic subgraphs I end up with, and then repeat this step a lot of times to have an idea of the distribution of the number of non-isomorphic subgraphs under the uniform sampling.
However I need to have a statistical measure on this. So what I did was approximating the probability distribution mentioned right above and use Chebyshev's inequality to infer an upper bound that is used as a $p$-value. This gives me what I expect (i.e. a very low $p$-value).
My first question is: is this method valid in any way? and my second question is: how can I measure the "density" of isomorphisms?
What I mean by "density of isomorphisms" is a scalar value (hopefully normalized so between 0 and 1) that will represent somehow how much of isomorphisms can be found within my subgraphs. The only thing I have been able to come up with so far is based on Shannon entropy (yeah computer science background here):
$$H(S) = frac 1{log |S|}sum_{s in S/simeq}frac {|s|}{|S|}logfrac {|s|}{|S|},$$
where $S/simeq$ is the set of isomorphism classes and $frac 1{log |S|}$ is there to normalize the value. But again I have no idea if this can get me somewhere in the statistical analysis of my results.
graph-theory graph-isomorphism
asked Jan 8 at 13:12
BermudesBermudes
15713
$endgroup$
add a comment |
$begingroup$
I have a "big" (biological) finite graph $Gamma = (V, E)$ and a set of subsets of vertices $S = {gamma(t)}_{t in mathcal T}$ (with a given function $gamma : mathcal T to mathcal P(V)$ where $|V| simeq 18,000$ and $|mathcal T| simeq 12,500$). I am interested in the different subgraphs induced by the $gamma(t)$ modulo isomorphisms. I claim that in my case, the number of different non-isomorphic subgraphs is clearly higher than expected if they were uniformly distributed among $V$. To do this, I sample uniformly selected subsets of $V$ (of the same size as the $gamma(t)$ subsets) and look at the number of non-isomorphic subgraphs I end up with, and then repeat this step a lot of times to have an idea of the distribution of the number of non-isomorphic subgraphs under the uniform sampling.
However I need to have a statistical measure on this. So what I did was approximating the probability distribution mentioned right above and use Chebyshev's inequality to infer an upper bound that is used as a $p$-value. This gives me what I expect (i.e. a very low $p$-value).
My first question is: is this method valid in any way? and my second question is: how can I measure the "density" of isomorphisms?
What I mean by "density of isomorphisms" is a scalar value (hopefully normalized so between 0 and 1) that will represent somehow how much of isomorphisms can be found within my subgraphs. The only thing I have been able to come up with so far is based on Shannon entropy (yeah computer science background here):
$$H(S) = frac 1{log |S|}sum_{s in S/simeq}frac {|s|}{|S|}logfrac {|s|}{|S|},$$
where $S/simeq$ is the set of isomorphism classes and $frac 1{log |S|}$ is there to normalize the value. But again I have no idea if this can get me somewhere in the statistical analysis of my results.
graph-theory graph-isomorphism
asked Jan 8 at 13:12
BermudesBermudes
15713
$endgroup$
I have a "big" (biological) finite graph $Gamma = (V, E)$ and a set of subsets of vertices $S = {gamma(t)}_{t in mathcal T}$ (with a given function $gamma : mathcal T to mathcal P(V)$ where $|V| simeq 18,000$ and $|mathcal T| simeq 12,500$). I am interested in the different subgraphs induced by the $gamma(t)$ modulo isomorphisms. I claim that in my case, the number of different non-isomorphic subgraphs is clearly higher than expected if they were uniformly distributed among $V$. To do this, I sample uniformly selected subsets of $V$ (of the same size as the $gamma(t)$ subsets) and look at the number of non-isomorphic subgraphs I end up with, and then repeat this step a lot of times to have an idea of the distribution of the number of non-isomorphic subgraphs under the uniform sampling.
However I need to have a statistical measure on this. So what I did was approximating the probability distribution mentioned right above and use Chebyshev's inequality to infer an upper bound that is used as a $p$-value. This gives me what I expect (i.e. a very low $p$-value).
My first question is: is this method valid in any way? and my second question is: how can I measure the "density" of isomorphisms?
What I mean by "density of isomorphisms" is a scalar value (hopefully normalized so between 0 and 1) that will represent somehow how much of isomorphisms can be found within my subgraphs. The only thing I have been able to come up with so far is based on Shannon entropy (yeah computer science background here):
$$H(S) = frac 1{log |S|}sum_{s in S/simeq}frac {|s|}{|S|}logfrac {|s|}{|S|},$$
where $S/simeq$ is the set of isomorphism classes and $frac 1{log |S|}$ is there to normalize the value. But again I have no idea if this can get me somewhere in the statistical analysis of my results.
graph-theory graph-isomorphism
graph-theory graph-isomorphism
asked Jan 8 at 13:12
BermudesBermudes
15713
asked Jan 8 at 13:12
BermudesBermudes
15713
edited Jan 9 at 22:49
Bermudes
asked Jan 8 at 13:12
BermudesBermudes
15713
asked Jan 8 at 13:12
BermudesBermudes
15713
asked Jan 8 at 13:12
BermudesBermudes
15713
15713
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3066147%2fmeasure-of-subgraph-isomorphisms%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3066147%2fmeasure-of-subgraph-isomorphisms%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
