Modularity in a graph -- derivation of modularity score

Question

Background

I am currently reading "Modularity and community structure in networks" (2006) by Newman [1].

In it, he derives a score for the modularity of a graph that, intuitively, is based on finding a division for the vertices, so that there are as many "unexpected" [2] edges as possible between vertices in the same group.

Relevant Facts and Definitions

Let $d_i$ be the degree of node $i$. Let $m$ be the number of edges. Then the expected number of edges between nodes $i$ and $j$ is defined as $$E_{ij} := \frac{d_i d_j}{2m}.$$

For now, we only consider a partition into two communities. Let $s_i = 1$ iff node $i$ is in community $A$, $-1$ else.

Then, we can define a modularity score $Q$ of a partition based on the difference between the number of edges in a partition and the expected number of edges from a random graph. $$ Q := \sum_{i,j} (A_{ij} - E_{ij}) s_i s_j .$$

With $B:= A_{ij} - E_{ij}$ and $s := (s_1, ..., s_n)$, we can also write this as $$ Q = s^T B s .$$

Question

The next sentence is the one I don't understand.

Given [this definition of $Q$] we proceed by writing $s$ as a linear combination of the normalised eigenvectors $u_i$ of $B$ so that $s = \sum_{i=1}^{n} a_i u_i$ with $a_i = u_i^T s$.

I can see that $B$ has $n$ linearly independent Eigenvectors which thus form a basis. Where I'm completely lost is why we can write $s$ like so and why it is relevant that the $u_i$ are normalised.

What I've tried

I've spent some time trying to write down the expressions in different way but I could never find a way so that $s = \sum_{i=1}^{n} (u_i^T s) u_i$.

I've checked whether other facts presented in the paper up to this point might be relevant but I just can't see which would be. I've tried reading on to make more sense of it but there's not much more.

I've looked at questions like this one but I couldn't find anything I could apply.

I think I am really just lacking some very basic Linear Algebra ingredient here. Would be great if someone could help me out!

---

Edit: I was given the hint that this has to do with the Gram-Schmidt process and that $u_i^Ts$ is the inner product of $u_i$ and $s$.

In fact, $\{u_1, ..., u_n\}$ form an orthonormal basis and in the corresponding Wikipedia article, we I found exactly the statement in question.

I will write a proper answer about this when I have obtained the necessary background knownledge.

---

References

[1] Newman, 2006 http://www.pnas.org/content/103/23/8577.full.pdf

[2] Modularity in a graph - definition of the random component

Answer 1

This is a linear algebra thing. The matrix B (called the modularity matrix in the paper of interest) is real symmetric, and a property of real symmetric matrices is that their eigenvectors form an orthonormal basis. The formula you ask about is just decomposing $s $ as a linear combination of these eigen-basis vectors.

Answer 2

Of course the comments and other answers are right, but for the sake of completeness and for those who are new to Linear Algebra (like me) I'll try to explain how this entire thing comes together.

$\mathbb{R}^n$ has a basis of $n$ real eigenvectors $(u_1, ...., u_n)$ of $\mathbf{B}$.

Proof sketch: $\mathbf{B}$ is symmetric and because symmetric matrices commute w.r.t to matrix multiplication and are equal to their transposed, $\mathbf{B}$ is normal. Thus, we can apply the finite-dimensional Spectral Theorem for inner product spaces from which the existence of $n$ eigenvectors follows. —— Information about this can be found in Linear Algebra coursebooks or at Theorem 7.5 in Down with Determinants (which is a very nice read). —— Because $\mathbf{B}$ is symmetric, it is self-adjoint: $$ <Bv, w> = (Bv)^Tw = v^TB^Tw = v^TBw = <v, Bw> $$ and thus all eigenvalues are real.

$(u_1, ...., u_n)$ are pairwise orthogonal and thus form an orthonormal basis of $\mathbb{R}^n$

Proof: Can be found here.

$s$ can be written as $s = \sum_{i=1}^n <s, u_i> u_i$

Proof: Since $(u_1, ..., u_n)$ is an basis, there exist unique $\lambda_i$ with $s = \sum \lambda_i u_i$. Further, because the basis is orthonormal: $$ <s, u_j> ~=~ <\sum \lambda_i u_i, u_j> ~=~ \lambda_i $$

Rewriting $\mathbf{Q}$

Let $a_i := <u_i,s>$ and $\beta_i$ the eigenvalue of $u_i$. Then:

\begin{eqnarray*} Q = s^T B s = (\sum a_i u_i)^T B (\sum a_i u_i) \\&=& (\sum a_i u_i^T) (\sum a_i B u_i) \\&=& \sum a_i^2 \beta_i \\&=& \sum <u_i, s>^2 \beta_i \end{eqnarray*}

You can find some additional notes of mine (more or less) proving some other statements in the paper here. There's also a report of mine about an application of the algorithm in brain network analysis. (Edit: link is now dead but I'll be happy to provide materials if anyone's interested.)