張樹森 ,魏玉黨，,梁 循,竇 勇,許 媛,梁天新

(1. 中國人民大學(xué) 信息學(xué)院，北京 100872；2. 國防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院 并行與分布處理國防科技重點(diǎn)實(shí)驗(yàn)室，湖南 長(zhǎng)沙 410073)

0　引言

在社會(huì)生活中，通信網(wǎng)絡(luò)能夠反映出人們現(xiàn)實(shí)生活中的社交關(guān)系，由此產(chǎn)生一種包含豐富信息的網(wǎng)絡(luò)，即移動(dòng)社交網(wǎng)絡(luò)。移動(dòng)社交網(wǎng)絡(luò)通常指的是結(jié)合移動(dòng)終端設(shè)備，并能通過移動(dòng)終端設(shè)備的位置信息而產(chǎn)生的一種社交網(wǎng)絡(luò)。與當(dāng)前移動(dòng)社交網(wǎng)絡(luò)概念不同，本文將通信網(wǎng)絡(luò)中的通訊錄網(wǎng)絡(luò)、通話網(wǎng)絡(luò)和短信網(wǎng)絡(luò)作為移動(dòng)社交網(wǎng)絡(luò)進(jìn)行研究。當(dāng)前，社交網(wǎng)絡(luò)[1]受到眾多學(xué)科的廣泛關(guān)注，成為了研究者關(guān)注的熱點(diǎn)。移動(dòng)社交網(wǎng)絡(luò)具有穩(wěn)定、可靠特性，能夠反映人們社交活動(dòng)的真實(shí)情況。因此，從社會(huì)網(wǎng)絡(luò)研究和社交關(guān)系分析的角度來講，移動(dòng)社交網(wǎng)絡(luò)具有一定的研究?jī)r(jià)值和意義。此外，移動(dòng)社交網(wǎng)絡(luò)的研究還對(duì)通信網(wǎng)絡(luò)的監(jiān)控和管理以及商業(yè)應(yīng)用等具有重要的現(xiàn)實(shí)意義。

近年來，由于我國網(wǎng)絡(luò)通信技術(shù)的快速發(fā)展，移動(dòng)社交網(wǎng)絡(luò)得到普及和應(yīng)用。如圖1所示，截至2016年12月，我國國內(nèi)網(wǎng)民達(dá)到7.31億，手機(jī)網(wǎng)民達(dá)6.95億，即時(shí)通信用戶達(dá)6.66億，比2015年年底增長(zhǎng)4 219萬。隨著社交網(wǎng)絡(luò)的不斷發(fā)展，為我們研究現(xiàn)實(shí)世界人與人之間的社交網(wǎng)絡(luò)和社交關(guān)系提供了廣闊的空間和研究條件。

圖1　2011—2016年國內(nèi)即時(shí)通信用戶規(guī)模

當(dāng)前，針對(duì)社交網(wǎng)絡(luò)的研究很多，如針對(duì)在線社交網(wǎng)絡(luò)Facebook、Twitter、微博等進(jìn)行的研究，并且許多研究結(jié)論已經(jīng)應(yīng)用到現(xiàn)實(shí)生活中的多個(gè)領(lǐng)域。然而，針對(duì)移動(dòng)社交網(wǎng)絡(luò)的研究則相對(duì)較少。本文探討的移動(dòng)社交網(wǎng)絡(luò)研究?jī)?nèi)容，主要包括移動(dòng)社交網(wǎng)絡(luò)中的冪律分布特征和用戶親屬關(guān)系的判別。社交網(wǎng)絡(luò)特征分析是研究和分析社交網(wǎng)絡(luò)的重要途徑，以往研究中的樣本規(guī)模往往不夠大，所得結(jié)論常常并不準(zhǔn)確[1]。在社交網(wǎng)絡(luò)中，人與人之間關(guān)系的研究一直是社會(huì)網(wǎng)絡(luò)的重要課題。研究人員通過收集和分析相關(guān)社交數(shù)據(jù)，利用用戶與其聯(lián)系人屬性和行為上的相關(guān)性，實(shí)現(xiàn)對(duì)用戶關(guān)系的判別和研究。然而，由于網(wǎng)絡(luò)的開放性，不可避免的丟失部分用戶之間固有的連接關(guān)系。同時(shí)，由于用戶在社交網(wǎng)絡(luò)中的親屬關(guān)系一般都是隱式表現(xiàn)的，而本文的親屬關(guān)系判別將有助于恢復(fù)網(wǎng)絡(luò)中的用戶親屬關(guān)系。此外，研究親屬關(guān)系不僅能夠分析出親屬關(guān)系網(wǎng)絡(luò)的構(gòu)成模式，而且有助于推進(jìn)社會(huì)結(jié)構(gòu)的進(jìn)一步優(yōu)化。

本文針對(duì)移動(dòng)社交網(wǎng)絡(luò)特征中的冪律分布特征以及用戶親屬關(guān)系進(jìn)行研究。在研究過程中，我們首先對(duì)移動(dòng)社交網(wǎng)絡(luò)中的冪律分布特征進(jìn)行分析，并對(duì)得到的結(jié)論和規(guī)律進(jìn)行說明。然后，通過用戶社交行為對(duì)用戶之間是否存在親屬關(guān)系進(jìn)行判別，提出用戶親屬關(guān)系判別模型。同時(shí)，將該模型與不同算法進(jìn)行對(duì)比，檢驗(yàn)該模型的有效性，其判別精確率達(dá)到81.01%。

1　相關(guān)工作

1.1　相關(guān)研究

在社交網(wǎng)絡(luò)中，用戶社交關(guān)系[2]的判別或預(yù)測(cè)，一直是社交網(wǎng)絡(luò)分析中的重要研究方向。其中，針對(duì)用戶關(guān)系的判別主要是從結(jié)構(gòu)和社會(huì)學(xué)角度加以研究。例如，Liben-Nowell等人[3]根據(jù)網(wǎng)絡(luò)共同點(diǎn)和網(wǎng)絡(luò)路徑兩種網(wǎng)絡(luò)結(jié)構(gòu)方面的相似度，通過計(jì)算其特征及特征之間的相互作用，對(duì)用戶之間的關(guān)系進(jìn)行了分析和預(yù)測(cè)。Adamic等人[4]基于統(tǒng)計(jì)共同好友的情況，提出了Adamic Adar算法。

在用戶關(guān)系的研究中，一些研究者還通過聚類分析以及圖分割分析的方法分析用戶間的關(guān)系。例如，Zhang Y[5]等人通過計(jì)算用戶間的相似性，利用K-means聚類算法識(shí)別微博用戶群體關(guān)系。Gao Q[6]等人將用戶關(guān)系作為邊，利用MSCC(maximal strongly connected components)方法對(duì)用戶進(jìn)行劃分，并對(duì)不同用戶群體關(guān)系進(jìn)行了挖掘。還有一些研究者通過用戶動(dòng)態(tài)分析判斷用戶間的關(guān)系，如袁毅[7]等通過跟蹤用戶對(duì)某一話題的交流數(shù)據(jù)，發(fā)現(xiàn)用戶所形成的關(guān)注、評(píng)論、轉(zhuǎn)發(fā)和引用四種關(guān)系。此外，Christopher C[8]等人通過同質(zhì)性原理提出一種時(shí)間分析方法來識(shí)別社交媒體中用戶的隱含關(guān)系。Noor F[9]等人通過分析不同社會(huì)網(wǎng)絡(luò)系統(tǒng)的模式和相關(guān)性，識(shí)別出不同社會(huì)網(wǎng)絡(luò)中群體中的朋友等用戶關(guān)系。在親屬關(guān)系的判別研究中，一些研究人員通過機(jī)器學(xué)習(xí)的方法實(shí)現(xiàn)對(duì)用戶親屬關(guān)系進(jìn)行認(rèn)證或判別。如根據(jù)用戶面部圖像，通過深度卷積神經(jīng)網(wǎng)絡(luò)提取親屬驗(yàn)證的特征[10]以及基于SIFT流的遺傳Fisher矢量特征[11]實(shí)現(xiàn)對(duì)用戶親屬關(guān)系的判別等。

本文主要研究移動(dòng)社交網(wǎng)絡(luò)中的冪律分布特征和用戶間親屬關(guān)系判別的問題。此外，與以往分析用戶關(guān)系的方法不同，本文的親屬關(guān)系判別研究沒有從網(wǎng)絡(luò)的結(jié)構(gòu)和用戶屬性出發(fā)，而是將用戶通話行為作為研究對(duì)象并進(jìn)行分析。

1.2　實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)數(shù)據(jù)采集時(shí)間為2016年2月至2017年2月，由三個(gè)數(shù)據(jù)集構(gòu)成，包括手機(jī)通信錄(mobile phone contacts，MPC)數(shù)據(jù)、通話記錄(Call Data Records，CDRs)數(shù)據(jù)和短信服務(wù)(Short Messaging Service，SMS)數(shù)據(jù)，如表1所示。

表1　實(shí)驗(yàn)數(shù)據(jù)集

由于本文數(shù)據(jù)中涉及用戶的隱私以及保護(hù)信息安全的需要，本文中所采用的所有數(shù)據(jù)均是經(jīng)過匿名替換處理的脫敏數(shù)據(jù)。同時(shí)，在實(shí)際分析過程中，還需要對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，將其中無效、異常的數(shù)據(jù)去除。實(shí)際上，本文采用的實(shí)驗(yàn)數(shù)據(jù)較為豐富且涵蓋國內(nèi)大部分省市，能真實(shí)地反映國內(nèi)移動(dòng)社交網(wǎng)絡(luò)用戶社交行為，具有廣泛的代表意義。

2　網(wǎng)絡(luò)冪律分布特征分析

1999年，Barabási[12]揭示了網(wǎng)絡(luò)中普遍存在的冪率分布，即網(wǎng)絡(luò)中大部分節(jié)點(diǎn)只有較少的連接，而網(wǎng)絡(luò)中具有較多連接的節(jié)點(diǎn)在網(wǎng)絡(luò)中占較小的比例，從而改變了傳統(tǒng)網(wǎng)絡(luò)中認(rèn)為的泊松分布特征，并將這種服從冪律度分布的網(wǎng)絡(luò)稱為無標(biāo)度網(wǎng)絡(luò)(scale-free network)，如圖2所示。

