一種社會網絡用戶身份特征識別方法

胡開先梁 英許洪波畢曉迪左 遙

1(中國科學院網絡數據科學與技術重點實驗室(中國科學院計算技術研究所) 北京 100190)2(中國科學院大學 北京 100049)(kaixian.hu@gmail.com)

?

一種社會網絡用戶身份特征識別方法

胡開先1,2梁 英1許洪波1畢曉迪1,2左 遙1,2

1(中國科學院網絡數據科學與技術重點實驗室(中國科學院計算技術研究所) 北京 100190)2(中國科學院大學 北京 100049)(kaixian.hu@gmail.com)

社會網絡是現代信息社會重要的組成部分.社會網絡用戶身份不透明、不可見的特性帶來一系列社會安全問題.提出了一種社會網絡身份特征識別方法，分別利用基于位置的社會網絡和社交關系進行社會網絡用戶的身份特征識別，融合2種識別結果推測社會網絡用戶真實身份.提出了一種基于位置的社會網絡用戶身份識別方法，通過計算中文分詞和二元組分詞的基本匹配權重和完全匹配權重得到近似度權重，并用它衡量實體為用戶所屬實體的可能性；通過實體名稱聚合算法，對近似度權重計算結果進行優化.根據好友之間傾向于擁有相似的身份特征和相同的興趣愛好的觀察，提出了一種基于社交關系的多數投票的身份識別方法，對社交關系中的用戶身份特征進行統計，推測當前用戶的地址信息、實體信息和用戶興趣.基于微博數據，進行了樣本數為1 000名用戶和10 000名用戶的2組實驗，涵蓋了超過250萬條社交關系.實驗結果表明，提出的虛實映射方法有很高的準確率和覆蓋率，與現有方法相比，該方法著眼于推測個人用戶細粒度的身份特征，具有較高的實際應用價值.

身份識別；用戶身份特征；基于位置的社會網絡；社交關系；去匿名化

社會網絡在人們生活中扮演著重要的角色，微博、微信、人人網等社會網絡已經成為人們獲取信息、展示自我和營銷推廣的重要途徑.由于社會網絡的匿名性，人們可以方便地以虛擬身份自由發表觀點和意見，每個人都是信息的生產者和消費者.信息的快速發布和傳播，使社會網絡成為一把雙刃劍，它既是應對突發事件的利器，也是謠言傳播的溫床.例如，新浪微博博主“秦火火”虛構的動車事故等謠言、微博博主“染香”捏造的“名人被去世”等謠言，這些造謠事件，嚴重擾亂網絡秩序、侵害他人名譽、敗壞社會風氣、危害社會安全.社會網絡的虛擬性和匿名性使之不易追蹤網絡虛假消息的發布者、不易定位危害國家治安言論的發布者、不易在網絡中追查違法犯罪行為等.因此，開展識別用戶社會網絡虛擬ID對應的真實身份的研究，對于維護網絡治安具有積極的社會意義.

目前，針對社會網絡中用戶身份識別的研究主要是通過社會網絡用戶公開的信息推測用戶群體的信息或傾向.通過挖掘用戶特征推測個體用戶所屬群體，將用戶按興趣愛好分類，可以為用戶提供個性化的產品營銷和廣告投遞等服務；將用戶按社交關系分類，可以應用于用戶群推薦和用戶群檢測等服務.通過挖掘用戶地理位置，可以推測用戶頻繁出現的地區和事件發生體.然而，上述方法主要是挖掘用戶的特征屬性對用戶群體進行分類，而不是面向用戶個體的識別.

本文提出了一種基于位置和社交關系的社會網絡身份特征識別方法.通過用戶在社會網絡上發布的帶位置信息的博文，挖掘分析用戶當前所屬的學校和工作單位；同時利用用戶自身及其社交圈的信息，挖掘分析該用戶的地址信息、學校、工作單位和興趣；最后融合上述2步結果對用戶的真實身份做出推斷，給出社會網絡用戶身份識別的方法.

1 相關工作

近年來，對社會網絡的數據挖掘和分析受到了學術界、工業界的廣泛關注，代表性研究包括話題事件分析、情感分析、社交關系分析、用戶信息檢索推薦等[1].其中，社會網絡用戶信息挖掘的相關研究主要是針對社會網絡用戶的興趣、位置和社交關系等進行分析，推測個體用戶所屬群體.由于不同的年齡、性別、教育背景、地理位置和觀點的人群在使用社會網絡時的差異性，通過分析個體用戶特征、言語行為，對用戶進行群體分類和個體定位，一方面可以進行個性化服務、產品營銷和廣告投遞等商業活動，另一方面也可以進行具有相同興趣愛好、主觀傾向、觀點言論的群體推薦或檢測.

挖掘社會網絡用戶興趣一般是利用用戶的歷史地理位置信息或者社交關系將用戶按照興趣愛好分類，并據此向用戶作推薦，推薦內容包括地理位置、產品、好友等.在根據興趣推薦地理位置的研究中[2-4],Bao等人[2]研發了一個基于位置的興趣認知推薦方法，利用用戶的歷史地理位置信息和某地理位置的用戶評價，在線為擁有相同興趣愛好的社會網絡用戶推薦他們感興趣的地理位置.在根據興趣推薦興趣點的研究中[5-6]，Wei等人[5]提出了一種基于位置的興趣點標識方法，通過提取訪問興趣點的用戶團體的特征描述用戶個體興趣點的特征，將獲得標識的興趣點推薦給有相同興趣的用戶.在根據簽到信息推測用戶傾向的研究中[7-8]，李敏等人[7]通過分析用戶簽到信息和用戶對簽到位置的評論，推測用戶的主觀傾向性，使社會網絡能更好地為不同類別的用戶作個性化推薦.除上述研究方向外，還有通過某用戶社交圈推測該用戶興趣的研究[9-10]，Xu等人[9]通過某用戶的社交關系中興趣屬性公開的用戶，利用貝葉斯分類方法推測該用戶的興趣.

