最近幾年，社群網路成為大家日常生活中很重要的活動之一，人們利用他分享生活中的事情，在上面和朋友們互動。因此，也產生了很多相關於社群網路的研究，像是作朋友的推薦，或是在上面找出有影響力的人，進而藉由他來擴散資訊。然而，這些研究幾乎都是著重在單一一個社群網路，但我們知道使用者往往會在不同的網站創建帳號，可能是為了要使用不同的服務，或是因為社群網站的興衰所造成的結果。若我們能夠將同一個人在多個網站的帳號串連起來，我們便可以發展出後續許多的應用。在之前的研究中有提到，約有15%的網路搜尋關鍵字包含了人名，人們往往會查詢他們感興趣的對象，也因此，我們可以滿足某些人對於人物蒐尋的需求。另外，我們涵蓋了更多使用者的資訊，我們可以建立一個整合的環境，讓人們可以從上面得到朋友們最新的資訊，也可以將過去著重在單一社群的研究，重新運用在一個更全面資訊的網路中。
在這篇論文，我們的問題在於試著將同一使用者的不同帳號串連起來。我們利用每個人社群的資訊來產生摘要，來代表每個使用者。根據社會學家同質性相交的理論，我們提出了兩階段的分群演算法，先找出朋友群中鍵結性最強的群，再將其他人依照結構以及特徵分配到適合的群中。最後對每一群產生出摘要，並比較兩人摘要的分佈計算出分數。我們在臉書以及無名小站進行實驗，並與其他兩個方法作比較，而我們的結果顯示我們的表現相較於其他兩個來得更好。另外，我們也針對欄位填入的狀況以及演算法中的參數作了一些分析。

In recent years, social networking has been one of the major activities in people’s life. Therefore, lots of researches pay attention on this area, such as friend recommendation [1], user influence estimation [3], and structure analysis. However, they mainly focused on single network due to the lack of links from one social network to others. As we know, users may create multiple accounts on various online social networks (OSNs) for different services, or network migration, but it is hard to link the same person if he does not provide his network information. However, if we can detect the same nature person on different OSNs, we can enable many applications. First, we can fulfill some users’ needs, since people may search someone they interested in, and it shows that people search is necessary for some people in [6]. Also, since we can cover more information about users, we can aggregate all their information in different OSNs, and can keep up-to-date information with their friends from an integrated environment. Moreover, we can apply previous works on a more global social graph.
In this paper, we focus on the problem of linking users across OSNs. We try to use social summaries to represent each user. According to homophily [18], we propose a two-phase clustering algorithm: ClusterSeed selecting to find strongly connected groups as seeds, and Clustering to assign other nodes to the clusters based on structure and attributes. Finally, we generate summaries for each cluster and attribute of the user, and compare the distributions of two users. We conduct an experiment on Facebook and Wretch, and compared with other two methods. Our result shows that we can achieve better performance than other methods. Also, we analyze the effect of missing values and parameter evaluation.

誌謝 i
中文摘要 iii
ABSTRACT v
CONTENTS vii
LIST OF FIGURES ix
LIST OF TABLES xi
Chapter 1 Introduction 1
Chapter 2 Notation and problem formulation 5
Chapter 3 Intuitive methods 7
3.1 Naive idea 7
3.2 Advanced idea 9
Chapter 4 Proposed method 13
4.1 Social summary 14
4.1.1 Cluster 14
4.1.2 Summary 17
4.1.3 Social attributes and cluster attributes 17
4.2 Match users 18
4.3 Flowchart 18
Chapter 5 Experiments 21
5.1 Datasets 22
5.2 Evaluation of matching users 24
5.3 Analysis for missing values 27
5.4 Parameter evaluation 30
5.5 Case study 31
Chapter 6 Related work 33
6.1 Search engine based 33
6.2 Based on same name 33
6.3 Profile or post based 34
6.4 Combine with social information 35
Chapter 7 Conclusion 37
REFERENCE 39

[1]Y. Dong, J. Tang, S. Wu, J.Tian, N.V. Vhawla, J. Rao, and H. Cao. Link prediction and recommendation across heterogeneous social networks. In proceedings of the 12th IEEE International Conference on Data Mining, pages 181-190, 2012.
[2]M. Newman. Communities, modules and large-scale structure in networks. Nature Physics, 8(1), 2011.
[3]J. Weng, E.-P. Lim, J. Jiang, and Q. He. Twitterrank: finding topic-sensitive influential twitters. In proceedings of WSDM, 2010.
[4]S. Perez. Who Uses Social Networks and What Are They Like? (Part 1). http://www.readwriteweb.com/archives/who_uses_social_networks_and_what_are_they_like_part_1.php
[5]M. Motoyama and G. Varghese. I seek you: searching and matching individuals in social networks. In Proceedings of the 11th Int’l Wksp. On Web Information and Data Management, WIDM’09, pages 67-75, New York, NY, USA, 2009, ACM
[6]W. Weerkamp, K. Balog, M. de Rijke, R. Berendsen, B. Kovachev, and E. Meij. People searching for people: Analysis of a people search engine log. In SIGIR’11: 34th international ACM SIGIR conference on Research and development in information retrieval, 2011.
[7]Y. Zhou, H. Cheng, and J.X. Yu. Graph clustering based on structural/attribute similarities. VLDM, 2(1): 718-729, 2009.
[8]C. Lee, F. Reid, A. McDaid, and N. Hurley. Detecting highly overlapping community structure by greedy clique expansion. KDD SNA 2010, 2010.
[9]Zafarani, R., and Liu, H. 2009 Connecting corresponding identities across communutues. In Proc. ICWSM, 354-357.
[10]J. Liu, F. Zhang, X. Song, Y.I. Song, C.Y. Lin, and H.W. Hon. What’s in a name? An unsupervised approach to link users across communities. In proceedings of WSDM, 2013.
[11]Motoyama, M., Varghese, G. I seek you – Searching and matching individuals in social networks. WIDM’09: Proceeding of the eleventh international workshop on Web information and data management.
[12]J. Vosecky, D. Hong, and V. Shen. User identification across multiple social networks. In proceedings of NDT, 2009.
[13]E. Raad, R. Chbeir, and A. Dipanda. User profile matching in social networks. 13th international conference on Network-Based Information Systems (NBiS), 2010.
[14]T. Iofciu, P. Fankhauser, F. Abel, and K. Bischoff. Identifying users across social tagging systems. In proceedings of ICWSM, 2011.
[15]A. Narayanan and V. Shmatikov. De-anonymizing social networks. In proceedings of S&P, 2009.
[16]S. Labitzke, I. Taranu, and H. Hartenstein. What your friends tell others about you: Low cost linkability of social network profiles. In proceedings of SNAKDD, 2011.
[17]S. Bartunov, A. Korshunov, S.-T. Park, W. Ryu, and H. Lee. Joint link-attribute user identity resolution in online social networks. In proceedings of SNAKDD, 2012.
[18]M. McPherson, L. Smith-Lovin, and J. Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27:415-444, 2001.