CS224W-圖神經(jīng)網(wǎng)絡(luò) 筆記2.2：Properties of Networks and Random Graph Models -網(wǎng)絡(luò)模型（Graph Model）

本文總結(jié)之日CS224W Winter 2021只更新到了第四節(jié)，所以下文會參考2021年課程的PPT并結(jié)合2019年秋季課程進(jìn)行總結(jié)以求內(nèi)容完整
課程主頁：CS224W: Machine Learning with Graphs
視頻鏈接：【斯坦戈悸伲】CS224W：圖機(jī)器學(xué)習(xí)( 中英字幕 | 2019秋)

1 引言

學(xué)完前面兩節(jié)之后旦万，我們已經(jīng)可以通過一些指標(biāo)對網(wǎng)絡(luò)莽红，進(jìn)行定量的分析竭业。為什么在這里要插入一個(gè)網(wǎng)絡(luò)模型嘱兼？或者說国葬，我們?yōu)槭裁匆獙W(xué)習(xí)它？難道只是研究者之間的數(shù)學(xué)小游戲嗎芹壕？

所以汇四，在一頭扎進(jìn)紛繁的圖模型之前，我們需要先明白學(xué)習(xí)的目的和研究的意義踢涌！

1.1 模型的價(jià)值

源于預(yù)測的需要：模型是抽象的手段通孽，預(yù)測才是目的

前面老師也介紹了不同領(lǐng)域，不同系統(tǒng)的各類網(wǎng)絡(luò)睁壁，它們是單案個(gè)體的分析背苦，它們是否具有共性，是否能通過參數(shù)化的模型去模擬潘明，去擬合現(xiàn)實(shí)網(wǎng)絡(luò)行剂，以進(jìn)一步研究現(xiàn)實(shí)網(wǎng)絡(luò)的其他未知性質(zhì)。

舉個(gè)栗子钳降，就像今年疫情期間厚宰，被大家熟知的傳染病模型，根據(jù)理論推導(dǎo)的性質(zhì)遂填，預(yù)測爆發(fā)期铲觉，評估響應(yīng)時(shí)間，提前防控風(fēng)險(xiǎn)城菊”溉迹火神山、雷神山凌唬，國內(nèi)的緊急動員都是在理論指導(dǎo)下并齐，實(shí)際行動反映。推薦大家看下畢導(dǎo)的科普視頻客税。

https://www.bilibili.com/video/BV1j7411z7KQ

1.2 圖模型產(chǎn)生過程

通常一個(gè)圖模型的誕生况褪，有點(diǎn)像抽簽。研究人員通過隨便提個(gè)網(wǎng)絡(luò)模型更耻，分析網(wǎng)絡(luò)模型的性質(zhì)测垛，然后拿真實(shí)網(wǎng)絡(luò)對比驗(yàn)證，基于模型與現(xiàn)實(shí)之間的差異秧均，不斷修正模型到貼合現(xiàn)實(shí)情況食侮。這個(gè)和機(jī)器學(xué)習(xí)模型訓(xùn)練機(jī)制很像号涯，是個(gè)不斷迭代和精進(jìn)的過程。

下面老師介紹的三個(gè)模型的誕生和研究過程都是這個(gè)思路

圖片

其實(shí)锯七，網(wǎng)絡(luò)模型研究至今链快，除了老師介紹的3個(gè)，還有很多模型眉尸，我找了些資料域蜗，整理了一個(gè)思維導(dǎo)圖供大家參考。

圖片

說著這么多噪猾，下面進(jìn)入具體理論部分霉祸。

2 圖模型的分類

2.1 ES隨機(jī)圖模型

ES隨機(jī)圖模型（Erd?s-Renyi Random Graph Model），用于生成無向圖袱蜡，它有兩類：

$G_{np}$ ： $n$ 個(gè)節(jié)點(diǎn)的無向圖丝蹭，每條邊以概率 $p$ 獨(dú)立隨機(jī)(i.i.d)出現(xiàn)
$G_{nm}:$$n$ 個(gè)節(jié)點(diǎn)的無向圖， $m$ 條邊一均勻分布概率隨機(jī)出現(xiàn)

課上老師重點(diǎn)介紹了第一類 $G_{np}$

圖片

下面研究下這類網(wǎng)絡(luò)的四大屬性情況:

2.1.1 $G_{np}$ 的度分布（Degree distribution）

$G_{np}$ 的度分布是二項(xiàng)分布（binomial）戒劫。

根據(jù)二項(xiàng)分布的性質(zhì)半夷，可以得到度平均為 $\overline{p}=p*(n-1)$

2.1.2 $G_{np}$ 圖的聚類系數(shù)（Clustering coefficient）

