在安全領域，“圖分析”廣泛應用在賬戶交易異常、不同事件關聯等各種場景下。與其他機器學習算法類比較， 其特有的優點在于分析方法符合人的思維方式，分析過程能直觀地可視化。
舉例來說，下圖是把瀚思某客戶企業中幾類安全事件 ： 登陸、使用USB盤、檢測到病毒、機器IP、 用戶使用機器 - 綜合到一起做關聯分析。
圖中“邊”代表發生過事件;點(機器、用戶、IP、病毒、USB盤五類之一) 的大小代表事件多少。一張圖上我們可以快速定位爆發次數最多的病毒、哪些用戶違規使用同臺機器、哪些機器使用過同一個USB盤。
下圖是另一類例子，瀚思幫銀行客戶做的交易異常分析：點大小與出度成正比， 顏色隨著入度大小按藍色⇒白色⇒紅色方向變化。用金融術語來說：出度過大的叫火山，入度過大的叫黑洞。這類情況往往和詐騙洗錢相關。
但是，圖一旦變大，分析過程會變慢，需要分析的邊數量，即使最壞不會到全連通有向圖中等于節點數N的N*(N-1)/2， 也往往遠大于N。而且可視化因為屏幕大小和易讀性的限制，不宜再把成千上萬個節點和對應的邊放到一張圖上。
這種情況下，我們采用分而治之策略：利用實際經驗中圖的社區性特征，把圖分割成若干個強聯通的區域， 對每一個區域做分析和可視化。
好的圖劃分算法在實際應用中要額外有三個特征：
1、高速度，最好能并行化或者能用GPU加速。
2、能處理小世界網絡特征(也就是節點度數呈肥尾分布)。
3、對參數不敏感。
很多算法無法滿足2和3，教科書中算法大多是把圖均分，而且假設知道圖要分為多少類。
根據前文所述，瀚思利用“圖計算”在實際應用中，幫助客戶解決了有關異常行為檢測的工作。而本文將重點針對三類應用廣泛、效率較高并可以應用于異常檢測的圖劃分算法進行詳述。
譜劃分
譜劃分算法：它是最早用于解決圖劃分的一類算法，其思想來源于譜圖劃分理論。 矩陣的譜就是它的特征值和特征向量。 求圖劃分準則的最優解是一個NP難問題。 一個很好的求解方法是考慮問題的連續松弛形式，將原問題轉換成求解Laplacian 矩陣的譜分解， 因此將這類方法統稱為譜劃分。
假定將每個數據樣本看作圖中的頂點V，根據樣本間的相似度將 頂點間的邊 E 賦權重值，便可得到一個基于相似度的無向加權圖 G=(V,E). 相似矩陣通常用 W 或 A 表示，有時也稱為親和矩陣(Affinity Matrix)， 往往是通過計算高斯核得到。
將相似度矩陣的每行元素相加，即得到對應點的度，以所有度值為對角元素構成的對角矩陣稱為度矩陣，通常記為 D。定義好相似矩陣W及度矩陣D，便可得如下的 Laplacian 矩陣：L=D – W
根據不同的準則函數及譜映射方法，譜劃分算法發展了很多不同的具體實現方法，但都可以歸納為下面的三個主要步驟：
對于給定的圖G=(V,E)，計算圖的 Laplacian 矩陣L;
對L矩陣進行特征值分解，取其前 k 個特征值對應的特征向量，構建特征向量矩陣Q;
利用K-means算法或其他經典聚類算法對矩陣Q進行劃分，每一行代表一個樣本點, 即原圖的頂點所屬的類別.
上述步驟只是譜劃分的一個框架，在具體實現中，還存在著不同的劃分準則，常見的有 Minimum Cut，Ratio Cut，Normalized Cut等。
譜劃分算法，首先通過引入 Laplacian 矩陣，運用 Laplacian Eigenmap 進行降維，再對這些 低維數據利用聚類算法進行劃分，使得運算量大大較少.下圖是用譜劃分算法實現的效果圖：
但譜劃分算法也有一些不足之處：
1)構建特征向量矩陣Q無疑是該算法中最耗時間的， 在高維情況下, 不說求解特征向量就是求解特征值都非常困難;
2)需要借助先驗知識定義遞歸終止條件，即不具備智能識別圖類別總數的能力;
3)現實世界中的復雜網絡圖往往包含多個類，而遞歸的二分策略不能保證得到的劃分是最優的劃分。
多層劃分算法
第二類圖劃分算法，稱為*多層劃分(Multilevel Partitioning，1995，Karypis)*。
以高效及運算時間快著稱，比譜劃分算法快10%-50%， 計算千萬數級的圖，時間基本是以秒計算。其主要實現步驟通常分為圖的 粗化階段(Coarsening phase), 初始劃分階段(Initial partitioning phase)和細化階段 (Uncoarsening phase)三個階段。
簡言之，如下圖所示，該算法就是將原始圖經粗化階段一層一層壓縮變“小”，得到頂點數目足夠小的圖， 再將這個數目足夠小的圖經過初始劃分階段和細化階段一層一層還原變“大”，直到還原成原始圖，完成劃分。
粗化階段主要是為了減少原始圖的復雜性，構建圖的多級層次. 它對原始圖的點和邊進行壓縮合并， 構造了一個層次化的較小的圖序列, 最終將原始圖壓縮成一個頂點數目足夠小的圖。 這種壓縮的思想(詳見下圖)可以形式化地定義為匹配 (Matching)，圖的匹配是指 邊的集合，其中任意兩條邊都沒有公共頂點。 在一個圖的所有匹配中，所含匹配邊數最多的匹配，稱為這個圖的最大匹配.
在整個粗化階段，原始圖的所有點以及權重都會累計，最終反應在最小規模圖。 將最小規模圖進行簡單的劃分，稱為初始劃分階段，該階段由于結點數目較少，運算非常快，基本不耗時。 也不是多層算法的核心部分，其算法與接下來的細化階段算法聯系比較相似，這里不再贅述.
細化階段，也可稱為圖的還原優化階段，該階段按照粗化層次一層一層將圖還原成原始圖，并在還原過程中 利用某些精細的算法逐層優化，直到得到對原始圖的劃分.
這其中的常見的劃分算法有譜二分法算法有Spectral Bisection(SB)，Graph Growing Algorithm(GGP), Greedy Refinement(GR)， Kernighan-Lin Refinement(KLR)等， 其中比較著名的是Kernighan-Lin劃分算法。
*Kernighan-Lin劃分算法*，簡稱KL算法，由Kernighan和Lin在1970年提出，是一個局部搜索優化算法, 優化的目標函數是連接不同類的邊權之和最小。
舉個簡單的例子，如下圖，紫色的點屬于一類，黑色的點屬于一類，KL算法是實現將下圖(a)轉換成下圖(b)的過程。
如何實現將紫色類別中的點和黑色類別中的點進行交換，則是通過計算不同類別損失權重的差值來判斷的， 即交換前的內外權重差(如下圖(a)的數字所示)減去交換后的內外權重的值。當且僅當該值為正進行交換，否則拒絕交換。 重復以上步驟，直至該值為負。
KL算法，較易理解，但得到的解往往是局部最優。下圖，是利用多層劃分算法進行圖劃分的例子：
多層劃分算法最大的局限在于它最大的局限性在于需要先驗知識來產生一個較好的初始類。
MCL
最后談談，Markov Cluster Algorithm(2000, Stijn van Dongen), 簡稱MCL算法，是一種快速可擴展的 無監督圖形聚類算法，有時也可以用于圖的劃分，其思想非常簡單，主要是基于 隨機游走(Random walk) 和馬爾科夫鏈 (Markov chain)。 先簡單說一下這兩個概念.
隨機游走說的是，如果我們從圖中的某一個點開始“瞎轉”，那么很可能就會在某一個子圖里面轉悠，而不是在子圖間來回游蕩. 而隨機游走的計算是通過 Markov鏈來實現的. Markov鏈指的是一個隨機序列，該序列滿足“無后效性”，即 將來的狀態只依賴當前狀態，而與過去的狀態無關。
MCL算法的關鍵思想就是：”隨機漫游者抵達稠密的類后，不會輕易的離開該類”. 前者是隨機游走的過程，后者依據是 Markov鏈的“無后效性”。 MCL算法中隨機漫游的過程，其實是一個不斷修改轉移概率矩陣的過程，該過程 重復執行擴展(Expansion)和膨脹(Inflation)兩個操作。
擴展就是前面提到的馬爾科夫鏈的轉移矩陣的極限分布， 這個步驟不斷地對轉移概率矩陣進行自乘直到它不再改變為止。 目的是連接圖的不同區域。膨脹是對每一個元素進行冪操作，再將每一列歸一化，目的是為了強鄰居的連接更強， 弱鄰居的連接更弱，也就是讓轉移矩陣中概率大的概率更大，而小的更小。 這兩個操作重復執行一直到概率轉移矩陣收斂為止，得到最終的矩陣，根據最終的矩陣便可得結果。
MCL算法對無權圖及有權圖均試用，劃分的子圖個數無需事先設定，這是該算法的 最大優勢; 劃分的子圖是非均勻的，試用于長尾分布的數據。 下圖就是利用 MCL 進行圖劃分的結果：
但是MCL算法對圖的直徑較大的情況不適用。(直徑是指兩個點之間的距離最大值，距離是兩個點之間的所有路的長度的最小值)
京公網安備 11010502049343號