圖2　無標(biāo)度網(wǎng)絡(luò)與度的冪律分布

2.1　度的冪律分布

在社交網(wǎng)絡(luò)中，節(jié)點(diǎn)的度能直觀反映用戶在社交網(wǎng)絡(luò)中的地位和影響力。度越大表示節(jié)點(diǎn)在網(wǎng)絡(luò)中越重要。在社交網(wǎng)絡(luò)中，度分布可定義為網(wǎng)絡(luò)中度為k的概率分布。如圖3所示，在考慮到方向性，從度(無向)、入度、出度三個(gè)方面對(duì)網(wǎng)絡(luò)進(jìn)行分析。我們發(fā)現(xiàn)，本文移動(dòng)社交網(wǎng)絡(luò)度分布均服從冪率分布且存在長(zhǎng)尾，其分布指數(shù)γ分別為3.19、3.26、1.75。這種“長(zhǎng)尾”分布表明，在社交網(wǎng)絡(luò)中絕大多數(shù)用戶的聯(lián)系廣度(范圍)是一定的。同時(shí)，存在極少數(shù)用戶聯(lián)系廣度較高。

由圖3可知，在本文移動(dòng)社交網(wǎng)絡(luò)中，短信網(wǎng)絡(luò)冪律指數(shù)最小，而冪律指數(shù)反映網(wǎng)絡(luò)無標(biāo)度特性的程度，值越大無標(biāo)度特性越明顯。由此說明，相比短信網(wǎng)絡(luò)，通話網(wǎng)絡(luò)與通信錄網(wǎng)絡(luò)的無標(biāo)度特性更加明顯。

為了進(jìn)一步對(duì)本文移動(dòng)社交網(wǎng)絡(luò)節(jié)點(diǎn)度進(jìn)行研究分析，我們計(jì)算網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度，并與其他社交網(wǎng)絡(luò)(在線社交網(wǎng)絡(luò))對(duì)比。不同社交網(wǎng)絡(luò)平均度(Ad) 具體信息，如表2所示。

表2　社交網(wǎng)絡(luò)平均度

本文中的度可以表征為用戶受歡迎程度、影響力、活躍度等。入度大說明該用戶受歡迎程度較高，出度較大則說明該用戶活躍性較高。

圖3　網(wǎng)絡(luò)(度)冪律分布

由表2可知，通話網(wǎng)絡(luò)平均度是短信網(wǎng)絡(luò)兩倍多，說明在現(xiàn)實(shí)生活中相比短信通信，人們更傾向于通過電話進(jìn)行溝通。本文社交網(wǎng)絡(luò)的平均度在2～7之間，與國外相應(yīng)社交網(wǎng)絡(luò)平均度相近，如文獻(xiàn)[13]中短信網(wǎng)絡(luò)平均度為4.3。與在線社交網(wǎng)絡(luò)相比，本文移動(dòng)社交網(wǎng)絡(luò)平均度明顯低于在線社交網(wǎng)絡(luò)，如Facebook[14]、Twitter[15-16]等。

我們分析產(chǎn)生這種差異的原因： 本文移動(dòng)社交網(wǎng)絡(luò)以用戶真實(shí)關(guān)系為基礎(chǔ)，社交廣度會(huì)受到一定的限制。而在線社交網(wǎng)絡(luò)則由于其開放性、虛擬性等特點(diǎn)，用戶范圍不會(huì)受到較大的限制，故在線社交網(wǎng)絡(luò)的平均度要高于本文社交網(wǎng)絡(luò)。同時(shí)，我們將平均度看作是用戶活躍程度，進(jìn)而表明人們?cè)谔摂M網(wǎng)絡(luò)中表現(xiàn)出更高的積極性，社交活動(dòng)更加活躍。

2.2　連通子圖規(guī)模冪律分布

根據(jù)圖論原理，如果無向圖的節(jié)點(diǎn)之間存在路徑，則稱兩節(jié)點(diǎn)是連通的。如果圖中任意兩節(jié)點(diǎn)都是連通的，該圖稱為連通圖，否則為非連通圖。在本文移動(dòng)社交網(wǎng)絡(luò)中，我們分別對(duì)強(qiáng)連通子圖和弱連通子圖規(guī)模(連通子圖節(jié)點(diǎn)數(shù))及連通子圖數(shù)目進(jìn)行分析，同樣發(fā)現(xiàn)冪律分布規(guī)律。我們以連通子圖節(jié)點(diǎn)數(shù)為橫軸，以相同節(jié)點(diǎn)數(shù)的連通子圖數(shù)為縱軸，得到如圖4所示結(jié)果。

由圖4可以發(fā)現(xiàn)，社交網(wǎng)絡(luò)的強(qiáng)連通子圖和弱連通子圖的規(guī)模同樣服從冪律分布，并且具有較為明顯的肥尾特征，都存在一個(gè)較大的連通子圖。

