CS224W-圖神經(jīng)網(wǎng)絡(luò) 筆記4.1：Community Structure in Networks - 網(wǎng)絡(luò)中社區(qū)的特性
本文總結(jié)之日CS224W Winter 2021只更新到了第四節(jié)茸习，所以下文會(huì)參考2021年課程的PPT并結(jié)合2019年秋季課程進(jìn)行總結(jié)以求內(nèi)容完整
課程主頁(yè)：CS224W: Machine Learning with Graphs
視頻鏈接：【斯坦讣ǎ】CS224W：圖機(jī)器學(xué)習(xí)( 中英字幕 | 2019秋)
[toc]
1 引言
本節(jié)斯稳，老師前半段部分主要是基于 Mark Granovetter 教授60年代的博士論文展開(kāi)的墓塌。介紹當(dāng)初的猜想，如何在后續(xù)研究過(guò)程中被逐步驗(yàn)證和接受的耙厚，很有意思勾哩。
2 定義
-
社區(qū)（community）：指具有大量?jī)?nèi)部邊連接和很少外部邊連接(到網(wǎng)絡(luò)的其余部分)的節(jié)點(diǎn)集
2.1 為什么要研究圖上的社區(qū)（community）
在回答具體問(wèn)題前，不妨先看個(gè)有趣的社會(huì)學(xué)研究案例：
Mark Granovetter 教授在他的博士論文中有做過(guò)這樣一項(xiàng)研究褒繁，他研究人們?cè)趺传@取新的工作信息亦鳞，是怎樣找到自己的工作的。他發(fā)現(xiàn)棒坏，人們通常更傾向于通過(guò)熟人（acquaintances）獲取這些信息燕差，而不是通過(guò)聯(lián)系更加親密的朋友（close friends）。這是一個(gè)比較“反嘲用幔”的結(jié)論徒探，因?yàn)樵谖覀兊挠∠笾校覀兛偸怯X(jué)得自己在遇到困難或事情的時(shí)候徽诲，會(huì)找更親密的人來(lái)幫忙刹帕。
注：在英文中，acquaintance的意思是a person that you know but who is not a close friend谎替，不會(huì)經(jīng)常聯(lián)系偷溺，關(guān)系上看應(yīng)該要比close friends要疏遠(yuǎn)一點(diǎn)。close friend指每天都聯(lián)系的意思钱贯。
2.1.2 如何解釋上述現(xiàn)象
教授的解釋?zhuān)?/p>
- 結(jié)構(gòu)角度
邊有強(qiáng)弱之分挫掏，它們?cè)诰W(wǎng)絡(luò)結(jié)構(gòu)上和網(wǎng)絡(luò)信息傳遞上起到的作用也是不同的。親密的朋友邊強(qiáng)度較強(qiáng)秩命，而距離較遠(yuǎn)的熟人邊強(qiáng)度較弱尉共。
- 信息角度
信息在網(wǎng)絡(luò)中是流動(dòng)的（flow of information），親密的朋友提供的信息（邊）是冗余的弃锐，即你知道的我也知道袄友。而關(guān)系較遠(yuǎn)的熟人，可以提供的信息更多新價(jià)值霹菊。
這是不是也說(shuō)明了 村里要通網(wǎng)的重要性剧蚣！
這里回答上面的問(wèn)題：
為什么要研究網(wǎng)絡(luò)中的社區(qū)？
- 在現(xiàn)實(shí)網(wǎng)絡(luò)存在社區(qū)結(jié)構(gòu)，反映了結(jié)構(gòu)的緊密程度鸠按。
- 能解釋信息的傳播礼搁。
總之很有用！它能用來(lái)分析解決很多問(wèn)題目尖。學(xué)吧馒吴！
3 一些重要概念
在進(jìn)行定量分析前，需要先熟悉幾個(gè)概念瑟曲，都是為了衡量社區(qū)緊密程度做的鋪墊：
三元閉包(triadic closure)：彼此相連的3個(gè)節(jié)點(diǎn)和對(duì)應(yīng)邊構(gòu)成的子圖饮戳。- 更多的三元閉包 = 高聚類(lèi)系數(shù).
- 有共同鄰居的兩點(diǎn)，更大概率相連测蹲。
邊的重疊度（Edge Overlap）
說(shuō)人話(huà)就是莹捡，兩點(diǎn)的共同鄰居在它們所有鄰居中的占比鬼吵。反映關(guān)系的強(qiáng)度（stength）扣甲。這點(diǎn)通過(guò)下面的電話(huà)網(wǎng)絡(luò)的實(shí)證研究中得到驗(yàn)證。
-
捷徑（local bridge）當(dāng)相鄰兩點(diǎn)的共同鄰居為0時(shí)齿椅，這條邊叫做捷徑琉挖。
4 真實(shí)的網(wǎng)絡(luò)案例
老師舉了個(gè)電話(huà)網(wǎng)絡(luò)（mobile call graph）的例子，來(lái)定量分析社區(qū)的一些特性涣脚。
4.1 邊的重疊度（overlap）與邊的強(qiáng)度（strength）關(guān)系
- 正相關(guān)關(guān)系
即邊的重疊度(通訊錄中有共同好友的)越高示辈，邊的強(qiáng)度（彼此打電話(huà)的概率）越高，如下圖左邊藍(lán)色線(xiàn)遣蚀。
從實(shí)際網(wǎng)絡(luò)上可以看到右圖矾麻，如果用電話(huà)次數(shù)多少代表邊的粗細(xì)“盘荩可以看到真實(shí)網(wǎng)絡(luò)中险耀，連接緊密的兩點(diǎn)邊越粗（通話(huà)越多）。明顯區(qū)別于隨機(jī)網(wǎng)絡(luò)隨機(jī)分配權(quán)重情況玖喘。
4.2 邊的強(qiáng)度（strength）與網(wǎng)絡(luò)結(jié)構(gòu)之間關(guān)系
- 低強(qiáng)度的邊對(duì)最大連通分量的大小影響更大
因?yàn)檫叺膐verlap 和 stength 是正相關(guān)關(guān)系甩牺。所以，從圖上可以看出來(lái)累奈，
- 先移除低overlap的邊贬派，對(duì)于網(wǎng)絡(luò)的最大連通分量的影響
大于先移除高overlap邊（左） - 先移除低stength的邊，對(duì)于網(wǎng)絡(luò)的最大連通分量的影響
大于先移除高strength邊（右）
5 總結(jié)
以上內(nèi)容澎媒，解決了網(wǎng)絡(luò)中社區(qū)是什么和為什么兩個(gè)問(wèn)題搞乏。下面就是怎么辦的問(wèn)題，怎么從網(wǎng)絡(luò)中挖掘社區(qū)?
本節(jié)的大部分內(nèi)容都是參考下面鏈接1戒努，作者總結(jié)的非常到位请敦，學(xué)習(xí)前讀兩遍很有收獲，在此表示感謝!
