郭 喆，王芙蓉，黃本雄

(華中科技大學(xué)電子與信息工程系，湖北 武漢 430074)

隨著通信技術(shù)的不斷發(fā)展，通信網(wǎng)絡(luò)已經(jīng)深入到人們的日常生活中。根據(jù)工信部2010年3月的統(tǒng)計(jì)數(shù)據(jù)［1］，我國目前固定電話用戶有3．1億戶，移動(dòng)電話用戶有7．7億戶。研究用戶行為對(duì)網(wǎng)絡(luò)規(guī)劃和優(yōu)化，客戶關(guān)系管理，市場(chǎng)營(yíng)銷等方面有重要意義。電信用戶行為主要指用戶的通信行為，包括通信的時(shí)間、對(duì)象、地點(diǎn)和應(yīng)用何種業(yè)務(wù)等。用戶行為能夠刻畫用戶的特征，從底層協(xié)議設(shè)計(jì)到各種電信應(yīng)用服務(wù)都與用戶的行為具有緊密的聯(lián)系。文獻(xiàn)［2－4］對(duì)移動(dòng)用戶的移動(dòng)性進(jìn)行了研究，指出用戶的移動(dòng)性符合冪率分布，移動(dòng)用戶的運(yùn)動(dòng)有很強(qiáng)的規(guī)律性，其移動(dòng)性在很大程度上是可預(yù)測(cè)的。文獻(xiàn)［5］從社會(huì)網(wǎng)絡(luò)的角度研究人們的談話內(nèi)容以確定其社會(huì)屬性。文獻(xiàn)［6］研究了電信用戶通話時(shí)長(zhǎng)規(guī)律，發(fā)現(xiàn)電信用戶的通話時(shí)長(zhǎng)符合對(duì)數(shù)正態(tài)分布或多個(gè)對(duì)數(shù)正態(tài)分布的加權(quán)和。以上研究從通信的時(shí)間和地點(diǎn)等方面對(duì)用戶行為進(jìn)行了分析和建模，為進(jìn)一步挖掘用戶特征提供了重要特征數(shù)據(jù)和結(jié)論。

研究用戶的行為不得不考慮用戶之間的相互影響，為更方便準(zhǔn)確地描述用戶之間的聯(lián)系和影響，可以將電信用戶看作社會(huì)網(wǎng)絡(luò)中的實(shí)體，用戶之間的通信看作點(diǎn)與點(diǎn)之間的鏈接。社會(huì)網(wǎng)絡(luò)具有動(dòng)態(tài)性，表現(xiàn)在隨時(shí)間推移有新的實(shí)體和鏈接加入，舊的實(shí)體和鏈接消失，這一點(diǎn)與通信網(wǎng)絡(luò)的特點(diǎn)也非常相符。社會(huì)網(wǎng)絡(luò)的鏈接挖掘近年成為研究的一個(gè)熱點(diǎn)。文獻(xiàn)［7］對(duì)鏈接挖掘作了綜述性介紹。對(duì)于鏈接的研究主要有兩方面，一方面是推測(cè)哪些實(shí)體在未來可能產(chǎn)生新鏈接，也就是鏈接預(yù)測(cè)問題。文獻(xiàn)［8］提出鄰近度的方法，文獻(xiàn)［9］用關(guān)系馬爾科夫網(wǎng)絡(luò)(RMN)進(jìn)行鏈接預(yù)測(cè)，文獻(xiàn)［10］比較了各種預(yù)測(cè)方法，文獻(xiàn)［11］用統(tǒng)計(jì)關(guān)系學(xué)習(xí)對(duì)鏈接預(yù)測(cè)進(jìn)行建模。另一方面是鏈接的穩(wěn)定性預(yù)測(cè)，這是鏈接挖掘中一個(gè)新的課題。鏈接的穩(wěn)定性預(yù)測(cè)指的是對(duì)當(dāng)前時(shí)間窗口內(nèi)已經(jīng)存在的鏈接進(jìn)行穩(wěn)定性評(píng)價(jià)，以預(yù)測(cè)在下一時(shí)間窗口該鏈接是否會(huì)消失。在通信網(wǎng)絡(luò)中，穩(wěn)定性預(yù)測(cè)更有實(shí)用意義，例如可以預(yù)測(cè)用戶流失，或者進(jìn)行精確有效的業(yè)務(wù)推薦等，此外，對(duì)于網(wǎng)絡(luò)資源分配優(yōu)化，用戶關(guān)系管理等方面也有幫助。

