張金龍

【摘 要】針對現(xiàn)有網(wǎng)絡(luò)節(jié)點重要性評估未能真實全面地反映通信網(wǎng)絡(luò)的用戶關(guān)系的問題，提出了一種基于結(jié)合TF-IDF和改進PageRank的關(guān)鍵用戶預(yù)測的算法。首先構(gòu)造有向加權(quán)的移動社交網(wǎng)絡(luò)；然后采用TF-IDF算法提取有效的移動用戶交往圈；最后采用改進PageRank算法識別關(guān)鍵用戶，實現(xiàn)關(guān)鍵用戶挖掘。實驗結(jié)果表明，該方法能夠有效、合理地評估有向加權(quán)網(wǎng)絡(luò)的關(guān)鍵用戶，從而提高通信網(wǎng)絡(luò)節(jié)點重要性評估的實踐價值。

【關(guān)鍵詞】關(guān)鍵用戶 TF-IDF 改進PageRank 有向加權(quán)網(wǎng)絡(luò)

1 引言

目前，針對無向加權(quán)復(fù)雜網(wǎng)絡(luò)的節(jié)點重要性評估有兩個方面：一是通過一些節(jié)點、度、節(jié)點介數(shù)、聚集系數(shù)等網(wǎng)絡(luò)特征向量來評估節(jié)點重要性；二是以系統(tǒng)論為基礎(chǔ)提出的基于系統(tǒng)的“核與核度”理論。比如：周漩[1]等人采用節(jié)點效率和節(jié)點重要度評價矩陣，用節(jié)點度值和效率值來表征其對相鄰節(jié)點的重要度貢獻，該方法在很大程度上克服了節(jié)點刪除法和收縮法的不足；李玉華[2]等人針對動態(tài)加權(quán)網(wǎng)絡(luò)，提出了基于距離增量分組的動態(tài)節(jié)點重要性評估算法；張益[3]提出一種采用系統(tǒng)論的思想，將灰色關(guān)聯(lián)度作為測度，評價網(wǎng)絡(luò)中每個節(jié)點的重要性。但由于上述算法沒有考慮真實網(wǎng)絡(luò)的有向加權(quán)性，因此不適合現(xiàn)實的需求。本文在綜合考慮有向加權(quán)網(wǎng)絡(luò)[4]的基礎(chǔ)上，結(jié)合用戶通信數(shù)據(jù)的獨特性，旨在提出一種改進PageRank算法挖掘關(guān)鍵用戶。

2 復(fù)雜網(wǎng)絡(luò)的相關(guān)理論研究

眾所周知，目前大多數(shù)真實網(wǎng)絡(luò)都是復(fù)雜且有向的。復(fù)雜網(wǎng)絡(luò)模型的主要統(tǒng)計特征量包括：節(jié)點的度、度的分布、度的相關(guān)性、平均路徑長度、聚類系數(shù)、介數(shù)、模塊性等。通過網(wǎng)絡(luò)的特征量，本文對節(jié)點的度、節(jié)點加權(quán)度和節(jié)點權(quán)重進行分析，提出了改進PageRank算法來挖掘通信數(shù)據(jù)的關(guān)鍵用戶。

2.1 有向加權(quán)網(wǎng)絡(luò)

2.2 關(guān)鍵節(jié)點的識別

關(guān)鍵節(jié)點的識別實質(zhì)上就是尋找網(wǎng)絡(luò)中最有影響力的節(jié)點。本文在參考前人研究的基礎(chǔ)上，認為通信數(shù)據(jù)關(guān)鍵節(jié)點的識別不僅需要考慮節(jié)點所在的位置和鄰居的數(shù)目，而且還需要考慮鄰居的網(wǎng)絡(luò)拓撲結(jié)構(gòu)的特征量。

2.3 基于改進PageRank算法的關(guān)鍵用戶識別

改進PageRank算法的關(guān)鍵用戶識別的主要思想如下：

（1）構(gòu)造以用戶通信數(shù)據(jù)為基礎(chǔ)的復(fù)雜網(wǎng)絡(luò)來模擬現(xiàn)實的用戶通信交往網(wǎng)絡(luò)。

（2）把評判用戶聯(lián)系的“緊密度”問題轉(zhuǎn)化為評判每個用戶的PageRank值（即用戶重要性的排名）[5]，用戶的PageRank值算法如下：

其中，Ti為撥打給用戶A的第i個主叫號碼；INA為用戶A的主叫號碼總數(shù)；wAi為Ti指向A的權(quán)值（也稱邊權(quán)值，計算方式為主叫號碼Ti撥打給A的PageRank值除以所有撥打給A的主叫號碼的PageRank值）。以Ti為主叫號碼撥打給包括A在內(nèi)有M1， M2， …， Mm等mi個被叫號碼。INj為撥打給Mj的主叫號碼總數(shù)；wmj為Ti撥打給Mj的權(quán)值；N為移動網(wǎng)絡(luò)用戶的數(shù)量。wTi為主叫號碼Ti撥打給A的通話時長與以Ti為主叫號碼撥打給包括A在內(nèi)有M1， M2， …， Mm等mi個被叫號碼的時長的比例。

通信數(shù)據(jù)的復(fù)雜網(wǎng)絡(luò)用戶撥打關(guān)系示意圖如圖1所示：

3 基于移動通信數(shù)據(jù)的關(guān)鍵用戶預(yù)測

3.1 關(guān)鍵用戶預(yù)測流程

本文基于移動通信數(shù)據(jù)的關(guān)鍵用戶預(yù)測流程如下：

（1）獲取用戶呼叫詳單信息，提取與本文相關(guān)的字段，如主叫號碼、被叫號碼、通話開始時間、通話結(jié)束時間等。根據(jù)上述字段建立移動通信用戶的呼叫交往圈。

（2）通過TF-IDF提取有效的用戶交往圈[6]。采用TF-IDF算法把一些公共號碼、快遞號碼、送餐號碼等非重要通話群體剔除。

（3）基于改進PageRank算法的關(guān)鍵用戶識別。綜合考慮網(wǎng)絡(luò)節(jié)點所在的位置，并根據(jù)網(wǎng)絡(luò)節(jié)點以及該節(jié)點的鄰居節(jié)點的鏈接關(guān)系對邊賦予不同的權(quán)重，再通過用戶之間的不均勻通信關(guān)系提高關(guān)鍵節(jié)點的PageRank值，保證核心節(jié)點重要性的計算。

（4）根據(jù)與核心用戶相連接的用戶的拓撲關(guān)系來確定“中間人”，以識別網(wǎng)絡(luò)中的關(guān)鍵用戶。

3.2 關(guān)鍵用戶的識別過程

（1）移動用戶通信數(shù)據(jù)的提取，構(gòu)建有向權(quán)值的用戶通信社交網(wǎng)絡(luò)

根據(jù)本文的需求，提取用戶呼叫詳單的關(guān)鍵字段，包括主叫號碼、被叫號碼、通話、通話開始時間和通話結(jié)束時間。根據(jù)用戶的通話對，對每一對用戶的通話信息進行提取，通信網(wǎng)絡(luò)的節(jié)點由主叫用戶和被叫用戶組成，通信用戶的邊從主叫用戶連向被叫用戶，邊權(quán)值則是由網(wǎng)絡(luò)的拓撲結(jié)構(gòu)決定的，不僅需要考慮用戶的通話次數(shù)，而且還需要考慮用戶的通話時長。用戶通話數(shù)據(jù)關(guān)鍵字段提取示例如表1所示：

（2）通過TF-IDF提取有效的用戶交往圈

有效交往圈是指與一個移動號碼發(fā)生通信行為且具有相對重要和緊密程度的對端號碼集合[7]。本文采用TF-IDF進行改進，在統(tǒng)計通話次數(shù)的基礎(chǔ)上，結(jié)合通話時長和通話逆頻率計算通信用戶之間的“重要性”，以此來甄別有效用戶。那么，用戶T的有效交往圈公式為：

TF-IDFTA=wTA×tfTA×idfTA （4）

其中，wTA為用戶T和用戶A在一段時間內(nèi)的總通話時長與用戶T和所有用戶在一段時間內(nèi)的總通話時長的占比；tfTA為用戶T和用戶A的通話頻率；idfTA為用戶T和所有用戶的通話逆頻率。

（3）基于改進PageRank算法的關(guān)鍵用戶識別

首先通過公式（3）得出所有通信用戶在整個網(wǎng)絡(luò)中的重要性，然后根據(jù)重要性從大到小進行排名，選取TopN進行核心人物的判定，再通過來判定通信網(wǎng)絡(luò)的“中間人”，以完善通信網(wǎng)絡(luò)關(guān)鍵用戶的預(yù)測方法。