我們繼續(xù)對(duì)本文移動(dòng)社交網(wǎng)絡(luò)中的最大連通圖進(jìn)行分析。在社交網(wǎng)絡(luò)中，最大連通子圖的節(jié)點(diǎn)數(shù)占整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)的比例，能夠反映該網(wǎng)絡(luò)的整體連通特性。通過分析，我們發(fā)現(xiàn)通信錄網(wǎng)絡(luò)、通話網(wǎng)絡(luò)以及短信網(wǎng)絡(luò)中最大連通圖比例都較高。通信錄網(wǎng)絡(luò)、通話網(wǎng)絡(luò)的最大連通圖比例分別為96.8%、97.8%，其中通話網(wǎng)絡(luò)與國外通話網(wǎng)絡(luò)的84.1%[15]相比，其值更高。由此我們可以得出“本文移動(dòng)社交網(wǎng)絡(luò)具有較高的最大連通比例”的結(jié)論。此外，在線社交網(wǎng)絡(luò)中，Twitter在2008年為97.6%[17]，F(xiàn)acebook在2011年為99.91%，新浪微博、騰訊微博最大連通比例同樣高達(dá)99.99%[17]。從而說明本文社交網(wǎng)絡(luò)與在線社交網(wǎng)絡(luò)均具有較強(qiáng)的連通性。

圖4　連通子圖冪律分布

此外，本文短信網(wǎng)絡(luò)的最大連通圖占比為66.3%，與2012年的91%、85%、97.92%[18]相比，明顯偏低。這主要是因?yàn)樵诰€社交網(wǎng)絡(luò)的快速發(fā)展對(duì)短信造成較大的影響，如微信、Twitter、Facebook等，在線社交網(wǎng)絡(luò)逐漸替代以文本信息為主要載體的短信服務(wù)，短信網(wǎng)絡(luò)中連接數(shù)量不斷降低，從而導(dǎo)致短信連通圖比例下降。

2.3　用戶聯(lián)系人數(shù)量?jī)缏煞植?/h3>

本文在對(duì)移動(dòng)社交網(wǎng)絡(luò)中用戶聯(lián)系人數(shù)量進(jìn)行分析過程中，也發(fā)現(xiàn)了冪律分布特征。在分析過程中，我們將網(wǎng)絡(luò)中的葉子節(jié)點(diǎn)也包含在內(nèi)，分析用戶聯(lián)系人的實(shí)際規(guī)模(聯(lián)系人數(shù)量)。如圖5所示，我們以聯(lián)系人數(shù)量為橫軸，以聯(lián)系人規(guī)模相同的用戶數(shù)量為縱軸，左圖為聯(lián)系人數(shù)量的累計(jì)概率密度分布圖。

由圖5可知，通信錄與通話網(wǎng)絡(luò)聯(lián)系人數(shù)量在一定規(guī)模內(nèi)保持均衡，而超過一定規(guī)模則表現(xiàn)出冪律分布特征，而短信網(wǎng)絡(luò)整體上服從冪律分布。通訊錄中聯(lián)系人數(shù)在128人以內(nèi)的用戶數(shù)量保持穩(wěn)定，說明128人的社交關(guān)系總量能夠滿足用戶在社交網(wǎng)絡(luò)中基本的社交需求。通話聯(lián)系人則反映出用戶存在實(shí)際交互行為，其數(shù)量在55以內(nèi)保持恒定，說明保持聯(lián)系較為緊密的團(tuán)體規(guī)模在55人以內(nèi)，即一定規(guī)模的人群構(gòu)成用戶的核心網(wǎng)絡(luò)成員。正如Marsden核心網(wǎng)絡(luò)[19]理論一樣，社交關(guān)系總量增長(zhǎng)的不是核心網(wǎng)絡(luò)成員數(shù)量，而是人們被動(dòng)偶然聯(lián)系的人數(shù)。

圖5　用戶聯(lián)系人規(guī)模冪律分布

相對(duì)于通話網(wǎng)絡(luò)與通信錄網(wǎng)絡(luò)，短信網(wǎng)絡(luò)用戶聯(lián)系人分布表現(xiàn)出整體上服從冪律分布，并沒有前期的穩(wěn)定階段。其原因在于隨著即時(shí)通信工具的不斷發(fā)展，如微信、QQ、Facebook等，以短信方式進(jìn)行溝通的用戶及短信的使用頻率越來越少。由圖5可知，通話網(wǎng)絡(luò)與短信網(wǎng)絡(luò)的聯(lián)系人數(shù)量要明顯小于通信錄網(wǎng)絡(luò)。通信錄網(wǎng)絡(luò)建立在社會(huì)關(guān)系存在的基礎(chǔ)上，用戶之間互相存在連接只能說明其社會(huì)關(guān)系存在，即路徑可達(dá)。通話網(wǎng)絡(luò)和短信網(wǎng)絡(luò)則是建立在至少發(fā)生一次交互行為的基礎(chǔ)上，是發(fā)生實(shí)際交互行為而產(chǎn)生的社會(huì)關(guān)系。由此，通話網(wǎng)絡(luò)與短信網(wǎng)絡(luò)的聯(lián)系人數(shù)量要明顯小于通信錄網(wǎng)絡(luò)。