社會網絡用戶社交關系挖掘利用用戶的社交關系、屬性或歷史地理位置檢測不同用戶之間的相似性，并在此基礎上向用戶推薦好友.一類是通過用戶行為模式挖掘[11]社會網絡結構進行好友推薦[12-13]，Crandall等人[12]發現經常在相同時間出現在相同的地理位置上的用戶之間有較強的社交聯系，并利用此結論挖掘用戶的社交結構向用戶推薦好友；另一類是通過挖掘社交關系推薦好友[14-16],王玙等人[14]認為擁有相似社交圈的用戶更易成為朋友，并在此基礎上提出了社交圈檢測算法，定義用戶間的社交圈相似性，根據相似程度劃分好友圈.另外，一個用戶通常會在多個社會網絡注冊不同賬號，賬號對齊研究通過分析用戶在不同社會網絡中的信息，利用社交關系圖、好友關系等識別出同一用戶在不同社交平臺的身份.如Bayati等人[17]將特征轉化為二部圖的一組結點，待對齊的所有實例為另一組結點，然后根據結點的度、排名、權重、聚類相關度來對齊；Korula和Lattanzi[18]利用朋友關系的網絡圖將跨社會網絡的賬號映射進行了數學建模.

社會網絡用戶地理位置推測主要通過某用戶社交圈的地理位置信息來推測該用戶所在的地理位置[19-21].Backstrom等人[19]利用Facebook上用戶的好友關系來推測當前用戶的地理位置，該文得到的結論是：當用戶好友關系中有5個以上可定位用戶時能有效利用社交關系推測其地理位置，否則應當使用IP地址推測其地理位置.Clodoveu,Diogo等人[21]通過Twitter用戶粉絲中可定位的用戶，運用多數投票方法來推斷其他用戶發布博文的地理位置.

社會網絡去匿名化方法研究如何去除匿名化偽裝的影響，根據已知的用戶信息推測其敏感信息和傾向.在針對圖結構數據的去匿名化研究中[22-23]，Narayanan等人[22]利用同一人在不同社會網絡中社交關系具有一定相關性進行多賬號身份識別，從已知的少量信息出發，尋找相似結構完成種子節點映射，通過擴散不斷找出新節點的映射關系，成功匹配了13同時使用Twitter和Flicker的用戶.基于文本數據的去匿名化研究中，Narayanan等人[24]抽取文本數據特征建立高維文本特征向量，用機器學習分類器識別文本作者或其博客.

除上述研究成果外，也有一些產品化的用戶特征分析工具.iResearch公司提供的網民用戶行為分析工具TargetPlus通過分析網絡用戶群網絡行為范式與特點，幫助廣告主了解不同類別的目標用戶需求，優化網絡營銷策略.Mixpanel公司推出的用戶特征分析工具Mixpanel[25]可以分析網站訪客的性別、國家等信息，對用戶分類，把相關信息精確地送達某一用戶群體.Webtrends公司的Reinvigorate工具和Chartbeat公司的Chartbeat工具可以實時監測網站的用戶行為.除此之外，大型電商網站如Amazon、淘寶、eBay、京東等通過分析網站用戶數據推測用戶生活特征和購物興趣或傾向，以此向用戶提供個性化購物體驗和更精確的產品推薦.

綜上所述，關于社會網絡用戶特征屬性挖掘的研究已被廣泛關注，當前研究主要著眼于挖掘用戶群體的信息和傾向，并沒有對個體用戶的特征屬性作深入分析；在分析用戶群體特征屬性時粒度不夠細化，難以推測個體用戶的真實身份.相比上述研究成果，本文主要貢獻為:

1) 利用用戶的地理位置信息和博文推測用戶的學校和工作單位，將地理位置的粒度細化到具體的某個實體；

2) 利用某用戶社交關系群體特征，推測該用戶的地址、學校和工作單位信息；

3) 融合上述2步結果，對用戶身份特征做出綜合性推測，進一步縮小用戶真實身份范圍，建立起社會網絡用戶虛擬身份和真實身份之間的虛實映射.

2 用戶身份特征識別方法

2.1 方法概述

為了從社會網絡用戶的虛擬身份信息推測其真實身份，需要不斷縮小用戶真實身份的范圍.地址信息、學校和工作單位對確定用戶身份具有重要作用，為方便分析，本文將其定義為用戶身份特征，示例如圖1所示.

Fig. 1 Sample of user identity feature.圖1 用戶身份特征示例

定義1. 用戶身份特征(UID).該特征特指地址信息、學校、工作單位和興趣.可用一個四元組UID=L,E,W,I描述.其中，L代表該用戶地址信息集合，可表示為：L={(li,Pli)|i=1,2,…,nL} ，li代表省、市、區、街道和門牌號等地址信息，Pli代表用戶地址為li的概率；E代表學校集合，可表示為：E={(ej,Pej)|j=1,2,…,nE}，ej代表用戶畢業或就讀的學校，Pej代表用戶畢業或就讀學校為ej的概率；W代表工作單位集合，可表示為：W={(wk,Pwk)|k=1,2,…,nW}，wk代表用戶曾經工作或在職的工作單位，Pwk為用戶在職或曾經工作的單位為wk的概率；I代表用戶興趣集合，可表示為：I={(ik,Pik)|k=1,2,…,nI}，ik代表用戶的興趣，Pik代表用戶興趣為ik的概率.

Fig. 2 Flow chart of user identity feature recognition method.圖2 用戶身份特征識別方法總體流程圖

定義2. 實體指學校和工作單位的集合.該集合是E和W的并集，可表示為：S={SP|SP∈E∪W,P=1,2,…,nE+nW}.

本文從社會網絡用戶(簡稱用戶)的地理位置信息和社交關系出發，推測用戶的地址信息、學校、工作單位和興趣，以縮小用戶真實身份的范圍.整體的流程如圖2所示，主要包括數據獲取、數據分析、結果融合和結果推送.

1) 數據獲取.通過給定的微博用戶唯一標識(昵稱)獲取該用戶的個人信息(特征屬性)、粉絲列表、博文內容和簽到信息.