4 實驗分析

4.1 數(shù)據(jù)來源

本文以河北省某市移動運營商的用戶詳單數(shù)據(jù)為例進行關(guān)鍵用戶預(yù)測，提取該市具有標(biāo)識的2萬用戶8月至10月的數(shù)據(jù)，該數(shù)據(jù)量大小為3 GB左右。通過將上述數(shù)據(jù)進行關(guān)鍵字段的提取之后，把隨機抽取的所有用戶70%的數(shù)據(jù)作為訓(xùn)練集，再把剩下的數(shù)據(jù)作為測試集。通過分析處理具有標(biāo)識的數(shù)據(jù)，進行關(guān)鍵用戶預(yù)測。

4.2 實驗對比

本文對實驗數(shù)據(jù)采取以下方法進行處理：

（1）通過改進PageRank算法識別關(guān)鍵用戶。

（2）結(jié)合TF-IDF和改進PageRank算法識別關(guān)鍵用戶，再重復(fù)10次實驗對比兩者的平均準確率，以此證明哪種方法具有一定的優(yōu)越性。

由圖2可知，不做有效用戶圈篩選的算法在預(yù)測關(guān)鍵用戶的準確率上比篩選有效用戶圈要低。因此，結(jié)合TF-IDF能夠在一定程度上剔除公共號碼、快遞號碼等的干擾，從而提高關(guān)鍵用戶預(yù)測的準確率。

5 結(jié)束語

本文基于真實的移動通信數(shù)據(jù)的用戶通話拓撲結(jié)構(gòu)提出了關(guān)鍵用戶預(yù)測的模型，首先根據(jù)通信數(shù)據(jù)的獨特性采用TF-IDF提取有效用戶圈以去除噪音，然后采用改進PageRank算法預(yù)測關(guān)鍵用戶。該方法從兩個方面衡量網(wǎng)絡(luò)節(jié)點的重要性：一是網(wǎng)絡(luò)節(jié)點所在的位置；二是該節(jié)點的鄰居節(jié)點的鏈接關(guān)系，從網(wǎng)絡(luò)全局的角度得到網(wǎng)絡(luò)的關(guān)鍵用戶。并通過實驗證明，結(jié)合TF-IDF和改進PageRank算法與基于改進PageRank算法相比具有較高的準確率。

參考文獻：

[1] 周漩，張鳳鳴，李克武，等. 利用重要度評價矩陣確定復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點[J]. 物理學(xué)報， 2012，61（5）： 1-7.

[2] 李玉華，賀人貴，鐘開，等. 動態(tài)加權(quán)網(wǎng)絡(luò)中節(jié)點重要度評估[J]. 計算機科學(xué)與探索， 2012，6（2）： 134-143.

[3] 張益. 一種定量評估復(fù)雜網(wǎng)絡(luò)節(jié)點重要度的算法[J]. 計算機工程， 2011，37（20）： 87-88.

[4] 唐俊. 復(fù)雜網(wǎng)絡(luò)在新聞網(wǎng)頁關(guān)鍵詞提取中的應(yīng)用[J]. 云南民族大學(xué)學(xué)報： 自然科學(xué)版， 2012，21（4）： 305-308.

[5] 杜翠鳳，王俊. 基于改進PageRank算法的城市軌道交通站點選址規(guī)劃[J]. 移動通信， 2016，40（14）： 60-65.

[6] 蔣仕寶，陳少權(quán). 基于呼叫指紋的重入網(wǎng)識別算法研究[J]. 移動通信， 2016，40（22）： 27-30.

[7] 陸菁. 基于移動通信交往圈的家庭用戶識別研究[D]. 上海： 上海交通大學(xué)， 2014.

[8] 蘇曉萍，宋玉蓉. 利用鄰域“結(jié)構(gòu)洞”尋找社會網(wǎng)絡(luò)中最具影響力節(jié)點[J]. 物理學(xué)報， 2015，64（2）： 1-11.

[9] 陳勇，胡愛群，胡駿，等. 通信網(wǎng)中最重要節(jié)點的確定方法[J]. 高技術(shù)通訊， 2004，14（1）： 21-24.

[10] 駱世順. 基于社團結(jié)構(gòu)和自信息的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測算法研究[D]. 蘭州： 蘭州大學(xué)， 2016.