Functions upon weights of a graph
$begingroup$
Given a oriented planar graph, $G(V,E)$, and a partitioning, $P$ of $V$ into two connected subgraphs of approximately equal orde, I'm trying to create a Markov process to generate other such partitioning $P$. I know I need to worry about the standard distribution and everything, but right now I'm just brainstorming ideas to further pursue.
For this goal, I thought it was natural to imagine defining the partition by weights, and then moving weights these weights along $G$. The partitioning, $P={S_1,S_2}$, could be defined by $forall vin S_1, w(v)=1, forall v in S_2, w(v)=0$. Below I have some crude ideas for creating functions upon these weights, but am itching to find spectral methods which make life easier, or any other interesting ideas.
By putting a vector field under $G$, you could create a flow network weighted to best reflect the flow of particles along the aforementioned vector field. Here, I could either create disjoint directed cycles, to keep everything nice and discrete, or relax weights to reals and then choose some threshold constant to convert things back to binary. I am aware that similar ideas are used sometimes in fluid dynamics, but have been unable to find useful papers in defining the weights of directed edges.
Another idea is to create a cut $C$ upon $G$, which bisects it, and then define something akin to a dihedral flip. Simply create some bijection between the vertices on the two sides of $C$. However, the bijection should be relatively likely to preserve connected-ness in the induced subgraph defined by the partitioning. Likely, I'd have to restrict myself to restricted kinds of cuts, and then define the bijection in terms of distance either along the edges of $G$, or the cartesian positioning of its orientation. Or maybe the mapping could involve real relaxation as well.
Anyways, I'd be really appreciative of any ideas, this is part of a research project in the fight against gerrymandering!
discrete-mathematics soft-question spectral-graph-theory
asked Dec 30 '18 at 21:27
Zachary HunterZachary Hunter
602111
$endgroup$
add a comment |
$begingroup$
Given a oriented planar graph, $G(V,E)$, and a partitioning, $P$ of $V$ into two connected subgraphs of approximately equal orde, I'm trying to create a Markov process to generate other such partitioning $P$. I know I need to worry about the standard distribution and everything, but right now I'm just brainstorming ideas to further pursue.
For this goal, I thought it was natural to imagine defining the partition by weights, and then moving weights these weights along $G$. The partitioning, $P={S_1,S_2}$, could be defined by $forall vin S_1, w(v)=1, forall v in S_2, w(v)=0$. Below I have some crude ideas for creating functions upon these weights, but am itching to find spectral methods which make life easier, or any other interesting ideas.
By putting a vector field under $G$, you could create a flow network weighted to best reflect the flow of particles along the aforementioned vector field. Here, I could either create disjoint directed cycles, to keep everything nice and discrete, or relax weights to reals and then choose some threshold constant to convert things back to binary. I am aware that similar ideas are used sometimes in fluid dynamics, but have been unable to find useful papers in defining the weights of directed edges.
Another idea is to create a cut $C$ upon $G$, which bisects it, and then define something akin to a dihedral flip. Simply create some bijection between the vertices on the two sides of $C$. However, the bijection should be relatively likely to preserve connected-ness in the induced subgraph defined by the partitioning. Likely, I'd have to restrict myself to restricted kinds of cuts, and then define the bijection in terms of distance either along the edges of $G$, or the cartesian positioning of its orientation. Or maybe the mapping could involve real relaxation as well.
Anyways, I'd be really appreciative of any ideas, this is part of a research project in the fight against gerrymandering!
discrete-mathematics soft-question spectral-graph-theory
asked Dec 30 '18 at 21:27
Zachary HunterZachary Hunter
602111
$endgroup$
1
$begingroup$
While I accept that your intentions are good, open ended chat-style discussions are really not in keeping with the StackExchange way of Q&A.
$endgroup$
– hardmath
Dec 30 '18 at 21:45
$begingroup$
Would focusing the question to whether or not there are specific operations in spectral graph theory which can nicely define movement of weights?
$endgroup$
– Zachary Hunter
Dec 30 '18 at 21:50
$begingroup$
Perhaps you can give an example that will lend your problem greater clarity. You mention various kinds of "restrictions", but I have difficulty what in the context of discrete weights on graphs it means "to preserve continuity". Brainstorming is not the forte of Math.SE.
$endgroup$
– hardmath
Dec 30 '18 at 22:07
$begingroup$
Whoops, I meant that given a connected component, the dihedral flip would give another connected component. One such example would be mapping $v_{i,j} rightarrow v_{2n-i,j}$ in a 2n by m grid graph.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 22:14
add a comment |
$begingroup$
Given a oriented planar graph, $G(V,E)$, and a partitioning, $P$ of $V$ into two connected subgraphs of approximately equal orde, I'm trying to create a Markov process to generate other such partitioning $P$. I know I need to worry about the standard distribution and everything, but right now I'm just brainstorming ideas to further pursue.
For this goal, I thought it was natural to imagine defining the partition by weights, and then moving weights these weights along $G$. The partitioning, $P={S_1,S_2}$, could be defined by $forall vin S_1, w(v)=1, forall v in S_2, w(v)=0$. Below I have some crude ideas for creating functions upon these weights, but am itching to find spectral methods which make life easier, or any other interesting ideas.
By putting a vector field under $G$, you could create a flow network weighted to best reflect the flow of particles along the aforementioned vector field. Here, I could either create disjoint directed cycles, to keep everything nice and discrete, or relax weights to reals and then choose some threshold constant to convert things back to binary. I am aware that similar ideas are used sometimes in fluid dynamics, but have been unable to find useful papers in defining the weights of directed edges.
Another idea is to create a cut $C$ upon $G$, which bisects it, and then define something akin to a dihedral flip. Simply create some bijection between the vertices on the two sides of $C$. However, the bijection should be relatively likely to preserve connected-ness in the induced subgraph defined by the partitioning. Likely, I'd have to restrict myself to restricted kinds of cuts, and then define the bijection in terms of distance either along the edges of $G$, or the cartesian positioning of its orientation. Or maybe the mapping could involve real relaxation as well.
Anyways, I'd be really appreciative of any ideas, this is part of a research project in the fight against gerrymandering!
discrete-mathematics soft-question spectral-graph-theory
asked Dec 30 '18 at 21:27
Zachary HunterZachary Hunter
602111
$endgroup$
Given a oriented planar graph, $G(V,E)$, and a partitioning, $P$ of $V$ into two connected subgraphs of approximately equal orde, I'm trying to create a Markov process to generate other such partitioning $P$. I know I need to worry about the standard distribution and everything, but right now I'm just brainstorming ideas to further pursue.
For this goal, I thought it was natural to imagine defining the partition by weights, and then moving weights these weights along $G$. The partitioning, $P={S_1,S_2}$, could be defined by $forall vin S_1, w(v)=1, forall v in S_2, w(v)=0$. Below I have some crude ideas for creating functions upon these weights, but am itching to find spectral methods which make life easier, or any other interesting ideas.
By putting a vector field under $G$, you could create a flow network weighted to best reflect the flow of particles along the aforementioned vector field. Here, I could either create disjoint directed cycles, to keep everything nice and discrete, or relax weights to reals and then choose some threshold constant to convert things back to binary. I am aware that similar ideas are used sometimes in fluid dynamics, but have been unable to find useful papers in defining the weights of directed edges.
Another idea is to create a cut $C$ upon $G$, which bisects it, and then define something akin to a dihedral flip. Simply create some bijection between the vertices on the two sides of $C$. However, the bijection should be relatively likely to preserve connected-ness in the induced subgraph defined by the partitioning. Likely, I'd have to restrict myself to restricted kinds of cuts, and then define the bijection in terms of distance either along the edges of $G$, or the cartesian positioning of its orientation. Or maybe the mapping could involve real relaxation as well.
Anyways, I'd be really appreciative of any ideas, this is part of a research project in the fight against gerrymandering!
discrete-mathematics soft-question spectral-graph-theory
discrete-mathematics soft-question spectral-graph-theory
asked Dec 30 '18 at 21:27
Zachary HunterZachary Hunter
602111
asked Dec 30 '18 at 21:27
Zachary HunterZachary Hunter
602111
edited Dec 30 '18 at 22:09
Zachary Hunter
asked Dec 30 '18 at 21:27
Zachary HunterZachary Hunter
602111
asked Dec 30 '18 at 21:27
Zachary HunterZachary Hunter
602111
asked Dec 30 '18 at 21:27
Zachary HunterZachary Hunter
602111
602111
1
$begingroup$
While I accept that your intentions are good, open ended chat-style discussions are really not in keeping with the StackExchange way of Q&A.
$endgroup$
– hardmath
Dec 30 '18 at 21:45
$begingroup$
Would focusing the question to whether or not there are specific operations in spectral graph theory which can nicely define movement of weights?
$endgroup$
– Zachary Hunter
Dec 30 '18 at 21:50
$begingroup$
Perhaps you can give an example that will lend your problem greater clarity. You mention various kinds of "restrictions", but I have difficulty what in the context of discrete weights on graphs it means "to preserve continuity". Brainstorming is not the forte of Math.SE.
$endgroup$
– hardmath
Dec 30 '18 at 22:07
$begingroup$
Whoops, I meant that given a connected component, the dihedral flip would give another connected component. One such example would be mapping $v_{i,j} rightarrow v_{2n-i,j}$ in a 2n by m grid graph.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 22:14
add a comment |
1
$begingroup$
While I accept that your intentions are good, open ended chat-style discussions are really not in keeping with the StackExchange way of Q&A.
$endgroup$
– hardmath
Dec 30 '18 at 21:45
$begingroup$
Would focusing the question to whether or not there are specific operations in spectral graph theory which can nicely define movement of weights?
$endgroup$
– Zachary Hunter
Dec 30 '18 at 21:50
$begingroup$
Perhaps you can give an example that will lend your problem greater clarity. You mention various kinds of "restrictions", but I have difficulty what in the context of discrete weights on graphs it means "to preserve continuity". Brainstorming is not the forte of Math.SE.
$endgroup$
– hardmath
Dec 30 '18 at 22:07
$begingroup$
Whoops, I meant that given a connected component, the dihedral flip would give another connected component. One such example would be mapping $v_{i,j} rightarrow v_{2n-i,j}$ in a 2n by m grid graph.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 22:14
1
1
$begingroup$
While I accept that your intentions are good, open ended chat-style discussions are really not in keeping with the StackExchange way of Q&A.
$endgroup$
– hardmath
Dec 30 '18 at 21:45
$begingroup$
While I accept that your intentions are good, open ended chat-style discussions are really not in keeping with the StackExchange way of Q&A.
$endgroup$
– hardmath
Dec 30 '18 at 21:45
$begingroup$
Would focusing the question to whether or not there are specific operations in spectral graph theory which can nicely define movement of weights?
$endgroup$
– Zachary Hunter
Dec 30 '18 at 21:50
$begingroup$
Would focusing the question to whether or not there are specific operations in spectral graph theory which can nicely define movement of weights?
$endgroup$
– Zachary Hunter
Dec 30 '18 at 21:50
$begingroup$
Perhaps you can give an example that will lend your problem greater clarity. You mention various kinds of "restrictions", but I have difficulty what in the context of discrete weights on graphs it means "to preserve continuity". Brainstorming is not the forte of Math.SE.
$endgroup$
– hardmath
Dec 30 '18 at 22:07
$begingroup$
Perhaps you can give an example that will lend your problem greater clarity. You mention various kinds of "restrictions", but I have difficulty what in the context of discrete weights on graphs it means "to preserve continuity". Brainstorming is not the forte of Math.SE.
$endgroup$
– hardmath
Dec 30 '18 at 22:07
$begingroup$
Whoops, I meant that given a connected component, the dihedral flip would give another connected component. One such example would be mapping $v_{i,j} rightarrow v_{2n-i,j}$ in a 2n by m grid graph.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 22:14
$begingroup$
Whoops, I meant that given a connected component, the dihedral flip would give another connected component. One such example would be mapping $v_{i,j} rightarrow v_{2n-i,j}$ in a 2n by m grid graph.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 22:14
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%2f3057218%2ffunctions-upon-weights-of-a-graph%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%2f3057218%2ffunctions-upon-weights-of-a-graph%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
1
$begingroup$
While I accept that your intentions are good, open ended chat-style discussions are really not in keeping with the StackExchange way of Q&A.
$endgroup$
– hardmath
Dec 30 '18 at 21:45
$begingroup$
Would focusing the question to whether or not there are specific operations in spectral graph theory which can nicely define movement of weights?
$endgroup$
– Zachary Hunter
Dec 30 '18 at 21:50
$begingroup$
Perhaps you can give an example that will lend your problem greater clarity. You mention various kinds of "restrictions", but I have difficulty what in the context of discrete weights on graphs it means "to preserve continuity". Brainstorming is not the forte of Math.SE.
$endgroup$
– hardmath
Dec 30 '18 at 22:07
$begingroup$
Whoops, I meant that given a connected component, the dihedral flip would give another connected component. One such example would be mapping $v_{i,j} rightarrow v_{2n-i,j}$ in a 2n by m grid graph.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 22:14