2) 數據分析.包括2種分析方法：①地理位置方法.通過用戶開啟GPS服務后博文數據帶有的經緯度信息得到用戶的頻繁地理位置，進而得到該位置周邊的實體信息，與用戶簽到的實體信息合并得到候選實體列表；實體列表中每個實體是用戶可能所屬的學校和工作單位，用近似度權重衡量可能性大小；通過實體名稱聚合算法合并實體名稱、優化近似度權重計算結果，推測用戶的地址信息、學校、工作單位和興趣.②社交關系多數投票方法.通過用戶的粉絲列表得到用戶的互粉好友，提取用戶互粉好友的用戶身份特征，并對得到的用戶身份特征集合L,E,W,I進行多數投票，選取各集合中滿足條件且計數靠前的各項作為當前用戶身份特征.

3) 結果融合.地理位置方法覆蓋開啟GPS服務的用戶，社交關系多數投票方法覆蓋有健壯社交關系的用戶(通過粉絲列表中互粉好友數目體現)，通過對2種方法結果的融合，能夠提高用戶身份識別的覆蓋率.

4) 結果推送.在結果融合后，整理匯總所得地址信息、學校、工作單位和興趣，推送給最終用戶.

在2.2節和2.3節中，將重點介紹基于位置的身份識別方法和基于社交關系的身份識別方法.

2.2 基于位置的社會網絡用戶身份識別方法

基于位置的社會網絡用戶身份識別方法根據社會網絡用戶的地理位置信息和博文內容來推測該用戶所屬的學校或工作單位.與社會網絡用戶相關的地理位置信息主要包括2種：1)用戶主動分享的數據，如簽到信息；2)開啟GPS服務的代價，例如博文帶有的地理位置坐標.本方法同時用到上述2類地理位置信息，再利用博文內容來匹配分詞后的實體名稱，本方法的主要步驟如下：

步驟1. 從用戶發布的博文中提取地理位置信息；

步驟2. 對得到的地理位置信息作頻率統計，獲得前N個頻繁的地理位置；

步驟3. 通過新浪微博API獲得這N個頻繁地理位置周邊的實體列表；

步驟4. 將上述列表和用戶的簽到信息合并，得到候選實體列表；

步驟5. 分析候選實體與用戶博文匹配度，計算其近似度權重；

步驟6. 使用實體名稱聚合算法聚合所有候選實體信息并去除冗余，優化近似度權重計算結果.

最終，根據新的近似度權重對實體排序，得到降序的候選實體列表.其中，最為關鍵的步驟是實體名稱近似度權重計算和實體名稱聚合，下面我們分別對這2個步驟進行專門介紹.

2.2.1 近似度權重計算

用戶的博文內容中包含和用戶直接相關的信息，如地址信息、學校、工作單位等.因此，我們可以通過將實體名稱匹配用戶博文的方法計算實體列表中各實體為用戶所屬實體的可能性.考慮到實體全稱在用戶博文中被提到的可能性低，為了提高命中率，我們先對實體列表中各實體名稱進行分詞處理(二元組分詞和中文分詞)，并在分詞過程中通過別名詞庫將分詞得到的實體簡稱、別名加入到分詞結果中以防止實體名稱漏配用戶博文中用戶習慣用語的情況.匹配的結果由近似度權重衡量，近似度權重越高，對應實體即為用戶所屬實體的可能性越大.近似度權重的大小和匹配內容的長度及匹配次數成正比，匹配內容的長度越大、次數越多,近似度權重越大.

實體名稱對應的分詞結果與博文內容進行匹配分為完全匹配和基本匹配.完全匹配表示實體名稱的全稱在博文內容中得到匹配(博文內容包含實體名稱的全稱“北京大學”)；而基本匹配表示實體名稱的分詞結果中的分詞(不包括實體名稱的全稱)在博文內容中得到匹配(博文內容只包含“北京”、“大學”等詞組).完全匹配的實體近似度權重高；基本匹配的實體近似度權重低.基于以上分析，設計了實體名稱s完全匹配的近似度權重Weightf(s)和實體名稱s的分詞結果si基本匹配的近似度權重Weightb(s)為

(1)

(2)

式(1)中，s代表輸入實體名稱，Weightf(s)代表輸入實體名稱的近似度權重，Len(s)代表輸入實體名稱的長度；式(2)中，si代表實體名稱s的一個分詞結果，Weightb(s)代表輸入實體名稱分詞的近似度權重，n代表實體名稱s分詞的總數，msi代表si與博文內容的匹配次數.

由式(1)和式(2)得到實體名稱s的近似度權重Weight(s)為

(3)

式(3)中，α和β代表可調參數.其中，α=qm，代表可調乘數因子，取值范圍為大于1的實數；m代表實體名稱s與博文內容的匹配次數，取值為正整數；qm代表權重增長的速率.β的取值范圍為大于等于0的實數.

計算得到候選實體列表各實體名稱的近似度權重后，對實體列表按近似度權重降序排列，得到用戶可能所屬的實體名稱列表序列.

2.2.2 實體名稱聚合算法

對于具有相同近似度權重的實體，需要再次計算近似度權重并優化排序結果.在實際項目中發現，通過地理位置信息和博文內容得到的實體名稱的粒度可能會精細到單位內的某個具體地點，比如“北京大學食堂”和“北京大學教學樓”，本文識別的是“北京大學”這個單位的名稱.因此，提出了一個實體名稱聚合算法，通過合并具有相同前綴的實體名稱，提取表示單位名稱的實體名稱，濾掉細粒度的實體名稱；計算合并近似度權重，優化實體名稱排序結果.

實體名稱聚合算法用到了Trie樹，又稱字典樹或前綴樹，是一個利用字符串的公共前綴來描述字符串序列的多叉樹.本文利用Trie樹描述從用戶地理位置信息獲得的實體序列，并滿足3點性質：1)根節點不包括字符，其他每個節點只包括一個漢字；2)從根節點到某一個葉子節點，路徑上經過的漢字連接起來，為一個實體；3)每個節點的所有子節點包含的字符串不同.

首先創建前綴樹.在生成實體序列前綴樹的過程中每個節點要記錄漢字出現的頻數，以及節點的深度.以具有相同近似度權重(均為1)的實體序列“北京大學食堂”、“北京大學教學樓”、“清華大學圖書館”和“中科院計算所”為例，圖3展示了該實體序列對應前綴樹建樹過程，其中節點右側標注的數字表示節點出現的頻數，圖3最左側標注的數字表示節點的深度.

