0
$\begingroup$

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?

  • 0
    @Snowball: th$e$ pap$e$r is at http://arxiv.org/pdf/1012.0623.pdf . In cas$e$ it is impo$r$ta$n$t to you, if I receive multiple good a$n$swers I am more likely to accept one from Legendre (see below).2012-10-10

2 Answers 2

1

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.

  • 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
1

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.