0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What about eigendecomposing $s$? $\endgroup$ – Bullet51 Apr 23 at 12:40
  • $\begingroup$ @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. $\endgroup$ – ngmir Apr 28 at 12:26
  • $\begingroup$ 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. $\endgroup$ – ngmir Apr 28 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.