筆者對(duì)電信網(wǎng)絡(luò)鏈接的穩(wěn)定性進(jìn)行了研究，建立鏈接穩(wěn)定性預(yù)測(cè)模型，并提出一種基于鏈接權(quán)重和節(jié)點(diǎn)度的評(píng)價(jià)方法。通過在大型通信網(wǎng)絡(luò)中的檢驗(yàn)，該方法具有很高的準(zhǔn)確性。

1 鏈接預(yù)測(cè)方法

用一個(gè)無向圖G=＜V，E＞來表示社會(huì)網(wǎng)絡(luò)，V為頂點(diǎn)集合，E為邊集合。鏈接相當(dāng)于邊e(u，v)∈E，其中 u，v為邊 e的兩個(gè)頂點(diǎn)，u，v∈V。對(duì)于兩個(gè)不同的時(shí)間 t＜t'，子圖 G［t，t'］包含在該時(shí)間內(nèi)所有出現(xiàn)過的邊，其集合為E［t，t'］。鏈接預(yù)測(cè)的問題是對(duì)4個(gè)不同的時(shí)間t0＜t1＜t2＜t3，由某種預(yù)測(cè)算法能夠得出在子圖 G［t2，t3］中存在，在子圖G［t0，t1］中不存在的邊，即預(yù)測(cè)會(huì)新出現(xiàn)哪些邊。為便于理解和計(jì)算，所有的預(yù)測(cè)方法都可以看作是一種打分方法，即對(duì)每一條不存在的邊進(jìn)行打分，得分越高則在將來這條邊出現(xiàn)的可能性越大。

1．1 基于共鄰點(diǎn)的方法

對(duì)于一個(gè)節(jié)點(diǎn)x，用Г(x)來表示x的鄰節(jié)點(diǎn)集合。在一般情況下，兩個(gè)并不直接相連的節(jié)點(diǎn)x，y，如果有很多相同的鄰節(jié)點(diǎn)，那么它們之間在將來可能出現(xiàn)鏈接。最簡(jiǎn)單的打分方法就是看它們之間重合的鄰居節(jié)點(diǎn)個(gè)數(shù)，即:

1．2 索爾頓指數(shù)

索爾頓指數(shù)定義如下:

式中，k(x)為節(jié)點(diǎn)x的度(x鄰居節(jié)點(diǎn)個(gè)數(shù))。

1．3 雅克比指數(shù)

該指數(shù)是由雅克比在100多年前提出來的，其定義如下:

1．4 索倫森指數(shù)

該指數(shù)通常使用在生態(tài)學(xué)領(lǐng)域，其定義如下:

1．5 Adamic－Adar指數(shù)

這種計(jì)算方法是在單純計(jì)數(shù)共同鄰居節(jié)點(diǎn)個(gè)數(shù)的基礎(chǔ)上加入了權(quán)重的概念，對(duì)于兩個(gè)節(jié)點(diǎn)的共有鄰居節(jié)點(diǎn)，如果度越小，則這種鄰居節(jié)點(diǎn)具有專一性，從而獲得較高的權(quán)重，這種專一的共同鄰居節(jié)點(diǎn)越多得分越高［12］。其定義如下:

1．6 擇優(yōu)聯(lián)結(jié)

擇優(yōu)聯(lián)結(jié)的機(jī)制可用于自由尺度網(wǎng)絡(luò)的演化(例如按照冪律分布的網(wǎng)絡(luò))［13］，節(jié)點(diǎn)x的一個(gè)新鏈接產(chǎn)生概率正比于該節(jié)點(diǎn)的度k(x)，那么兩個(gè)節(jié)點(diǎn)之間產(chǎn)生新鏈接的評(píng)分標(biāo)志為:

1．7 卡茨指數(shù)

