進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-1908201516254800
論文名稱(中文) 基於特徵值之社群網路特性化與分類
論文名稱(英文) Feature-based Characterization and Clustering of Social Networks
校院名稱 成功大學
系所名稱(中) 電腦與通信工程研究所
系所名稱(英) Institute of Computer & Communication
學年度 103
學期 2
出版年 104
研究生(中文) 林致聖
研究生(英文) Chih-Sheng 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 DGA-based 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 K-means 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 DGA-based 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. 2201-2217, 2012.
[2] Belnet History, https://www.belnet.be/en/about-us/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.164-176, 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. 1019-1031, 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, 26-29, 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 Protocol-and Structure-Independent Botnet Detection," USENIX Security Symposium, Vol. 5, No. 2, pp. 139-154, 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. 255-259, 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 566-575, 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. 267-278, 2006.
[13] J. J. McGregor, "Backtrack search algorithms and the maximal common subgraph problem." Software: Practice and Experience, pp. 23-34, 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. Eliassi-Rad, and C. Faloutsos, "Netsimile: A scalable approach to size-independent 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. 404-409, 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 NP-Completeness, " WH. Freeman and Co., 1979.
[27] N. B. Silva, I. R. Tsang, G. D. Cavalcanti, and I. J. Tsang, "A graph-based friend recommendation system using Genetic Algorithm," Evolutionary Computation (CEC), 2010 IEEE Congress on, pp.1,7, 18-23, July 2010.
[28] P. Papadimitriou, A. Dasdan, H. Garcia-Molina, "Web graph similarity for anomaly detection," Journal of Internet Services and Applications, pp. 19-30, 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. 112-115, 2002.
[31] T. S. Wang, W. T. Cheng, and H. T. Lin, "Research and implementation of DGA-based 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.3977-3980, 25-30, March 2012.
[33] T. Yingfei, "Centrality characteristics analysis of urban rail network," Intelligent Rail Transportation (ICIRT), 2013 IEEE International Conference on, pp.285-290, 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.31-40, 3-5, 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.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2020-08-31起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw