圖演算法練手 by networkx part1
- 2020 年 5 月 11 日
- AI
下面提到的圖演算法除了一般意義上的演算法，還包括了基於圖數據的一些統計指標，例如度，中心性等等。
才疏學淺，關於圖演算法的高級應用，比如用圖神經網路來做欺詐檢測這類的應用沒怎麼接觸過，目前接觸過的，所了解的，主要是以規則為主，圖演算法在其中扮演的角色偏輔助，通過節點的pagerank值來查找活躍用戶，或者使用社區發現來找到關聯緊密，並且關聯用戶很大的社區等等，通過這些方式首先找到非正常的用戶（在金融領域中，異常活躍往往意味著風險；在金融領域中，較少存在非常大的社區結構等），然後對這些用戶進行一些eda，比如在薅羊毛的問題中，看看這類用戶的平均獲取的羊毛數量，例如用戶獲得的積分總額，用戶獲取的紅包總額等等。 簡而言之，目前所接觸到的所謂的反欺詐比較初階，圖演算法只是作為業務的輔助應用。
下面介紹的演算法主要來自於：
1、《智慧風控》；
2、《Network Science with Python and NetworkX Quick Start Guide 》；
3、O』Reilly 系列的《Graph Algorithms》
然後演算法的分類，感覺按照networkx的官方文檔的分類方法還是比較準確全面的。注意，networkx2.X和1.X版本的差異蠻多的，所以還是看2.0的官方文檔吧：
networkx.algorithms.community.kclique.k_clique_communities – NetworkX 2.4 documentation
當然，不可能一個一個去研究所有的圖演算法，只會挑其中比較熱門的、常提到的、業務中可能會用到的一些演算法進行學習或分享，而這個挑選的過程就是參照上面給的三份材料來的。
pandas的格式要處理成這樣的，左邊是source節點右邊是target節點，value是權重，其它的屬性可以以列的形式添加，這是以edge形式存儲的圖數據的表格形式，其實通過join或者merge的方法很容易構造出這樣的數據集。這也給普通的表格數據轉圖數據提供了一個較好的範例；
首先，最基本的，計算節點的度：
nx.degree(G) 
如果是有向圖，則：
G=nx.from_pandas_edgelist(edge_list,edge_attr='weight',create_using=nx.DiGraph)
plt.figure(figsize=(15,10))
nx.draw(G,with_labels=True,
edge_color='grey',
node_color='pink',
node_size = 50,
font_size = 14,
pos=nx.spring_layout(G,k=0.2))
如果要計算其出度於入度則：
所有的度：
可以發現有向圖的nodes的degree都增加了一倍，因為把出入都算進去了，如果是無向圖則出入度不重複計算（也就沒有出入度的概念了）
如果要實現帶權則：
計算degree的時候把nodes的屬性中的某個屬性指定為weight，帶權圖的權重作為nodes的屬性之一進行設計。
有向帶權圖也是一樣的，非常簡單；
這樣我們就能很方便的得到每一個樣本的度了，然後我們將其轉化為dict：
dict(G.out_degree())
再使用map就可以直接將每個樣本的度對應到原始的dataframe里去了：
對於中小型數據來說，這種處理方式非常的簡單容易上手了。
前面提到了圖數據的特徵抽取方法之一——度，這種方法的問題在於沒有考慮到節點的領節點的具體資訊，舉個例子，例如微博，我們如果簡單的通過明星-粉絲的網路結構，計算明星的degree，則顯然計算結果會受到「買粉」問題影響嚴重，明星的粉絲水分非常嚴重，但是degree的計算方式並不考慮明星的粉絲號的具體的數據情況，單純的根據連接明星的邊來計算其度，那麼如何處理，明星的機器人粉一般都是非常不活躍的用戶，永遠都是給明星點贊轉發，除此之外再也沒有任何的其它的社交行為發生，因此，這類殭屍粉的活躍度是非常低的，這也意味著殭屍粉本身可能基本上沒什麼粉絲或者粉絲數量稀少，那麼這種情況下，我們可以通過改進的eigenvector。
eigenvector的思路很簡單，一個活躍的用戶（中心度強），不僅僅體現在其朋友多，他的朋友也應該是活躍的，因此節點B的中心都定義為：
B=Wa*A+Wc*C+beta
這裡我們假設B的鄰節點只有A和C，W對應的連接的邊的權重，如果無權則默認為1，beta是隨機初始化的值。max_iter是迭代次數，tol是收斂的判斷標準，nstart可用於自定義初始權重，weight用於指定邊的權重。
然後和上述操作一樣可以合併到原始的特徵矩陣中。
不過eigenvector也存在問題，比如賣粉公司，這些垃圾公司有幾百萬個虛擬的微博賬戶，專門給買粉的人點贊，雖然eigenvector計算出來這些買粉的人的中心都都會較低，但是架不住人多，這個時候我們就可以用上pagerank了。
pagerank的原理可見上，這裡舉個例子很好理解：
pagerank和eigenvector一樣隨機為每個node初始化一個值，然後迭代到收斂，以上圖這個有向圖為例，B僅僅指向C節點，而A指向B和C節點，因此：
pagerank（C）=alpha * （1/2*pagerank(A)+1*pagerank(B)）+beta
其中beta是隨機初始化的值，pagerank()表示這個節點的pagerank值用于衡量nodes的熱門程度，alpha表示整個迭代過程中的所謂阻尼係數；
因為A指向了2個節點，所以A的貢獻度應該是減半的。當然，以上面的偶像微博的例子為例，一個殭屍粉給一大堆明星點贊的話，那麼使用pagerank可以較好的得到明星的真實的熱門程度，說老實話，如果微博公開了它的原始的數據，明星的真實熱門水平甚至是真實的粉絲數會被扒得一乾二淨。
Google當初發明pagerank主要是針對有向圖的，但是networkx也可以針對無向圖，具體的做法就是把無向圖當作雙向圖，從而進行計算，以上面的A、B、C為例，假設上圖為無向圖，則計算公式為：
pagerank（C）=alpha * （1/2*pagerank(A)+1/2*pagerank(B)）+beta
把無向當雙向，則適用於有向圖的演算法可以非常簡單迅速的移植到無向圖上來。
import networkx as nx
nx.pagerank(G,alpha=0.9) 
上述三種方法都是從近鄰節點的角度來描述節點的中心度的，除此之外還可以通過最短路徑的方式來定義節點的中心度：
已經有大佬解釋過了~，
如何簡單地理解中心度，什麼是closeness、betweenness和degree？
這裡直接用程式碼驗證一下：
G = nx.Graph() # 創建無(雙)向圖
edges=[('A','B'),('B','C'),('C','D')]
G.add_edges_from(edges)
plt.figure(figsize=(15,15))
pos=nx.shell_layout(G)
nx.draw(G,pos,with_labels=True)
所以原理很簡單，就是計算圖G上的所有路徑的數量之和，然後某個節點的betweeness中心度就是經過G的路徑的數量除以總的路徑數量，至於路徑總數的計算可以使用深度或者廣度優先的方式來計算得到，至於networkx是如何計算的不太清楚，也不重要，不複雜，數據結構與演算法得複習複習了。。。//www.cnblogs.com/DWVictor/p/10048554.html
補充，betweeness意味著在中間，也就是節點必須在至少兩個節點之間才算是這個節點的路徑，例如上圖的A不再任意兩個節點之間，因此其betweeness的計算結果為0，因為沒有最短路徑；
原理也很簡單，以A為例，A和B、C、D都通過不同長度的路徑建立了連接，則A的closeness為 （連接節點數）/連接路徑長度之和。
關於上述演算法在有無向、有無權的不同類型的圖上的計算差異其實是非常好理解的，感興趣的可以用demo自己跑一下就知道結果了，這裡就不廢話了。
除此之外，還可以通過jaccard相似性來度量節點的一度關聯的相似性，公式也很簡單
jaccard(a,b)=U(a)交U(b)/U(a)並U(b)，U表示取節點的一階鄰節點，交表示交集，並表示並集：
還是以上面的demo為例：
a和c節點的共同鄰節是B，數量為1，A和B的所有鄰節點的交集為(B,D)，因此其jaccard相似性為1/2=0.5.
這裡主要介紹了一些比較常用且簡單的計算中心度和相似性的圖演算法，注意，上述介紹的演算法主要的作用常作為特徵的抽取工具，不直接支援決策，也可以作為一種輔助分析的手段。
後面繼續介紹更複雜一些的圖演算法，例如經典的社區發現 標籤傳播 等，至於一些相對新的反欺詐類型的演算法，不知道有沒有demo。。。圖神經網路等這兩個月忙好了慢慢整理應用程式碼。
補充：
G = nx.Graph() # 創建無(雙)向圖
edges=[('A','B'),('B','C'),('C','D'),('A','C')]
G.add_edges_from(edges)
plt.figure(figsize=(15,15))
pos=nx.shell_layout(G)
nx.draw(G,pos,with_labels=True)
triangles = nx.triangles(G)
sorted(triangles.items(), key=lambda x:x[1], reverse=True)[0:10]
節點所在三角形的數量，也是一個常看到的基於圖數據的統計特徵；
還有一個是聚類係數
三角計數（Triangle Count）和聚類係數（Clustering Coefficient）經常被一起使用。三角計數計算圖中由節點組成的三角形的數量，要求任意兩個節點間有邊（關係）連接。聚類係數演算法的目標是測量一個組的聚類緊密程度。該演算法計算網路中三角形的數量，與可能的關係的比率。聚類係數為 1 表示這個組內任意兩個節點之間有邊相連。
有兩種聚類係數：局部聚類係數（Local Clustering Coefficient）和全局聚類係數（Global Clustering Coefficient）。
局部聚類係數計算一個節點的鄰居之間的緊密程度，計算時需要三角計數。計算公式：
其中，
u代表我們需要計算聚類係數的節點，R(u)代表經過節點u和它的鄰居的三角形個數，k(u)代表節點u的度。下圖是三三角計數聚類係數計算示意圖：
clustering = nx.clustering(G)
clustering
以點A為例，點A所在三角形個數為1，點A的度為2（和B、C互相連接），因此按照公式點A的局部聚類係數為 1，其它點計算結果也是一樣一樣的。
全局聚類係數是局部聚類係數的歸一化求和。我們計算出所有nodes的局部聚類係數之後做歸一化即可。
當需要計算一個組的穩定性或者聚類係數時，我們可以使用三角計數。三角計數在社交網路分析中有廣泛的應用，通航被用來檢測社區。聚類係數可以快速評估特定組或整個網路的內聚性。這些演算法可以共同用於特定網路結構的尋找。例如，探索網頁的主題結構，基於網頁之間的相互聯繫，檢測擁有共同主題的 「網頁社群」。
