金融風控反欺詐圖算法先介紹下金融借貸業務流程：用戶前來申請借貸，會先經過欺詐識別，把欺詐團伙和主觀欺詐的個人拒絕掉，然后對通過的人做信用評估，最后根據額度模型，算出利潤最大化時放款金額。剛才提到了團隊欺詐，舉個真實的例子。宜人貸在他們的財報中公布的，他們被20004w8000w那么如何防范這種風險呢。這就是今天要分享的圖算法。圖可以將這些一個個有良好記錄的個體關聯起來,一網打盡。再舉一些團伙欺詐的行為。比如一個團伙，注冊真實的淘寶商家，然后刷出良好的淘寶購物記錄。或者來回轉賬，刷出良好的銀行流水。剛才前兩位老師都沒有提到額度模型，簡單介紹下，如果只給用戶放款5000，可能壞賬風險很小，但是利息也少，如果放款10000，利息雖然收到利息多了，但是壞賬風險高嶺，所以需要做個權衡Graph簡介G=(V,E)G=(V,E)V:vertexsetE:edgeset有向，無向，有權重和沒有權重)舉例，兩個人之間的聯系，A給B買了東西，A和B之間的通話次數時長多于A和C之間。度中心性（DegreeCentrality）-表示連接到某節點的邊數。在有向圖中，2接近中心性（ClosenessCentrality）-從某節點到所有其他節點的最短路徑的平均長度。反映在網絡中某一節點與其他節點之間的接近程度。介中心性（BetweennessCentrality）-某節點在多少對節點的最短路徑上。社團發現算法一般有：最小割，正則化割:通過計算圖的最小割，即將網絡劃分為預定的分組數，并使連接各分組的邊的條數最少。非負矩陣分解:基本原理是將原始矩陣分解得到社區指示矩陣和基矩陣基于模塊度的社區劃分基于節點相似性的社區劃分最小割算法廣泛應用在分布式計算的負載均衡中，對集群節點的分組有利于減少不相關節點之間的通信。然而由于該算法限定了網絡最終分組的個數，而不能通過算法“發現”節點間的內在聯系并自然地構成若干個社區，因此最小割算法應用較為局限。本文主要分享這兩類的主要算法，基于模塊度的louvain和基于信息熵infomap，基于相似度的node2vec模塊度(Modularity)公式及簡化優化目標：一般認為社團內部的點之間的連接相對稠密，而不同社團的點之間的連接相對稀疏。所以模塊度也可以理解是社區內部邊的權重減去所有與社區節點相連的邊的權重和，對無向圖更好理解，即社區內部邊的度數（內部的連線數）減去社區內節點的總度數。模塊度公式的解釋節點i和節點j之間邊的權重，網絡不是帶權圖時，所有邊的權重可以看做是1；表示所有與節點i相連的邊的權重之和（度數）；表示節點i所屬的社區；表示所有邊的權重之和（邊的數目）。其中 表示社區c內的邊的權重之和， 表示與社區c內的節點相的邊的權重之和，即社區c節點的度之和（包含與其他社區相連邊的度）。從概率的角度去看：表示實際情況下，c社區內產生邊的概率。表示在一種理想情況下，給定任意節點i的的度ki，對節點i和節點j進行隨機連邊，邊屬于社區c的概率期望。于是上式就表示了社區內連邊數與隨機期望的一個差值。連邊數比隨機期望值越高，表明社區劃分的越好。一般使用后面簡化的公式，簡化后的公式刪除了判斷兩個節點是否劃為同一個社區的函數，所以在一定程度上大大減少了Q值計算量。LouvainLouvain算法的思想很簡單：將圖中的每個節點看成一個獨立的社區，此時社區的數目與節點個數相同；i配前與分配后的模塊度變化，并記錄最大的那個鄰居節點，如果，則把節點i分配最大的那個鄰居節點所在的社區，否則保持不變；2，直到所有節點的所屬社區不再變化；對圖進行壓縮，將所有在同一個社區的節點壓縮成一個新節點，社區內節點之間的邊的權重轉化為新節點的環的權重，社區間的邊權重轉化為新節2，3；2~4，直到整個圖的模塊度不再發生變化。第一階段稱為ModularityOptimization，主要是將每個節點劃分到與其鄰接的節點所在的社區中，以使得模塊度的值不斷變大；第二階段稱為CommunityAggregation，主要是將第一步劃分出來的社區聚合成為一個點，即根據上一步生成的社區結構重新構造網絡。重復以上的過程，直到網絡中的結構不再改變為止。移動是社區c內節點與節點i的邊權重之和，再乘以2前面部分表示把節點i加入到社區c后的模塊度，后一部分是節點i作為一個獨立社區和社區c的模塊度Louvain社區發現算法\h/fengfenggirl/p/louvain.html\hSparkGraphX分布式圖計算實戰infomap從信息論的角度出發，假設一個randomworker在圖上進行隨機游走，那么怎么用最少的編碼長度來表示其路徑呢？如果節點存在社區結構，那么社區內的節點就可以共享社區的bit位碼，可以得到更小的平均比特,所以社區劃分的越好，那么表示任意一條隨機游走的路徑所需的平均比特就越小。如果我們能夠計算出每個節點的到達概率，就可以依據信息熵的公式來量化平均比特了：怎么計算每個點的到達概率呢？一個暴力的辦法是在圖上進行長時間的隨機游走，最后統計每個節點的出現概率。太暴力了。利用pagerank思路，初始化了每個節點的到達概率之后，就可以不斷地迭代更新每個節點的到達概率，這個結果會很快趨于收斂。其實這過程就是一個馬爾科夫隨機過程，隨機初始化起始值，然后隨機游走就相當于不停地用概率轉移矩陣相乘，最后就可以達到馬爾科夫穩態。把隨機游走事件歸為三類：進入某個社團，離開某個社團，再社團內部游走。定義清楚各類事件的發生概率，依據信息熵公式，就可以得到此時編碼所需的平均比特了,其本質就是從信息論的角度出發。Infomap算法的迭代過程初始化，對每個節點都視作獨立的社區；while平均比特的值不再下降；參考鏈接Themapequation\h/apps/MapDemo.html\h/s/qUxMesQA-edSyHeudQRRGADEEPGRAPHINFOMAX閱讀筆記/p/58682802GraphembeddingsDeepwalk使用隨機游走(RandomWalk)的方式在圖中進行節點采樣獲得節點共關系，skip-gram1中生成的節點序列學習每個節點的向量表示。skip-gram就是根據給定輸入的節點，預測上下文節點。Deepwalk有多不足，比如泛化能力，有新節點加入時，它必須重新訓練模型以表示該節點。其中一個就是采樣，從其鄰居中隨機采樣節點作為下一個訪問節點，是一種可重復訪問已訪問節點的深度優先遍歷算法。node2vec是一種綜合考慮DFS鄰域和BFS鄰域的graphembedding方法node2vec優化目標：條件獨立假設：特征空間的對稱性：優化目標：計算量非常大，所以論文采用負采樣(negativesample)進行近似計算。這個node2vec優化目標函數，因為它跟大名鼎鼎的word2vec是一樣。我們最初是用一個Python寫的包，跑一遍算法需要一周。后來想，既然優化目標是一樣的，那能不能用word2vec包，因為word2vec用c寫的，而且還采用了HierarchicalSoftmax，negativesampling加速。然后在網上找到了一個套用word2vec實現的node2vec包，速度快很多。隨機游走的方式復雜網絡處理的任務其實離不開兩種特性，前面也提到過：一種是同質性，就是之前所說的社區。一種就是結構相似性，值得注意的是，結構相似的兩個點未必相連，可以是相距很遠的兩個節點。能不能改進DeepWalk中隨機游走的方式，使它綜合DFS和BFS的特性呢？所以本文引入了兩個參數用來控制隨機游走產生的方式。Z是分子的歸一化常數如果已經采樣了(t,v)，也就是說現在停留在節點v上，那么下一個要采樣的節點x是哪個？作者定義了一個概率分布，也就是一個節點到它的不同鄰居的轉移概率：直觀的解釋一下這個分布：如果t與x相等，那么采樣x的概率為；txx1；txxp、q的意義分別如下：返回概率p：DataFunTalk成就百萬數據科學家！如果pmaq,)t。如果p<q,)，那么采樣會更傾向于返回上一個節點，這樣就會一直在起始點周圍某些節點來回轉來轉去。出入參數q：如果q>1，那么游走會傾向于在起始點周圍的節點之間跑，可以反映出一BFS特性。如果q1DS特性。p，q1DeWak簡而言之：參數p控制重復訪問剛剛訪問過的頂點的概率，q控制著游走是向外還是向內，若q>1，隨機游走傾向于訪問和t接近的頂點(BFS)q<1t的頂點(DFS)。缺點慢embedding再聚類，感覺這兩個過程很割裂！！融合一下comEGraphembedding得到向量后，可以做很多事情，在我們這個主題可以簡單的通過聚類來講節點分組。但是這個過程比較割裂，先優化node2vec，然后再優化聚類。能不能整體上一次性優化完呢。comE這個算法優化目標中加入了社區的檢測和嵌入。通過一個混合高斯模型將節點劃分開。優化目標中前面兩項跟LINE定義的相似度相似：/u012151283/article/details/87013915LearningCommunityEmbeddingwithCommunityDetectionandNodeEmbeddingonGraphs/p/36924789Lea