臺灣博碩士論文加值系統

隨著資訊時代蓬勃的發展，改變了人與人互動的行為模式，人們於網路平台的互動越來越普及，所以在網路上出現許多人際網路的社群結構，而社群網路分析技術的應用已經可以廣泛的運用於各大領域上，如金融、行銷、商業及犯罪，因此社群網路分析慢慢的受到重視。
社群之發現往往是社群網路分析的領域上重要的研究項目之一，而其目的是找出隱藏在大型網路結構中符合高緊密度的重疊社群之結構。其方法常見的方法藉由移除Betweenness Centrality最高的邊來實做分割式分群的GN演算法或以合併相鄰Clique來達到社群成長的CPM演算法，而種子集擴展(Expansion)為目前常見的分群方式之一，透過演算法在大型網路結構中蒐集有意義的節點做為種子集，以種子集內的節點為中心向四周成長合併周邊節點達到發現社群的效果。
本研究以效能做為考量，透過80/20法則的精神結合高分支度理論提出兩種建立種子集的方式，接著依計算節點局部群聚係數(Local Clustering coefficient, LCC)以先量測其緊密程度再決定是否擴展的方式進行重疊社群之發現，而研究結果證實效能上優於CPM(Clique Percolation Method)，且可以有效的提升分群品質。

一、緒論 1
1.1 前言 1
1.2 研究動機 4
1.3 文章架構 5
二、文獻探討 6
2.1 80/20 Rule 6
2.2 Maximal Cliques 7
2.3 Clustering Coefficient 8
2.4 Clique Percolation Method 9
2.5 Seedset Expansion 9
2.5.1 Seeding 10
2.5.2 Expansion 11
2.6 Modularity Q 12
三、研究方法 14
3.1 Data Pre-Processing 15
3.2 Seeding Phase 16
3.2.1 Seeding I 16
3.2.2 Seeding II 17
3.3 Expansion Phase 18
3.3.1 Expansion Level-1 19
3.3.2 Expansion Level-2 20
3.4 研究流程 21
四、實驗結果 30
4.1 實驗環境 30
4.2 實驗數據 30
4.3 實驗結果 31
4.4 實驗效率 37
五、結論 40
參考文獻 43

