階層式重疊社群偵測演算法之研究

A Study of Hierarchical Overlapping Community Detection Algorithm

陳舒嫻(Shu-Hsien Chen)

指導教授 ： 張瑞雄 ； 彭勝龍

國立臺北商業大學/管理學院/資訊與決策科學研究所/碩士(2021年)

摘要

隨著社群軟體和媒體的蓬勃發展，社群網絡也在不斷進化，其規模也變得更 加廣泛和多樣化。按照慣例，社群網絡可以用圖來建模，其中頂點代表個人或帳 號，邊代表這些人與人之間的關聯，可能是有相互加好友或訊息來往等等的關 聯。基於實際應用，社區偵測是網絡分析中的一項很重要的任務。由於網絡結構 的複雜性，現實世界中的社區通常是重疊和分層的。近年來，很多社區偵測的研 究都用單單尋找重疊社區的方法，只有少數研究是從階層式結構的角度來找出社 區。在本論文中，我們提出了一種新的社區偵測的演算法，該演算法同時考慮重 疊和階層式來找出社區，特別是採用階層式聚類，我們的演算法中找出重疊社區 的基本思想非常簡單，它只依賴於尋找所有節點的鄰接(即閉鄰域)。

關鍵字

社區偵測 ； 重疊社區 ； 階層式社區 ； 社群網絡

並列摘要

With the vigorous development of social software and media, social networks are evolutionary, and their scale has become more extensive and diversified. As a convention, a social network can be modeled by a graph, where vertices represent individuals or objects and edges represent connections among these individuals. Based on practical applications, community detection is an inherent task in network analysis. Due to the complexity of the network structure, communities are usually overlapping and hierarchical in the real world. In recent years, a lot of researches for community detection have been directed to methods for finding overlapping communities, and only a few works addressed from the perspective of hierarchy. In this paper, we propose a new algorithm for detecting communities that meet the demand of taking into account the overlap and hierarchy simultaneously. In particular, to adopt a hierarchical clustering, our basic idea in the algorithm is very simple, and it only relies on finding the adjacency (i.e., closed neighborhoods) of all nodes.

並列關鍵字

community detectio ； overlapping community ； hierarchical community ； social networks

參考文獻

[1] A. Amelio, & C. Pizzuti. (2014). Overlapping Community Discovery Methods: A Survey. Social Networks: Analysis and Case Studies, 105–125.

[2] D. Avis, & K. Fukuda. (1996). Reverse search for enumeration. Social Networks: Analysis and Case Studies, 65(1–3), 21–46.

[3] P. Bedi, & C. Sharma. (2016). Community detection in the social networks. WIREs, 6(3), 115–135.

[4] M. Girvan, & M. E. J. Newman. (2002). Community structure in social and biological networks. PNAS, 99(12), 7821–7826.

[5] I. Jeantet, Z. Miklos, & D. Gross-Amblard. (2020). Overlapping Hierarchical Clustering (OHC). Intelligent Data Analysis.