隨著網路技術的進步和手持裝置的發展與流行，人們的社交行為漸漸由現實轉向虛擬，造就了線上社群網路平台的快速發展，當然此一轉變也引起了許多研究者的關注。多數針對社群網路的研究主要著重的問題在於對單一網路內部的研究，如一個社群網路中誰的朋友多、誰的影響力比較大、誰與誰之間的連結對整個網路影響最大等等問題。而本論文的重點則是較少被討論到的部份：網路與網路之間的關聯。本研究根據每個網路的結構給予一特徵值向量將網路特性化，利用此特徵值向量可再進一步對不同的社群網路類型進行分群。因為所有的特徵值皆是單純藉由網路拓撲即可得到，因此並不需要去處理節點對映(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.

[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.