Application of SVD Analysis on Detecting Community Structure in Complex Networks
Date Issued
2009
Date
2009
Author(s)
Yang, Hong-Li
Abstract
The detection and analysis of community structure in complex network like social network, metabolic network and World Wide Web is one of the most important issues in the study of networked systems. In this article, we present how to use the singular value decomposition analysis to detect the community structure. The running time of our algorithm on a network with n vertices and m edges is O(min{n2m, m2n}). We transform the network to incidence matrix, and do the singular value decomposition. Use the left singular vector ui to determine the community structure. The results of algorithm include several possible community structures. Here we use Newman’s modularity to choose which community structure should be the best one. Also we use the expecting modularity based on ER random model which proposed by Reichardt and Bornholdt to decide when to stop the algorithm. I apply our algorithm to several real world network examples to test our algorithm. Some of examples are unweighted networks, others are weighted networks. We show that our algorithm can successfully detect the meaningful community structure for both networks. And according to the known community structures in network examples, we find that the accuracy of our algorithm is good too.
Subjects
complex network
community structure
singular value decomposition
modularity
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R96524069-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):3237865b1681b503f8c95949879bd377