移動(dòng)社交網(wǎng)絡(luò)中手機(jī)通信錄(MPC)網(wǎng)絡(luò)、通話(CDRs)網(wǎng)絡(luò)和短信服務(wù)(short messaging service，SMS)網(wǎng)絡(luò)都是手機(jī)用戶在通信交流過程中形成的社交網(wǎng)絡(luò)，都能夠反映用戶在實(shí)際生活中的社交狀況。其中，通信錄(MPC)網(wǎng)絡(luò)是由用戶通信錄中用戶之間形成的社交網(wǎng)絡(luò)，可以說是用戶認(rèn)識(shí)的人之間的社交網(wǎng)絡(luò)。而通話網(wǎng)絡(luò)和短信網(wǎng)絡(luò)中用戶沒有這種限制，用戶之間可能是不認(rèn)識(shí)的，尤其是通話網(wǎng)絡(luò)。相對(duì)短信使用更加頻繁，更能反映出用戶現(xiàn)實(shí)中的社交情形。

實(shí)際上，冪律分布規(guī)律是社交網(wǎng)絡(luò)中廣泛在的規(guī)律。本文在研究過程中找出移動(dòng)社交網(wǎng)絡(luò)中存在的三個(gè)冪律分布規(guī)律，并與其他社交網(wǎng)絡(luò)相對(duì)比。同時(shí)，對(duì)移動(dòng)社交網(wǎng)絡(luò)平均度低于在線社交網(wǎng)絡(luò)，短信網(wǎng)絡(luò)的最大連通圖占比更低等規(guī)律和結(jié)論進(jìn)行分析，進(jìn)而優(yōu)化驗(yàn)證了相關(guān)研究結(jié)論，對(duì)移動(dòng)社交網(wǎng)絡(luò)的結(jié)構(gòu)及其用戶社交行為有了更深入的認(rèn)識(shí)，從而實(shí)現(xiàn)對(duì)移動(dòng)社交網(wǎng)絡(luò)的深入了解和分析。

3　用戶親屬關(guān)系判別模型

3.1　親屬關(guān)系研究問題

在社會(huì)網(wǎng)絡(luò)中，親屬關(guān)系是與用戶聯(lián)系最為密切的社交關(guān)系。在以往親屬關(guān)系研究中，研究人員由于研究條件的限制，往往通過調(diào)查問卷的形式采集數(shù)據(jù)進(jìn)行研究，采集的樣本規(guī)模也不夠大。因此，研究中往往存在數(shù)據(jù)規(guī)模小、樣本少的問題。當(dāng)前，由于計(jì)算機(jī)及信息技術(shù)的快速發(fā)展，使大規(guī)模社會(huì)關(guān)系數(shù)據(jù)的獲取和分析成為可能，為我們研究和分析親屬關(guān)系提供了條件。本文所采用的移動(dòng)社交網(wǎng)絡(luò)數(shù)據(jù)，具有數(shù)據(jù)量多、范圍廣的特點(diǎn)。因此，與小規(guī)模樣本數(shù)量的研究相比，更具實(shí)際意義。

本文親屬關(guān)系研究的問題，主要是基于用戶通話行為特征判別用戶間是否存在親屬關(guān)系。我們通過提取用戶通話行為的顯著特征，采用GBDT(gradient boost decision tree)與LR(logistic regression)融合方法，建立一個(gè)親屬關(guān)系判別模型，并使用用戶數(shù)據(jù)和提取的特征數(shù)據(jù)訓(xùn)練該模型。由此，通過該模型我們?cè)诰哂型ㄔ捊换バ袨榈挠脩糁g，判別他們是否存在親屬關(guān)系。

在本文親屬關(guān)系判別模型訓(xùn)練過程中，需要具有親屬關(guān)系的用戶數(shù)據(jù)來訓(xùn)練模型。本文將具有親屬關(guān)系的用戶數(shù)據(jù)，看成由八類關(guān)系用戶數(shù)據(jù)組成，即夫妻關(guān)系、父子關(guān)系、兄妹關(guān)系、祖孫關(guān)系、堂表關(guān)系、伯舅關(guān)系、嫂夫關(guān)系及其他(如外祖、姨等)。在提取親屬用戶數(shù)據(jù)中，用戶之間具有這八類關(guān)系中的一種，本文即認(rèn)為用戶之間具有親屬關(guān)系。其中，在基于短信文本內(nèi)容提取親屬關(guān)系用戶數(shù)據(jù)過程中，祖孫關(guān)系、伯舅關(guān)系這兩種親屬關(guān)系用戶的準(zhǔn)確率和數(shù)量相比其他親屬關(guān)系用戶明顯偏低。因此，在實(shí)際提取親屬關(guān)系數(shù)據(jù)及判別實(shí)驗(yàn)中不再考慮這兩種關(guān)系的用戶數(shù)據(jù)。本文結(jié)合機(jī)器學(xué)習(xí)和關(guān)系邏輯推理的方法，從短信數(shù)據(jù)中提取親屬關(guān)系用戶數(shù)據(jù)。

3.2　數(shù)據(jù)特征選擇

