一種移動通信網絡的關鍵用戶預測方法

張金龍

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

【關鍵詞】關鍵用戶 TF-IDF 改進PageRank 有向加權網絡

1 引言

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

2 復雜網絡的相關理論研究

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

2.1 有向加權網絡

2.2 關鍵節點的識別

關鍵節點的識別實質上就是尋找網絡中最有影響力的節點。本文在參考前人研究的基礎上，認為通信數據關鍵節點的識別不僅需要考慮節點所在的位置和鄰居的數目，而且還需要考慮鄰居的網絡拓撲結構的特征量。

2.3 基于改進PageRank算法的關鍵用戶識別

改進PageRank算法的關鍵用戶識別的主要思想如下：

（1）構造以用戶通信數據為基礎的復雜網絡來模擬現實的用戶通信交往網絡。

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

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

通信數據的復雜網絡用戶撥打關系示意圖如圖1所示：

3 基于移動通信數據的關鍵用戶預測

3.1 關鍵用戶預測流程

本文基于移動通信數據的關鍵用戶預測流程如下：

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

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

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

（4）根據與核心用戶相連接的用戶的拓撲關系來確定“中間人”，以識別網絡中的關鍵用戶。

3.2 關鍵用戶的識別過程

（1）移動用戶通信數據的提取，構建有向權值的用戶通信社交網絡

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

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

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

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

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

（3）基于改進PageRank算法的關鍵用戶識別

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

4 實驗分析

4.1 數據來源

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

4.2 實驗對比

本文對實驗數據采取以下方法進行處理：

（1）通過改進PageRank算法識別關鍵用戶。

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

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

5 結束語

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

參考文獻：

[1] 周漩，張鳳鳴，李克武，等. 利用重要度評價矩陣確定復雜網絡關鍵節點[J]. 物理學報， 2012，61（5）： 1-7.

[2] 李玉華，賀人貴，鐘開，等. 動態加權網絡中節點重要度評估[J]. 計算機科學與探索， 2012，6（2）： 134-143.

[3] 張益. 一種定量評估復雜網絡節點重要度的算法[J]. 計算機工程， 2011，37（20）： 87-88.

[4] 唐俊. 復雜網絡在新聞網頁關鍵詞提取中的應用[J]. 云南民族大學學報： 自然科學版， 2012，21（4）： 305-308.

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

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

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

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

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

[10] 駱世順. 基于社團結構和自信息的復雜網絡鏈路預測算法研究[D]. 蘭州： 蘭州大學， 2016.