項(xiàng)英倬，徐正國(guó)，游凌

（盲信號(hào)處理國(guó)家重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041）

1 引言

通信網(wǎng)絡(luò)中的指控信息流是指一條指控信息在網(wǎng)絡(luò)中傳播所經(jīng)過(guò)的一條有向路徑，比如節(jié)點(diǎn)A將一個(gè)條指控傳給了節(jié)點(diǎn)B，命令B 去通知節(jié)點(diǎn)C某個(gè)事情，那么可以認(rèn)為一條指令由A 發(fā)出，經(jīng)過(guò)B 到達(dá)了C，A—B—C 構(gòu)成了一條指控信息流。通信網(wǎng)絡(luò)中指控信息流在僵尸網(wǎng)絡(luò)發(fā)現(xiàn)、入侵檢測(cè)，甚至是對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)之間關(guān)系的挖掘都具有重要的意義。一般來(lái)說(shuō)，指控信息流的挖掘方法大多依賴于雙方通信的內(nèi)容。比如，在僵尸網(wǎng)絡(luò)的挖掘中，文獻(xiàn)[1-2]通過(guò)提取數(shù)據(jù)內(nèi)容和屬性的指控特征，動(dòng)態(tài)分析系統(tǒng)執(zhí)行惡意樣本所產(chǎn)生的流量，發(fā)現(xiàn)僵尸網(wǎng)絡(luò)或惡意軟件中的指控信息流。文獻(xiàn)[3-5]給出了多組通信數(shù)據(jù)的統(tǒng)計(jì)特征，并據(jù)此區(qū)分網(wǎng)絡(luò)中的指控信息流和正常的流量。文獻(xiàn)[6]使用語(yǔ)義模型來(lái)分析通信流量中的負(fù)載，并以此對(duì)信息流的安全性進(jìn)行分析。而社交網(wǎng)絡(luò)中，文獻(xiàn)[7-12]通過(guò)Hashtags、主題信息、內(nèi)容信息、轉(zhuǎn)發(fā)時(shí)延、網(wǎng)絡(luò)連接等屬性，利用機(jī)器學(xué)習(xí)中貝葉斯網(wǎng)絡(luò)等有監(jiān)督的方法學(xué)習(xí)網(wǎng)絡(luò)中指控信息流的特征。這些方法均假設(shè)可以直接觀測(cè)到通信的全部?jī)?nèi)容或者部分內(nèi)容，然而在許多場(chǎng)景中無(wú)法獲取到通信的內(nèi)容，僅知道通信發(fā)生的時(shí)間，例如加密通信數(shù)據(jù)中指控信息流的挖掘問(wèn)題。針對(duì)這種情況，目前并沒(méi)有有效的算法，本文將針對(duì)通信內(nèi)容未知情況下的指控信息流挖掘問(wèn)題進(jìn)行研究，該問(wèn)題的難點(diǎn)在于網(wǎng)絡(luò)中存在著大量的非指控信息流（背景流量），而指控信息流通常淹沒(méi)在其中，難以挖掘。

2 節(jié)點(diǎn)通信行為模型

2.1 問(wèn)題描述

為了更好地介紹本文研究的問(wèn)題和模型，下面給出一些概念的定義。

定義1通信網(wǎng)絡(luò)G(V,E)中的一個(gè)指控信息流c指一條指控信息從單一的節(jié)點(diǎn)出發(fā)，傳播所經(jīng)過(guò)的所有節(jié)點(diǎn)及有向路徑構(gòu)成的聯(lián)通子圖。

定義2通信網(wǎng)絡(luò)G(V,E)中，節(jié)點(diǎn)vi的行為時(shí)序ai指觀測(cè)到的節(jié)點(diǎn)通信行為及發(fā)生通信行為的時(shí)間t所構(gòu)成的序列，如式(1)所示。

定義2 給出了通信網(wǎng)絡(luò)中節(jié)點(diǎn)行為時(shí)序的定義，本文研究的問(wèn)題是通過(guò)已知的節(jié)點(diǎn)行為時(shí)序Ac:=[a1,a2,…,an]，推斷出通信網(wǎng)絡(luò)G(V,E)中存在的指控信息流C=[c1,c2,…,ck]。由于通信網(wǎng)絡(luò)中節(jié)點(diǎn)的通信行為未必全都是指控信息，節(jié)點(diǎn)之間也會(huì)存在著正常通信，在無(wú)法得知通信內(nèi)容的情況下，只能通過(guò)節(jié)點(diǎn)行為的相關(guān)性及網(wǎng)絡(luò)結(jié)構(gòu)的特性來(lái)分析。圖1 給出了幾個(gè)節(jié)點(diǎn)的行為時(shí)序及由此推測(cè)得到的一個(gè)指控信息流，其中A～D 代表4 個(gè)不同的節(jié)點(diǎn)，箭頭代表指控信息的傳遞方向。本文認(rèn)為，如果節(jié)點(diǎn)間通信行為發(fā)生的時(shí)間比較接近，那么這2 個(gè)行為相關(guān)的概率就較大，因此轉(zhuǎn)發(fā)同一信息（指令）的概率也就越高。

圖1 節(jié)點(diǎn)行為時(shí)序與指控信息流

2.2 通信網(wǎng)絡(luò)中節(jié)點(diǎn)背景通信行為模型

