楊正權 翟欣虎 秦益飛

一.引言

圖是一種揭示實體之間關系的語義網絡，以符號形式對現實世界的事物及其相互關系進行形式化地描述。其基本組成單位“實體-關系-實體”三元組，以及實體及其相關屬性值對，實體間通過關系相互聯結構成網狀的結構?，F階段圖計算在各個領域都有廣泛的應用，例如：信息檢索/搜索，自然語言理解，問答系統(tǒng)，推薦系統(tǒng)，公安刑偵，社交類業(yè)務等。通過圖的方式可以更好的展示實體之間的關系。

互聯網上的各類數據以圖的方式存儲則可以更清晰直觀的展現各個實體的行為以及實體間的關系。一種典型的場景是，當用戶產生登錄運營商服務器，訪問互聯網網站，下載文件等行為時，以及運營商內部一些資產服務器上的應用自動訪問互聯網用于軟件更新，一些監(jiān)控服務對其他資產服務器進行安全掃描等等。運營商都會記錄下這些行為日志并進行相應的分析審計。通常的行為日志內容表述如下：

A用戶 - 在某個時間 - 登錄了 - a應用

B用戶 - 在某個時間 - 訪問了 - b網站

C用戶 - 在某個時間 - 下載了 - c文件

A設備 - 在某個時間 - 連接了 - a服務

B應用 - 在某個時間 - 掃描了 - C設備

上述日志條目中，頭尾兩端的字段為網絡實體（用戶，設備，應用等），中間的字段為關系（登錄，訪問，下載，連接，掃描等），時間屬性則作為實體或關系的屬性值。

使用圖的形式展現網絡實體行為關系更為清晰直觀，但存在的問題是當網絡規(guī)模變大，網絡中實體數量大幅增加時，例如實體數量達到數以千計萬計時，如此龐大的數量以圖的形式展現將變的無法適應，審計人員無法從千萬個節(jié)點以及千萬條邊中找出需要關注最有價值的數據。所以采用圖的形式展現，和傳統(tǒng)數據表形式展現相比同樣需要一套數據的評估排序篩選的方法，以找出最有價值的數據。

從龐大的圖數據集中找出更有價值的數據用于呈現有一些方法，比較常見的一種是在圖中為每個實體計算若干項評估指標，例如該實體的最后更新時間，該實體出現的次數，該實體關聯關系數等。審計人員從若干項指標中人工選擇需要關注的按數值大小按升序或降序排列，最終篩選出topN項實體及其關聯關系。

進一步出現了上述方法的改進方法，在計算出每個實體的若干項評估指標的基礎上，給每種指標賦一個經驗權重值，再計算所有指標的加權平均值，審計人員直接按最終的加權平均值的數值大小升序或降序排列實體，同樣最終列出topN項實體及其關聯關系。

針對上述例舉的現有方法中的第一種，最大的弊端是通過單個指標的排序并不能完整的評價某個實體的真實情況，并且這種單一維度的評價方法本質上和采用圖表方式的存儲并無本質區(qū)別，并不能很好發(fā)揮出圖的關聯關系特性。

針對上述例舉的現有方法的改進方法，該方法雖然通過多個指標對實體做了多維度的綜合評估，但其對每種指標權重的選擇完全基于人工經驗，而這種基于經驗確定的權重值并不能保證其合理性，不合理的權重值會導致某幾項指標在計算加權平均后完全失去了效果，影響最終的評估結果。

和上述兩種現有方法相比較，本文設計的算法避免了通過單個指標對實體評估的單一性，同時在采用多個指標綜合評估的基礎上，改進了通過人工設置經驗權重這種不太合理的方法，充分利用了圖的特性，采用一種基于動態(tài)指標的評估方法，可以更加全面準確的對實體進行評估，在圖中篩選并展現出更合理的網絡實體及其關聯關系。

二.網絡實體行為評估算法設計

（一）評估算法總體流程設計

運營商記錄的其網絡中各種網絡實體的各種操作記錄的日志，提取抽象以后通常都可以用以下屬性來描述：

上表中舉例的行為記錄表示：

用戶Tom在2020.08.01 12：23：45下載了名叫Manual的pdf文件。

通常情況下，運營商服務器每時每刻都會記錄下上述大量的行為日志，本設計算法收到這些日志后，按如下流程處理：

步驟①，獲取指定時間范圍內運營商服務器所產生的各種行為日志，時間范圍長短不做限制。

