Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Without 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. –  Brian M. Scott Oct 10 '12 at 0:48
    
Are you able to provide a link to the paper? –  Snowball Oct 10 '12 at 2:48
    
@Brian: the paper is at 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). –  Stefan Smith Oct 10 '12 at 12:17
    
@Snowball: the paper is at 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). –  Stefan Smith Oct 10 '12 at 12:17

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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. –  Stefan Smith Oct 10 '12 at 12:14
    
@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. –  Legendre Oct 10 '12 at 13:15
    
I 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. –  Stefan Smith Oct 10 '12 at 17:18
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 ... –  Brian M. Scott Oct 11 '12 at 4:46
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. –  Brian M. Scott Oct 11 '12 at 4:47

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.