老師用公式推到，其實(shí)可以根據(jù)聚類系數(shù)定義：節(jié)點(diǎn)的鄰居節(jié)點(diǎn)彼此相連的概率迅细。還記得 $G_{np}$ 的前提假設(shè)嗎巫橄？這個(gè)概率就等于任意兩點(diǎn)之間相連的概率 $p$ 。

這里有個(gè)前提茵典，當(dāng)節(jié)點(diǎn)數(shù) $n->\infty$ 時(shí)湘换，大圖的平均度趨于一個(gè)常數(shù)。這和直覺也是一致的统阿，通常社交網(wǎng)絡(luò)中一個(gè)人的好友數(shù)量彩倚，并不會隨著人口的增加而增加。所以根據(jù)上面平均度的定義扶平，就可以得到聚類系數(shù) $C=\frac{\overline{k}}{n-1}\approx\frac{\overline{k}}{n}$

2.1.3 $G_{np}$ 圖的連通分量

這里我調(diào)整了連通性和路徑長度的順序帆离，更利于路徑長度的理解。這里課上老師跳過了一頁P(yáng)PT结澄。

隨著概率的不斷增大哥谷，圖的連接情況，會發(fā)生變換麻献。

圖片

老師做了個(gè)實(shí)驗(yàn)们妥，對于10萬個(gè)節(jié)點(diǎn)的圖， $k=p(n-1)$ 從0.5到3對于巨分支的節(jié)點(diǎn)占比情況勉吻。

圖片

可見监婶，當(dāng)平均度 $k=p(n-1)>1$ 時(shí)，巨分支就開始出現(xiàn)。這個(gè)結(jié)論很重要惑惶！

2.1.4 $G_{np}$ 圖的路徑長度（Path Length）和直徑

老師先引入了一個(gè)定義擴(kuò)展系數(shù) Expension $\alpha$ ,公式如下：

圖片

它描述了圖的任意節(jié)點(diǎn)集與剩余節(jié)點(diǎn)之間邊的數(shù)量煮盼。可以理解為任取圖中節(jié)點(diǎn)的一個(gè)子集带污，下一步（step）處達(dá)的最小節(jié)點(diǎn)數(shù)目孕似。

（平均）路徑長度

基于expension定義,老師給出路徑長度為 $O((logn)/\alpha)$ 。說實(shí)話刮刑，具體的證明，我不會养渴，網(wǎng)上也沒有找到雷绢。但是以二叉樹舉例，這個(gè)路徑長度是對數(shù) $log(n)$ 還是好理解的理卑。

圖片

直徑（Diameter ）其實(shí)這一塊翘紊，單獨(dú)理解有點(diǎn)困難。結(jié)合上面關(guān)于連通分量的介紹：當(dāng) $k=p(n-1)>1$ 時(shí)藐唠，隨機(jī)圖中出現(xiàn)巨分支帆疟，而網(wǎng)絡(luò)的形態(tài)取決于巨分支的形態(tài)。隨機(jī)圖在 $logn>np>c$ , $c$ 為常數(shù)條件下宇立，保證巨分支的出現(xiàn)踪宠，此時(shí)直徑為 $diam(G_{np}=O(logn/log(np)))$ . 相關(guān)證明在參考資料4可以查看（22頁）。

另外妈嘹，網(wǎng)絡(luò)有巨分支存在柳琢，自然廣度搜索算法（BFS）運(yùn)算是對數(shù)復(fù)雜度 $O(logn)$ .

2.1.5 對比現(xiàn)實(shí)模型

通過上面大篇幅的模型介紹，那么真實(shí)情況隨機(jī)圖模型 $G_{np}$ 對于現(xiàn)實(shí)的擬合情況如何呢润脸？

圖片

可以看到：

優(yōu)點(diǎn)
- 巨分支所占比例是接近的
- 平均路徑長度也比較接近柬脸。
  
  這點(diǎn)是最有趣的發(fā)現(xiàn)：原先在實(shí)際網(wǎng)絡(luò)（MSN）分析的時(shí)候，我們對于6度理論以及小世界效應(yīng)非常驚訝毙驯。但實(shí)際上不足為奇倒堕。通過這個(gè)簡單的隨機(jī)圖模型，就能做到爆价。（平平無奇）
不足
- 度分布差異較大垦巴。現(xiàn)實(shí)網(wǎng)絡(luò)呈現(xiàn)冪律分布，而隨機(jī)圖呈現(xiàn)泊松分布（二項(xiàng)分布）
- 聚類系數(shù)相差極大允坚。對于這一屬性魂那，這才是應(yīng)該更關(guān)注。

總結(jié)一下稠项，隨機(jī)圖模型 $G_{np}$ 很粗糙涯雅，對于現(xiàn)實(shí)網(wǎng)絡(luò)的擬合并不好。但是展运，并不是學(xué)習(xí)它沒有意義活逆，它是后續(xù)隨機(jī)圖模型的“迭代”基礎(chǔ)精刷。算是地基工程！

