I am reading a paper on weighted undirected graphs, and it states that if $A$ is the adjacency matrix of the graph $G$, then $a_{i,i}$ is the node weight of vertex $v_i$. What does this mean? Is there an edge of weight $a_{i,i}$ or of weight $a_{i,i}/2$ going from $v_i$ to itself?
What is the "node weight" of a vertex?
-
1Without more context I can’t be sure, but it sounds as if this is simply a way of incorporating the weights of the vertices into the adjacency matrix; if the graphs are simple, the entries on the diagonal of the matrix are available for other uses, like this one. – 2012-10-10
-
0Are you able to provide a link to the paper? – 2012-10-10
-
0@Brian: the paper is at http://arxiv.org/pdf/1012.0623.pdf . In case it is important to you, if I receive multiple good answers I am more likely to accept one from Legendre (see below). – 2012-10-10
-
0@Snowball: the paper is at http://arxiv.org/pdf/1012.0623.pdf . In case it is important to you, if I receive multiple good answers I am more likely to accept one from Legendre (see below). – 2012-10-10
2 Answers
In general, node weights are just the numbers associated with each nodes. For example, the node weights in a binary search tree: http://en.wikipedia.org/wiki/Binary_search_tree
The node weight of a node $i$ is much more likely to be $a_{i,i}$, than $a_{i,i}/2$. And usually, it does not represent the weight of a self edge (e.g. the binary search tree).
Of course, all these depends on the intent and context of the paper. If you don't mind providing a link to the paper, I can take a look and (pardon the pun) weigh in on the matter.
Edit
This answer is expanded and discussed in the comments.
-
0http://arxiv.org/pdf/1012.0623.pdf . See p. 3, "$P =I$ gives us the total sum of the node weights". I don't really understand what a node weight is for. All the reading I have done before is for simple undirected unweighted graphs where $a_{i,i}$ was always 0. The wikipedia article you cited above doesn't seem related to the paper. There is likely to be a link somewhere that answers my question. If you posted it, with no further explanation, I would accept your answer. – 2012-10-10
-
0@bogus - I think Brain M. Scott's answer pretty much answers it. In particular, the quoted paragraph on p. 7 echoes what I was saying: the diagonal entries give the vertex weight, off diagonal the edge weights. Yes, my link isn't related to the paper but it is an example of node weights being used. E.g. For a binary search tree, a similar "modified" adjacency matrix would have $1$s and $0$s elsewhere representing the edge weights, but $a_{i,i}$ (the node weight) in the diagonal. – 2012-10-10
-
0I accepted your answer. I get the impression that the diagonal of the adjacency matrix (for simple graphs) is not important for most graph theory issues but can be used to store extra information that may be useful depending on what the graph is used for. That sort of information seems to be unnecessary in the problems examined in the paper I cited ( arxiv.org/pdf/1012.0623.pdf ). If my impression is incorrect, I would appreciate being corrected. – 2012-10-10
-
1@bogus: The main purpose of the paper is to introduce convex graph invariants and study their basic properties; maximum node weight and sum of node weights are both elementary convex graph invariants. Convex spectral invariants depend on the eigenvalues of the adjacency matrix, which in turn depend on the node weights as well as the edge weights. Solution 1 in Section 5.2 uses all of the elementary convex graph invariants, so it involves node weight; the example at the foot of p. 31 uses spectral constraints; and Section 5.3 deals with arbitrary structural constraints, which may certainly ... – 2012-10-11
-
1@bogus: ... include constraints involving node weight. Similarly, the application in Section 5.4 may involve any invariants. In short, information on node weights is one of the kinds of information considered in the applications in that paper. – 2012-10-11
-
0@Brian: I appreciate the time you put into your answer. I will reread those parts of the paper considering what you wrote. – 2012-10-11
As they say at the beginning of Section 3 (p. 7), the authors are considering only simple undirected graphs; this means that the adjacency matrices are symmetric and in the unweighted case have zeroes on the main diagonal. They then explicitly allow themselves both node (vertex) weights and edge weights. Since the entries $a_{i,i}$ on the diagonal are otherwise unused, they are available for the vertex weights; an entry $a_{i,j}$ with $i\ne j$, which would be $1$ or $0$ for an unweighted graph depending on whether there was or was not an edge between vertex $i$ and vertex $j$, is used for the weight of that edge.
All of this is confirmed by the last paragraph on p. 7:
Given a graph $\mathcal{G}$ defined on $n$ nodes, a labeling of the nodes of $\mathcal{G}$ is a function $\ell$ that maps the nodes of $\mathcal{G}$ onto distinct integers in $\{1,\dots,n\}$. An adjacency matrix in $\mathbf{S}^n$ is then said to represent or specify $\mathcal{G}$ if there exists a labeling $\ell$ of the nodes of $\mathcal{G}$ so that the weight of the edge between nodes $i$ and $j$ equals $A_{\ell(i)\ell(j)}$ for all pairs $\{i,j\}$ and the weight of node $i$ equals $A_{\ell(i)\ell(i)}$ for all $i$.
That last sentence makes it explicit that the diagonal entries give the vertex weights and the off-diagonal entries, the edge weights.