這是一種基于全路徑的方法，該方法找出節(jié)點(diǎn)x與y之間所有的路徑，對(duì)每一條路徑進(jìn)行一次評(píng)分，然后相加。路徑越短評(píng)分越高，表示為:

1．8 SimRank

SimRank使用一種遞歸算法來計(jì)算兩個(gè)節(jié)點(diǎn)之間的相似度，并以此相似度作為兩節(jié)點(diǎn)的打分，其定義如下:

其中，sxx=1，γ∈［0，1］。SimRank也可以表述為一種隨機(jī)游走模型，即兩個(gè)節(jié)點(diǎn)之間的相似度為γl。其中，l為一隨機(jī)變量，表示任意時(shí)刻從節(jié)點(diǎn)x隨機(jī)游走到節(jié)點(diǎn)y的步數(shù)。

上述方法基本上分為兩類，一類是基于共同鄰節(jié)點(diǎn)的方法(即前6種方法)，一類為基于路徑的方法(即后兩種方法)?；诼窂降姆椒ㄍ枰@得全網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，計(jì)算全路徑需要很大的計(jì)算量，在實(shí)際應(yīng)用中受到很多限制，但其準(zhǔn)確性較高。基于共同鄰節(jié)點(diǎn)的方法所需要的信息不多，計(jì)算量也不大，應(yīng)用更為廣泛。對(duì)于鏈接穩(wěn)定性其圖論模型的基礎(chǔ)不變，這些方法都可以借鑒，筆者將用這些方法來對(duì)鏈接的穩(wěn)定性進(jìn)行打分，從而確定鏈接的穩(wěn)定性。

在電信網(wǎng)絡(luò)中一個(gè)現(xiàn)實(shí)情況是幾家電信運(yùn)營(yíng)商并存，出于商業(yè)原因各運(yùn)營(yíng)商之間的數(shù)據(jù)并不共享，于是單一運(yùn)營(yíng)商并不能完整獲知電信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。如圖1所示，運(yùn)營(yíng)商A只能獲得自己網(wǎng)絡(luò)的用戶(以下稱為本網(wǎng)用戶)信息，而其他運(yùn)營(yíng)商的用戶(以下稱為外網(wǎng)用戶)雖然與本網(wǎng)用戶有聯(lián)系，但其信息無法獲得。這就給研究工作帶來了巨大的挑戰(zhàn):不管是基于共同鄰節(jié)點(diǎn)還是基于路徑的方法，都不能直接應(yīng)用于電信網(wǎng)絡(luò)。例如，從圖1可以看出，邊a連接著本網(wǎng)用戶x與外網(wǎng)用戶y，運(yùn)營(yíng)商A無法獲知y的度，也無法計(jì)算x與y的全路徑。這并不意味著在現(xiàn)有信息條件下運(yùn)營(yíng)商不能對(duì)鏈接的穩(wěn)定性做出判斷。

2 權(quán)重和度對(duì)電信網(wǎng)路鏈接穩(wěn)定性的影響

所采用的數(shù)據(jù)為某省會(huì)城市電信公司的5 000名CDMA用戶4個(gè)月(2010年1月到4月)的通話清單，出于個(gè)人隱私和保密考慮，這些用戶的個(gè)人信息和聯(lián)系人信息已經(jīng)匿名處理。為了使研究具有盡量客觀的結(jié)論，5 000名CDMA用戶為隨機(jī)選取。1月和2月的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，3月和4月的數(shù)據(jù)作為測(cè)試數(shù)據(jù)。

圖1 電信網(wǎng)絡(luò)聯(lián)系人拓?fù)鋱D

鏈接穩(wěn)定性和鏈接預(yù)測(cè)最大的不同在于，鏈接穩(wěn)定性研究的是已存在的鏈接，而鏈接預(yù)測(cè)則是預(yù)測(cè)現(xiàn)在還不存在的鏈接在將來是否會(huì)出現(xiàn)，在實(shí)際應(yīng)用中這兩個(gè)問題同等重要。

筆者統(tǒng)計(jì)了d(u)在2010年1月和2月的比值，并對(duì)該比值求對(duì)數(shù)，即:

其中，Ctcu為用戶u的度變化系數(shù)(以下簡(jiǎn)稱變化系數(shù))，顯然，如果兩個(gè)月的度差異越小，則變化系數(shù)越接近0。這5 000個(gè)用戶的變化系數(shù)分布情況如圖2所示。