為了對(duì)節(jié)點(diǎn)的行為進(jìn)行建模，首先研究節(jié)點(diǎn)的背景通信行為。節(jié)點(diǎn)的背景通信指節(jié)點(diǎn)正常情況下的通信行為，可以認(rèn)為是除了指控信息通信之外的通信行為。一般情況下，可以假設(shè)節(jié)點(diǎn)的背景通信行為在時(shí)間上有如下特征。

1)節(jié)點(diǎn)每次發(fā)送信息的行為都是獨(dú)立的，也就是說(shuō)節(jié)點(diǎn)發(fā)送的每條信息前后都沒(méi)有相關(guān)性。

2)節(jié)點(diǎn)發(fā)送信息的行為在時(shí)間上是均勻的。

3)節(jié)點(diǎn)的每次通信行為都是單獨(dú)發(fā)生的，2 個(gè)通信行為同時(shí)發(fā)生的概率很低。

4)節(jié)點(diǎn)的通信行為在短時(shí)間內(nèi)僅發(fā)生一次。

以上假設(shè)中的特征在通信網(wǎng)絡(luò)中是普遍存在的，比如考慮一個(gè)節(jié)點(diǎn)發(fā)送郵件的情況，在不考慮指控信息的情況下回復(fù)他人郵件，每次主動(dòng)發(fā)送郵件的行為都是獨(dú)立的，而且每一封不同郵件的發(fā)送方式都是一封一封地發(fā)送，這就是假設(shè)1)、3)、4)所描述的事情。上述假設(shè)2)指在觀測(cè)的時(shí)間內(nèi)，節(jié)點(diǎn)發(fā)送一條信息的概率，其與觀測(cè)時(shí)間的長(zhǎng)短成正比，可以理解為觀測(cè)的時(shí)間越長(zhǎng)，觀測(cè)到節(jié)點(diǎn)發(fā)送信息行為的次數(shù)越多。而且，這個(gè)過(guò)程是不依賴于觀測(cè)的起始時(shí)間。例如考慮一個(gè)平均每天發(fā)送20 封郵件的節(jié)點(diǎn)，其5 天內(nèi)發(fā)送郵件的數(shù)量大概是其10 天內(nèi)發(fā)送郵件數(shù)量的一半。這一點(diǎn)在絕大多數(shù)的場(chǎng)景下都可以滿足。盡管節(jié)點(diǎn)發(fā)送信息的時(shí)間并不是嚴(yán)格均勻的，比如工作日通信要比周末頻繁，但是可以對(duì)不同情況分別進(jìn)行處理。下面將對(duì)滿足這些條件的通信行為進(jìn)行建模。

定理1如果一個(gè)通信網(wǎng)絡(luò)中節(jié)點(diǎn)的通信行為滿足以上4 個(gè)假設(shè)，那么時(shí)間t內(nèi)節(jié)點(diǎn)發(fā)送消息的數(shù)量N(t)滿足齊次泊松過(guò)程。

證明該定理的證明參見(jiàn)文獻(xiàn)[13-14]中泊松過(guò)程的定義和證明。

證畢。

下面，考察通信網(wǎng)絡(luò)中節(jié)點(diǎn)的通信時(shí)間間隔分布情況。

定理2在滿足以上4 個(gè)假設(shè)的通信網(wǎng)絡(luò)中，令Xn表示某一節(jié)點(diǎn)第n-1次通信行為和第n次通信行為之間的時(shí)間間隔，那么Xn(n=1,2,…)為獨(dú)立同分布的指數(shù)隨機(jī)變量。

證明由定理1 可知，在時(shí)間t內(nèi)節(jié)點(diǎn)發(fā)送消息的數(shù)量N(t)滿足齊次泊松過(guò)程。根據(jù)文獻(xiàn)[13-14]中泊松分布的相關(guān)定理可以證明該定理。

證畢。

定理2 表明，在沒(méi)有指控信息的情況下，節(jié)點(diǎn)相鄰2 次通信時(shí)間間隔的分布滿足強(qiáng)度為λ的指數(shù)分布，其均值為。然而對(duì)于指控信息的轉(zhuǎn)發(fā)，其發(fā)送行為是被動(dòng)的，而且通常會(huì)在較短的時(shí)間內(nèi)對(duì)指控信息做出反應(yīng)，這樣，節(jié)點(diǎn)發(fā)送指控信息的時(shí)間間隔不會(huì)滿足指數(shù)分布。

2.3 通信網(wǎng)絡(luò)中節(jié)點(diǎn)的指控通信行為建模

對(duì)于通信網(wǎng)絡(luò)中的指控信息，假設(shè)其具有如下的特征。

1)節(jié)點(diǎn)在收到指控信息后會(huì)在相對(duì)較短的時(shí)間內(nèi)執(zhí)行該指控信息。

2)節(jié)點(diǎn)對(duì)指控信息的執(zhí)行并不影響其正常的通信行為。