Fig. 3 Building process of trie tree.圖3 前綴樹的建樹過程

前綴樹建立后，合并有最大共同前綴的實體名稱并計算對應的近似度權重.求解最大共同前綴方法的步驟如下：1)尋找出現頻數最大的節點；2)如果出現頻數相同，尋找節點深度最大的節點；3)找到上述節點后，將該節點到根節點路徑上經過的漢字連接起來即為最大共同前綴；4)如果所有節點出現頻數都為1，當前實體序列沒有最大共同前綴；5)如果出現頻數最大的節點深度不滿足條件，即最大共同前綴不滿足最短長度要求或者并不包含于前綴詞庫中，當前序列沒有最大共同前綴.在圖3的示例中，“北京大學”即為最大共同前綴.

得到最大共同前綴后，聚合實體名稱，其步驟如下：1)合并擁有最大共同前綴的實體名稱為最大共同前綴；2)計算1)中被合并實體名稱近似度權重之和作為最大共同前綴的近似度權重；3)根據新的近似度權重計算結果重新對候選實體列表排序.在圖3的示例中，“北京大學食堂”和“北京大學教學樓”合并為“北京大學”，并計算其近似度權重為2.最終得到的實體序列為“北京大學”、“清華大學圖書館”和“中科院計算所”，相應的近似度權重分別為2，1，1.

在聚合當前近似度權重對應的實體名稱后，迭代聚合其他近似度權重對應的實體名稱.最后，根據別名詞庫聚合不同近似度權重間實體名稱相同或互為別名的實體名稱，并合并其近似度權重.接下來根據近似度權重計算對應實體為當前用戶所在實體的概率PWeight(si)為

(4)

算法1. 實體名稱聚合算法.

輸入:Sall，P，N;

輸出:MSall.

① while(Sall≠?) /*遍歷Sall*/

②new_tree=createTrie();

/*初始化前綴樹*/

③ while(SWeighti∈Sall且SWeighti≠?)

/*生成前綴樹*/

④ for eachSP∈SWeighti

⑤insertTrie(SP); /*將SP逐字插入前綴樹中*/

⑥ end for

⑦ end while

⑧prefix=new_tree.findMaxPrefix();

/*遍歷前綴樹獲得最大共同前綴*/

⑨ ifLen(prefix)≥Lengthorprefix∈P

then /*最大共同前綴長度滿足要求*/

⑩ while(SPi∈SWeighti且prefix?SPi)

/*求或包含于前綴詞庫*/

/*計算最大共同前綴的近似度權重*/

刪除有最大共同前綴的實體*/

前綴到實體列表集合*/

/*合并兩者近似度權重*/

重新對Sall排序*/

實體名稱聚合完成后就得到了最終的實體排序結果.

2.3 基于社交關系的多數投票身份識別方法

2.3.1 方法描述

社會網絡的發展把人們的社交圈從現實生活中映射到網絡世界，可通過社會網絡上互為好友或者互為粉絲等社交關系體現.屬于同一個社交圈的人擁有更多的共同點，例如居住在較近的地理區域、就讀或畢業于相同學校、在相同的工作單位等.本方法基于社會網絡用戶的社交關系鄰居節點的屬性信息，利用互粉用戶地址信息條目和實體信息條目，通過多數投票的方法推測當前用戶的地址信息、學校和工作單位.

多數投票是一種簡單有效的方法，它利用分類器對給定的測試樣本輸出分類類別及各類別的投票結果.設當前用戶樣本Xu的分類器為C，有m個類別Tji(j=1,2,3,4;i=1,2,…,nj;nj≤m)，分類器C輸入一個分類樣本Xu，輸出一個分類編號ji，即C(Xu)=ji.每個類別Tji對應一個投票計數count(Tji)，其中：

count(Tji)=

(5)

其中，xfeature為當前用戶待推測的某個身份特征的集合，可以取為地址信息L或學校E或工作單位W或興趣I；xk是xfeature對應的條目；Tji是當前用戶所有互粉的身份特征對應的條目，當j取不同的值時，分別代表地址信息L或學校E或工作單位W或興趣I，如j=1代表地址信息L，Tji可以為北京市海淀區、北京市中關村南路80號等.

(6)

其中，Lv是最低有效投票數.最低有效投票數限定了地址信息、學校、工作單位或興趣的計數結果必須超過的數，如果計數結果小于最低有效投票數，則結果無效.

最后，對j的每一個取值分別計算概率Tji為

(7)

對j的不同取值，按概率結果降序排序，得到當前地址信息地址信息L或學校E或工作單位W或興趣I的推測結果.

2.3.2 參數選取與結果判斷

地址信息的最低有效投票數Lv可以設為1，因為每個用戶注冊信息都有地址信息，有充足的投票數用來判斷結果，判斷標準為用戶填寫的地址信息出現在計算結果Tj的前3個條目中就認為計算結果是準確的.

學校工作單位最低有效票數Lv可通過實驗統計獲得，實驗結果如圖4所示：

Fig. 4 The Least effective friends number corresponding to the minimum effective vote count.圖4 各最低有效互粉數對應的最低有效票數統計

由圖4的統計結果得到，當互粉數量小于25時，設置學校工作單位最低有效投票數為2；當互粉數量大于25時，設置其最低有效投票數為4.

用戶興趣的投票結果通過該用戶的博文內容和用戶自己填寫的興趣標簽(如果該用戶在信息中填寫了興趣字段)驗證其正確性.如果投票結果和該用戶博文內容中出現的高頻詞存在交集或者符合用戶自己填寫的興趣字段，則判定其準確，反之則判定其不準確.

2.4 基于概率的結果融合

(8)

其中，若Lg中的身份特征li在Lr中無對應項，默認其概率為0，反之亦如此.計算方式不變.

為了簡化表達方式，我們定義一種新的運算符號⊙表示上述運算，則融合結果為

Lg⊙Lr,Eg⊙Er,Wg⊙Wr,Ig⊙Ir.

(9)

