Sum of the degrees of second neighbours of a vertex in a graph
$begingroup$
The question is: "Using only matrix formalism find the vector $pmb{v}$ whose element $i$ is the sum of the degrees of vertex's $i$ second neighbours".
My attempt:
Let $A$ be the adjacent matrix of the graph. The vector $pmb{k}$ whose elements are the degree of the vertices is $pmb{k}=Acdotpmb{1}$ where $pmb{1}$ is a column vector off all ones. Now, to find the sum of the degrees of the second neighbours I need a proper matrix to rearrange and sum the elements of the vector $pmb{k}$. For instance if I want instead the sum of the degrees of the first neighbours the proper matrix is the adjacent matrix. Indeed $Acdotpmb{k}$ is the vector whose element $i$ is the sum of the degrees of vertex $i$-th.
I tried to use a matrix similar to: $A^2-diag(pmb{k})$, but, of course, it will not work due to repetitions and loops.
Thanks
graph-theory network adjacency-matrix
edited Jan 15 at 14:55
amWhy
1
asked Oct 4 '18 at 11:06
AlexAlex
32319
$endgroup$
add a comment |
$begingroup$
The question is: "Using only matrix formalism find the vector $pmb{v}$ whose element $i$ is the sum of the degrees of vertex's $i$ second neighbours".
My attempt:
Let $A$ be the adjacent matrix of the graph. The vector $pmb{k}$ whose elements are the degree of the vertices is $pmb{k}=Acdotpmb{1}$ where $pmb{1}$ is a column vector off all ones. Now, to find the sum of the degrees of the second neighbours I need a proper matrix to rearrange and sum the elements of the vector $pmb{k}$. For instance if I want instead the sum of the degrees of the first neighbours the proper matrix is the adjacent matrix. Indeed $Acdotpmb{k}$ is the vector whose element $i$ is the sum of the degrees of vertex $i$-th.
I tried to use a matrix similar to: $A^2-diag(pmb{k})$, but, of course, it will not work due to repetitions and loops.
Thanks
graph-theory network adjacency-matrix
edited Jan 15 at 14:55
amWhy
1
asked Oct 4 '18 at 11:06
AlexAlex
32319
$endgroup$
$begingroup$
Well, $Apmb{k}$ counts the degree of each vertex, $A^2pmb{k}$ counts the sum of the degrees of the neighbours of each vertex, and something like $A^3pmb{k} - diag^2(A pmb{k})$ counts the sum of the degrees of the second neighbours of each vertex, the problem being caused by multiple counting due to cycles of length 3 or 4. What was the exact wording of the question?
$endgroup$
– Mike
Oct 4 '18 at 20:22
add a comment |
$begingroup$
The question is: "Using only matrix formalism find the vector $pmb{v}$ whose element $i$ is the sum of the degrees of vertex's $i$ second neighbours".
My attempt:
Let $A$ be the adjacent matrix of the graph. The vector $pmb{k}$ whose elements are the degree of the vertices is $pmb{k}=Acdotpmb{1}$ where $pmb{1}$ is a column vector off all ones. Now, to find the sum of the degrees of the second neighbours I need a proper matrix to rearrange and sum the elements of the vector $pmb{k}$. For instance if I want instead the sum of the degrees of the first neighbours the proper matrix is the adjacent matrix. Indeed $Acdotpmb{k}$ is the vector whose element $i$ is the sum of the degrees of vertex $i$-th.
I tried to use a matrix similar to: $A^2-diag(pmb{k})$, but, of course, it will not work due to repetitions and loops.
Thanks
graph-theory network adjacency-matrix
edited Jan 15 at 14:55
amWhy
1
asked Oct 4 '18 at 11:06
AlexAlex
32319
$endgroup$
The question is: "Using only matrix formalism find the vector $pmb{v}$ whose element $i$ is the sum of the degrees of vertex's $i$ second neighbours".
My attempt:
Let $A$ be the adjacent matrix of the graph. The vector $pmb{k}$ whose elements are the degree of the vertices is $pmb{k}=Acdotpmb{1}$ where $pmb{1}$ is a column vector off all ones. Now, to find the sum of the degrees of the second neighbours I need a proper matrix to rearrange and sum the elements of the vector $pmb{k}$. For instance if I want instead the sum of the degrees of the first neighbours the proper matrix is the adjacent matrix. Indeed $Acdotpmb{k}$ is the vector whose element $i$ is the sum of the degrees of vertex $i$-th.
I tried to use a matrix similar to: $A^2-diag(pmb{k})$, but, of course, it will not work due to repetitions and loops.
Thanks
graph-theory network adjacency-matrix
graph-theory network adjacency-matrix
edited Jan 15 at 14:55
amWhy
1
asked Oct 4 '18 at 11:06
AlexAlex
32319
edited Jan 15 at 14:55
amWhy
1
asked Oct 4 '18 at 11:06
AlexAlex
32319
edited Jan 15 at 14:55
amWhy
1
edited Jan 15 at 14:55
amWhy
1
edited Jan 15 at 14:55
amWhy
1
1
asked Oct 4 '18 at 11:06
AlexAlex
32319
asked Oct 4 '18 at 11:06
AlexAlex
32319
asked Oct 4 '18 at 11:06
AlexAlex
32319
32319
$begingroup$
Well, $Apmb{k}$ counts the degree of each vertex, $A^2pmb{k}$ counts the sum of the degrees of the neighbours of each vertex, and something like $A^3pmb{k} - diag^2(A pmb{k})$ counts the sum of the degrees of the second neighbours of each vertex, the problem being caused by multiple counting due to cycles of length 3 or 4. What was the exact wording of the question?
$endgroup$
– Mike
Oct 4 '18 at 20:22
add a comment |
$begingroup$
Well, $Apmb{k}$ counts the degree of each vertex, $A^2pmb{k}$ counts the sum of the degrees of the neighbours of each vertex, and something like $A^3pmb{k} - diag^2(A pmb{k})$ counts the sum of the degrees of the second neighbours of each vertex, the problem being caused by multiple counting due to cycles of length 3 or 4. What was the exact wording of the question?
$endgroup$
– Mike
Oct 4 '18 at 20:22
$begingroup$
Well, $Apmb{k}$ counts the degree of each vertex, $A^2pmb{k}$ counts the sum of the degrees of the neighbours of each vertex, and something like $A^3pmb{k} - diag^2(A pmb{k})$ counts the sum of the degrees of the second neighbours of each vertex, the problem being caused by multiple counting due to cycles of length 3 or 4. What was the exact wording of the question?
$endgroup$
– Mike
Oct 4 '18 at 20:22
$begingroup$
Well, $Apmb{k}$ counts the degree of each vertex, $A^2pmb{k}$ counts the sum of the degrees of the neighbours of each vertex, and something like $A^3pmb{k} - diag^2(A pmb{k})$ counts the sum of the degrees of the second neighbours of each vertex, the problem being caused by multiple counting due to cycles of length 3 or 4. What was the exact wording of the question?
$endgroup$
– Mike
Oct 4 '18 at 20:22
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%2f2941979%2fsum-of-the-degrees-of-second-neighbours-of-a-vertex-in-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%2f2941979%2fsum-of-the-degrees-of-second-neighbours-of-a-vertex-in-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
$begingroup$
Well, $Apmb{k}$ counts the degree of each vertex, $A^2pmb{k}$ counts the sum of the degrees of the neighbours of each vertex, and something like $A^3pmb{k} - diag^2(A pmb{k})$ counts the sum of the degrees of the second neighbours of each vertex, the problem being caused by multiple counting due to cycles of length 3 or 4. What was the exact wording of the question?
$endgroup$
– Mike
Oct 4 '18 at 20:22