步驟②，將日志中的“實體”以及“作用對象實體”作為頂點，“行為”作為邊，采用圖的方法存儲，即按頂點的關鍵字分組。

步驟③，統(tǒng)計圖中上述指定時間范圍內的每個頂點的各項指標，即每一組中實體的相關指標，這些指標包括并不限于：頂點上報次數，度中心性，緊密中心性，中介中心性等。

步驟④，計算每個實體每種指標在上述時間范圍內的數據中相應的概率密度（對于離散型隨機變量即指其分布律），即該計算的概率密度數值只基于本次獲取的這批數據得出。

步驟⑤，計算每個實體所有指標概率密度結果的數學期望，即求每個頂點所有指標的算術平均值。

步驟⑥，將每個實體按按數學期望大小排序，選出其topN實體及其關聯關系作為最終結果展現給審計人員查看。

（二）實體行為圖存儲方式設計

圖是由（V， E）來表示的，對于無向圖來說，其中 V =（v0， v1， ... ， vn），E = { （vi，vj） （0 <= i， j <= n且i 不等于j）}，對于有向圖，E = { < vi，vj > （0 <= i， j <= n且i 不等于j）}。V是頂點的集合，E是邊的集合。圖可以有兩種典型的表示方法，一個是鄰接矩陣，另一個是鄰接鏈表，這兩種方法都可以表示有向圖和無向圖。

鄰接矩陣是用兩個數組來表示一個圖：一個一維數組用來存儲每個頂點的信息；一個二維數組（即鄰接矩陣）用來存儲圖中的邊或弧信息。對于圖G =（V， E）來說，鄰接矩陣matrix是一個|V|*|V|的方陣，假設1 <= i， j <= |V|，如果matrix[i][j] == 0，則表示頂點i和頂點j之間沒有邊相連；反之，如果matrix[i][j] ！= 0，則表示表示頂點i和頂點j之間有邊相連，且matrix[i][j]存儲的值即為該邊的權重。

鄰接鏈表是一種不錯的圖存儲結構，由于它在表示稀疏圖的時候非常緊湊而成為通常的選擇。對于圖G =（V， E）來說，在其鄰接鏈表表示中，每個結點對應一條鏈表，因此這個圖里有V條鏈表。假設用一個V維的數組Adj來存儲這V條鏈表，且Adj[i]表示的是結點i對應的鏈表，那么Adj[i]這條鏈表里存儲的就是所有與節(jié)點i之間有邊相連的結點，即與結點i相鄰的結點。

在本算法適用場景中，采用有向圖來描述網絡實體的行為關系并采用鄰接鏈表的方式存儲數據更為合適。以用戶Tom在2020.08.01 12：23：45下載了名叫Manual的pdf文件這條行為日志為例，將“Tom”和“Manual.pdf”這類關鍵字唯一的實體名作為圖的頂點，此次的“下載”行為作為從頂點“Tom”到頂點“Manual.pdf”的有向邊。即：

1. 采用實體名作為頂點唯一性的關鍵字；

2. 采用和有向邊相鄰的一組兩個實體名作為邊唯一性的聯合關鍵字；

3. 給每個頂點設置特征數組：（上報次數，度中心性，緊密中心性，中介中心性，...）。

反復將行為日志抽象提取后加入圖并計算頂點的屬性值即構成了一個復雜的有向圖。圖上的每個頂點應該都有1-N條相連接的邊，同理也就擁有1-N個相鄰的頂點，即采用鄰接鏈表的方式按頂點的關鍵字進行了分組操作。

（三）實體行為評估算法設計

評估算法主要涉及對圖中頂點相關特征的計算，具體如下：

1. 頂點上報次數：當行為日志中的實體名在圖的頂點集V中已經存在，則該頂點的上報次數加1，統(tǒng)計一段時間內每個頂點的上報次數。

2. 度中心性：該特征是計算頂點上傳入和傳出關系的數量，可以用于在圖中查找“熱”（popular）的節(jié)點。在本算法適用的場景中，即統(tǒng)計一段時間內每個頂點的鄰接頂點數。

3. 緊密中心性：該特性是一種檢測節(jié)點通過子圖傳播信息有效性的方法。該方法度量是節(jié)點與所有其他節(jié)點的距離近的程度。在所有節(jié)點對的最短路徑計算的基礎上，緊密中心性算法計算一個節(jié)點到所有其他節(jié)點的距離之和。然后將得到的和求倒數，以確定該節(jié)點的緊密性中心性得分。節(jié)點的緊密中心性用以下的公式來計算：