上述規則中，考慮到地理位置方法獲取的用戶身份特征是近期的、實時的，它的時間屬性比較新；而社交關系多數投票方法獲取的用戶身份特征是用戶填寫的，可以包含小學、中學等項，有些時間屬性可能不是最新的.但2種方法得到的結果都有一定的合理性并可以互補，因此，我們將2個結果根據式(9)計算平均概率，得到融合后的推測結果.

3 實驗與效果評估

為了準確評價基于位置的方法和基于社交關系方法的推斷準確性，我們用新浪微博開放API收集了新浪微博的用戶數據，包括用戶信息、用戶簽到信息、用戶博文和用戶的社交關系.驗證基于位置方法的準確率時，保留用戶博文內容帶有地理位置信息的數據；驗證基于社交關系方法的準確率時，保留擁有互粉關系并且互粉數滿足最低有效互粉數的用戶數據.

實驗收集的新浪微博數據超過1.2億用戶，我們從中隨機選擇3組樣本.其中，組1為注冊用戶，樣本數為1 000；組2、組3為認證用戶，樣本數分別為1 000和10 000.本文以樣本用戶的互粉列表為基礎，從新浪微博獲得其互粉好友共 2 521 925名用戶信息及其互粉列表.

3.1 數據集分析

從新浪微博獲得的2 521 925名用戶中隨機抽取40 621名用戶用來分析樣本數據.如圖5所示，縱坐標表示用戶數量的對數，橫坐標代表統計量.圖5(a)展示了互粉數量情況分布；圖5(b)展示了互粉好友的地址信息條目數的分布情況；圖5(c)展示了互粉好友的學校工作單位條目數的分布情況；圖5(d)展示了互粉好友的興趣條目數的分布情況.圖5(a)和圖5(b)數據分布吻合，說明所有的用戶都有地址信息，地址信息的出現率接近100%；從圖5(c)和圖5(d)的數據分布可以看出，與圖5(a)和圖5(b)相比，互粉學校工作單位條目數和互粉興趣條目數小于互粉數和互粉地址信息條目數，這說明只有部分用戶有學校工作單位信息和興趣字段.注意到圖5中4幅圖的縱坐標刻度是用以10為底的對數作為單位，說明滿足條件的用戶數隨著互粉數的增加呈指數下降.

Fig. 5 Data distribution charts.圖5 數據分布圖

3.2 實驗與效果評估

在實驗中，我們使用了第3節第2段提到的3組樣本用戶作為實驗數據，對實驗效果進行驗證.我們采用2個被廣泛使用的指標來分析實驗的有效性：準確率與召回率，考慮到覆蓋率更能體現本文“最低有效互粉數”的概念，同時還使用覆蓋率作為實驗效果的衡量指標.

3.2.1 基于位置的身份識別方法實驗結果分析

本方法適用于用戶的博文內容中帶有地理位置信息，對于用戶的互粉關系并沒有要求.在1 000名認證樣本用戶中有地理位置信息的用戶有188名，占18.8%.

在實驗中，我們用2個指標衡量基于位置方法的準確性，即地址信息推測的準確性和學校工作單位推測的準確性.

在地址信息準確性判斷中，如果有至少1條頻繁地理位置與用戶填寫的地址信息吻合，我們就判定其地址信息推測是準確的.

在學校工作單位準確性判斷中，我們設定了3條判斷標準，如果學校工作單位推測滿足下述任何1條，則我們判定其地址信息推測是準確的：1)經過計算排序后的候選實體列表與用戶信息相符；2)候選實體列表前3名中有完全匹配且實體名稱滿足一定長度；3)推測出的頻繁地理位置信息精確到門牌號.

基于上述判斷標準，我們得到實驗結果如表1所示.基于位置的身份識別方法只適用有地理位置信息的用戶，我們選取包含地理位置信息的188個用戶數據做測試，得到準確率和召回率，并通過覆蓋率衡量本方法的適用范圍.

Table 1 Experimental Results of Geo-Location Based Identity Recognition Method

從表1中觀察到，地址信息推測和學校工作單位推測覆蓋率都為18.80%，因為兩者的覆蓋率都取決于開啟GPS服務的用戶比例.學校工作單位推測結果中，有114例樣本不準確.其中36.84%的樣本是因地理位置信息過于稀疏(即雖有地理位置信息，但是地理位置信息條目數不足導致實體位置推測不準確)；39.47%的樣本是因缺少博文信息導致實體匹配準確率下降；17.54%的樣本地理位置信息過于稀疏，同時還缺少博文信息.因此，本方法在用戶有充足地理位置信息和博文信息的時候最為適用.

3.2.2 基于社交關系的身份識別方法實驗結果分析

基于社交關系的身份識別方法中互粉數的取值對準確率、召回率和覆蓋率有一定影響[17].

本文為充分研究互粉數和實驗結果之間的關系，設置學校工作單位最低有效互粉數為0、最低有效投票數為2作為實驗的基準情況.實驗中，本文用了2組信息已知的微博認證用戶數據，樣本數分別為1 000名用戶和10 000名用戶.實驗結果如表2所示.注意到表2中實驗只是基準情況，對所有用戶都適用，并且都能得到推測結果.因此，表2中實驗準確率和召回率的值相同，實驗覆蓋率均為100%.其中，對于樣本數為1 000名用戶的組別，本文使用人工核實和程序自動判斷2種驗證方法比較推測結果與已知用戶信息是否相符計算準確率.表2結果顯示2種驗證方法結果的誤差不大于3.2%，說明程序自動判斷的驗證方法可行.

Table 2 Experimental Results of Education and Work Inference Method Based on Social Relationships

從表2中觀察到，學校工作單位推測的準確率低于地址信息推測的準確率,這是因為填寫學校工作單位信息的用戶少于填寫地址信息的用戶.此外，地址信息推測準確率最低為96.10%，學校工作單位推測準確率最低為80.60%，說明在最低有效互粉數為0、最低有效投票數為2時，本方法已經有了較高的準確率.不準確的情況是因為用戶的社交關系不夠健壯，即互粉數量不足.

考慮到在實際應用中，對推測準確率會有更高的要求，我們對不同最低有效互粉數作了實驗并對結果進行統計(見圖6(a)和圖6(b)).從統計結果可知：