本文通過分析用戶之間的通話行為特征，將親屬關(guān)系判別問題轉(zhuǎn)換成數(shù)據(jù)挖掘中的分類問題。由于原始數(shù)據(jù)只有用戶之間的通話時(shí)長(zhǎng)、通話時(shí)間、及通話類型這三種屬性特征，不能夠有效對(duì)親屬關(guān)系進(jìn)行判別，需要我們對(duì)用戶通話行為特征進(jìn)行提取。用戶通話行為特征提取過程是以用戶的通話時(shí)長(zhǎng)與類型為基本屬性，在通話次數(shù)、時(shí)間等維度上進(jìn)行擴(kuò)展。根據(jù)用戶間通話的基本信息以人工的方式在不同指標(biāo)和維度上進(jìn)行擴(kuò)展，如用戶在通話時(shí)長(zhǎng)上可擴(kuò)展出通話總時(shí)長(zhǎng)、平均通話時(shí)長(zhǎng)、白天通話時(shí)長(zhǎng)、夜間通話時(shí)長(zhǎng)、日均通話時(shí)長(zhǎng)、月均通話時(shí)長(zhǎng)、工作日通話時(shí)長(zhǎng)、周末通話時(shí)長(zhǎng)等特征。

通話數(shù)據(jù)的采集時(shí)間跨度和時(shí)間點(diǎn)均與短信數(shù)據(jù)相同，但數(shù)據(jù)總量和用戶量比短信數(shù)據(jù)要大得多。通過聚合通話數(shù)據(jù)與短信數(shù)據(jù)，求取其共有用戶，并通過短信數(shù)據(jù)中用戶親屬名稱、稱謂等提取親屬關(guān)系用戶數(shù)據(jù)。在清理后得到的用戶中，具有親屬關(guān)系的用戶數(shù)為147.4萬，不存在親屬關(guān)系的用戶數(shù)為1 124.6萬。由此，我們分別得到親屬關(guān)系用戶數(shù)據(jù)集和不存在親屬關(guān)系用戶數(shù)據(jù)集。同時(shí)，根據(jù)提取的特征分別得到兩種數(shù)據(jù)集中的特征數(shù)據(jù)。

3.3　親屬關(guān)系判別模型選擇

3.3.1相關(guān)算法

(1) 邏輯回歸(LR)是當(dāng)前比較常用的機(jī)器學(xué)習(xí)方法，通常用于估計(jì)某種事物的可能性，是一種廣義線性模型。由于LR決策邊界是線性的，當(dāng)面對(duì)復(fù)雜的學(xué)習(xí)任務(wù)時(shí)，其效果并不理想。只能通過人工的特征工程制造出有效的變量和變量組合，間接的增加其非線性學(xué)習(xí)的能力。如何實(shí)現(xiàn)自動(dòng)的特征發(fā)現(xiàn)、組合，以彌補(bǔ)人工經(jīng)驗(yàn)的不足，從而縮短特征工程周期，成為當(dāng)前LR分析中所面臨的問題。

(2) 梯度提升決策樹 (GBDT)是一種基于boosting思想的集成學(xué)習(xí)算法。GBDT中每一棵提升樹都可以看作構(gòu)造特征的一種方法，且有監(jiān)督式產(chǎn)生的特征具有一定區(qū)分性。

3.3.2判別模型選擇

本文將提升樹葉子節(jié)點(diǎn)作為L(zhǎng)R的特征變量，由此大大減少了人工尋找特征及特征組合的時(shí)間，由此我們得到GBDT與LR融合方法。將GBDT與LR融合前需要人工尋找有區(qū)分性的特征(raw feature)、特征組合(cross feature)，融合后直接通過GBDT進(jìn)行特征、特征組合的自動(dòng)發(fā)現(xiàn)。

本文選擇GBDT與LR融合方法進(jìn)行親屬關(guān)系判別，主要是為了綜合考慮親屬關(guān)系判別中的運(yùn)行速度和準(zhǔn)確率，以及運(yùn)行大規(guī)模數(shù)據(jù)的可行性。采用LR模型前加GBDT模型，是因?yàn)橐鉀QLR的非線性判別能力問題，GBDT模型后接LR是解決算法速度或者應(yīng)用于大規(guī)模數(shù)據(jù)性能問題，兩者結(jié)合是能夠在性能和速度上都有所提高。

GBDT與LR融合方法處理流程，如圖6所示。GBDT模型通過學(xué)習(xí)得出兩棵決策樹Tree1、Tree2，輸入樣本x經(jīng)過對(duì)兩個(gè)決策樹遍歷后，分別在兩個(gè)提升樹的葉子節(jié)點(diǎn)上形成值。如果x分別落在Tree1、Tree2的第二個(gè)葉子節(jié)點(diǎn)和第一個(gè)葉子節(jié)點(diǎn)，則相應(yīng)的特征則為[0,1,0,1,0]。決策樹是簡(jiǎn)單的預(yù)測(cè)模型，其代表著樣本數(shù)據(jù)與目標(biāo)變量之間的一種映射關(guān)系。決策樹中的每個(gè)節(jié)點(diǎn)表示某個(gè)對(duì)象，而每個(gè)路徑則代表某種可能的屬性值。葉子節(jié)點(diǎn)則對(duì)應(yīng)從根節(jié)點(diǎn)到所歷經(jīng)的路徑所表示的對(duì)象值。每條路徑都是通過損失函數(shù)最小化等方法得到的具有區(qū)分性的路徑。通過該路徑處理的特征，是經(jīng)過決策樹判斷整合后的特征。通過這種方式得到的特征或者特征組合，其模型效果理論上不低于人工處理的方式。GBDT模型的特點(diǎn)，非常適合用來挖掘有效的特征及特征組合。

