3.3.2　圖計(jì)算

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

標(biāo)簽傳播（Label Propagation Algorithm，LPA）是一種基于關(guān)聯(lián)圖的半監(jiān)督學(xué)習(xí)方法，利用已標(biāo)記的樣本來推論未標(biāo)記的樣本。標(biāo)簽傳播算法的核心在于利用節(jié)點(diǎn)之間邊的權(quán)重構(gòu)建轉(zhuǎn)移矩陣，每輪傳播后更新除已標(biāo)記樣本外其他樣本的標(biāo)簽，直至所有樣本的標(biāo)簽收斂。標(biāo)簽傳播算法最大的優(yōu)勢是簡單高效，不過也存在結(jié)果不穩(wěn)定等問題。

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