利用社群網路中的互動資訊進行社群探勘

近年來有許多各種真實世界中的網路(networks)已逐漸成為資料探勘的對象，如網際網路(worldwide web)、社群網路(social network)、引用網路(citation network)、生物網路(biological network)等，而本論文著重於目前高度使用的社群網路中進行社群探勘(community detection)。社群探勘為社群網路分析(social network analysis)中相當熱門的研究議題，希望透過對整體社群網路結構的分析，將整個網路分成多個子群體，也稱為社群(community)。在目前大部分的社群探勘演算法中，大多為以網路結構為基礎的方法，意即從網路中或圖形中，以結構觀點來辨認次群體，找出有緊密連結的次團體如cliques, n-cliques, n-clans, n-plexes。而此類方法通常假設整個網路結構的資訊是已知的，也就是說所有在社群間的關係都清楚已知。除此之外，大部分的社群探勘演算法並不會區分不同型態的關係，而將所有關係看成單一種關係類型。若以在Facebook的情況為例，使用者可以與任何認識的人成為朋友。但在現實世界中，我們同時擁有多種身分關係是相當常見的。因此如何將Facebook上的所有朋友關係區分出不同的社群是本研究的主要研究議題。我們希望在不完整的社群網路資訊下，能夠利用社群網路上的社交互動資訊來進行社群探勘以彌補現有方法的缺陷。我們試著利用關聯規則探勘的概念來找出頻繁互動的集合，藉以作為初始的社群。接著找出最相近的兩個社群進行合併，直到社群數目達到所設定的數量為止。在本研究的實驗中，我們從Facebook中擷取10個使用者的分享文章及個人資訊，分別做為10個實驗資料集。我們採用了Community purity與Cluster purity作為評量我們的方法所找出的社群結果之評量指標，實驗結果顯示出我們所探勘出的社群分類與使用者先行所分類的結果有高度的相關性。

關鍵字

資料探勘；社群網路探勘；社群探勘

並列摘要

There has been much recent research about identifying communities in networks. Based on the online social network, which is getting more and more popular recently, we explore the community detection problem, i.e., how to identify the hidden sub-groups in the heterogeneous social network. Traditional research on community detection usually assumed that the structural information of the network is fully known, which is not feasible for many practical networks. Moreover, most previous algorithms for community detection did not differentiate multiple relations existing among objects or persons in a real world. In Facebook, two persons can be either friend or not friend. But in reality a friend relation may come from different reasons and belong to different social groups. Thus, how to differentiate different relations among users on Facebook is a key research issue in our work. In this paper, we propose a new approach utilizing the social interaction data, rather than structural information of the network, to address the community detection problem in Facebook. Specifically, we develop a method to find the multiple social groups of a Facebook user from his/her past interaction data with friends. The advantages of our approach include: i) it does not depend on the structural information, ii) it can differentiate different relations existing among friends, iii) it allows a friend belonging to multiple communities at the same time. In the experiment, we retrieve 10 Facebook user’s data as our datasets and evaluate the performance of each dataset. The results show that our method can identify the hidden social groups of users successfully from the interaction data in Facebook. Experimental results verify the feasibility and effectiveness of our approach.

並列關鍵字

Community detection ； Social network mining ； Data mining

參考文獻

[1]. Albert, R., H. Jeong, and A.-L. Barabasi, Diameter of the world-wide web. Nature, 401: p. 130-131, 1999.

[2]. Wasserman, S. and K. Faust, Social Network Analysis, Cambridge: Cambridge University Press, 1994.

[3]. Li, X.-L., et al., Searching for Rising Stars in Bibliography Networks, in DASFAA, 2009.

[4]. Palla, G., et al., Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435: p. 814-818, 2005.

[6]. Li, X.-L., C.-S. Foo, and S.-K. Ng, Discovering Protein Complexes in Dense Reliable Neighborhoods of Protein Interaction Networks, in CSB. 2007.

國際替代計量

利用社群網路中的互動資訊進行社群探勘

未授權

主題瀏覽