應用混合整數規劃於偵測社群網路之 階層式社群結構

Abstract

由於隨著社群網站的出現和普及，從中找尋社群之間互動以及個體社交行為的社群網路分析研究變成一個熱門的議題。為了進一步了解社群網絡，偵測社群結構是一個常用來分析社群網路的工具之一，因為它經常被用來解釋個體之間的關係以及其個體社交行為的預測。然而，近幾年來的研究發現，社群結構可以進一步構成一個階層式的結構，其中在階層較高的社群中仍可以觀察到一些比較小的子社群如同一個巢狀結構。過去大部分的研究透過啟發解(heuristics)或是萬用啟發式演算法(metaheuristics)用於偵測階層式社群結構去獲得近似解，其運算的效率雖然高，但是卻不能保證獲得階層式社群結構的最佳解。因此，本文提出一個混合整數規劃模型然後透過真實的社群網絡去進行階層式社群結構之偵測，並且將階層數量和每個階層中社群大小的容量限制納入考量，同時最佳化階層式社群結構偵測的品質。之後，在我們的實驗結果中，透過本研究提出的方法可以找到一個合理的階層式社群結構，一個擁有許多節點的社群可以觀察到複雜的階層結構，使得不同階層中社群之間的相互作用，可以更清楚被表示。此外，我們的模型可以保有彈性的調整階層數量去快速於因應不同規模大小的社群網絡，同時保持高品質的階層式社群結構。

With emergence and popularity of social networking websites, social network analysis has been widely used to investigate social interaction and social behavior of individuals. To understand social networks, detection of community structures is one of the most crucial tasks as it is often used for explaining the inner relationship among individuals and prediction of social behavior. The community structures further constitute a hierarchical structure, in which the super node at a higher level represents a nested structure so that the relationship of subgroups in a community can be observed. Most of the previous works focused on designing metaheuristics for detecting hierarchical community structures, which may be computationally efficient, but cannot guarantee the community partition optimality. As a result, this paper proposes a mixed integer programming model for correctly detecting the hierarchical community structure in real social networks, which takes into account the number of levels and the limit of community size of each level while maximizing a quality measure for community partition. Our experimental results show that our model can find a reasonable hierarchical community structure, and the community with more nodes has a complicated hierarchical structure, so that the interaction between communities at different levels can be comprehended more clearly. In addition, our model can flexibly set the number of levels to have a fast adaption to different scale of networks while retaining a high community partition quality.