3.3.2　圖計(jì)算

圖計(jì)算（Graph Computing）是以關(guān)聯(lián)圖譜為基礎(chǔ)引申出來(lái)的一類(lèi)算法的統(tǒng)稱(chēng)，主要解決了圖數(shù)據(jù)模型的表示和計(jì)算問(wèn)題。圖計(jì)算是目前比較熱門(mén)的一個(gè)研究方向，比較成熟的應(yīng)用場(chǎng)景有社區(qū)發(fā)現(xiàn)、標(biāo)簽傳播、圖嵌入等。社區(qū)發(fā)現(xiàn)（Communication Detection）主要用于關(guān)聯(lián)圖中社區(qū)的劃分，與聚類(lèi)算法的目標(biāo)類(lèi)似，我們也希望社區(qū)劃分后每個(gè)社區(qū)內(nèi)部節(jié)點(diǎn)聯(lián)系密切，而社區(qū)之間的連接較為稀疏，因而這里定義了模塊度的概念。簡(jiǎn)單理解，模塊度是社區(qū)內(nèi)部節(jié)點(diǎn)的連接邊數(shù)與隨機(jī)情況下邊數(shù)的差，這個(gè)差值越大說(shuō)明社區(qū)內(nèi)部的連接程度越緊密。以最大化全局模塊度為學(xué)習(xí)目標(biāo)，就有了經(jīng)典的Louvain算法。Louvain算法在初始化的時(shí)候?qū)⒚總€(gè)節(jié)點(diǎn)看作一個(gè)社區(qū)，通過(guò)分配節(jié)點(diǎn)使得相鄰社區(qū)的模塊度增益最大，直至所有社區(qū)不再變化，之后將生成的社區(qū)壓縮成一個(gè)新的節(jié)點(diǎn)，重復(fù)上述工作，直至整個(gè)圖中的模塊度不再變化。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)記的樣本來(lái)推論未標(biāo)記的樣本。標(biāo)簽傳播算法的核心在于利用節(jié)點(diǎn)之間邊的權(quán)重構(gòu)建轉(zhuǎn)移矩陣，每輪傳播后更新除已標(biāo)記樣本外其他樣本的標(biāo)簽，直至所有樣本的標(biāo)簽收斂。標(biāo)簽傳播算法最大的優(yōu)勢(shì)是簡(jiǎn)單高效，不過(guò)也存在結(jié)果不穩(wěn)定等問(wèn)題。

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