<1>社交網(wǎng)絡(luò)的結(jié)構(gòu)與關(guān)系強(qiáng)度及其在OSN 上的體現(xiàn)
主要內(nèi)容：三元閉包關(guān)系的強(qiáng)度及其與網(wǎng)絡(luò)結(jié)構(gòu)的關(guān)系
一映砖、圖論
1真慢、圖：包含一組元素以及他們之間連接關(guān)系的集合
（1）節(jié)點(diǎn)（vertex，node榕吼，point）
邊（鏈接饿序，連接，關(guān)系羹蚣，聯(lián)系原探；edge，link顽素，tie）
鄰居
（2）常用的圖：合作圖咽弦、即時(shí)通信圖、信息鏈接圖
（3）有向圖（節(jié)點(diǎn)胁出、有向邊）型型、無向圖
2、圖的同構(gòu)：畫法不同全蝶，但本質(zhì)上（結(jié)構(gòu)上）相同
節(jié)點(diǎn)的連接關(guān)系比節(jié)點(diǎn)的位置更重要闹蒜。
【題目】下面哪些圖是同構(gòu)的？
【題目】
3埂蕊、路徑往弓、最短路徑、距離蓄氧、圈
①路徑：一個(gè)節(jié)點(diǎn)序列的集合函似，且序列中任意兩個(gè)相鄰節(jié)點(diǎn)都有一條邊相連。
兩點(diǎn)之間可有多條路徑喉童。
路徑的長(zhǎng)度：一條路徑所包含的邊數(shù)
②最短路徑-->又叫兩點(diǎn)之間的距離
③距離-->最短路徑的長(zhǎng)度
【題目】下圖中節(jié)點(diǎn)A和節(jié)點(diǎn)B之間的距離是多少撇寞？
④圈
環(huán)狀結(jié)構(gòu)堂氯；至少三條邊蔑担，起點(diǎn)與終點(diǎn)相同，所有節(jié)點(diǎn)均不重復(fù)咽白。
部署網(wǎng)絡(luò)的一個(gè)原則：要求每條邊都至少在一個(gè)圈里（為了保證連通性啤握，帶來冗余）。eg：ARPANET的每條邊都在圈里
4晶框、連通性
（1）連通圖：一個(gè)圖中任意兩點(diǎn)間有路徑相通排抬；每條邊都在一個(gè)圈里。
（2）非連通圖
（3）連通分量
若圖G的節(jié)點(diǎn)子集滿足：①連通性：子集中任意兩個(gè)節(jié)點(diǎn)間均有路徑相連蹲蒲；②獨(dú)立性：該子集不是其他滿足條件1的子集的一部分；則稱G的節(jié)點(diǎn)子集是連通分量
【題目】下面指出的哪些節(jié)點(diǎn)集合不對(duì)應(yīng)這個(gè)6節(jié)點(diǎn)圖的一個(gè)連通分量咖祭？
（4）超大連通分量（giant component）
非形式化地對(duì)于包含其中大部分節(jié)點(diǎn)的連通分量的稱謂蔫骂。
Q：全世界友誼圖是否為連通圖么翰？A：即使本身不具備聯(lián)通性，其中的連通分量也是巨大的辽旋。
5浩嫌、距離與廣度優(yōu)先搜索法
深度搜索和廣度搜索的算法復(fù)雜度相同，但是深度搜索用的多补胚，因?yàn)閺V度搜索對(duì)存儲(chǔ)的要求高码耐，一層中節(jié)點(diǎn)太多。
廣度優(yōu)先：從一個(gè)節(jié)點(diǎn)開始溶其，沿著相連的邊骚腥，將圖的節(jié)點(diǎn)一一列舉。
二瓶逃、弱聯(lián)系和強(qiáng)聯(lián)系
1廓块、三元閉包（triadic closure）
在一個(gè)社交圈內(nèi)，如果兩個(gè)互不認(rèn)識(shí)的人有了一個(gè)共同的朋友契沫，則他們將來成為朋友的可能性會(huì)提高带猴。
三元閉包是社交網(wǎng)絡(luò)演化的基本結(jié)構(gòu)性原因。
三語閉包產(chǎn)生的原因：機(jī)會(huì)懈万、信任拴清、動(dòng)機(jī)
三元閉包原理擴(kuò)展：
①“量”的方面
兩個(gè)人的共同朋友越多会通，他們成為朋友的可能性越高
②“質(zhì)”的方面
兩個(gè)人與共同朋友的關(guān)系越密切贷掖，則他們成為朋友的可能性越高。
2渴语、聚集系數(shù)
節(jié)點(diǎn)A的聚集系數(shù)：A的任意兩個(gè)朋友彼此也是朋友的概率
總對(duì)數(shù)=節(jié)點(diǎn)的度*（節(jié)點(diǎn)度-1）/2
聚集系數(shù)就是三元閉包在一個(gè)節(jié)點(diǎn)上的屬性測(cè)度苹威，表示“凝聚力”的大小
聚集系數(shù)隨時(shí)間的變化體現(xiàn)了三元閉包對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響趨勢(shì)。節(jié)點(diǎn)附近的三元閉包過程越強(qiáng)驾凶，其聚集系數(shù)就越大牙甫。
【題目】
3、三元閉包原理的大數(shù)據(jù)驗(yàn)證
（1）三元閉包原理的表達(dá)（定量）
最初表述：如果兩個(gè)互不認(rèn)識(shí)的人有了一個(gè)共用朋友调违，則他們?cè)谖磥沓蔀榕笥训目赡苄栽黾印?/p>
轉(zhuǎn)變成：兩個(gè)互不認(rèn)識(shí)的人的共同朋友數(shù)越多窟哺，則他倆在未來成為朋友的可能性越大。
（2）驗(yàn)證數(shù)據(jù)：電子郵件網(wǎng)絡(luò)≈社會(huì)網(wǎng)絡(luò)
（3）考察網(wǎng)絡(luò)的演化：考察兩個(gè)相繼的網(wǎng)絡(luò)快照
考察三元閉包現(xiàn)象的測(cè)度：當(dāng)前共同朋友數(shù)與后來成為朋友的概率關(guān)系技肩。
得到一個(gè)圖-->找不連接的邊-->計(jì)算不連接節(jié)點(diǎn)他們的共同朋友-->過一定的時(shí)間再做且轨。
【題目】
4虚婿、弱聯(lián)系的力量
（1）橋：一張圖中旋奢，已知A和B相連，若去掉連接A和B的邊然痊，會(huì)導(dǎo)致A和B屬于不同的連通分量至朗，則該邊稱為橋。（斷開就不通）
（2）捷徑（local bridge）：若邊A-B的端點(diǎn)A和B沒有共同朋友剧浸，則稱邊A-B為捷徑锹引。（斷開距離>2）
（3）跨度：沒有捷徑時(shí)的距離。
如果A和B的跨度>2唆香，則A和B之間的邊是捷徑嫌变。
跨度很大的捷徑的作用類似于橋。
通過捷徑聯(lián)系的人更可能為你提供工作信息躬它。（找工作問題的第一個(gè)解釋）
5腾啥、強(qiáng)三元閉包
捷徑很大程度上可能是弱聯(lián)系
考慮社交網(wǎng)絡(luò)中關(guān)系的強(qiáng)度-->邊的屬性
邊屬性的一種測(cè)度：強(qiáng)-弱（強(qiáng)度可以使連續(xù)變量）
（1）強(qiáng)三元閉包原理（架設(shè)）：如果A-B和A-C之間的關(guān)系為強(qiáng)聯(lián)系，則B-C之間形成邊的可能性應(yīng)該很高
若A有兩個(gè)強(qiáng)聯(lián)系鄰居B和C，但B-C之間沒有任何關(guān)系（s或w碑宴，即strengh或weak），則稱節(jié)點(diǎn)A違背了強(qiáng)三元閉包原理桑谍。反之延柠，則稱A符合強(qiáng)三元閉包原理。
（2）在一定條件下：捷徑-->弱聯(lián)系
若節(jié)點(diǎn)A符合強(qiáng)三元閉包锣披，且至少有兩個(gè)強(qiáng)聯(lián)系鄰居贞间，則與A相連的任何捷徑必定是弱聯(lián)系。
（假設(shè)A-B是s雹仿，而A有個(gè)強(qiáng)聯(lián)系鄰居C增热，即A-C為s，那么根據(jù)強(qiáng)三元閉包胧辽，一段時(shí)間后B-C會(huì)有聯(lián)系峻仇，A-B的跨度為2，與捷徑的定義矛盾）
連接關(guān)系：強(qiáng)聯(lián)系邑商、弱聯(lián)系
結(jié)構(gòu)關(guān)系：捷徑摄咆、非捷徑
三元閉包將連接關(guān)系和結(jié)構(gòu)關(guān)系連接起來了。
（兩人的關(guān)系強(qiáng)度如何人断，與兩人是否有共同好友相關(guān)吭从，但不等價(jià)）捷徑意味著沒有共同朋友，強(qiáng)度為“弱”恶迈。
（3）統(tǒng)計(jì)推論：共同朋友越多涩金，關(guān)系強(qiáng)度越高
6、鄰里重疊度
（1）社交網(wǎng)絡(luò)中暇仲，橋步做、捷徑一般不存在-->鄰里重疊度（Neighborhood Overlap）
①捷徑是鄰里重疊度為0的邊
②可以把鄰里重疊地很低的邊粗略的視為捷徑
③一種很好的從二到多的數(shù)學(xué)抽象的例子
目標(biāo)3：弱聯(lián)系起到將包含大量強(qiáng)聯(lián)系的緊密社區(qū)連接起來的作用。（方法：從強(qiáng)度最強(qiáng)的關(guān)系邊開始桅狠，按強(qiáng)度的降序逐漸刪邊讼载；從強(qiáng)度最弱的關(guān)系邊，按強(qiáng)度的升序中跌，逐漸刪除邊咨堤。發(fā)現(xiàn)：從弱的開始刪，網(wǎng)絡(luò)崩的快）
（2）社交網(wǎng)絡(luò)實(shí)驗(yàn)
Facebook的三種連接：相互連接漩符、單向連接一喘、保持關(guān)系。
社交網(wǎng)絡(luò)中好友數(shù)目：盡管一個(gè)用戶可聲明關(guān)注大量（幾百）其，但實(shí)際關(guān)注的大約在50以下凸克，而真正有聯(lián)系的則更少议蟆，在20以下。
社會(huì)網(wǎng)絡(luò)是用弱系連起來的若干緊密群體萎战。
7咐容、結(jié)構(gòu)洞
（1）嵌入性：一條邊的嵌入性為其兩個(gè)端點(diǎn)共同的鄰居數(shù)
①嵌入性就是鄰里疊度的分子
②捷徑就是嵌入性0的邊
③嵌入性越大的邊相互間的信任就越強(qiáng)；嵌入性越強(qiáng)的邊社會(huì)資本也越多
節(jié)點(diǎn)A：
①聚集系數(shù)較高（7/10）
②A關(guān)聯(lián)的邊多數(shù)具有較大的嵌入性
③處于一個(gè)相對(duì)比較誠(chéng)實(shí)可信的群體
節(jié)點(diǎn)B：
①聚集數(shù)較（2/10）
②他關(guān)聯(lián)的邊多數(shù)具有較小的嵌入性
③結(jié)構(gòu)洞：兩個(gè)沒有緊密聯(lián)系的節(jié)點(diǎn)集合之間的“空地”
節(jié)點(diǎn)B具有的優(yōu)勢(shì)：
①信息優(yōu)勢(shì)： 可以較早地獲得網(wǎng)絡(luò)中多個(gè)互不交叉部分的信息
②創(chuàng)新優(yōu)勢(shì)： 處在捷徑的一端對(duì)創(chuàng)造性有放大功能
③權(quán)力優(yōu)勢(shì)：所處位置具有某種社交“把關(guān)”的機(jī)會(huì)
啟示：有效破壞網(wǎng)絡(luò)的連通性（以最快最小的代價(jià)）：破壞處于結(jié)構(gòu)洞位置的節(jié)點(diǎn)或捷徑（關(guān)鍵連接）
（2）數(shù)字大炮（一種DDoS）（攻的是路由器的BGP協(xié)議）
邊界網(wǎng)關(guān)協(xié)議（BGP）
主要用于兩個(gè)自治系統(tǒng)（AS）間交換路由信息
使用矢量路徑機(jī)制蚂维，路由信息格式：<目的站戳粒， AS有序列表（由AS構(gòu)成的路徑） >
UPDATE報(bào)文：（發(fā)生時(shí)機(jī)：發(fā)生變化時(shí)，發(fā)送UPDATE報(bào)文）
“數(shù)字大炮”攻擊示意：
攻擊的基本原理：
數(shù)字大炮的攻擊步驟：
① 構(gòu)建僵尸網(wǎng)絡(luò)（可預(yù)先構(gòu)建）
② 啟動(dòng)僵尸網(wǎng)絡(luò)中的計(jì)算機(jī)之間流量發(fā)送虫啥，建立它們之間的“路徑地圖” （拓?fù)浒l(fā)現(xiàn)）蔚约，找到眾多路共用的連接（關(guān)鍵鏈路）（可預(yù)先構(gòu)建）
③ 由僵尸網(wǎng)絡(luò)對(duì)關(guān)鍵鏈路兩端路由器BGP協(xié)議發(fā)動(dòng)ZMW攻擊，使得關(guān)鍵鏈路處于斷開狀態(tài)
④ 附近路由器會(huì)對(duì)此作出回應(yīng)涂籽，發(fā)送BGP更新消息
⑤ 很短的時(shí)間之后苹祟，這兩個(gè)被切斷的路由器可能會(huì)重新連接，并發(fā)送BGP更新信息
⑥ 不斷重復(fù)（3） ~（5）评雌，最后互聯(lián)網(wǎng)上每一臺(tái)路由器都會(huì)接收到超出自身處理能力的更新消息苔咪，從而導(dǎo)致互聯(lián)網(wǎng)癱瘓
數(shù)字大炮的攻擊效果：
選好節(jié)點(diǎn)，靠網(wǎng)絡(luò)自身的擴(kuò)散功能柳骄。實(shí)驗(yàn)不錯(cuò)团赏，但是實(shí)際中很難。這幾年很少用耐薯，DDoS多用放大協(xié)議舔清，即受到的包不大，但是會(huì)回過來一個(gè)很大的包曲初。
（3）如何找到重要的邊
①橋体谒，捷徑，鄰里疊度很低的邊，……
②許多節(jié)點(diǎn)之間的最短路徑都要經(jīng)過它
8、介數(shù)
節(jié)點(diǎn)介數(shù)定義為網(wǎng)絡(luò)中所有最短路徑中經(jīng)過該節(jié)點(diǎn)的路徑的數(shù)目占最短路徑總數(shù)的比例畦娄。
邊介數(shù)定義為網(wǎng)絡(luò)中所有最短路徑中經(jīng)過該邊的路徑的數(shù)目占最短路徑總數(shù)的比例旭蠕。
（本課中官撼，后面說的介數(shù)，都是指最短路徑數(shù)）
（1）介數(shù)：一條邊承載的一種“流量”
①兩個(gè)節(jié)點(diǎn)A和B，設(shè)想1個(gè)單位的流量從A到B，均分到它們之間所有的最短路徑上
②K條路徑彩届，則每條路徑上分得1/k，
③若一條邊被m條路徑共用誓酒，則在它面流過m/k
④所有節(jié)點(diǎn)對(duì)都考慮后樟蠕，一條邊上的累記流量就是它的介數(shù)（betweenness）
（2）破壞連通性
①Girvan-Neman方法： 逐步刪除高介數(shù)邊
（3）介數(shù)計(jì)算的一種方法-->廣度搜索
路徑的數(shù)目從上往下算
下圖：因?yàn)锳給每個(gè)人都發(fā)了一個(gè)單位流量（可以想數(shù)據(jù)包），所以每個(gè)節(jié)點(diǎn)都會(huì)留下1個(gè)單位流量
介數(shù)：很適合描述實(shí)際網(wǎng)絡(luò)中寨辩，承載流量的邊的信息
三吓懈、回顧總結(jié)