1) 用戶互粉數量越多，推測準確率越高，覆蓋率越低；

2) 人工核實和程序自動判斷2種驗證方法結果基本相符.

Fig. 6 Precision and coverage of address, education and work inference on 1 000 users with two kinds of verification.圖6 2種驗證方法驗證1 000名用戶的地址、學校和工作單位推測的準確率和覆蓋率

從圖6(a)可以看到當最低有效互粉數為0時，地址信息推測準確率超過95%，同時有100%的覆蓋率.從圖6(b)可以看到當最低有效互粉數為30時，學校工作單位推測準確率超過85%；當最低有效互粉數為70時，學校工作單位推測準確率達到88.37%，但是覆蓋率下降到68.80%.結合上述規律，在實際應用時，應根據對準確率和覆蓋率的要求選取不同的最低有效互粉數.此外，從圖6中可以看到人工核實和程序自動判斷2種驗證方法得到的準確率結果誤差不大于3.2%，證明程序自動判斷的驗證方法是可行的.在此基礎上，本文利用程序自動判斷的驗證方法計算樣本數為10 000名用戶的組別的準確率和覆蓋率，結果如圖7所示:

Fig. 7 Inference precision and coverage on 10 000 users verified by program.圖7 程序驗證10 000名用戶的推測準確率和覆蓋率

從圖7可以看到，隨著最低有效互粉數的增加，程序驗證的推測準確率上升、覆蓋率下降.其中當最低有效互粉數為0時，地址信息推測準確率超過95%，學校工作單位推測準確率超過80%，覆蓋率100%；當最低有效互粉數為30時，學校工作單位推測準確率超過85%，覆蓋率87.47%；當最低有效互粉數為90時，學校工作單位準確率超過90%，覆蓋率下降到61.32%.

從圖8可以看到，用程序自動驗證的方法推測不同樣本數對應的地址信息推測準確率、學校工作單位推測準確率和覆蓋率非常接近，證明對于不同的樣本數，實驗得到的準確率和覆蓋率是一致的、有效的.

Fig. 8 Inference precision and coverage comparison between 1 000 users and 10 000 users verified by program.圖8 程序驗證1 000名用戶和10 000名用戶結果對比

在基于社交關系的身份識別方法推測用戶興趣的實驗中，本文同時利用認證用戶的樣本和注冊樣本.其中，認證樣本中，樣本數1 000的用戶中有興趣投票結果的用戶為952名，根據博文內容和用戶信息驗證正確的用戶為750名；樣本數為10 000的用戶中有興趣投票結果的用戶為9 613名，驗證正確的用戶為8 050名.注冊樣本中，有興趣投票的用戶為889名，驗證正確的用戶為640名.為充分研究互粉數和實驗結果之間的關系，設置最低有效互粉數為0、最低有效投票數為3.當推測結果出現在用戶填寫的興趣信息中或者在博文內容中出現3次以上則判定該結果正確.實驗結果如表3所示:

Table 3 Experimental Results of Interests Inference Using Method Based on Social Relationships

從表3觀察到認證用戶中，樣本數1 000組推測準確率為78.78%；樣本數10 000組推測準確率為83.74%;注冊用戶樣本推測準確率為71.99%，相比認證用戶有所降低.考慮到注冊用戶推測結果人工驗證很困難，本文下面主要采用認證用戶數據進行實驗，并簡稱為用戶.在實際應用中，對推測準確率會有更高的要求，我們對不同最低有效互粉數作了實驗并對結果進行統計，如圖9所示.從統計結果可知用戶互粉數量越多，推測準確率越高，覆蓋率越低.

Fig. 9 Precision and coverage of interests inference.圖9 用戶興趣推測的準確率和覆蓋率

從圖9可以看到，隨著最低有效互粉數增加，2組樣本數據準確率和覆蓋率的變化趨勢基本相同.1 000名用戶推測準確率上漲約20個百分點，10 000名用戶推測準確率上漲11個百分點.1 000名用戶推測結果中，當最低有效互粉數為20時，推測準確率超過80%，同時仍有90%以上的覆蓋率；當最低有效互粉數為70時，推測準確率超過90%，但是覆蓋率下降到70%左右.10 000名用戶推測結果中，推測準確率在最低有效互粉為0時就達到將近85%，同時有超過95%的覆蓋率.這說明本方法具有很好的泛化能力.

為了進一步驗證本文方法的效果，我們在上述1 000名用戶的樣本數據上，將本文興趣推測方法和TextRank方法[26]、直接博文推測方法進行對比實驗.根據相同的驗證方法得到的結果如圖10所示:

Fig. 10 Precision comparison of different interests inference methods on 1 000 users.圖10 1 000名用戶興趣推測準確率對比結果

從圖10看到，本方法推測準確率明顯高于直接用博文推測的準確率,且本方法的推測準確率高于TextRank方法的推測準確率.

綜上實驗結果表明，用戶的社交關系越健壯，基于社交關系的推測準確率越高.

3.2.3 方法融合效果分析

基于地理位置的方法和基于社交關系的方法有不同的適用范圍.基于地理位置的方法要求用戶開啟GPS服務，因此方法覆蓋率較低；而基于社交關系的方法只要求用戶有互粉，有較高的覆蓋率.因此，我們在基于社交關系的方法推測結果的基礎上使用基于地理位置的方法提高相同特征屬性的推測準確率和召回率.此外，由于基于地理位置的方法不涉及用戶興趣的推測，故只針對地址信息、學校工作單位信息進行討論.

(10)

(11)

圖11和圖12是方法融合前后的實驗結果對比，地址信息、學校工作單位推測的準確率和召回率比融合前都有了進一步的提升.

Fig. 11 Improvements of inference precision on address, education and work.圖11 地址信息、學校工作單位推測準確率的提升

圖11中準確率隨著最低有效互粉數的增加而減少，這是因為基于社交關系的方法準確率高，基于地理位置的方法準確率低，隨著最低有效互粉數的增加適用基于社交關系方法的用戶N1減少，適用基于地理位置方法的用戶N2增加，使得融合后的準確率趨向于基于地理位置方法的準確率.注意到圖11中最低有效互粉數為10時，準確率達到最高點.

