社群網路中群體演變的偵測及預測

Community Evolution Detection and Prediction in Online Social Network

陳昶亦(Chang-Yi Chen)

指導教授 ： 廖婉君

共同指導教授 ： 張正尚(Cheng-Shang Chang)

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2016年)

https://doi.org/10.6342/NTU201601504

摘要

在社群網路當中，有相同特性，或是連結較緊密的人，會形成社群網路當中的群體。有非常多的論文都在探討如何準確找出網路當中的群體。由於社群網路會隨時間演進而改變，網路當中的群體組成也是日新月異，如何去偵測群體的演變，已經成為了社群網路分析當中的新議題。有越來越多的論文在研究新的方法，去偵測或追蹤群體的演變。但我們想要更進一步，不僅要準確預測群體的演化，還要預測群體會如何演化。這是一個嶄新的研究，我們決定使用林維栩的演算法(Long-term Evolution Method)去偵測群體的演化，首先利用一個自己設計的人造網路，來檢驗他的演算法是否正確，以及分析他的演算法的結果。接下來我們將他的演算法用在Facebook和DBLP，同時套用我們自行定義的群體演化模式，去偵測這些資料的社群和演化，並且我們更進一步去討論Facebook的群體演變，發現群體的演變能夠反映到發生在Facebook的事件上。最後，我們利用Libsvm，從我們的資料中抽取足夠的features，去建立預測的模型。預測的結果顯示，我們所建立的模型有非常好的表現，而我們所抽取的feature也的確達到良好的效果。此外，我們還比較了SGCI演算法的預測結果，SGCI為一偵測群體演化的演算法，比較的結果顯示出我們所定義的演化模式，以及我們所用的演算法，比SGCI更加準確和有代表性。

關鍵字

社群網路分析 ； 群體 ； 群體演化 ； 偵測群體演化 ； 預測群體演化 ； 林維栩 ； SGCI

並列摘要

In a social network, a group in which people are similar to each other or have tight connections form a community. There are many works trying to precisely detect communities in a social network. As the social network change from time to time, the communities in the social network keep changing. Detecting community’s evolution become a new topic in social network analysis. More and more papers are about finding new algorithms to detect or track communities’ evolution. But, we want to go further in this topic. We want to not only detect communities’ evolution but predict the communities’ evolution. This is a brand new problem, and we decide to take advantage of Weiux Lin’s algorithm (Long-term Evolution Method) to detect the communities’ evolution. We first generate our synthetic data to verify and analysis the algorithm. We apply Weiux’s algorithm on DBLP and Facebook dataset, and use our own defined evolution types to analysis the community evolution. We deeply discuss the community evolution in Facebook dataset, and find that the communities’ evolution can match to the events happening in Facebook. Finally, we use Libsvm, select enough features from our detecting data, and build a prediction model. The prediction result shows that our model performs pretty well, and the feature we selected help a lot to our prediction model. Besides, we compare our result with SGCI algorithm, which is a community evolution detection algorithm. The comparison shows the evolution types we defined and the algorithm we used are more accurate and more representative than SGCI.

並列關鍵字

social network analysis ； community ； community evolution ； community evolution detection ； community evolution prediction ； Weiux Lin ； SGCI

參考文獻

[1] Girvan, Michelle, and Mark EJ Newman. "Community structure in social and biological networks." Proceedings of the national academy of sciences 99.12 (2002): 7821-7826.

[2] Fortunato, Santo. "Community detection in graphs." Physics reports 486.3 (2010): 75-174.

[4] Holland, Paul W., Kathryn Blackmond Laskey, and Samuel Leinhardt. "Stochastic blockmodels: First steps." Social networks 5.2 (1983): 109-137.

[5] Karrer, Brian, and Mark EJ Newman. "Stochastic blockmodels and community structure in networks." Physical Review E 83.1 (2011): 016107.

[11] Saganowski, S., Gliwa, B., Brodka, P., Zygmunt, A., Kazienko, P., & Koźlak, J. (2015). Predicting community evolution in social networks. Entropy, 17(5), 3053-3096.