圖6　融合算法流程

3.3.3親屬關(guān)系判別模型

本文中，我們將GBDT與LR的融合方法應(yīng)用到親屬關(guān)系的判別。由此，得到本文親屬關(guān)系判別模型。本文親屬關(guān)系判別過程為：

輸入： 訓(xùn)練數(shù)據(jù)T={(x1,y1)，(x2,y2),...，(xN,yN)}，xi∈x?Rn，yi∈y?R。

輸出： 提升樹fM(x)，KI值，親屬關(guān)系模型

(1) 初始提升樹f0(x)=0

(2) 對(duì)m=1,2,...,M

+T(xi;Qm))

其中，Qm為決策樹參數(shù)

殘差γmi=yi-fm-1(xi)，i=1,2,...,N

(b) 擬合殘差γm i學(xué)習(xí)一個(gè)回歸樹，得到

T(x;Qm)

(c) 更新fm(x) =fm-1(x) +T(x;Qm)

(3) 得到回歸問題提升樹。

(1)

(4) 每個(gè)樣本點(diǎn)再映射到每個(gè)樹上的相應(yīng)節(jié)點(diǎn)，則有M個(gè)特征。

(5) 將得到的M個(gè)特征作為L(zhǎng)R的輸入，進(jìn)行訓(xùn)練。

(6) 通過LR得到關(guān)系預(yù)測(cè)值R，R≥0.5時(shí)，我們認(rèn)為用戶之間具有親屬關(guān)系，否則沒有親屬關(guān)系。

本文用戶親屬關(guān)系的判別研究是以用戶間通話的記錄和短信數(shù)據(jù)進(jìn)行分析。通過短信數(shù)據(jù)中具有的親屬關(guān)系定義中的稱謂、身份等信息確定用戶間是否具有親屬關(guān)系，進(jìn)而得到實(shí)驗(yàn)數(shù)據(jù)集(具有親屬關(guān)系的數(shù)據(jù)集和不具有親屬關(guān)系的數(shù)據(jù)集)。通過提取用戶通話行為特征，使用實(shí)驗(yàn)數(shù)據(jù)集對(duì)分類算法模型進(jìn)行訓(xùn)練，得到親屬關(guān)系的分類模型，然后進(jìn)行驗(yàn)證分析。在實(shí)驗(yàn)數(shù)據(jù)中，我們得出的僅僅是兩類數(shù)據(jù)，并沒有對(duì)具體親屬關(guān)系類型進(jìn)行分類和處理。對(duì)于其他用戶關(guān)系，如朋友、同事等，在本文數(shù)據(jù)中難以確認(rèn)用戶之間是否是朋友或同事等關(guān)系。因此，本文研究過程中通過用戶間的通話行為進(jìn)行分析，只對(duì)是否存在親屬關(guān)系進(jìn)行判別，沒有對(duì)其親屬類別進(jìn)行詳細(xì)判別。

3.4　實(shí)驗(yàn)過程

在實(shí)驗(yàn)過程中，我們將本文親屬關(guān)系判別模型的實(shí)驗(yàn)結(jié)果與其他機(jī)器學(xué)習(xí)算法實(shí)驗(yàn)結(jié)果進(jìn)行比較，驗(yàn)證本文親屬關(guān)系判別模型的有效性。

3.4.1評(píng)價(jià)指標(biāo)

在實(shí)驗(yàn)結(jié)果評(píng)價(jià)中，我們通過K折交叉驗(yàn)證評(píng)估方法驗(yàn)證本文親屬判別方法的有效性。該方法將數(shù)據(jù)集分割成K個(gè)等份，其中K-1份作為訓(xùn)練，1份作為測(cè)試，實(shí)踐中一般取K=10，本文中我們將K取值為10。同時(shí)，本文在交叉驗(yàn)證的基礎(chǔ)上，采用多種評(píng)價(jià)指標(biāo)對(duì)親屬關(guān)系判別模型及對(duì)比算法實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)價(jià)，包括： 精確率、召回率、F1值及AUC。本文實(shí)驗(yàn)中的混淆矩陣如表3所示。

表3　混淆矩陣

本文結(jié)合表3所示的混淆矩陣，分別介紹這幾種判別指標(biāo)的計(jì)算方法。

(1) 精確率(Precision)是模型預(yù)測(cè)為親屬關(guān)系而占實(shí)際親屬關(guān)系的比例，即查準(zhǔn)率。

(2)

(2) 召回率(Recall)是模型預(yù)測(cè)為親屬關(guān)系樣本中實(shí)際上也是親屬的比例，即查全率。

(3)

(3)F1-Score是精準(zhǔn)率和召回率的調(diào)和均值，是對(duì)模型的一種中和評(píng)價(jià)。