該假設(shè)容易理解，也符合絕大多數(shù)實(shí)際情況中節(jié)點(diǎn)執(zhí)行指控信息的情況[15]。從這2 個(gè)假設(shè)出發(fā)，對(duì)于通信網(wǎng)絡(luò)中的指控信息流，節(jié)點(diǎn)在收到指控后的行為顯然不滿足2.2 節(jié)中的假設(shè)，因?yàn)橥ǔＪ盏街缚氐囊环綍?huì)在較短的時(shí)間內(nèi)做出回應(yīng)。考慮節(jié)點(diǎn)A 命令節(jié)點(diǎn)B 發(fā)送消息給節(jié)點(diǎn)C，這種情況下B 發(fā)送消息給C 的行為是由A 發(fā)送消息給B 激發(fā)的，這一過(guò)程必然不是獨(dú)立的。又如通信中A 與B 進(jìn)行聊天，雙方發(fā)送消息的行為顯然也不是獨(dú)立的。由于指控信息流與非指控信息流之間存在的這種差異，給區(qū)分這2 種信息提供了可能。文獻(xiàn)[15-16]研究表明，節(jié)點(diǎn)轉(zhuǎn)發(fā)指令的時(shí)間間隔服從指數(shù)分布或者冪律分布，即

基于指控信息假設(shè)的特征2)，考慮到節(jié)點(diǎn)收到指控信息后的行為并不影響其背景通信的行為，對(duì)于每個(gè)節(jié)點(diǎn)的通信行為序列，去除指控信息通信行為后，便可以得到其正常的信息通信行為序列，根據(jù)定理1，該序列滿足齊次泊松過(guò)程。節(jié)點(diǎn)通信行為的示例如圖2 所示，其中B 的通信行為序列中的虛線代表其對(duì)A 指控信息的回應(yīng)，去除掉B 中的虛線后，B 的行為序列基本上是一個(gè)泊松過(guò)程。因此，判斷B的通信行為是否是指控信息的一個(gè)有效方法是依據(jù)的大小。結(jié)合定理2，節(jié)點(diǎn)對(duì)于指控信息的轉(zhuǎn)發(fā)，其發(fā)送行為是被動(dòng)的，而且通常會(huì)在較短的時(shí)間內(nèi)對(duì)指控信息做出反應(yīng)，這樣，節(jié)點(diǎn)發(fā)送指控信息的時(shí)間間隔將會(huì)在很大的概率上不能滿足指數(shù)分布。這樣便可以得到一個(gè)區(qū)分出指控信息的統(tǒng)計(jì)量。

圖2 節(jié)點(diǎn)通信行為示例

由于實(shí)際能夠觀測(cè)到的數(shù)據(jù)是上述2 種信息模型獨(dú)立生成數(shù)據(jù)的并集，如何從融合的數(shù)據(jù)中根據(jù)模型篩選出指控信息流是本文的核心問(wèn)題。

3 模型求解

定理2 給出了節(jié)點(diǎn)在無(wú)指控信息流時(shí)發(fā)送信息的時(shí)間間隔滿足強(qiáng)度為λ的指數(shù)分布，眾所周知，λ的極大似然估計(jì)為，其中，為通信時(shí)間間隔的均值。假設(shè)網(wǎng)絡(luò)中的指控信息與正常通信信息的占比為r，一般情況下，r?1 。設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)j接收到由節(jié)點(diǎn)i發(fā)送信息的強(qiáng)度為λi,j，則節(jié)點(diǎn)j發(fā)送信息的強(qiáng)度，即每個(gè)子節(jié)點(diǎn)發(fā)送信息強(qiáng)度的和。易知，節(jié)點(diǎn)j接收來(lái)自節(jié)點(diǎn)i信息的過(guò)程是速率為λi,j的泊松過(guò)程；節(jié)點(diǎn)j發(fā)送消息到節(jié)點(diǎn)k的過(guò)程是速率為λj,k的泊松過(guò)程?？紤]節(jié)點(diǎn)j收到節(jié)點(diǎn)i信息的時(shí)刻ti,j，以及最近的一次節(jié)點(diǎn)j發(fā)送消息到節(jié)點(diǎn)k的時(shí)刻tj,k,那么有

其中，Nj,k(t)指時(shí)間t內(nèi)節(jié)點(diǎn)j給節(jié)點(diǎn)k發(fā)送信息的數(shù)量，Ni,j(t)指時(shí)間t內(nèi)節(jié)點(diǎn)i給節(jié)點(diǎn)j發(fā)送信息的數(shù)量。從式(3)可以看出，正常通信中，節(jié)點(diǎn)收到一條消息后，又恰好在t時(shí)間內(nèi)給特定節(jié)點(diǎn)發(fā)送一條消息的概率，僅與該節(jié)點(diǎn)與特定節(jié)點(diǎn)之間發(fā)送消息的強(qiáng)度λj,k及t有關(guān)，而與接收節(jié)點(diǎn)的發(fā)送消息強(qiáng)度無(wú)關(guān)。

對(duì)于指控信息的轉(zhuǎn)發(fā)，根據(jù)2.3 節(jié)的分析，其轉(zhuǎn)發(fā)時(shí)間t的概率為指數(shù)分布或者冪律分布。圖3給出了3 種分布函數(shù)。從圖3 中可以看出，節(jié)點(diǎn)轉(zhuǎn)發(fā)指令的時(shí)間間隔概率隨著間隔的增加而單調(diào)遞減，而節(jié)點(diǎn)恰好發(fā)送正常通信信息的時(shí)間間隔概率有一個(gè)波峰，其概率先增加后減小。那么，針對(duì)如上所述的分布函數(shù)，如何選擇一個(gè)閾值t′才能使分類正確的概率最大。一個(gè)直觀的答案是選擇2 個(gè)分布曲線的交點(diǎn)作為閾值，如果小于該閾值，判斷為指令轉(zhuǎn)發(fā)；如果大于該閾值，判斷為正常通信行為。

