
系統識別號 
U00261908201516254800 
論文名稱(中文) 
基於特徵值之社群網路特性化與分類 
論文名稱(英文) 
Featurebased Characterization and Clustering of Social Networks 
校院名稱 
成功大學 
系所名稱(中) 
電腦與通信工程研究所 
系所名稱(英) 
Institute of Computer & Communication 
學年度 
103 
學期 
2 
出版年 
104 
研究生(中文) 
林致聖 
研究生(英文) 
ChihSheng Lin 
學號 
Q36024052 
學位類別 
碩士 
語文別 
英文 
論文頁數 
42頁 
口試委員 
指導教授林輝堂 口試委員楊竹星 口試委員陳嘉玫 口試委員王平

中文關鍵字 
社群網路
中間度指標
分群
特性化

英文關鍵字 
Social Network Analysis
Centrality Measures
Classification
Characterization

學科別分類 

中文摘要 
隨著網路技術的進步和手持裝置的發展與流行，人們的社交行為漸漸由現實轉向虛擬，造就了線上社群網路平台的快速發展，當然此一轉變也引起了許多研究者的關注。多數針對社群網路的研究主要著重的問題在於對單一網路內部的研究，如一個社群網路中誰的朋友多、誰的影響力比較大、誰與誰之間的連結對整個網路影響最大等等問題。而本論文的重點則是較少被討論到的部份：網路與網路之間的關聯。本研究根據每個網路的結構給予一特徵值向量將網路特性化，利用此特徵值向量可再進一步對不同的社群網路類型進行分群。因為所有的特徵值皆是單純藉由網路拓撲即可得到，因此並不需要去處理節點對映(Node correspondence)的問題。尤其近年來用戶對於隱私權的重視，可運用的社群網路資料完整度不一定足以使用節點對映的方式。經由實驗發現此網路特性化的方式與分群有不錯的效果，將來可以被運用來協助廣告發送系統、朋友推薦系統、殭屍網路偵測系統等方面。另外實驗也顯示此一特性化的方式可發現網路拓撲的變動，可以用來偵測網路的重大變化或不正常行為。

英文摘要 
How do we distinguish one type of social networks from another if topologies are the only available information? In this thesis, we proposed an approach to characterize social networks with techniques widely used in the social network analysis. These features are computed only based on the given topologies. With the aid of proposed characteristics, classification can then be performed between different types of networks. Our experiments show that a high accuracy can be achieved based on the proposed method. The approach can be used for advertisement distribution system, recommendation systems, and DGAbased botnet detection systems. Experiment also shows that the proposed system can be applied to anomaly detection system.

論文目次 
摘要 i
Abstract ii
Table of Contents iii
List of Tables iv
List of Figures v
Chapter 1 Introduction 1
1.1 Overview 1
1.1.1 Definition and Representation of a Network 3
1.1.2 Centrality Measures 4
1.2 Motivation 9
1.3 Objective 10
1.4 Outline 10
Chapter 2 Related Work and Literature Review 11
2.1 Graph Matching Problem 11
2.2 Statistical Classification of Social Networks 15
Chapter 3 System Architecture and Design 16
3.1 System Overview 16
3.2 Feature Selection 17
3.3 Weight Setting 18
3.4 Clustering 20
3.4.1 Kmeans Algorithm 20
Chapter 4 Experiment Results 23
4.1 Data Sets 23
4.2 Data Preprocessing 24
4.3 Results 26
4.3.1 Classification Between Social Networks about Politics 26
4.3.2 Classification Between Different Social Networks 29
4.3.3 Detecting the Change of Network Patterns 30
4.3.4 DGAbased Botnet Detection 35
Chapter 5 Conclusion and Future work 38
Bibliography 39

