基於鄰接矩陣修飾之社群偵測演算法

Abstract

社群偵測(community detection)是社會網路分析(social network analysis)所使用的一種方法之一，通過比對社群網路內實體之間的連線關係能找出網路當中看不到的隱性族群，能用已挖掘潛藏在數據背後所隱藏的重要訊息，在這近十年來，已受到各領域學者的關注。期間，亦有不少針對分群定義社群偵測的演算法不斷被學者提出。 在社群偵測演算法當中，本研究以Martelot與Hankin提出的快速品質塊膜度最佳化演算法(以下簡稱FMSm演算法)為基礎，提出強化特定網路節點關連之方法探討鄰接矩陣(adjacency matrix)修飾對FMSm演算法在社群偵測產生的影響。 在節點間鄰接關係之修飾中，本研究基於相同族群之節點會有高度關聯性之條件及過去文獻經常使用的隨機漫步法提出以共同好友集與PageRank方法從原始鄰接矩陣中萃取精煉矩陣，並與原始鄰接矩陣疊加之修飾演算法－F-FMSm與P-FMSm。經實驗結果證實，利用本研究所提出鄰接關係之修飾，能增加網路內部節點間相似關聯的差異性，使社群偵測演算法在判別節點所屬族群時，在分歧點差異較多之情況下將節點分至正確的族群當中。在標竿模型下量測，F-FMSm與P-FMSm在標竿網路樣本中最高可提升NMI (Normalized Mutual Information) 量值9.5%與6.2%，在非結合基因類型之演算法當中，此方法中有最優良的整體表現。Community detection is one of the methods for social network analysis. By comparing the connections among entities in a social network, community detection discovers important messages hidden in the data. This method has become the focus of research in various fields for the past decade, during which time numerous algorithms for community definition and community detection have been proposed.

The community detection algorithm used in this study is based on the Fast Multi-Scale Detection algorithm (hereafter referred to as the FMSm algorithm) proposed by Martelot and Hankin, which enhances the association between specific network nodes, where the study investigated the effects of adjacency matrix modification in the FMSm algorithm.

In terms of node adjacency relationship modification, this study proposed using common friend set and PageRank method to extract refined matrix from original adjacency matrix and superpose the original adjacency matrix with modification algorithms F-FMSm and P-FMSm, based on the high association between nodes in the same community and the Random Walk method used in much past research. Results show that with the adjacency relationship modification proposed by this study, the difference in association between internal nodes in the network can be increased, so that when the community detection algorithm determines the community of a node, the node can be assigned to the correct community when there are more differences between branch points. When measured in the benchmark model, F-FMSm and P-FMSm can increase Normalized Mutual Information (NMI) by 9.5% and 6.2% respectively in benchmark network samples. With non-genetic algorithms, this method yielded the best overall performance.