圖3 不同分布函數(shù)

基于上述的推理和計(jì)算，為了求得閾值，需要首先估計(jì)出每個(gè)節(jié)點(diǎn)發(fā)送給相應(yīng)節(jié)點(diǎn)信息的速率λj,k。由于通常情況下指令類信息占比非常少，因此可以采用觀測(cè)數(shù)據(jù)中節(jié)點(diǎn)通信的頻率作為其發(fā)送速率的估計(jì)值。而轉(zhuǎn)發(fā)指令的時(shí)間間隔參數(shù)α可以采用迭代的方法來(lái)估計(jì)。算法1 給出了FlowMine算法對(duì)網(wǎng)絡(luò)信息流的挖掘，具體如下。

算法1FlowMine 算法

輸入Ac:=[a1,a2,…,an]，信息流最大長(zhǎng)度ML，跳出臨界值e

算法1 中Δt表示發(fā)送相鄰信息的時(shí)間間隔，|Δt|表示每次循環(huán)后閾值變化的絕對(duì)值。該算法的一個(gè)關(guān)鍵在于對(duì)α的估計(jì)，其收斂性及收斂速度直接影響到算法的性能。定理3 給出相應(yīng)的分析。

定理3已知轉(zhuǎn)發(fā)指令的時(shí)間間隔服從指數(shù)分布或者冪律分布，那么根據(jù)FlowMine 算法對(duì)α的估計(jì)是收斂的。

證明考慮2 個(gè)分布的差，如式(4)所示。

在本文假設(shè)中，由于α?λ，且fλ(t)的極值在t=λ處，那么僅考慮t∈(0,λ)的情況，有F(0)＞ 0＞F(λ)，又因?yàn)镕(t)連續(xù)，因此必然存在某個(gè)點(diǎn)t′∈(0,λ)使F(t′)=0。

假設(shè)閾值初始值為t0，根據(jù)FlowMine 算法，由t0得到F，進(jìn)而由F估計(jì)α，記α0=fF(t0)。由于F中節(jié)點(diǎn)的轉(zhuǎn)發(fā)間隔均小于t0，因此，。由于隨著閾值tn的減小，對(duì)指令轉(zhuǎn)發(fā)參數(shù)αn的估計(jì)隨之減小，將tn、αn代入式(4)，得到

考慮式(5)和式(6)，兩者的差值僅在于α，現(xiàn)在分析指令轉(zhuǎn)發(fā)服從指數(shù)分布的情況，即f(t|a)=ae-at。容易驗(yàn)證，當(dāng)α=t時(shí)，函數(shù)取得最大值，且在區(qū)間(0,t)單調(diào)遞增，在區(qū)間(t,∞)單調(diào)遞減。因此，有

再結(jié)合式(8)及F(t)連續(xù)單調(diào)遞減，可得

這樣，對(duì)閾值t的估計(jì)可以收斂到真實(shí)值附近。因此，當(dāng)給定一個(gè)初始閾值，隨著迭代次數(shù)增加，tn依次遞減，依次遞增，達(dá)到相應(yīng)閾值后，tn的單調(diào)性被破壞，此時(shí)，tn便在真實(shí)閾值附近穩(wěn)定地波動(dòng)，因此算法收斂。冪律分布的相關(guān)證明與上述證明過(guò)程類似。

證畢。

FlowMine 算法的收斂性也可以從圖3 中看出，當(dāng)t′取值變大時(shí)，算法1 中得到的F中節(jié)點(diǎn)間信息轉(zhuǎn)發(fā)的平均間隔變大，從而導(dǎo)致估計(jì)的變小，由此估計(jì)出的閾值t′變??；而當(dāng)t′取值變小時(shí)，從算法1 中得到的F中節(jié)點(diǎn)信息轉(zhuǎn)發(fā)平均間隔變小，導(dǎo)致變大，由此估計(jì)出的閾值t′變大。

需要指出，當(dāng)一個(gè)節(jié)點(diǎn)具有多個(gè)父節(jié)點(diǎn)時(shí)，單位時(shí)間內(nèi)，其會(huì)收到多條來(lái)自不同父節(jié)點(diǎn)的多條指令，這樣，該節(jié)點(diǎn)會(huì)相對(duì)比較繁忙，有可能會(huì)導(dǎo)致該節(jié)點(diǎn)觀測(cè)到的平均轉(zhuǎn)發(fā)間隔與指控信息轉(zhuǎn)發(fā)間隔接近，甚至更小。對(duì)于這種情況，通常難以區(qū)分節(jié)點(diǎn)發(fā)送的信息是指控信息還是正常通信，尤其在無(wú)法知曉通信內(nèi)容的情況下，至今沒(méi)有有效的辦法。

4 實(shí)驗(yàn)分析

本節(jié)首先通過(guò)模擬數(shù)據(jù)對(duì)文中的定理進(jìn)行仿真驗(yàn)證，然后對(duì)FlowMine 算法的性能進(jìn)行分析，最后將算法應(yīng)用于實(shí)際數(shù)據(jù)，對(duì)實(shí)際數(shù)據(jù)中的信息流進(jìn)行挖掘并分析。

4.1 模擬數(shù)據(jù)仿真實(shí)驗(yàn)

