前言
圖是對事物之間關(guān)系的一種原生的表達(dá)，利用圖可以深入直接地認(rèn)識世界中的關(guān)聯(lián)。社交網(wǎng)絡(luò)、交易數(shù)據(jù)、知識圖譜、交通運(yùn)輸、生物技術(shù)等都是圖數(shù)據(jù)的典型應(yīng)用。
社交網(wǎng)絡(luò)是一種特殊的圖數(shù)據(jù)，它建立在圖網(wǎng)絡(luò)的基礎(chǔ)上，又遵循一定的社會學(xué)理論。
EasyGraph是復(fù)旦大學(xué)MSN小組開發(fā)的一款基于Python語言的圖計(jì)算開源包，它是第一個(gè)包含全面的結(jié)構(gòu)洞占據(jù)者探測方法的開源庫，同時(shí)覆蓋了圖嵌入和其他一些傳統(tǒng)的圖計(jì)算方法。Easygraph補(bǔ)齊了現(xiàn)有的圖分析開源庫如igraph, NetworkX在社交網(wǎng)絡(luò)領(lǐng)域的短板，同時(shí)利用混合編程和并行計(jì)算提高了運(yùn)行效率
什么是結(jié)構(gòu)洞理論
由于細(xì)化的工作分工，人們聚集到不同的群體中。在同一個(gè)群體中，人們的交流比跨群體的交流更密切，從而逐漸在不同社區(qū)之間形成術(shù)語障礙。在封閉網(wǎng)絡(luò)中，人們可以以較低的成本獲得更高可信度的信息。這些封閉的網(wǎng)絡(luò)或社區(qū)可以促進(jìn)內(nèi)部交流和社區(qū)發(fā)展，并產(chǎn)生冗余和重疊的信息。
根據(jù)伯特提出的結(jié)構(gòu)洞理論，充當(dāng)這些社區(qū)的橋梁和中介的，就是結(jié)構(gòu)洞占據(jù)者。結(jié)構(gòu)洞占據(jù)者與社交網(wǎng)絡(luò)的不同社區(qū)的聯(lián)系增加了它在競爭領(lǐng)域的社會資本，而具有同質(zhì)和重復(fù)信息的封閉網(wǎng)絡(luò)不會帶來這樣的優(yōu)勢。這就是結(jié)構(gòu)洞理論的核心。
結(jié)構(gòu)洞的潛在價(jià)值在于信息效益和控制效益。結(jié)構(gòu)洞占據(jù)者占據(jù)了社區(qū)之間獨(dú)特的連接位置，從而可以訪問多個(gè)非冗余信息源，獲取高價(jià)值信息。在社會學(xué)研究中，社區(qū)中信息、想法和創(chuàng)新匯集的個(gè)體被稱為意見領(lǐng)袖。結(jié)構(gòu)洞占據(jù)者得益于互聯(lián)社區(qū)的獨(dú)特信息，擁有與意見領(lǐng)袖互動的優(yōu)先權(quán)，從而發(fā)掘有利可圖的機(jī)會。
基于社交網(wǎng)絡(luò)分析，結(jié)構(gòu)洞理論已經(jīng)被開發(fā)出諸多應(yīng)用場景。結(jié)構(gòu)洞被用于企業(yè)人力資源管理，以及社交關(guān)系中高收益聯(lián)系的建立。同時(shí)由于結(jié)構(gòu)洞占據(jù)者占據(jù)了連接不同社區(qū)的關(guān)鍵結(jié)構(gòu)位置，結(jié)構(gòu)洞理論也被用于在傳播信息方面最大化影響力。
由于結(jié)構(gòu)洞體現(xiàn)了圖的整體和局部結(jié)構(gòu)，結(jié)構(gòu)洞理論在不同的層面上都具有巨大的應(yīng)用潛力
個(gè)體層面：分析個(gè)人行為和屬性；預(yù)測用戶情緒等
連接層面：鏈路預(yù)測；預(yù)測投資行為；分析社會關(guān)系等
圖級層面：圖分類，圖同構(gòu)和圖分區(qū)等
全面的圖網(wǎng)絡(luò)分析工具
Easygraph的架構(gòu)包含：
圖的輸入輸出
圖的可視化：利用結(jié)構(gòu)洞占據(jù)者標(biāo)記，CDF圖和節(jié)點(diǎn)定位對復(fù)雜網(wǎng)絡(luò)進(jìn)行完整呈現(xiàn)
karate club數(shù)據(jù)集的結(jié)構(gòu)洞占據(jù)者標(biāo)記 |
karate club數(shù)據(jù)集CDF圖 |
圖分析方面，Easygraph覆蓋了圖表示學(xué)習(xí)，經(jīng)典網(wǎng)絡(luò)算法和結(jié)構(gòu)洞占據(jù)者檢測方法：
圖表示學(xué)習(xí) ：DeepWalk,Need2Vee,LINE,SDNE等
社區(qū)檢測，中心性，Component,Clustering等方法
Easygraph集成了全面的結(jié)構(gòu)洞占據(jù)者探測方法，包含：
基于信息流的HIS, MaxD,HAM,NOBE,maxBlock等算法
基于網(wǎng)絡(luò)中心性的WeakTie-Local,WeakTieBi,ICC,BICC,Ap_Greedy等算法
基于此架構(gòu)，Easygraph能夠在生物，交通，化學(xué)，社會，生態(tài)等眾多領(lǐng)域的圖數(shù)據(jù)分析中發(fā)揮應(yīng)用價(jià)值
易用性和運(yùn)行效率
Easygraph注重API的易用性和極低學(xué)習(xí)成本
以下是一個(gè)以6行python代碼實(shí)現(xiàn)對圖數(shù)據(jù)進(jìn)行結(jié)構(gòu)洞占據(jù)者分析并可視化的示例
from easygraph.datasets import get_graph_karateclub
import easygraph as eg
G = get_graph_karateclub()
# Calculate five shs(Structural Hole Spanners) in G
shs = eg.common_greedy(G, 5)
# Draw the Graph, and the shs is marked by red star
eg.draw_SHS_center(G, shs)
# Draw CDF curves of "Number of Followers" of SH spanners and ordinary users in G.
eg.plot_Followers(G, shs)
深入了解Easygraph