[1]S Milgram, "The small world problem," 1967.
[2]D. Watts and S. Strogatz,"Collective dynamics of small-world networks," Nature, vol. 393, no. 6684, pp. 440–442, Jun. 1998.
[3]S. Wasserman, "Social network analysis:Methods and applications," Cambridge university press, 1994.
[4]L. Garton, C. Haythornthwaite, B. Wellman, "Studying online social networks," Journal of Computer-Mediated Communication, vol 3, no. 1, 1997.
[5]L. Freeman, "Centrality in social networks conceptual clarification," Social Networks, pp. 215–239, 1979.
[6]J. Scott, "Social network analysis," Sage, 2012.
[7]U. Brandes, "A faster algorithm for betweenness centrality," The Journal of Mathematical Sociology, vol. 25, no. 2, pp. 163-177, 2001.
[8]G, Palla, I. Derenyi, and T. Vicsek, "The Critical Point of k-Clique Percolation in the Erdos–Renyi Graph," Journal of Statistical Physic, vol. 128, pp. 219–227, 2007.
[9]M. Newman, "Fast algorithm for detecting community structure in networks," Physical Review E, vol. 69, no. 6, 2004.
[10]J. Kleinberg, "Authoritative sources in a hyperlinked environment," Journal of the ACM, vol. 46, no. 5, pp. 604-632, 1999.
[11]M. Toyoda and M. Kitsuregawa, "Creating a web community chart for navigating related communities," Proceedings of the 12th ACM conference on Hypertext and Hypermedia. ACM, 2001.
[12]K. PEARSON, "The Problem of the Random Walk," Nature, vol. 72, no. 1867, pp. 342-342, 1905.
[13]M. Newman, "Modularity and community structure in networks," Proceedings of the National Academy of Sciences, Vol. 103, No. 23, pp. 8577-8582, 2006.
[14]A. Kemper, "Valuation of network effects in software markets: a complex networks approach," Springer, 2009.
[15]V. Furlan, "Vilfredo Pareto, Manuale di Economia Politica," Jahrbücher für Nationalökonomie und Statistik, vol. 91, no. 1, 1908.
[16]J. C. Turner, "Towards a cognitive redefinition of thesocial group," Social identity and intergroup, pp. 15-40, 1982.
[17]蘇怡仁, 陳岳群, 許維麟, 溫建成, "Based on overlapping topic group to develop automatic documeng classification system," Proceedings of 2012 symposium on digital life technologies, 2012.
[18]M. Garey, D. Johson, "computers and intractability a guide to the theory of np-completeness," WH Freeman & Co., 1979.
[19]C. Bron, J. Kerbosch "Finding all clique of undirected graph," Communications of the ACM, vol. 16, No.9, pp.575-577, 1973.
[20]M. Schmidt, N. Samatova, K. Thomas and B. Park, "A scalable, parallel algorithm for maximal clique enumeration," Journal of Parallel and Distributed Computing, vol. 69, no. 4, pp. 417-428, 2009.
[21]E. Tomita, A. Tanaka and H. Takahashi, "The worst-case time complexity for generating all maximal cliques and computational experiments," Theoretical Computer Science, vol. 363, no. 1, pp. 28-42, 2006.
[22]K. Makino, T. Uno, "New algorithms for enumerating all maximal cliques," SWAT, vol. 3111, 2004.
[23]N. Modani and K. Dey. "Large maximal cliques enumeration in sparse graphs," CIKM, pp. 1377-1378, 2008.
[24]J. Kleinberg, "Authoritative sources in a hyperlinked environment," Journal of the ACM, vol. 46, no. 5, pp. 604-632, 1999.
[25]R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, "Trawling the Web for emerging cyber-communities," Computer Networks, Vol. 31, pp. 11-16, 1999.
[26]J. Whang, D. Gleich, and I. Dhillon, "Overlapping community detection using seed set expansion," Proc. of the 22nd ACM international conference on information & knowledge management. ACM, 2013.
[27]R. Andersen and K. Lang. "Communities from seed sets," In Proceedings of the 15th international conference on World Wide Web, pp. 223-232, 2006.
[28]I. Kloumann and J. Kleinberg. "Community membership identification from small seed sets," Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 2014.
[29]Y. Li, K. He, D. Bindel, and J. Hopcroft. "Uncovering the small community structure in large networks: A local spectral approach," In WWW, pp. 658–668, 2015.
[30]J. Whang, D. Gleich, & I. Dhillon, "Overlapping community detection using neighborhood-inflated seed expansion," IEEE Transactions on Knowledge and Data Engineering, vol. 28, no. 5, pp.1272–1284, 2016.
[31]Z. Jiang, J. Liu and S. Wang, "Traveling salesman problems with PageRank Distance on complex networks reveal community structure," Physica A: Statistical Mechanics and its Applications, vol. 463, pp. 293-302, 2016.
[32]H. Avron, L. Horesh, "Community detection using time-dependent personalized pagerank," In Proceedings of The 32nd International Conference on Machine Learning, pp. 1795-1803, 2015.
[33]R. Andersen, F. Chung, and K. Lang. "Local graph partitioning using pagerank vectors," Foundations of Computer Science. 2006. FOCS’06. 47th Annual IEEE Symposium, pp 475-486, 2006.
[34]J. Yang and J. Leskovec, "Defining and evaluating network communities based on ground-truth," In ICDM, pp. 10-13, 2012.
[35]K. Kloster and D. Gleich. "Heat kernel based community detection," In KDD. ACM, 2014.
[36]I. Dhillon, Y. Guan and B. Kulis, "Weighted Graph Cuts without Eigenvectors A Multilevel Approach," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 11, pp. 1944-1957, 2007.
[37]B. Schölkopf, A. Smola and K. Müller, "Nonlinear Component Analysis as a Kernel Eigenvalue Problem," Neural Computation, vol. 10, no. 5, pp. 1299-1319, 1998.
[38]V. Zlatić, A. Gabrielli and G. Caldarelli, "Topologically biased random walk and community finding in networks," Physical Review E, vol. 82, no. 6, 2010.
[39]P. Pons and M. Latapy, "Computing Communities in Large Networks Using Random Walks," Journal of Graph Algorithms and Applications, vol. 10, no. 2, pp. 191-218, 2006.
[40]M. Meila and J. Shi. "A random walks view of spectral segmentation," 2001.
[41]A. Clauset, C. Shalizi, and M. Newman, "Power-law distributions in empirical data," SIAM review, vol. 51, no. 4, pp. 661-703, 2009.
[42]Stanford Network Analysis Project. "http://snap.stanford.edu"
[43]Networkrepository "http://networkrepository.com"
[44]igraph "http://igraph.org"