實(shí)驗(yàn)中，首先采用Kronecker Graph[17-18]來(lái)生成真實(shí)的有向網(wǎng)絡(luò)結(jié)構(gòu)，節(jié)點(diǎn)之間的指控信息將在網(wǎng)絡(luò)的有向邊上傳播。該網(wǎng)絡(luò)結(jié)構(gòu)通常代表了節(jié)點(diǎn)之間的組織關(guān)系，比如上下級(jí)關(guān)系、指揮關(guān)系等。本文考慮了隨機(jī)圖（Kronecker 參數(shù)矩陣為[0.5,0.5;0.5,0.5]，后文實(shí)用Random 代表該模型）[19]、層次社區(qū)結(jié)構(gòu)（Kroneckev 參數(shù)矩陣為[0.962,0.107;0.107,0.962]，后文使用Hierarchical 代表該模型）[20]及隨機(jī)冪律樹(shù)（后文使用Random-Tree 代表該模型）[21]這3 種不同的網(wǎng)絡(luò)結(jié)構(gòu)。每次在網(wǎng)絡(luò)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為起始節(jié)點(diǎn)，該節(jié)點(diǎn)將一條信息以一定概率隨機(jī)發(fā)送給其子節(jié)點(diǎn)，收到信息的子節(jié)點(diǎn)將按照2.3 節(jié)中的模型，將信息在網(wǎng)絡(luò)中傳遞出去，由此可以得到一個(gè)指令轉(zhuǎn)發(fā)的信息流。重復(fù)上述過(guò)程，便可以得到多條不同的信息流。為了模擬節(jié)點(diǎn)之間的正常通信行為，隨機(jī)依次從網(wǎng)絡(luò)中選擇2 個(gè)節(jié)點(diǎn)，構(gòu)成節(jié)點(diǎn)間的正常通信行為。根據(jù)2.2 節(jié)的模型，節(jié)點(diǎn)正常發(fā)送一條信息的行為滿足泊松分布，因此在觀測(cè)時(shí)間窗口中，均勻地選擇一個(gè)時(shí)間作為節(jié)點(diǎn)背景通信的發(fā)生時(shí)刻[13]。本文將上述觀測(cè)的指控信息及正常通信信息混合在一起構(gòu)成實(shí)驗(yàn)中觀測(cè)的節(jié)點(diǎn)通信行為時(shí)序集合。

實(shí)驗(yàn)中，設(shè)定指控信息與背景通信數(shù)量的比值為SN，通常SN 越低，說(shuō)明實(shí)驗(yàn)數(shù)據(jù)中指控信息所占比率越低，那么還原出信息流的難度越大。為了衡量算法性能，本文采用了F1-measure[22]，其中查全率定義為算法識(shí)別出的信息流占實(shí)際信息流的比例，準(zhǔn)確率定義為識(shí)別正確的信息流占全部識(shí)別出的信息流的比例。

按照上述設(shè)置，分別生成了64 個(gè)節(jié)點(diǎn)，75 條邊的層次網(wǎng)絡(luò)、隨機(jī)圖及隨機(jī)樹(shù)3 種不同結(jié)構(gòu)的網(wǎng)絡(luò)，并模擬生成了180 條指控信息在網(wǎng)絡(luò)中隨機(jī)傳播，實(shí)驗(yàn)中每條邊的傳播概率設(shè)置為0.5，SN 設(shè)置為0.07。由于算法在估計(jì)閾值時(shí)，先估計(jì)α并不斷迭代，因此如果α收斂，那么算法對(duì)閾值的估計(jì)將收斂。圖4 展示了不同的指控信息轉(zhuǎn)發(fā)模型下算法1 的收斂性情況。從圖4 中可以看出，算法對(duì)于不同的模型、不同的網(wǎng)絡(luò)結(jié)構(gòu)均可以穩(wěn)定在某個(gè)值附近。算法對(duì)于冪律分布的收斂性稍差于指數(shù)分布，冪律分布的波動(dòng)性要大一些，而指數(shù)分布中估計(jì)值的波動(dòng)非常小，但估計(jì)值均圍繞某個(gè)中值進(jìn)行波動(dòng)。因此在實(shí)際的應(yīng)用中，可以對(duì)算法1 的每次迭代乘以一個(gè)收斂因子，或者取每次波動(dòng)的平均值作為估計(jì)值。圖4(a)中算法對(duì)不同網(wǎng)絡(luò)結(jié)構(gòu)的α估計(jì)值基本上在真實(shí)值附近，差別并不大；而圖4(b)中算法對(duì)不同網(wǎng)絡(luò)結(jié)構(gòu)的α估計(jì)值相差比較大。對(duì)于這種情況，本文認(rèn)為是由于在不同的網(wǎng)絡(luò)結(jié)構(gòu)中，指令信息傳播的范圍有很大差別，這會(huì)明顯影響到觀測(cè)節(jié)點(diǎn)轉(zhuǎn)發(fā)信息的平均時(shí)間間隔，而這對(duì)于閾值及α的估計(jì)會(huì)產(chǎn)生較大影響。從收斂速度上看，算法可以很快地收斂到穩(wěn)定狀態(tài)，基本上5 輪迭代就能夠達(dá)到平穩(wěn)的狀態(tài)。

圖4 不同模型下算法的收斂性分析