Fig. 12 Improvements of inference recall on address, education and work.圖12 地址信息、學校工作單位推測召回率的提升

綜上所述，基于位置的方法和基于社交關系的方法融合后，實驗結果的準確率和召回率都有提升，同時可以得到具有高準確率及較高召回率和覆蓋率的最低有效互粉數.

通過以上實驗與分析可知，本文提出的基于位置的方法適用于有充足地理位置信息和博文內容的用戶，挖掘其所屬學校和工作單位；基于社交關系的身份特征識別方法適用于社交關系強壯、互粉數量多的用戶，可以應用到學校、工作單位、興趣等身份特征屬性的推測，且都有較高的準確率和覆蓋率，并具有較好的泛化能力.2種方法互補結合，可以更準確識別用戶的身份特征.

3.3 案例運行結果

實驗結尾，我們用引言中提到的制造“名人被去世”謠言的微博博主“染香”和微博粉絲最多的大V博主“姚晨”為例，運用本文提出的方法推測其用戶身份特征.注意到上述兩者并沒有開啟GPS服務，因此只適用于基于社交關系的方法，得到結果如表4、表5所示：

Table 4 Experimental Results of Case “Ranxiang”

Table 5 Experimental Results of Case “Yao Chen”

從表4觀察到，“染香”地址推測結果主要為“北京”和“廣州”.因為沒有“染香”的真實身份官方信息，本文只能根據現有資料對實驗結果作推斷.其中，“北京”符合網絡猜測的“染香”的地址，如圖13(a)所示；“廣東廣州”符合網友推測“染香”身份中的地址，如圖13(b)所示.其學校工作單位推測結果中，“清華大學”等學校也符合網絡對“染香”真實畢業院校的猜測，如圖13(a)所示.其興趣推測結果中“互聯網”、“讀書”和“媒體”符合其自媒體人的身份.

在上述案例中，本方法計算出的匿名博主“染香”的用戶身份特征與網絡猜測相符，實名博主“姚晨”的用戶身份特征與其真實身份相符(如圖14所示)，說明本方法有較高的準確性和實用性.

Fig. 13 Guesses on Ranxiang’s real identity.圖13 網絡對“染香”身份的猜測

Fig. 14 Yao Chen’s biography on Sina Weibo and Baidu Baike.圖14 新浪微博大V博主“姚晨”資料

4 結束語

本文提出了一種基于位置和社交關系的社會網絡用戶身份特征識別方法.其中基于位置的方法和基于社交關系的方法通過互補的方式有效推測用戶的地址信息、學校、工作單位和興趣等用戶身份特征.與當前社會網絡用戶信息挖掘方法多著眼于用戶群體不同，本文方法針對個體用戶挖掘身份特征推測出更細粒度的用戶信息，如學校和工作單位，能更有效地定位用戶.實驗證明本文方法有較高的準確率和覆蓋率.

下一步，我們將基于社會網絡用戶推文及其他身份特征對社會網絡用戶個體的身份進行挖掘，探索更精準的社會網絡用戶身份的識別方法.

[1]Ding Zhaoyun, Jia Yan, Zhou Bin. Survey of data mining for microblogs[J]. Journal of Computer Research and Development, 2014, 51(4): 691-706 (in Chinese)

(丁兆云, 賈焰, 周斌. 微博數據挖掘研究綜述[J]. 計算機研究與發展, 2014, 51(4): 691-706)

[2]Bao J, Zheng Y, Mokbel M F. Location-based and preference-aware recommendation using sparse geo-social networking data[C] //Proc of the 20th Int Conf on Advances in Geographic Information Systems. New York: ACM, 2012: 199-208

[3]Ye M, Yin P, Lee W C. Location recommendation for location-based social networks[C] //Proc of the 18th SIGSPATIAL Int Conf on Advances in Geographic Information Systems. New York: ACM, 2010: 458-461

[4]Zheng Y, Zhang L, Xie X, et al. Mining interesting locations and travel sequences from GPS trajectories[C] //Proc of the 18th Int Conf on World Wide Web. New York: ACM, 2009: 791-800

[5]Wei L Y, Yeh M Y, Lin G, et al. Discovering point-of-interest signatures based on group features from geo-social networking data[C] //Proc of the 18th Conf on Technologies and Applications of Artificial Intelligence (TAAI). Piscataway, NJ: IEEE, 2013: 182-187

[6]Liu B, Xiong H. Point-of-interest recommendation in location based social networks with topic and location awareness[C] //Proc of the 13th Conf on Data Mining(SDM). Philadelphia, PA: SIAM, 2013: 396-404

[7]Li Min, Wang Xiaocong, Zhang Jun, et al. Study on check-in and related behaviors of location-based social network users[J]. Computer Science, 2013, 40(10): 72-76 (in Chinese)

(李敏, 王曉聰, 張軍, 等. 基于位置的社交網絡用戶簽到及相關行為的研究[J]. 計算機科學, 2013, 40(10): 72-76)

[8]Cheng Z, Caverlee J, Lee K, et al. Exploring millions of footprints in location sharing services[C] //Proc of the 5th Int Conf on Weblogs and Social Media (ICWSM). Menlo Park, CA: AAAI, 2011: 81-88

[9]Xu W, Zhou X. Inferring privacy information via social relations[C] //Proc of the 24th IEEE Int Conf on Data Engineering Workshop. Piscataway, NJ: IEEE, 2008: 525-530

[10]He J, Chu W W, Liu Z V. Inferring privacy information from social networks[G] //Intelligence and Security Informatics. Berlin: Springer, 2006: 154-165

[11]González M C, Hidalgo C A, Albert-László B. Understanding individual human mobility patterns[J]. Nature, 2008, 453(7196): 779-782

[12]Crandall D J, Lars B, Dan C, et al. Inferring social ties from geographic coincidences[J]. Proceedings of the National Academy of Sciences of the United States of America, 2010, 107(52): 22436-22441

[13]Nathan E, Alex S P, David L. Inferring friendship network structure by using mobile phone data[J]. Proceedings of the National Academy of Sciences of the United States of America, 2009, 106(36): 15274-15288

