臺灣博碩士論文加值系統

多數存在於社群媒體服務中的使用者因個人興趣或不同時間扮演不同的角色而同時隸屬於多個網路社群，重疊社群發現(Overlapping Communities Discovery)的研究多數以複雜人際網路為研究對象，並採用社群網路分析(Social Network Analysis, SNA)相關技術來達到發現高品質重疊社群的目的。
SNA主要是透過人際網路中的種子節點(Seeds)為基礎，透過逐步地合併鄰居節點形成社群方式找出隱含的重疊社群。若僅選取高分支度節點作為Seeds容易忽略低分支度節點形成的緊密群體，本研究提出以區域叢集係數(Local Clustering Coefficient, LCC)高的節點作為Seeds來改善以往提取Seeds方法，並以鄰點的互動程度來擴展群體方式來進行重疊社群發現。在實驗中與高分支度提取Seeds方法、知名的重疊社群發現法Clique Percolation Method(CPM)及高分支度節點為Seeds的LCC分群法進行分群品質與執行效率的比較。

Most users of online social networks play different roles at different times due to the diversity of their interests. Overlapping community discovery studies the complexity involved in interpersonal social networks, using various techniques of Social Network Analysis (SNA).
SNA identifies seed nodes of social networks, based on which hidden overlapping communities could be found by gradually merging neighboring seeds to form large groups. In methods that select nodes of high degrees only, close-knit groups consisting of nodes of low degrees are often neglected. To overcome the problem, this study proposes to select nodes of high Local Clustering Coefficients (LCC) as seeds and then examine the relationship degrees between neighboring seeds to discover overlapping communities. The proposed method was compared with those adopting nodes of high degrees as seeds, as well as the famous Clique Percolation Method (CPM). The result showed effective improvement in grouping quality and graph efficiency.

表目錄 vi
圖目錄 vii
一、緒論 1
1.1 前言 1
1.2 研究動機 4
1.2.1蒐集Seeds的方式 4
1.2.2透過互動鄰點進行Seeds擴展 6
1.3 論文架構 7
二、文獻探討 8
2.1社群網路分析(Social Network Analysis) 8
2.2小世界理論(Small World) 9
2.3區域叢集係數(Local Clustering Coefficient) 11
2.4 Seeding 13
2.5 Seeds Expansion 13
2.6 Clique Percolation Method(CPM) 14
2.7 Modularity Q 15
2.8 Conductance 17
三、 研究方法 19
3.1 Filter Nodes 21
3.2 Seeding 22
3.3 Seeds Expansion 26
3.4 Nodes Expansion 31
四、 研究結果 33
4.1實驗數據的資訊 34
4 2 高分支度節點作為Seeds的問題 34
4.3計算LCC為1的節點數量與計算3-clique的效率比較 36
4.4鄰居節點互動程度的門檻值選擇比較表 37
4.5分群品質的比較 40
五、 結論 42
參考文獻 45

[1]D.J. Watts, S.H. Strogatz, ”Collective dynamics of small-world networks,” Nature, Vol. 393, No. 6684, pp. 440-442, 1998.
[2]M.E.J. Newman, M. Girvan, “Finding and evaluating community structure in networks,” Physical review, Vol. 69, pp. 56-68, 2004.
[3]許維麟, “基於MapReduce 實現社群網路重疊社群發現之研究,” 樹德科技大學資訊工程系碩士班學位論文, pp. 1-48, 2014.
[4]R. Andersen, K.J. Lang, “Communities from seed sets,” Proceedings of the 15th international conference on World Wide Web, pp. 223-232, 2006.
[5]Y. Li, K. He, D. Bindel, J.E. Hopcroft, “Uncovering the small community structure in large networks： A local spectral approach,” Proceedings of the 24th international conference on world wide web, pp. 658-668, 2015.
[6]D.F. Gleich, C. Seshadhri, “Vertex neighborhoods, low conductance cuts, and good seeds for local community methods,” Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 597-605, 2012.
[7]E.R. Wilson, D.S. Gosling, T.L. Graham, “A review of Facebook research in the social sciences,” Perspectives on Psychological Science, Vol. 7, No. 3, pp. 203-220, 2012.
[8]C.L. Freeman, “The development of social network analysis. Vancouver,” Empirical Press, 2004.
[9]H. Shen, “Detect overlapping and hierarchical community structure in networks,” Physica A: Statistical Mechanics and its Applications, Vol. 388, No. 8, pp. 1706-1712, 2009.
[10]K. Isabel M, J.M. Kleinberg, “Community membership identification from small seed sets,” Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM. pp. 1366-1375, 2014.
[11]L. Jure, “Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters,” Internet Mathematics. pp. 29-123, 2009.
[12]Y. Jaewon, J. Leskovec, “Defining and evaluating network communities based on ground-truth,” Knowledge and Information Systems. pp. 181-213, 2015.
[13]J. Xie, S. Kelley, B.K. Szymanski, “Overlapping Community Detection in Networks:the State of the Art and Comparative Study,” Knowledge and Information Systems, ACM Computing Surveys(csur), Vol. 45, No. 4. pp. 1-37, 2013.
[14]J.J. Whang, D.F. Gleich, I.S. Dhillon, “Overlapping community detection using seed set expansion,” Proceedings of the 22nd ACM international conference on Conference on information & knowledge management, ACM, pp. 2099-2108, 2013.
[15]李哲均, “以局部群聚係數進行種子集擴展的重疊社群發現之研究,” 第16屆離島資訊技術與應用研討會, 2017
[16]R.J. Mokken, “Cliques, clubs and clans,” Quality and Quantity, Vol. 13, pp. 161-173, 1979.
[17]X.S. Zhang, “Modularity optimization in community detection of complex networks,” EPL (Europhysics Letters), Vol. 87, No. 3, pp. 38002, 2009.
[18]W.A. Wolfe, “Social network analysis: Methods and applications,” American Ethnologist, Vol. 24, No. 1, pp. 219-220, 1997.
[19]M.E.J. Newman, “Modularity and community structure in networks,” Proceedings of the national academy of sciences, Vol.103, No 23, pp. 8577-8582, 2006.
[20]M.K.K. Chen, K.S. Boleslaw, “Extension of modularity density for overlapping community structure,” Proceedings of 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 856-863, 2014.
[21]R. Kannan, S. Vempala, A. Vetta, “On clusterings: Good, bad and spectral,” Journal of the ACM (JACM), Vol.51, pp. 497-515, 2004.
[22]J. Han, J. Pei, M. Kamber, “Data mining: concepts and techniques,” Elsevier, 2011.