FlowMine 算法在不同模型以及網(wǎng)絡(luò)結(jié)構(gòu)下的性能如圖5 所示。從結(jié)果中看，算法在SN=0.5 以上時(shí)均能夠達(dá)到較高的F1-measure，雖然并沒(méi)有完全準(zhǔn)確地還原出所有指控信息流，但也能夠達(dá)到一個(gè)可以接受的性能。算法對(duì)于冪律分布的還原性能要優(yōu)于指數(shù)分布，這一點(diǎn)可以通過(guò)圖4 來(lái)解釋。算法雖然對(duì)冪律分布的收斂性不如指數(shù)分布，但其波動(dòng)范圍能夠覆蓋到其參數(shù)的真實(shí)值，這樣，取均值后對(duì)于冪律分布參數(shù)的估計(jì)誤差會(huì)小于指數(shù)分布的誤差。因此，其在還原時(shí)可以達(dá)到更高的精度。從這一點(diǎn)可以看出，對(duì)模型參數(shù)的估計(jì)誤差能夠明顯地影響到算法的性能，提高估計(jì)精度可以有效地提高算法性能。

實(shí)驗(yàn)表明，算法在SN=0.8 左右會(huì)有一點(diǎn)下降，其原因主要在于，算法中假設(shè)了指控信息數(shù)量遠(yuǎn)小于背景通信的信息數(shù)量，當(dāng)SN 提升后，該假設(shè)造成的誤差會(huì)大大增加，因此造成了算法性能的下降，而隨著SN 的提升，指控信息的還原難度隨之降低，因此，算法的性能在SN=0.8之后又提升了許多。

圖5(b)中算法對(duì)于層次社區(qū)型網(wǎng)絡(luò)結(jié)構(gòu)的還原要差于其他2 個(gè)類型的網(wǎng)絡(luò)結(jié)構(gòu)，而圖4(b)中算法對(duì)于層次型網(wǎng)絡(luò)的參數(shù)估計(jì)誤差是最大的，這從另一方面佐證了上述分析中參數(shù)誤差對(duì)算法性能的影響。在圖4(a)中，算法對(duì)幾種網(wǎng)絡(luò)結(jié)構(gòu)的參數(shù)估計(jì)的均值均落在了真實(shí)值附近，因此，圖5(a)中算法的性能相差無(wú)幾。

圖5 算法1 在不同模型以及網(wǎng)絡(luò)結(jié)構(gòu)下的性能

4.2 安然郵件數(shù)據(jù)集分析

本節(jié)通過(guò)對(duì)安然郵件集[23]進(jìn)行分析，挖掘其中的指控信息流，并分析網(wǎng)絡(luò)中指控信息的傳播模式和特點(diǎn)。安然數(shù)據(jù)集是安然公司幾千名員工辦公郵箱中的郵件數(shù)據(jù)集合，最初由聯(lián)邦能源局公開(kāi)，由卡內(nèi)基梅隴大學(xué)的William Cohen 收集并用于科學(xué)研究。本文使用了其中一個(gè)含有151 名標(biāo)注了員工崗位職級(jí)的版本，由于僅需要郵件通信的雙方及時(shí)間，舍棄了郵件的內(nèi)容，僅提取了郵件的發(fā)送者、接收者及郵件發(fā)送時(shí)間，然后將這些數(shù)據(jù)存入MySQL 數(shù)據(jù)庫(kù)中。本文選取了郵件集合中時(shí)間在2001 年1 月1 日—3 月1 日共2 個(gè)月的郵件，并手動(dòng)標(biāo)注了涉及指控信息流的郵件，統(tǒng)計(jì)結(jié)果如表1所示。

表1 數(shù)據(jù)集簡(jiǎn)介

為了驗(yàn)證FlowMine 算法所求閾值的性能，本文將參數(shù)ratio 與求得的閾值相乘，也就是假設(shè)判別指控信息流的閾值為FlowMine 求得閾值的ratio倍。通過(guò)對(duì)ratio 取不同的值，得到算法挖掘指控信息流的性能F1-measure，如圖6 所示。

圖6 FlowMine 性能分析

從圖6 中可以看出，當(dāng)ratio=1 時(shí)，求得的指控信息流最準(zhǔn)確，這可以說(shuō)明，F(xiàn)lowMine 對(duì)于閾值的估計(jì)在實(shí)際數(shù)據(jù)中相對(duì)是比較準(zhǔn)確的，對(duì)指控信息流挖掘的F1-measure 可以高達(dá)0.8，可以認(rèn)為其結(jié)果對(duì)該數(shù)據(jù)集是可信的。

將基于文獻(xiàn)[2-3]思想提出的Disclosure 算法與本文的FlowMine 算法在安然郵件數(shù)據(jù)集中進(jìn)行對(duì)比，挖掘指控信息流的PR（precision-recall）曲線如圖7 所示。Disclosure 算法采用了流量大小、通信時(shí)間等多種屬性特征來(lái)挖掘指控信息流。從圖7所示的實(shí)驗(yàn)結(jié)果可以看出，F(xiàn)lowMine 算法在安然數(shù)據(jù)集中性能遠(yuǎn)優(yōu)于Disclosure。

圖7 安然數(shù)據(jù)中的算法性能對(duì)比

對(duì)安然郵件集使用算法1 挖掘其中的信息流，結(jié)果如圖8 所示。圖8 中的每個(gè)子圖為挖掘出來(lái)的每條信息流，其崗位標(biāo)注在了節(jié)點(diǎn)周圍，未知的崗位采用NA 來(lái)表示。其中，有向邊代表信息的流向，每條信息流存在一個(gè)根節(jié)點(diǎn)，代表信息的發(fā)起方，至少存在一個(gè)子節(jié)點(diǎn)，代表信息的流向。

