3.3.2　圖計算

圖計算（Graph Computing）是以關聯圖譜為基礎引申出來的一類算法的統稱，主要解決了圖數據模型的表示和計算問題。圖計算是目前比較熱門的一個研究方向，比較成熟的應用場景有社區發現、標簽傳播、圖嵌入等。社區發現（Communication Detection）主要用于關聯圖中社區的劃分，與聚類算法的目標類似，我們也希望社區劃分后每個社區內部節點聯系密切，而社區之間的連接較為稀疏，因而這里定義了模塊度的概念。簡單理解，模塊度是社區內部節點的連接邊數與隨機情況下邊數的差，這個差值越大說明社區內部的連接程度越緊密。以最大化全局模塊度為學習目標，就有了經典的Louvain算法。Louvain算法在初始化的時候將每個節點看作一個社區，通過分配節點使得相鄰社區的模塊度增益最大，直至所有社區不再變化，之后將生成的社區壓縮成一個新的節點，重復上述工作，直至整個圖中的模塊度不再變化。Louvain在Spark環境下已經實現分布式，因而可以較好地支持工業界的需求。

標簽傳播（Label Propagation Algorithm，LPA）是一種基于關聯圖的半監督學習方法，利用已標記的樣本來推論未標記的樣本。標簽傳播算法的核心在于利用節點之間邊的權重構建轉移矩陣，每輪傳播后更新除已標記樣本外其他樣本的標簽，直至所有樣本的標簽收斂。標簽傳播算法最大的優勢是簡單高效，不過也存在結果不穩定等問題。

圖嵌入（Graph Embedding）借鑒了NLP中word2vec的思想，將關聯圖中的節點嵌入某個高維空間中，使得每個節點向量化，并且映射后的向量還能夠保留圖的結構和性質。圖嵌入的方式有很多，例如DeepWalk、Line、node2vec、SDNE等，并沒有絕對意義上最優的嵌入方式，需要建模人員根據數據的分布特性和實際業務效果，不斷地嘗試和迭代。圖嵌入后的向量可以表示每個樣本的社交屬性，既可以作為入模特征放到欺詐或者風險模型中訓練，又可以利用聚類算法進行客群間的劃分。