圖2中曲線為高斯擬合曲線:

擬合的結(jié)果:a=0．04，b=0．005，c=0．14。

從實(shí)際圖形和擬合結(jié)果都可以看出，鏈接減少和增多的情況大致相同，這也說明如果在已知全拓?fù)浣Y(jié)構(gòu)信息的前提下，鏈接預(yù)測(cè)和鏈接穩(wěn)定性研究思路大致相同。

圖2 電信用戶鏈接變化情況

根據(jù)人們?nèi)粘Ｍㄔ捔?xí)慣的特點(diǎn)，有兩點(diǎn)值得注意:一是某段時(shí)間內(nèi)聯(lián)系某個(gè)聯(lián)系人的次數(shù);二是某段時(shí)間內(nèi)與多少個(gè)聯(lián)系人聯(lián)系過。在圖論模型里，前者可以看成是某條鏈接的權(quán)重，聯(lián)系某個(gè)聯(lián)系人次數(shù)越多，這條鏈接的權(quán)重越高;后者可看作這個(gè)節(jié)點(diǎn)的度，不同聯(lián)系人越多，這個(gè)節(jié)點(diǎn)的度越高。在限制條件下這里僅取鏈接兩個(gè)節(jié)點(diǎn)中的一個(gè)節(jié)點(diǎn)進(jìn)行度的測(cè)量。

在圖論模型中，節(jié)點(diǎn)u、v代表兩個(gè)用戶，如果他們?cè)跁r(shí)間［t0，t1］內(nèi)有聯(lián)系，則鏈接 e=(u，v)在子圖 G［t0，t1］中存在，鏈接 e的權(quán)重 w 為 u、v的聯(lián)系次數(shù)。u的度為u的鄰居節(jié)點(diǎn)的個(gè)數(shù)，即用戶的聯(lián)系人個(gè)數(shù)，用d(u)表示。

(1)鏈接權(quán)重的影響。以邊權(quán)重w為變量，P{w=k}表示當(dāng)權(quán)重為k(k=1，2，…)時(shí)穩(wěn)定性，即:

式中:E［t0，t1］、E［t2，t3］分別為子圖 G［t0，t1］、G［t2，t3］的邊集;Ew=k表示權(quán)重為 k 的邊集;|*|為集合內(nèi)元素的個(gè)數(shù)。

筆者統(tǒng)計(jì)了5 000個(gè)電信用戶構(gòu)成的電信網(wǎng)絡(luò)的鏈接權(quán)重的穩(wěn)定性，如圖3所示。

圖3 鏈接權(quán)重對(duì)鏈接穩(wěn)定性的影響

可以看出隨著鏈接權(quán)重w的增加，穩(wěn)定性也增加，邊權(quán)重和穩(wěn)定性有正相關(guān)關(guān)系，可用指數(shù)函數(shù)f(k)=1 －e－λk來擬合 P{w=k}的概率，其中λ = －0．177，k為鏈接權(quán)重。

(2)節(jié)點(diǎn)度的影響。從上述的各種方法來看，節(jié)點(diǎn)u、v之間的鏈接穩(wěn)定性與這兩個(gè)節(jié)點(diǎn)的度有關(guān)系，但是由于實(shí)際條件僅能獲知其中一個(gè)節(jié)點(diǎn)的度，故選擇一條鏈接中任一個(gè)節(jié)點(diǎn)u，研究u的所有鏈接的平均穩(wěn)定性與d(u)的關(guān)系，u的平均鏈接穩(wěn)定性記為sta(u)，定義如下:

其中，Eu為含節(jié)點(diǎn)u的邊集。統(tǒng)計(jì)的5 000個(gè)電信用戶的d(u)和sta(u)的關(guān)系如圖4所示。

圖4 節(jié)點(diǎn)度對(duì)鏈接穩(wěn)定性的影響