參考文獻 
[1] A. Passarella, R. I. Dunbar, M. Conti,and F. Pezzoni, "Ego network models for future internet social networking environments," Computer Communications, Vol. 35, No. 18, pp. 22012217, 2012.
[2] Belnet History, https://www.belnet.be/en/aboutus/history.
[3] C. Biemann, "Chinese whispers: an efficient graph clustering algorithm and its application to natural language processing problems," Proceedings of the first workshop on graph based methods for natural language processing, 2006.
[4] D. Fay, H. Haddadi, A. Thomason, A. W. Moore, R. Mortier, A. Jamakovic, S. Uhlig, and M. Rio, "Weighted Spectral Distribution for Internet Topology Analysis: Theory and Applications," Networking, IEEE/ACM Transactions on , vol.18, no.1, pp.164176, Feb. 2010.
[5] D. Liben‐Nowell and J. Kleinberg, "The link‐prediction problem for social networks,” Journal of the American society for information science and technology, pp. 10191031, 2007.
[6] E. Serin and S. Balcisoy, "Entropy Based Sensitivity Analysis and Visualization of Social Networks," Advances in Social Networks Analysis and Mining (ASONAM), 2012 IEEE/ACM International Conference on , vol., no., pp.1099,1104, 2629, Aug. 2012.
[7] Foreseeing Innovative New Digiservices (FIND), http://www.find.org.tw/find/home.aspx?page=many&id=390
[8] G. Gu, R. Perdisci, J. Zhang, and W. Lee, "BotMiner: Clustering Analysis of Network Traffic for Protocoland StructureIndependent Botnet Detection," USENIX Security Symposium, Vol. 5, No. 2, pp. 139154, 2008.
[9] G. Guofei, J. Zhang, and W. Lee, "BotSniffer: Detecting botnet command and control channels in network traffic," Network and Distributed System Security Symposium, 2008.
[10] H. Bunke and K. Shearer, "A graph distance metric based on the maximal common subgraph" Pattern recognition letters, pp. 255259, 1998.
[11] H. Jiang, H. Wang, P. S. Yu, and S. Zhou, "Gstring: A novel approach for efficient search in graph databases," Proceedings of the International Conference on Data Engineering, pp 566575, 2007.
[12] H. Yu, M. Kaminsky, P. B. Gibbons, A. Flaxman, "Sybilguard: defending against sybil attacks via social networks," ACM SIGCOMM Computer Communication Review, Vol. 36, No. 4, pp. 267278, 2006.
[13] J. J. McGregor, "Backtrack search algorithms and the maximal common subgraph problem." Software: Practice and Experience, pp. 2334, 1982.
[14] J. Leskovec and J. J. Mcauley, "Learning to discover social circles in ego networks," Advances in neural information processing systems, 2012.
[15] J. MacQueen, "Some methods for classification and analysis of multivariate observations," Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, Vol. 1, No. 14, 1967.
[16] K. Aoyama, "Advertisement distribution system," U.S. Patent Application 10/952,776, 2005.
[17] L. A. Adamic and N. Glance, "The political blogosphere and the 2004 US election: divided they blog," Proceedings of the 3rd international workshop on Link discovery, ACM, 2005.
[18] L. Akoglu, H. Tong, and D. Koutra, "Graph based anomaly detection and Description: a survey," Data Mining and Knowledge Discovery, 2014.
[19] M. Bastian, S. Heymann, and M. Jacomy, "Gephi: an open source software for exploring and manipulating networks," International AAAI Conference on Weblogs and Social Media, 2009.
[20] M. Berlingerio, D. Koutra, T. EliassiRad, and C. Faloutsos, "Netsimile: A scalable approach to sizeindependent network similarity," CoRR, Vol. abs/1209.2684, 2012.
[21] M. E. J. Newman, "Community detection and graph partitioning," Europhysics Letters, 2013.
[22] M. E. J. Newman, "Finding community structure in networks using the eigenvectors of matrices," Physical review E, 2006.
[23] M. E. J. Newman, "Mathematics of networks," The New Palgrave Encyclopedia of Economics, Palgrave Macmillan, Basingstoke, 2008.
[24] M. E. J. Newman, "The structure of scientific collaboration networks," Proceedings of the National Academy of Sciences, pp. 404409, 2001.
[25] M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten, "The WEKA Data Mining Software: An Update," SIGKDD Explorations, Volume 11, Issue 1, 2009.
[26] M. R. Gary and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NPCompleteness, " WH. Freeman and Co., 1979.
[27] N. B. Silva, I. R. Tsang, G. D. Cavalcanti, and I. J. Tsang, "A graphbased friend recommendation system using Genetic Algorithm," Evolutionary Computation (CEC), 2010 IEEE Congress on, pp.1,7, 1823, July 2010.
[28] P. Papadimitriou, A. Dasdan, H. GarciaMolina, "Web graph similarity for anomaly detection," Journal of Internet Services and Applications, pp. 1930, 2010.
[29] R. Balasubramanyan, F. Lin, and W. W. Cohen, "Node clustering in graphs: An empirical study," NIPS Workshop on Networks Across Disciplines in Theory and Applications, 2010.
[30] R. Giugno and D. Shasha, "Graphgrep: A fast and universal method for querying graphs," Proceedings of the International Conference on Pattern Recognition, Vol.2, pp. 112115, 2002.
[31] T. S. Wang, W. T. Cheng, and H. T. Lin, "Research and implementation of DGAbased Botnet Detection," National Computer Symposium, Taiwan, 2013.
[32] T. Wang and H. Krim, "Statistical classification of social networks," Acoustics, Speech and Signal Processing (ICASSP), 2012 IEEE International Conference on , pp.39773980, 2530, March 2012.
[33] T. Yingfei, "Centrality characteristics analysis of urban rail network," Intelligent Rail Transportation (ICIRT), 2013 IEEE International Conference on, pp.285290, 2013.
[34] V. Arnaboldi, M. Conti, A. Passarella, F. Pezzoni, "Analysis of Ego Network Structure in Online Social Networks," Privacy, Security, Risk and Trust (PASSAT), 2012 International Conference on and 2012 International Confernece on Social Computing (SocialCom), pp.3140, 35, Sept. 2012.
[35] V. E. Krebs, http://www.orgnet.com/.
[36] Wash Univ. BIO5488 lecture, 2004.
[37] X. Huang, J. Lai, and S. F. Jennings, "Maximum common subgraph: some upper bound and lower bound results," BMC bioinformatics, 2006.
[38] Y. Matsukawa, "Advertisement distribution system." U.S. Patent Application 09/851,518, 2001.

論文全文使用權限 
同意授權校內瀏覽/列印電子全文服務，於20200831起公開。 


