以奇異值分解偵測複雜網路中之群組結構

Abstract

本研究之目的為嘗試是否能使用奇異值分解偵測出複雜網路中之群組結構，對於複雜網路之研究，偵測出群組結構已經逐漸為研究學者們所重視，在文獻回顧中，簡單地介紹各種偵測群組結構之方法，每種方法皆有其優缺點，適用之網路也不相同，本研究之目的是希望以不同之角度看待偵測網路中之群組結構，希望能在此領域開創新的道路。 本研究以奇異值分解為基礎，將實際上存在於多維度空間中的網路資料點，投射於空間中任一平面，再依據各點較靠近平面上哪一軸而分為兩個群組，由於並無限制投射於空間中哪個平面，故實際上可得到多組可能之群組結構，本研究使用Newman所提出之模組性，判斷哪一個結果為最佳之群組結構。本研究演算法之時間複雜度為奇異值分解的時間複雜度O(min{n2m, m2n})，雖然並不算非常快，但相對於其準確性我們認為是可以接受的。 對於如何判斷何時停止演算法之運算，本研究使用Reichardt 與 Bornholdt所提出之預期之模組性，判斷所得之群組結構是否具有意義，若最大之模組型仍低於預期之模組性，代表此網路已不存在任何群組結構，此時可停止演算法之運算。 最後本研究藉由數個真實世界網路，測試本研究奇異值分解之方法之準確性，其中包括了邊線等值之無權重網路與邊線不等值之權重網路，皆獲得不錯之結果。

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.