Return to 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$. But for reasons of time I could not look further into it yet.

References

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

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

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

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!

References

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

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

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$. But for reasons of time I could not look further into it yet.

References

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

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

Background

I am current 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!

References

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

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

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!

References

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

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