其中，u是一個節(jié)點，n是圖中的節(jié)點數，d（u，v）是另一個節(jié)點V和U之間的最短路徑距離。

更常見的是將該分數歸一化，使該得分代表最短路徑的平均長度，而不是它們的總和。這種調整允許比較不同大小圖節(jié)點的緊密性中心性。

歸一化后的緊密中心性公式如下：

在本算法適用場景中，即篩選出一段時間范圍內的所有頂點和邊，在此基礎上計算每個頂點的緊密中心度。

4. 中介中心性：該特征是一種檢測節(jié)點對圖中信息或資源流的影響程度的方法。它通常用于查找充當從圖的一部分到另一部分的橋梁型節(jié)點。該算法首先計算連接圖中每對節(jié)點之間的最短（權重）路徑。每個節(jié)點都會根據這些通過該節(jié)點的最短路徑的數量得到一個分數。經過節(jié)點的最短路徑越多，該節(jié)點的得分越高。

中介中心性是將最短路徑通過如下公式計算后累加的結果：

在公式中u是一個節(jié)點，p是節(jié)點s和t之間最短路徑的數量，p（u）是s和t之間通過u的最短路徑的數量。

同理在本算法適用場景中，即篩選出一段時間范圍內的所有頂點和邊，在此基礎上計算每個頂點的中介中心度。

計算出一段時間范圍內圖中每個頂點的上述4種或更多特征的特征數組后，將該批數據中出現的不重復的頂點對應的其中一種特征作為離散型隨機變量，將該特征的數值作為隨機變量的出現次數，計算這批數據中不重復的頂點的所有特征相應的分布律，即每個頂點對應特征在所有頂點對應特征中的占比。舉例如下：選取了一段時間范圍的行為日志按圖存儲后有3個頂點，計算這3個頂點對應的特征數組分別為（20，3，0.3，4），（4，1，1，2），（12，2，0.6，1.4），那么對于3個頂點特征分布律數組為：

計算每個頂點特征分布律數組中所有數值的數學期望，最終結果即為每個頂點的評估值，按評估值大小進行排序，選出topN對應的頂點即最終被篩選出的實體及其對應的行為關系。

三.網絡實體行為評估算法驗證

（一）驗證數據建立

Apache JMeter是Apache組織開發(fā)的基于Java的壓力測試工具，用于對軟件做壓力測試，JMeter 可用于模擬在服務器、網絡或者其他對象上附加高負載以測試其提供服務的受壓能力，或者分析其提供的服務在不同負載條件下的總性能情況。

驗證方法基于JMeter搭建，使用一臺服務器作為代理網關，可以記錄下接入用戶的上網日志，另一臺PC終端上運行JMeter，用于模擬多用戶的互聯網訪問行為。設置JMeter模擬50名不同的用戶，隨機訪問100個預選出的互聯網網站，為每位用戶設置不同的訪問網站數量閾值以及訪問的頻率閾值，從網關服務器收集一天內所有訪問請求記錄約80萬條作為待檢測樣本。同時記錄下JMeter針對每個用戶訪問量及訪問頻率的設置，如下：

將上述數據采用本文設計的圖方式存儲并分析評估每個模擬用戶的行為，得到每個用戶最終的評估值的排名，同時也給出每個特性單獨的排名，如下：

（二）驗證方法及結果分析

對于無監(jiān)督的預測結果業(yè)界并沒有評估結果“好壞”的統(tǒng)一標準，本驗證通過將評估結果和互聯網領域比較常用及容易理解的PageRank熱度排名的方式做對比，計算50名模擬用戶的排名和PageRank排名兩數組的相關系數，系數約接近于1表示評估的排名和PageRank排名越接近。驗證結果如下：

結果表明，本算法評估的結果和PageRank排名最接近，可以認為是通常情況下比較認可的結果。

四.結束語

因為本文所描述的方法通過多個維度對網絡實體進行評估，相比于人工選擇單一維度的評估，評估結果更全面。

同時本文所述方法基于預選出的實際時間范圍的數據，對網絡實體動態(tài)計算多個維度權重的相對比例而不是固定不變的比例值，評估結果的準確性更高。

作者單位：江蘇易安聯網絡技術有限公司