(4)

(4) AUC是ROC(receiver operating characteristic)曲線下的面積，是對(duì)模型敏感性和特異性的綜合評(píng)價(jià)指標(biāo)。AUC處于[0,1]之間，AUC值越大表示決策的準(zhǔn)確率越高。AUC的基準(zhǔn)值為0.5，即隨機(jī)猜測(cè)。

3.4.2實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)中對(duì)移動(dòng)社交網(wǎng)絡(luò)用戶間是否存在親屬關(guān)系進(jìn)行判別，驗(yàn)證親屬關(guān)系判別模型的有效性。同時(shí)，本文通過多種機(jī)器學(xué)習(xí)算法作為對(duì)比算法，驗(yàn)證判別模型的有效性。其中，對(duì)比算法包括決策樹(decision tree，DT)、支持向量機(jī)(support vector machine，SVM)、Logistic回歸(logistic regression，LR)、梯度提升決策樹 (gradient boost decision tree，GBDT)。

在實(shí)驗(yàn)過程中，我們通過預(yù)處理的用戶通話記錄數(shù)據(jù)集，對(duì)本文親屬關(guān)系判別模型和對(duì)比算法模型進(jìn)行訓(xùn)練和測(cè)試。首先，我們根據(jù)用戶間的通話記錄數(shù)據(jù)得到通話用戶數(shù)據(jù)特征值，進(jìn)而得到實(shí)驗(yàn)用的數(shù)據(jù)集。然后，將實(shí)驗(yàn)數(shù)據(jù)集分成10個(gè)子集，其中九個(gè)作為訓(xùn)練集，一個(gè)作為測(cè)試集。最后，我們將DT、SVM、LR、GBDT算法以及本文親屬關(guān)系判別模型分別在訓(xùn)練集和測(cè)試集上進(jìn)行訓(xùn)練和測(cè)試，計(jì)算實(shí)驗(yàn)中不同評(píng)價(jià)指標(biāo)值。

由此，我們得到不同方法實(shí)驗(yàn)結(jié)果評(píng)價(jià)指標(biāo)，實(shí)驗(yàn)結(jié)果比較如表4所示。

表4　實(shí)驗(yàn)結(jié)果評(píng)價(jià)指標(biāo)比較

同時(shí)，根據(jù)上述指標(biāo)結(jié)果，我們對(duì)各指標(biāo)以AUC值的大小進(jìn)行排序，其結(jié)果如圖7所示。

圖7　親屬關(guān)系判別模型算法比較

由圖7可知，本文提出的GBDT與LR融合模型能夠取得良好的實(shí)驗(yàn)效果。實(shí)驗(yàn)中GBDT+LR融合模型的精確率為81.01%，召回率為76.24%，準(zhǔn)確率為79.18%。與其他對(duì)比算法相比，實(shí)驗(yàn)效果更好。

4　結(jié)論

本文針對(duì)人們生活中聯(lián)系較為緊密的移動(dòng)社交網(wǎng)絡(luò)進(jìn)行分析和研究，主要工作包括以下兩部分。

(1) 對(duì)移動(dòng)社交網(wǎng)絡(luò)中存在的冪律分布特征進(jìn)行了分析，對(duì)其中的規(guī)律和結(jié)論進(jìn)行解釋和說明，并與其他社交網(wǎng)絡(luò)相關(guān)結(jié)論進(jìn)行對(duì)比。實(shí)現(xiàn)對(duì)本文移動(dòng)社交網(wǎng)絡(luò)冪律分布特征的分析和研究，優(yōu)化了相關(guān)研究結(jié)論。

(2) 通過提取用戶通話行為顯著特征，采用GBDT與LR融合方法建立親屬關(guān)系判別模型。在實(shí)驗(yàn)中，將該判別模型與多種算法進(jìn)行對(duì)比實(shí)驗(yàn)。通過該模型，我們能夠在移動(dòng)社交網(wǎng)絡(luò)中具有交互行為的用戶之間，較好地判別用戶間是否存在親屬關(guān)系，其判別精確率達(dá)到81.01%。

在今后的工作中，我們將繼續(xù)對(duì)移動(dòng)社交網(wǎng)絡(luò)中的網(wǎng)絡(luò)特征及用戶關(guān)系進(jìn)行研究。例如，本文用戶親屬關(guān)系研究中，用戶間的親屬關(guān)系判別是基于通話網(wǎng)絡(luò)中用戶的行為信息，并沒有充分地考慮用戶之間的結(jié)構(gòu)特征及短信網(wǎng)絡(luò)中用戶結(jié)構(gòu)和行為特征。因此，我們可以結(jié)合不同網(wǎng)絡(luò)中用戶的結(jié)構(gòu)和行為對(duì)用戶之間的親屬關(guān)系進(jìn)行判別分析。本文只對(duì)用戶間是否存在親屬關(guān)系進(jìn)行判別，下一步可以將用戶親屬關(guān)系分成更加具體的類別，并對(duì)其他用戶關(guān)系進(jìn)行提取和分析，進(jìn)而通過本文判別方法及其他分類算法的訓(xùn)練學(xué)習(xí)，判別出用戶具體的關(guān)系類別。