2.2 小世界網(wǎng)絡(luò)模型 The Small-world model

原因：為了解決前面隨機(jī)圖蔗候，對于現(xiàn)實(shí)網(wǎng)絡(luò)的聚類系數(shù)的嚴(yán)重低估問題怒允。
目標(biāo)：生成一個(gè)有較短的平均路徑長度又具有較高的聚類系數(shù)的隨機(jī)圖
方法：隨機(jī)重連，由[Watts-Strogatz ‘98]提出
- 從一個(gè)環(huán)狀的規(guī)則網(wǎng)絡(luò)（regular attic ）開始锈遥，網(wǎng)絡(luò)含有N個(gè)結(jié)點(diǎn)纫事，每個(gè)節(jié)點(diǎn)向它左邊最近的K個(gè)節(jié)點(diǎn)連出K條邊 $K\ge2$ ，并滿足 $N>>K>>ln(N)>>1$ 所灸。
- 隨機(jī)化重連：以概率p隨機(jī)地重新連接網(wǎng)絡(luò)中的每個(gè)邊丽惶，即將邊的一個(gè)端點(diǎn)保持不變，而另一個(gè)端點(diǎn)取為網(wǎng)絡(luò)中隨機(jī)選擇的一個(gè)節(jié)點(diǎn)爬立。規(guī)定钾唬，圖無重邊和自環(huán)（self loop）。
- 改變p 值可以實(shí)現(xiàn)從規(guī)則網(wǎng)絡(luò)(p = 0 )向隨機(jī)網(wǎng)絡(luò)(p = 1)轉(zhuǎn)變侠驯。

圖片

從實(shí)驗(yàn)結(jié)果來看抡秆，通過較小的重連概率p就可以實(shí)現(xiàn)這一目標(biāo)預(yù)期的目標(biāo)。給個(gè)小世界模型的定義：

小世界網(wǎng)絡(luò)模型是一類具有較短的平均路徑長度又具有較高的聚類系數(shù)的網(wǎng)絡(luò)的總稱吟策。

總結(jié)下小世界模型：

優(yōu)點(diǎn)

提供了聚類系數(shù)與路徑長度（小世界效應(yīng)）之間的聯(lián)系
讓隨機(jī)圖模型在聚類系數(shù)方面擬合了現(xiàn)實(shí)網(wǎng)絡(luò)儒士。

不足

對現(xiàn)實(shí)網(wǎng)絡(luò)節(jié)點(diǎn)度的冪律分布這一特點(diǎn)，不能很好的擬合

說明還有進(jìn)一步提升的空間檩坚。這就是下一個(gè)要介紹的隨機(jī)圖模型乍桂。

2.3 隨機(jī)Kronecker圖模型（Kronecker Graph Model）

這時(shí)候輪到隨機(jī)Kronecker圖模型出場了，它可以解決最后的度分布的問題效床。

原因：為了解決隨機(jī)圖度分布與現(xiàn)實(shí)網(wǎng)絡(luò)度分布差異問題睹酌。
方法：采用遞歸方法

通過Kronecker乘積來遞歸來生成網(wǎng)絡(luò)，Kronecker乘積就是生成自相似矩陣的一種方式.

2.3.1 基礎(chǔ)知識

自相似性（Self-similarity）：物體總是和自身的某些局部是相似的剩檀。
克羅內(nèi)克積（Kronecker product）：

圖片

如果初始的 $K_1$ 矩陣是這樣的0-1鄰接矩陣憋沿。那么3階的Kronecker圖是最右邊的樣子。

圖片

這么做雖然可以生成圖沪猴，但有個(gè)問題辐啄！當(dāng)初始 $K_1$ 矩陣和階數(shù)確定了最終的結(jié)果也就確定了。不夠靈活运嗜，也不能解決度分布的問題壶辜。

2.3.2 隨機(jī)Kronecker圖

為了解決上面的問題，引入隨機(jī)性担租，將初始矩陣 $K_1$ 由無權(quán)的鄰接矩陣砸民，改為帶權(quán)的權(quán)重（概率）矩陣。

圖片

這雖然可以實(shí)現(xiàn)隨機(jī)性的目標(biāo)，但是也有個(gè)問題——計(jì)算量太大岭参！運(yùn)算慢反惕！,它需要計(jì)算 $N*N$ 次，如果是一百萬個(gè)節(jié)點(diǎn)演侯，將要計(jì)算 $1*10^{14}$ 次姿染！需要一種更快速的方法。

2.3.3 快速生成隨機(jī)Kronecker圖