由于只測(cè)量了其中一個(gè)節(jié)點(diǎn)的度，因此穩(wěn)定性的波動(dòng)比較大，但仍然呈現(xiàn)一定的規(guī)律性。從圖4可以看出，節(jié)點(diǎn)度在40以下時(shí)，隨著度的增加平均穩(wěn)定性也增加，度在40以上時(shí)，平均穩(wěn)定性在0．39左右波動(dòng)(0．39為全部鏈接的平均穩(wěn)定性)。筆者用指數(shù)函數(shù)來擬合。

其中，a=0．177，μ = －0．058 9，d 為節(jié)點(diǎn)u 的度。綜合圖3和圖4，可得一個(gè)電信用戶鏈接穩(wěn)定性計(jì)算模型:

其中，stae為鏈接e的穩(wěn)定性打分;w0為調(diào)節(jié)因子，介于0到1之間;f(k)為邊權(quán)重?cái)M合函數(shù);k為該鏈接的權(quán)重;f(d)為節(jié)點(diǎn)度擬合函數(shù);d為已知的一個(gè)節(jié)點(diǎn)度。用該模型對(duì)鏈接進(jìn)行打分，得分越高則穩(wěn)定性越高。根據(jù)實(shí)際數(shù)據(jù)，f(k)的分辨度較f(d)要好，因此調(diào)節(jié)因子一般大于0．5。

3 結(jié)果評(píng)價(jià)

筆者將提出的模型與基于共同鄰節(jié)點(diǎn)各種方法進(jìn)行對(duì)比，對(duì)比的機(jī)制如下:按照某種方法對(duì)所有考察的邊進(jìn)行打分后，按照得分高低順序進(jìn)行排序，然后將得分平均分為若干段，計(jì)算每個(gè)分段的平均穩(wěn)定性，得到一個(gè)序列。如果該方法具有較高的可信度，則該序列應(yīng)該是單調(diào)下降的，且各相鄰分段之間有足夠的差異，差異越大越好。

這里將筆者提出的方法與所介紹的各種鏈接預(yù)測(cè)方法進(jìn)行比較。將打分按照從高到低平均分為10段，調(diào)節(jié)因子w0取0．8。為了更直觀地比較各方法的性能，給出了變化曲線，如圖5所示。訓(xùn)練集的鏈接共有15 689，測(cè)試集的鏈接共有16 102，其中公有鏈接數(shù)為6 118，平均穩(wěn)定性為0．39。在圖5中，筆者提出的方法用粗線條繪出，平均穩(wěn)定性用細(xì)實(shí)線繪出。

圖5 各種鏈接方法的穩(wěn)定性比較

從圖5可以看出，筆者提出的方法性能最優(yōu)，其曲線斜率最大，且沒有得分低而穩(wěn)定性高的情況(打分順序顛倒)，在其他的方法中，共鄰點(diǎn)的方法性能較好，索爾頓指數(shù)和索倫森指數(shù)性能較差。這是因?yàn)樵陔娦啪W(wǎng)絡(luò)中隨著節(jié)點(diǎn)度的增加，鏈接穩(wěn)定性是增加的，但是索爾頓指數(shù)和索倫森指數(shù)卻認(rèn)為節(jié)點(diǎn)度增加會(huì)導(dǎo)致穩(wěn)定性降低，這兩種方法不適用電信網(wǎng)絡(luò)。另外，各種方法都存在順序顛倒的情況。

4 結(jié)論

筆者對(duì)電信用戶鏈接的穩(wěn)定性進(jìn)行了分析，得到一種能夠準(zhǔn)確評(píng)價(jià)電信用戶鏈接穩(wěn)定性的方法，將該方法與經(jīng)典鏈接預(yù)測(cè)的方法進(jìn)行對(duì)比，該方法具有較高的準(zhǔn)確性，應(yīng)用也很方便，不需要大規(guī)模的計(jì)算。分析結(jié)果可歸納為以下幾點(diǎn):

(1)兩個(gè)不同時(shí)間段電信用戶聯(lián)系人數(shù)量增多和減少的概率基本相等，在不同月份之間的聯(lián)系人數(shù)量比值求對(duì)數(shù)的概率分布可以用均值為0的高斯函數(shù)近似;

