# Modularity in a graph — derivation of modularity score

Background

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

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"  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

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

• What about eigendecomposing $s$? – Bullet51 Apr 23 at 12:40
• @Bullet51 I looked into it for a bit but could not find an answer right away. I'll have to put this on ice for a while. – ngmir Apr 28 at 12:26
• I was given the hint that this has to do with the Gram-Schmidt process but for reasons of time I will have to put this question aside for a while. – ngmir Apr 28 at 12:26