**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](https://math.stackexchange.com/questions/1064016/linear-combination-of-eigenvectors-corresponding-to-the-same-eigenvalue?rq=1) 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](https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_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](https://en.wikipedia.org/wiki/Orthonormal_basis), 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](https://mathoverflow.net/questions/212761/modularity-in-a-graph-definition-of-the-random-component)



Modularity in a graph -- derivation of modularity score
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](https://en.wikipedia.org/wiki/Normal_matrix). 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*](https://www.maa.org/sites/default/files/pdf/awards/Axler-Ford-1996.pdf) (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](https://yutsumura.com/orthogonality-of-eigenvectors-of-a-symmetric-matrix-corresponding-to-distinct-eigenvalues/).



> 
> $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](https://cloud.uni-konstanz.de/index.php/s/9fXzkL9DGqcs9br). 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.)


