Mixing
Graph edges total distance
$begingroup$
Say one has the following graph
One has $8$ (black) vertices.
Say one has a $8 times 1$ vector of distances between each black vertex and the red vertex. By distances, I mean that all my vertices are members of a metric space, e.g. a geographical space. Let's denote this vector by $boldsymbol{d}$.
Say one has a $8 times 8$ matrix in which each element represents the percentage of edge-distance in common between two vertices (a fortiori with entries equal to $1$ on the main diagonal and a priori asymmetric since two vertices are very likely to share different percentages). Let's denote this matrix by $boldsymbol{D}$.
Do you have any reference which explains how to compute the total distance over edges when having only $boldsymbol{d}$ and $boldsymbol{D}$ in hand?
Starting with a very simple case, and complexifying it progressively, I ended with
$|(boldsymbol{D}^{-1})^{'} boldsymbol{d}|$
Where the operator $|.|$ stands for the L$1$-norm, i.e. the sum of all the absolute elements' value of $(boldsymbol{D}^{-1})^{'} boldsymbol{d}$ (although the absolute-value of entries is not needed since everything is already positive).
Am I right by computing this (total graph) distance like this ?
linear-algebra graph-theory
asked Sep 22 '17 at 0:21
keepAlivekeepAlive
178111
$endgroup$
add a comment |
$begingroup$
Say one has the following graph
One has $8$ (black) vertices.
Say one has a $8 times 1$ vector of distances between each black vertex and the red vertex. By distances, I mean that all my vertices are members of a metric space, e.g. a geographical space. Let's denote this vector by $boldsymbol{d}$.
Say one has a $8 times 8$ matrix in which each element represents the percentage of edge-distance in common between two vertices (a fortiori with entries equal to $1$ on the main diagonal and a priori asymmetric since two vertices are very likely to share different percentages). Let's denote this matrix by $boldsymbol{D}$.
Do you have any reference which explains how to compute the total distance over edges when having only $boldsymbol{d}$ and $boldsymbol{D}$ in hand?
Starting with a very simple case, and complexifying it progressively, I ended with
$|(boldsymbol{D}^{-1})^{'} boldsymbol{d}|$
Where the operator $|.|$ stands for the L$1$-norm, i.e. the sum of all the absolute elements' value of $(boldsymbol{D}^{-1})^{'} boldsymbol{d}$ (although the absolute-value of entries is not needed since everything is already positive).
Am I right by computing this (total graph) distance like this ?
linear-algebra graph-theory
asked Sep 22 '17 at 0:21
keepAlivekeepAlive
178111
$endgroup$
$begingroup$
Do you by "total distance" mean the number of edges in the graph?
$endgroup$
– wonce
Sep 23 '17 at 16:26
$begingroup$
@wonce. No I really mean that all my vertices are members of a metric space. As if each of the vertices were a location in a geographical world.
$endgroup$
– keepAlive
Sep 23 '17 at 18:51
$begingroup$
Are you assuming your graph is a tree (so there's exactly one path from any vertex to any other vertex)?
$endgroup$
– Gerry Myerson
Jan 29 at 8:30
$begingroup$
@GerryMyerson Yes it is a tree.
$endgroup$
– keepAlive
Jan 29 at 9:09
add a comment |
$begingroup$
Say one has the following graph
One has $8$ (black) vertices.
Say one has a $8 times 1$ vector of distances between each black vertex and the red vertex. By distances, I mean that all my vertices are members of a metric space, e.g. a geographical space. Let's denote this vector by $boldsymbol{d}$.
Say one has a $8 times 8$ matrix in which each element represents the percentage of edge-distance in common between two vertices (a fortiori with entries equal to $1$ on the main diagonal and a priori asymmetric since two vertices are very likely to share different percentages). Let's denote this matrix by $boldsymbol{D}$.
Do you have any reference which explains how to compute the total distance over edges when having only $boldsymbol{d}$ and $boldsymbol{D}$ in hand?
Starting with a very simple case, and complexifying it progressively, I ended with
$|(boldsymbol{D}^{-1})^{'} boldsymbol{d}|$
Where the operator $|.|$ stands for the L$1$-norm, i.e. the sum of all the absolute elements' value of $(boldsymbol{D}^{-1})^{'} boldsymbol{d}$ (although the absolute-value of entries is not needed since everything is already positive).
Am I right by computing this (total graph) distance like this ?
linear-algebra graph-theory
asked Sep 22 '17 at 0:21
keepAlivekeepAlive
178111
$endgroup$
Say one has the following graph
One has $8$ (black) vertices.
Say one has a $8 times 1$ vector of distances between each black vertex and the red vertex. By distances, I mean that all my vertices are members of a metric space, e.g. a geographical space. Let's denote this vector by $boldsymbol{d}$.
Say one has a $8 times 8$ matrix in which each element represents the percentage of edge-distance in common between two vertices (a fortiori with entries equal to $1$ on the main diagonal and a priori asymmetric since two vertices are very likely to share different percentages). Let's denote this matrix by $boldsymbol{D}$.
Do you have any reference which explains how to compute the total distance over edges when having only $boldsymbol{d}$ and $boldsymbol{D}$ in hand?
Starting with a very simple case, and complexifying it progressively, I ended with
$|(boldsymbol{D}^{-1})^{'} boldsymbol{d}|$
Where the operator $|.|$ stands for the L$1$-norm, i.e. the sum of all the absolute elements' value of $(boldsymbol{D}^{-1})^{'} boldsymbol{d}$ (although the absolute-value of entries is not needed since everything is already positive).
Am I right by computing this (total graph) distance like this ?
linear-algebra graph-theory
linear-algebra graph-theory
asked Sep 22 '17 at 0:21
keepAlivekeepAlive
178111
asked Sep 22 '17 at 0:21
keepAlivekeepAlive
178111
edited Jan 29 at 8:26
keepAlive
asked Sep 22 '17 at 0:21
keepAlivekeepAlive
178111
asked Sep 22 '17 at 0:21
keepAlivekeepAlive
178111
asked Sep 22 '17 at 0:21
keepAlivekeepAlive
178111
178111
$begingroup$
Do you by "total distance" mean the number of edges in the graph?
$endgroup$
– wonce
Sep 23 '17 at 16:26
$begingroup$
@wonce. No I really mean that all my vertices are members of a metric space. As if each of the vertices were a location in a geographical world.
$endgroup$
– keepAlive
Sep 23 '17 at 18:51
$begingroup$
Are you assuming your graph is a tree (so there's exactly one path from any vertex to any other vertex)?
$endgroup$
– Gerry Myerson
Jan 29 at 8:30
$begingroup$
@GerryMyerson Yes it is a tree.
$endgroup$
– keepAlive
Jan 29 at 9:09
add a comment |
$begingroup$
Do you by "total distance" mean the number of edges in the graph?
$endgroup$
– wonce
Sep 23 '17 at 16:26
$begingroup$
@wonce. No I really mean that all my vertices are members of a metric space. As if each of the vertices were a location in a geographical world.
$endgroup$
– keepAlive
Sep 23 '17 at 18:51
$begingroup$
Are you assuming your graph is a tree (so there's exactly one path from any vertex to any other vertex)?
$endgroup$
– Gerry Myerson
Jan 29 at 8:30
$begingroup$
@GerryMyerson Yes it is a tree.
$endgroup$
– keepAlive
Jan 29 at 9:09
$begingroup$
Do you by "total distance" mean the number of edges in the graph?
$endgroup$
– wonce
Sep 23 '17 at 16:26
$begingroup$
Do you by "total distance" mean the number of edges in the graph?
$endgroup$
– wonce
Sep 23 '17 at 16:26
$begingroup$
@wonce. No I really mean that all my vertices are members of a metric space. As if each of the vertices were a location in a geographical world.
$endgroup$
– keepAlive
Sep 23 '17 at 18:51
$begingroup$
@wonce. No I really mean that all my vertices are members of a metric space. As if each of the vertices were a location in a geographical world.
$endgroup$
– keepAlive
Sep 23 '17 at 18:51
$begingroup$
Are you assuming your graph is a tree (so there's exactly one path from any vertex to any other vertex)?
$endgroup$
– Gerry Myerson
Jan 29 at 8:30
$begingroup$
Are you assuming your graph is a tree (so there's exactly one path from any vertex to any other vertex)?
$endgroup$
– Gerry Myerson
Jan 29 at 8:30
$begingroup$
@GerryMyerson Yes it is a tree.
$endgroup$
– keepAlive
Jan 29 at 9:09
$begingroup$
@GerryMyerson Yes it is a tree.
$endgroup$
– keepAlive
Jan 29 at 9:09
add a comment |
0
active
oldest
votes
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%2f2439682%2fgraph-edges-total-distance%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%2f2439682%2fgraph-edges-total-distance%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
$begingroup$
Do you by "total distance" mean the number of edges in the graph?
$endgroup$
– wonce
Sep 23 '17 at 16:26
$begingroup$
@wonce. No I really mean that all my vertices are members of a metric space. As if each of the vertices were a location in a geographical world.
$endgroup$
– keepAlive
Sep 23 '17 at 18:51
$begingroup$
Are you assuming your graph is a tree (so there's exactly one path from any vertex to any other vertex)?
$endgroup$
– Gerry Myerson
Jan 29 at 8:30
$begingroup$
@GerryMyerson Yes it is a tree.
$endgroup$
– keepAlive
Jan 29 at 9:09