圖8 安然郵件集合中的指控信息流

從挖掘到的指控信息流可以看出，每條指控信息流的長(zhǎng)度均不會(huì)太長(zhǎng)，所發(fā)現(xiàn)的最大深度為4 層。最常見(jiàn)的信息流結(jié)構(gòu)為星型和樹(shù)形，通常是某個(gè)節(jié)點(diǎn)將信息傳遞給多個(gè)子節(jié)點(diǎn)，以達(dá)到信息擴(kuò)散的目的。從人員崗位的組成上看，處于領(lǐng)導(dǎo)地位的節(jié)點(diǎn)通常位于信息流的末端，而一般信息流中的中間節(jié)點(diǎn)崗位通常為員工；僅有少數(shù)的信息流由領(lǐng)導(dǎo)發(fā)出，然后傳播給其他員工。挖掘出的信息流中還存在著大量?jī)H有2 個(gè)節(jié)點(diǎn)構(gòu)成的信息流，盡管這些信息流在圖中看起來(lái)很短，實(shí)際上，在2 個(gè)節(jié)點(diǎn)之間存在多次郵件的往來(lái)，這種情況一般是雙方互相回復(fù)對(duì)方的郵件。通過(guò)對(duì)挖掘出的信息流郵件內(nèi)容進(jìn)行分析發(fā)現(xiàn)，星型結(jié)構(gòu)中的中心節(jié)點(diǎn)的角色是秘書(shū)，其行為通常是將信息分發(fā)給他的上司；另一方面也會(huì)將領(lǐng)導(dǎo)的指令或任務(wù)傳達(dá)給相應(yīng)的員工。通過(guò)信息流的挖掘還發(fā)現(xiàn)，有的節(jié)點(diǎn)經(jīng)常給自己發(fā)送郵件，這種情況一般是員工將重要信息留存到自己郵箱做備份，或是方便檢索用，這個(gè)與員工的行為習(xí)慣相關(guān)。

通過(guò)上述分析發(fā)現(xiàn)，處于領(lǐng)導(dǎo)崗位的員工并不一定是信息的發(fā)起方，因?yàn)榻?jīng)常遇到這種下屬將信息匯總并報(bào)告給領(lǐng)導(dǎo)的情況，因此，很難僅僅通過(guò)節(jié)點(diǎn)在信息流的位置來(lái)判斷節(jié)點(diǎn)的身份信息。然而，通過(guò)對(duì)信息流的分析，可以發(fā)現(xiàn)很多節(jié)點(diǎn)的行為習(xí)慣，以及網(wǎng)絡(luò)中信息傳遞的路徑等。更進(jìn)一步，可以斷定同一個(gè)信息流內(nèi)的節(jié)點(diǎn)在業(yè)務(wù)上至少是相關(guān)的。在星型結(jié)構(gòu)中的中心節(jié)點(diǎn)通常是一個(gè)紐帶的角色，這種節(jié)點(diǎn)的角色一般是秘書(shū)，其需要與上級(jí)和下級(jí)保持聯(lián)系，因此在信息的傳播路徑中處于中心位置。

更進(jìn)一步，可以知道在安然公司中，其組織相對(duì)扁平，因?yàn)橥ㄟ^(guò)郵件對(duì)信息的傳播深度并沒(méi)有超過(guò)4 層。盡管公司實(shí)際的組織結(jié)構(gòu)并不知曉，但這一現(xiàn)象的原因可能是電子郵件拉近了人們之間的距離，因此管理上的層級(jí)更加扁平。

下面對(duì)所得到的指控信息流進(jìn)一步分析，考察一些特殊的節(jié)點(diǎn)，比如sara.shackleton，這些節(jié)點(diǎn)出現(xiàn)在多個(gè)不同的指控信息流中。圖9 給出了員工sara.shakleton@enron.com 在不同指控信息流中所處的不同位置，該節(jié)點(diǎn)在觀測(cè)時(shí)間內(nèi)一共出現(xiàn)在了4 個(gè)不同的信息流中，節(jié)點(diǎn)名稱標(biāo)記在節(jié)點(diǎn)上。容易發(fā)現(xiàn)，該員工與mark.e.taylor、tana.jones、stephanie及susan.balley 幾名員工關(guān)系比較密切，該員工在信息流D 中處信息流末端位置，與員工susan.balley、stephanie 等一起收到了mark.e.taylor 的信息；在信息流C 中，該員工收到mark.e.taylor 的信息后將信息轉(zhuǎn)發(fā)給了tana.jones 以及susan.balley 等，在信息流B 中，該員工與tana.jones 進(jìn)行了信息的交互，并一起將交互的信息傳遞給了其他幾名員工；在信息流A 中，該員工收到stephanie 的信息后轉(zhuǎn)發(fā)給了susan.balley 等，通過(guò)這幾個(gè)信息流，可以初步推測(cè)該員工要比 mark.e.taylor 等級(jí)低一些，且與susan.balley、tana.jones、stephanie 這幾名員工等級(jí)相同。更進(jìn)一步發(fā)現(xiàn)，susan.balley、tana.jones、stephanie 及sara.shackleton 這幾名員工多次共同出現(xiàn)在幾個(gè)不同的指控信息流中，那么可以推測(cè)這幾名員工應(yīng)該屬于同一個(gè)部門，但是這幾名員工的身份信息應(yīng)該是不同的。在信息流D 中，mark.e.taylor處于中心節(jié)點(diǎn)位置，而且該節(jié)點(diǎn)與該部門多個(gè)外部節(jié)點(diǎn)有聯(lián)系，可以推斷mark.e.taylor 不屬于該部門。mark.e.taylor 一次性給sara.shackleton、susan.balley和stephanie 這3 名員工同時(shí)發(fā)送信息，該行為可以推測(cè)為一次信息的下達(dá)過(guò)程。sara.shackleton 在信息流 A、B 以及 C 中均處于中心位置，其收到stephanie、tana.jones 及mark.e.taylor 的信息后對(duì)其他的員工進(jìn)行了信息的廣播，從這個(gè)信息流中推測(cè)，sara.shackleton 的角色比較類似于部門的中轉(zhuǎn)者或者操作員，負(fù)責(zé)一些信息的傳達(dá)等。