思想：優(yōu)先生成概率最高的邊秒际。
方法：遞歸逐層向下悬赏，優(yōu)先計(jì)算概率最大的邊。具體后面結(jié)合代碼介紹娄徊。

圖片

通常生成隨機(jī)圖的前舷嗡，我們有著預(yù)定的節(jié)點(diǎn)數(shù)和邊數(shù)。通過這種方法生成隨機(jī)圖恰好可以滿足我們的需求嵌莉，免去很多無效計(jì)算。

2.3.4 模型與現(xiàn)實(shí)對比

課上捻脖，老師給出了對應(yīng)的實(shí)驗(yàn)結(jié)果锐峭，可以看到隨機(jī)Kronecker圖模型在多個(gè)維度很好的擬合了現(xiàn)實(shí)網(wǎng)絡(luò)。

圖片

3 總結(jié)

至此可婶，完成了隨機(jī)圖模型對于現(xiàn)實(shí)網(wǎng)絡(luò)的擬合沿癞，有了可以更好的分析和預(yù)測現(xiàn)實(shí)網(wǎng)絡(luò)的工具。

這節(jié)課內(nèi)容很多矛渴，不少新的概念和公式椎扬，期間查了不少資料，用了不少時(shí)間消化具温，好在基本理解了蚕涤！

4 參考文章

http://web.stanford.edu/class/cs224w/slides/02-gnp-smallworld.pdf
《網(wǎng)絡(luò)科學(xué)引論》郭世澤陳哲譯
https://blog.csdn.net/Jenny_oxaza/article/details/106142668
http://cseweb.ucsd.edu/~fan/research/papers/diameter.pdf
https://www.geeksforgeeks.org/erdos-renyl-model-generating-random-graphs/
https://snap-stanford.github.io/cs224w-notes/preliminaries/measuring-networks-random-graphs

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市铣猩，隨后出現(xiàn)的幾起案子揖铜，更是在濱河造成了極大的恐慌，老刑警劉巖达皿，帶你破解...
沈念sama閱讀 211,639評論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件天吓，死亡現(xiàn)場離奇詭異，居然都是意外死亡峦椰，警方通過查閱死者的電腦和手機(jī)龄寞，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,277評論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來汤功，“玉大人物邑，你說我怎么就攤上這事。” “怎么了拂封？”我有些...
開封第一講書人閱讀 157,221評論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵茬射，是天一觀的道長。經(jīng)常有香客問我冒签，道長在抛，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 56,474評論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任萧恕，我火速辦了婚禮刚梭，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘票唆。我一直安慰自己朴读，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 65,570評論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布走趋。她就那樣靜靜地躺著衅金，像睡著了一般。火紅的嫁衣襯著肌膚如雪簿煌。梳的紋絲不亂的頭發(fā)上氮唯，一...
開封第一講書人閱讀 49,816評論 1贊 290
城市分裂傳說
那天，我揣著相機(jī)與錄音姨伟，去河邊找鬼惩琉。笑死，一個(gè)胖子當(dāng)著我的面吹牛夺荒，可吹牛的內(nèi)容都是我干的瞒渠。我是一名探鬼主播，決...
沈念sama閱讀 38,957評論 3贊 408
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼技扼，長吁一口氣：“原來是場噩夢啊……” “哼伍玖！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起剿吻，我...
開封第一講書人閱讀 37,718評論 0贊 266
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤私沮，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后和橙，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體仔燕，經(jīng)...
沈念sama閱讀 44,176評論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,511評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年魔招，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了晰搀。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,646評論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡办斑，死狀恐怖外恕，靈堂內(nèi)的尸體忽然破棺而出杆逗，到底是詐尸還是另有隱情，我是刑警寧澤鳞疲，帶...
沈念sama閱讀 34,322評論 4贊 330
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布罪郊，位于F島的核電站，受9級特大地震影響尚洽，放射性物質(zhì)發(fā)生泄漏悔橄。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,934評論 3贊 313
男人毒藥：我在死后第九天來索命
文/蒙蒙一腺毫、第九天我趴在偏房一處隱蔽的房頂上張望癣疟。院中可真熱鬧，春花似錦潮酒、人聲如沸睛挚。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,755評論 0贊 21
一樁弒父案急黎，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽扎狱。三九已至，卻和暖如春勃教，著一層夾襖步出監(jiān)牢的瞬間淤击，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 31,987評論 1贊 266
情欲美人皮
我被黑心中介騙來泰國打工荣回，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人戈咳。一個(gè)月前我還...
沈念sama閱讀 46,358評論 2贊 360
代替公主和親
正文我出身青樓心软，卻偏偏與公主長得像，于是被迫代替她去往敵國和親著蛙。傳聞我的和親對象是個(gè)殘疾皇子删铃，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,514評論 2贊 348