Research On Structure Based Cross Social Network User Identification Techniques

With the advent of Internet,social networks have been enormously popular in our lives.Users may enjoy all kinds of services through social networks.For example,Douban provides book,movie and music sharing services,Zhihu provides question an-swering services and Weibo provides self-media services.Rather than staying in a single social network,people prefer to join in multiple networks for comprehensive services.Consequently,user identification across social networks has attracted great attention.This issue may integrate user resources scattered among social networks,which has significant promotion in user recommendation,advertisement injecting and group recommendation.Traditional structure based cross social network user identification methods focus on proposing effective similarity metrics.Considering state-of-the-art similarity metrics,two shortages are as follows:(1)Most similarity metrics are based on local structure or global structure,and it is hard to make a balance between accuracy and time complexity;(2)Most similarity metrics are heuristic and only applicable to well designed networks,which means the lack of theoretical guarantee and applicability to different types of so-cial networks.Therefore,we present four methods to improve the performance of cross network user identification in this paper:(1)We propose a SimRank based cross network user identification method.Firstly,a SimRank based similarity metric is proposed to measure the similarity between users across networks,which successfully balances the accuracy and time complexity through parameter adjustment.Secondly,an iterative matching algorithm is proposed,including two steps,similarity computation and matching strategy.In similarity computation,we focus on computation complexity optimization and propose the incremental similarity computation method.In matching strategy,we focus on the candidate filtering condition.Finally,we conduct experiments on real-world datasets to demonstrate the advantages of our SimRank based cross network user identification method.(2)We propose a Bi-verification based cross network user identification method.Firstly,three different similarity metrics CPS,CPS+ and CCS are proposed.Exploiting aligned network model,we prove theoretically that the users with higher CPS or CPS+are the same user and the users with lower CCS are not the same user,which guarantees the applicability to different types of social networks.Secondly,using CPS+ and CCS,we propose an iterative Bi-verification based cross network user identification method.In each iteration,CPS+ is used for identification and CCS is used for verification.Then,we also discuss clearly the convergence and termination condition of our algorithm.Finally,we conduct experiments on real-world datasets and demonstrate that Bi-verification based method has higher precision and recall than our SimRank based method.(3)We propose a maximum common subgraph based cross network user identi-fication method.Firstly,we attempt to leverage maximum common subgraph ?-MCS to solve the problem of cross network user identification and compute the value of a self-adaptively with the combination of aligned network model.Compared to tradi-tional heuristic parameter assignment methods,our method can efficiently distinguish the matched and unmatched users in different networks.Secondly,we present a max-imum common subgraph based cross network user identification method with two key steps.In the first step,we select the candidates in networks separately.And in the sec-ond step,only the candidates are used for identification in the target network.Compared to other method,our method has lower computation complexity and wild applicability by self-adaptive parameters.Finally,we conduct experiments on real-world datasets and demonstrate that our maximum common subgraph based method has higher efficiency on the basis of precision and recall.(4)We propose a generation probability based cross network user identification method.Firstly,exploiting aligned network model,we propose the notion of generation probability of social networks and make an assumption that the matching users with the maximum generation probability are correctly identified.Secondly,based on this assump-tion,an iterative generation probability based cross network user identification method is proposed.In each iteration,only the candidates that can improve the generation probabil-ity are identified to improve the efficiency and accuracy.Finally,we conduct experiments on real-world datasets and demonstrate that our generation probability based method has higher precision and recall than most methods,but has higher computation complexity than our maximum common subgraph based method.