(2)電信網(wǎng)絡(luò)鏈接穩(wěn)定性和鏈接權(quán)重有正相關(guān)性，聯(lián)系頻度越高該聯(lián)系人的穩(wěn)定度越高，當(dāng)聯(lián)系頻度超過6次時(shí)，穩(wěn)定度大于0．7，當(dāng)聯(lián)系頻度超過15次時(shí)，穩(wěn)定度大于0．9，其關(guān)聯(lián)性可用指數(shù)函數(shù)近似;

(3)鏈接穩(wěn)定性和節(jié)點(diǎn)度有正相關(guān)性，但當(dāng)節(jié)點(diǎn)度超過40，鏈接穩(wěn)定性接近整體鏈接平均穩(wěn)定性，其關(guān)聯(lián)性可用指數(shù)函數(shù)近似;

(4)電信網(wǎng)絡(luò)有其特殊性，即運(yùn)營(yíng)商僅能獲知部分節(jié)點(diǎn)的拓?fù)湫畔ⅲ虼嘶谌窂郊逆溄宇A(yù)測(cè)方法不能直接應(yīng)用到鏈接穩(wěn)定性判斷，筆者提出的方法具有較高的準(zhǔn)確性和較佳的實(shí)用性。

筆者的結(jié)論對(duì)于電信用戶的行為分析特別是聯(lián)系人方面的行為分析具有重要意義，例如對(duì)于網(wǎng)絡(luò)底層而言可以用于基于移動(dòng)節(jié)點(diǎn)通信概率的網(wǎng)絡(luò)資源分配和物理層協(xié)議設(shè)計(jì)，對(duì)于網(wǎng)絡(luò)應(yīng)用層有助于研究用戶之間的社會(huì)關(guān)系，更好地進(jìn)行客戶關(guān)系管理等。

［1］ 中華人民共和國工業(yè)和信息化部．2010年3月統(tǒng)計(jì)數(shù)據(jù)［EB/OL］．［2010 －11 －01］．http://www．miit．gov．cn/．2010．3．

［2］ TAM W M，LAU F C M，TSE C K．Traffic analysis of a mobile cellular system based on a scale－free user network and a power－law－distributed mobility model［C］//IEEE Asia Pacific Conference on Circuits and Systems．［S．l．］:［s．n．］，2008:1120 － 1123．

［3］ GONZALEZ M，HIDALGO C A，BARABSI A L．Understanding individual human mobility patterns［J］．Nature，2008(453):779 －782．

［4］ SONG C，QU Z，BLUMM N，et al．Limits of predictability in human mobility［J］．Science，2010(327):1018－1021．

［5］ APOLLONI A，CHANNAKESHAVA K，DURBECK L，et al．Study of information diffusion over a realistic social network model［C］//International Conference on Computational Science and Engineering．［S．l．］:［s．n．］:2009:675 －682．

［6］ 張奇支，廖建新．移動(dòng)智能網(wǎng)用戶的通話時(shí)長(zhǎng)模型分析［J］．高技術(shù)通訊，2006，16(4):1 －4．

［7］ GETOOR L，DIEHL C．Link mining:a survey［J］．Sigkdd Explorations，2005，7(2):3 －12．

［8］ LIBEN － NOWELL D，KLEINBERG J．The link prediction problem for social networks［C］//Proceedings of the 12th International Conference on Information and Knowledge Management．New York:ACM Press，2003:556－559．

［9］ TASKAR B，WONG M F，ABBEEL P，et al．Link prediction in relational data［C］//Proceedings of Neural Information Processing Systems．Cambridge:MIT Press，2004:659 －666．

［10］ HASAN M A，CHAOJI V，SALEM S，et al．Link prediction using supervised learning［C］//Proceedings of the Fourth Workshop on Link Analysis，Counterterrorism and Security，Philadelphia．PA:SIAM Press，2006:443－461．

［11］ POPESCUL A，UNGAR L H．Statistical relational learning for link prediction［C］//Proceedings of the Workshop on Learning Statistical Models from Relational Data at I JCAI．New York:ACM Press，2003:81 －90．

［12］ ADAMIC L A，ADAR E．Friends and neighbors on the Web［J］．Social Networks，2003，25(3):211 －230．

［13］ NEWMAN M E J．Clustering and preferential attachment in growing networks［J］．Physical Review E，2001，64(2):1 －4．