[14]Wang Yu, Gao Lin. Social circle-based algorithm for friend recommendation in online social networks[J]. Chinese Journal of Computers, 2013, 37(4): 801-808 (in Chinese)

(王玙, 高琳. 基于社交圈的在線社交網絡朋友推薦算法[J]. 計算機學報, 2013, 37(4): 801-808)

[15]Guy I, Ronen I, Wilcox E. Do you know? Recommending people to invite into your social network [C] // Proc of the 14th Int Conf on Intelligent User Interfaces. New York: ACM, 2009: 77-86

[16]Yoshida T. Toward finding hidden communities based on user profile[J]. Journal of Intelligent Information Systems, 2013, 40(2): 189-209

[17]Bayati M, Gerritsen M, Gleich D F, et al. Algorithms for large, sparse network alignment problems[C] //Proc of the 9th IEEE Int Conf on Data Mining. Piscataway, NJ : IEEE, 2009: 705-710

[18]Korula N, Lattanzi S. An efficient reconciliation algorithm for social networks[J]. Proceedings of the VLDB Endowment, 2014, 7(5): 377-388

[19]Backstrom L, Sun E, Marlow C. Find me if you can: Improving geographical prediction with social and spatial proximity[C] //Proc of the 19th Int Conf on World Wide Web. New York: ACM, 2010: 61-70

[20]MaxMind LLC. GeoIP city accuracy for selected countries[OL]. 2010[2015-03-12]. https://www.maxmind.com/zh/home

[21]Clodoveu A, Diogo R, Rocha O, et al. Inferring the location of Twitter messages based on user relationships[J]. Transactions in GIS, 2011, 15(6): 735-751

[22]Narayanan A, Shmatikov V. De-anonymizing social networks[C] //Proc of the 30th Symp on Security and Privacy. Piscataway, NJ: IEEE, 2009: 173-187

[23]Narayanan A, Shmatikov V. Robust de-anonymization of large sparse datasets[C] // Proc of the 29th Symp on Security and Privacy. Piscataway, NJ: IEEE, 2008: 111-125

[24]Narayanan A, Paskov H, Gong N Z, et al. On the feasibility of internet-scale author identification[C] // Proc of the 23rd Symp on Security and Privacy. Piscataway, NJ: IEEE, 2012: 300-314

[25]Mixpanel Inc. Mixpanel[OL]. 2013[2015-03-12]. https://www.mixpanel.com

[26]Mihalcea R, Tarau P. TextRank: Bringing order into text[C] //Proc of the 42nd Conf on Annual Meeting of the Association for Computational Linguistics. New York: ACM, 2004: 404-411

Hu Kaixian, born in 1989. Received his MSc degree in computer software and theory from the Institute of Computing Technology, Chinese Academy of Sciences in 2015. His main research interests include network data and science, big data, etc.

Liang Ying, born in 1962. Associate professor in the Institute of Computing Technology, Chinese Academy of Sciences. Senior member of China Computer Federation. Her main research interests include data mining, big data process, middleware, service computing, etc.

Xu Hongbo, born in 1975. Associate professor in the Institute of Computing Technology, Chinese Academy of Sciences. Member of China Computer Federation. His main research interests include Web search and data mining, text classification, information filtering, etc (hbxu@ict.ac.cn).

Bi Xiaodi, born in 1992. Master candidate. Student member of China Computer Federation. Her main research interests include network data and science, big data, etc (bixiaodi@ict.ac.cn).

Zuo Yao, born in 1991. Received his MS degree in computer software and theory from the Institute of Computing Technology, Chinese Academy of Sciences in 2016. His main research interests include big data and data mining (laike9m@gmail.com).

A Method for Social Network User Identity Feature Recognition

Hu Kaixian1,2, Liang Ying1, Xu Hongbo1, Bi Xiaodi1,2, and Zuo Yao1,2

1(KeyLaboratoryofNetworkDataScienceandTechnology(InstituteofComputingTechnology,ChineseAcademyofSciences),ChineseAcademyofSciences,Beijing100190)2(UniversityofChineseAcademyofSciences,Beijing100049)

Social network is an important part of modern information society. The anonymity of social network users brings a series of problems concerning social security. This paper presents a method to recognize social network user identity feature by location-based social network (LBSN) and social relationships, and combine the results of those two to infer social network user true identity. The method of geo-location uses approximation weight which is calculated by computing full match weight and basic match weight based on Chinese segmentation and bi-word segmentation to evaluate the possibility that the entity is where the user studies or works, and the method uses entity name aggregation algorithm to optimize the result of approximation weight calculation. According to the observation that friend relationship between users on social network tends to indicate a certain same identity features or a share of common interests, the method of social relationships uses majority voting scheme to count user’s friends identity features to infer user address, entity information and interests. Based on microblog data, we conduct experiments on two samples which cover 1 000 users and 10 000 users respectively and involve a total of more than 2.5 million users relationships. Results shows that our method has a high rate of precision and recall. Compared with the existing methods, our method focuses on individual user identity feature and is valuable in practice.

identity recognition; user identity features; location-based social network (LBSN); social relationships; de-anonymizing

2015-03-19；

2015-12-22

國家重點研發計劃項目(2016YFB0800403)；國家“九七三”重點基礎研究發展計劃基金項目(2014CB340406,2013CB329602);國家“八六三”高技術研究發展計劃基金項目(2015AA015803);國家自然科學基金重點項目(61232010);國家自然科學基金面上項目(61173064);國家科技支撐計劃基金項目(2015BAK20B03)；山東省自主創新及成果轉化專項(2014CGZH1103)

梁英(liangy@ict.ac.cn)

TP391；TP393

This work was supported by the National Key Research and Development Program of China (2016YFB0800403), the National Basic Research Program of China (973 Program) (2014CB340406,2013CB329602), the National High Technology Research and Development Program of China (863 Program) (2015AA015803), the Key Program of the National Natural Science Foundation of China (61232010), the General Program of the National Natural Science Foundation of China (61173064), the National Key Technology R&D Program of China (2015BAK20B03), and the Independent Innovation and Achievement Transformation Project of Shandong Province (2014CGZH1103).