Singular Value Decomposition - Social Network Analysis

Question

I have a very large network of nodes represented by an adjacency matrix. I would like to reduce the amount of nodes in the network to include the more important nodes. I am aware that SVD can help me achieve this and I have used the ILNumerics library to run the svd() method on the adjacency matrix.

Could someone explain simply to me how the output is mean to help me reduce the dimensions of my network? The SVD process leaves me with a matrix of the same size with descending values diagonally ranging from ~2 to many 0s. How do I know which dimensions to remove which are deemed unimportant?

I am likely doing this process incorrectly overall so any help would be greatly appreciated! Many of the explanations online get very confusing very quickly.

Answer 1

I'm not too familiar with ILNumerics, so I'll try explaining what the SVD in general is able to in your case. First of all, Wikipedia gives some basic information of possible applications of SVD. In your case, the parts about "Range, null space and rank" and "Low-rank matrix approximation" are of particular interest. A singular value decomposition can help you determine the real rank of your system matrix. If your adjacency graph is sparse, your system matrix (say, an N times N matrix) is likely to have a rank M that is smaller than N. In that case, you can compute a low-rank approximation of it. That is, you construct a M times M (M < N) where you neglect the N - M smallest eigenvalues since they only have a very small influence in your results. What small means in this context does of course strongly depend on your application.

Edit: In your example data, your original matrix A has been decomposed as A = outU svdOut outV. The diagonal matrix svdOut constists of the eigenvalues singular values of A whereas the columns/rows of outU and outV are the left- and right-singular vectors of A, respectively. In your example, the singular values are 1.61803, 1.41421, 0.61803 and 0 (two times). The rank of your original matrix is thus given by the number of non-zero singular values (three, in your example). So, you can define a matrix B = outU svdOut* outV where the asterisk indicates that the least significant singular values have been removed. For instance, you could decide that you want to neglect the smallest eigenvalue, thus

svdOut* =
| 1.61803  0        0  0  0 | 
| 0        1.41421  0  0  0 | 
| 0        0        0  0  0 |
| 0        0        0  0  0 |
| 0        0        0  0  0 |

However, after thinking about it again, I think that an SVD of your adjacency matrix will not directly give you what you're looking for. You have to define somehow what an important node actually is in your context.

Edit2 (in response to the comments below): The SVD doesn't give you direct information about your nodes, but about your matrix. The singular vectors form an orthonormal basis that can be used to express your original matrix in a different form. The singular values give you information about how strong the influence of each of these vectors is. Again, Wikipedia might help you getting a feeling how this can be interpreted. Coming back to your original question, I would suppose that a simple SVD is not really what you're looking for.