圖9 單個(gè)員工在指控信息流中的情況

以上是在不知道任何一名員工的職位的情況下僅通過(guò)挖掘出的指控信息流做出的一些推測(cè)。通過(guò)對(duì)郵件的內(nèi)容進(jìn)行確認(rèn)后，可以證明上述的這些分析。盡管數(shù)據(jù)集中沒(méi)有對(duì)這幾名員工的職位進(jìn)行標(biāo)注，但是，通過(guò)對(duì)用戶在不同指控信息流中的分析可以發(fā)現(xiàn)一些額外的信息，并能夠推測(cè)出mark.e.taylor 等級(jí)要高于sara.shackleton，以及sara.shackleton 的同部門同事有哪些。

但是這些分析仍然具有一些局限性，本文只是隨機(jī)挑選了sara.shackleton 這名員工，其他員工的情況還需要更進(jìn)一步地分析才能得到更多、更準(zhǔn)確的信息。如果只分析幾名員工的指控信息流，又容易造成“盲人摸象”的情況，信息流中的其他用戶的行為難以體現(xiàn)在這些指控信息流中。

4.3 實(shí)驗(yàn)總結(jié)

本節(jié)首先通過(guò)模擬數(shù)據(jù)對(duì)算法的性能進(jìn)行了分析，驗(yàn)證了本文提出算法的收斂性。對(duì)算法的性能分析中，采用了F1-measure，在低信噪比的情況下算法能夠達(dá)到約0.8 的水平，這說(shuō)明算法具有較高的準(zhǔn)確率與查全率。然后使用該算法對(duì)安然郵件集合中的節(jié)點(diǎn)通信行為進(jìn)行分析，并根據(jù)挖掘出的信息流對(duì)節(jié)點(diǎn)的屬性及網(wǎng)絡(luò)的信息傳播路徑等進(jìn)行了分析。分析后發(fā)現(xiàn)，公司中處于領(lǐng)導(dǎo)地位的節(jié)點(diǎn)并不一定是信息的發(fā)起節(jié)點(diǎn)，而是有時(shí)會(huì)由秘書(shū)將信息匯總給上級(jí)。其次，信息流的中心節(jié)點(diǎn)一般是秘書(shū)之類的角色，其不僅將信息匯總給上級(jí)，而且還會(huì)將上級(jí)的任務(wù)或指令傳達(dá)給下級(jí)相應(yīng)人員。從信息流的長(zhǎng)度看，電子郵件有效地拉近了上級(jí)與下級(jí)的距離，并使公司的網(wǎng)絡(luò)更加扁平化。

更進(jìn)一步，通過(guò)分析同一名員工在不同指控信息流中的情況，能夠挖掘出更加深入的一些信息，比如員工間關(guān)系、等級(jí)等。通過(guò)對(duì)郵件內(nèi)容的確認(rèn)，驗(yàn)證了算法挖掘出指控信息流的有效性。

5 結(jié)束語(yǔ)

本文研究了通信網(wǎng)絡(luò)中節(jié)點(diǎn)的通信行為，并對(duì)節(jié)點(diǎn)的正常通信行為和指令轉(zhuǎn)發(fā)行為分別進(jìn)行了建模。然后提出了FlowMine 算法對(duì)模型的相關(guān)參數(shù)進(jìn)行估計(jì)，提取節(jié)點(diǎn)的指令轉(zhuǎn)發(fā)行為。在實(shí)驗(yàn)部分，首先通過(guò)模擬數(shù)據(jù)和實(shí)際標(biāo)注的數(shù)據(jù)對(duì)算法的收斂性和性能進(jìn)行了評(píng)估，然后將FlowMine 算法應(yīng)用于安然郵件集合，并對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的行為和角色進(jìn)行了分析，驗(yàn)證了算法的有效性。

盡管本文已經(jīng)實(shí)現(xiàn)了網(wǎng)絡(luò)中信息流的挖掘，并取得了許多有意思的結(jié)論，但是對(duì)于該方面的研究還存在許多問(wèn)題，把握節(jié)點(diǎn)的指控信息流具有一定的局限性，還需要一種手段將這些不同的信息流進(jìn)行綜合處理，得到目標(biāo)網(wǎng)絡(luò)中用戶間信息的傳遞模式，這樣才能從整體上對(duì)網(wǎng)絡(luò)及用戶進(jìn)行把握和分析。