https://leovan.me/cn/2020/11/graph-theory/
https://leovan.me/cn/2020/12/network-algorithms/
https://leovan.me/cn/2020/12/network-algorithms/
網(wǎng)絡(luò)表示，測度和度量 (Network Representation, Measures & Metrics)
復(fù)雜網(wǎng)絡(luò)系列
范葉亮 / 2020-11-21
分類:?機器學(xué)習(xí),?復(fù)雜網(wǎng)絡(luò)?/?標(biāo)簽:?復(fù)雜網(wǎng)絡(luò),?網(wǎng)絡(luò),?網(wǎng)絡(luò)表示,?圖,?Graph,?頂點,?Vertex,?邊,?Edge,?重邊,?Multiedge,?簡單網(wǎng)絡(luò),?Simple Network,?簡單圖,?Simple Graph,?重圖,?Multigraph,?無向網(wǎng)絡(luò),?Undirected Network,?邊列表,?Edge List,?鄰接矩陣,?Adjacency Matrix,?加權(quán)網(wǎng)絡(luò),?Weighted Network,?賦值網(wǎng)絡(luò),?Valued Network,?有向網(wǎng)絡(luò),?Directed Network,?有向圖,?Directed Graph,?有向邊,?Directed Edge,?超邊,?Hyperedge,?超圖,?Hypergraph,?隸屬網(wǎng)絡(luò),?二分網(wǎng)絡(luò),?二分圖,?Bipartite Network,?關(guān)聯(lián)矩陣,?Incidence Matrix,?單模投影,?One-mode Projection,?樹,?Tree,?森林,?Forest,?度,?Degree,?連通度,?Connectance,?密度,?Density,?入度,?in-degree,?出度,?out-degree,?路徑,?測地路徑,?Geodesic Path,?最短路徑,?Shortest Path,?直徑,?Diameter,?歐拉路徑,?Eulerian Path,?哈密頓路徑,?Hamiltonian Path,?連通,?Connected,?非連通,?Disconnected,?分支,?Component,?連通度,?Connectivity,?子圖,?Subgraph,?生成子圖,?Spanning Subgraph,?導(dǎo)出子圖,?Induced Subgraph,?Motif,?Graphlets,?測度,?度量,?中心性,?Centrality,?度中心性,?Degree Centrality,?Katz 中心性,?Katz Centrality,?PageRank,?接近度中心性,?Closeness Centrality,?調(diào)和中心性,?Harmonic Centrality,?介數(shù)中心性,?Betweenness Centrality,?傳遞性,?Transitivity,?團,?Clique,?完全傳遞性,?部分傳遞性,?閉合三元組,?Closed Triad,?聚類系數(shù),?Clustering Coefficient,?局部聚類系數(shù),?Local Clustering Coefficient,?相互性,?Reciprocity,?相似性,?結(jié)構(gòu)等價,?Structural Equivalence,?規(guī)則等價,?Regular Equivalence,?余弦相似性,?Cosine Similarity,?皮爾遜相關(guān)系數(shù),?Pearson Correlation Coefficient,?同質(zhì)性,?Homophily,?同配混合,?Assortative Mixing,?異配混合,?Disassortative Mixing,?模塊度,?Modularity,?同配系數(shù),?Assortativity Coefficience,?邊緣,?Periphery,?核心結(jié)構(gòu),?Core Structure,?邊緣結(jié)構(gòu),?Periphery Structure?/?字數(shù):?7603
本文內(nèi)容主要參考自：《網(wǎng)絡(luò)科學(xué)引論》1
網(wǎng)絡(luò)（network）也稱為圖（graph），是一個由多個頂點（vertex）及連接頂點的邊（edge）組成的集合浴井。在網(wǎng)絡(luò)中，我們通常用?n?表示頂點的數(shù)目亮曹，用?m?表示邊的數(shù)目。在大多數(shù)網(wǎng)絡(luò)中兩個頂點之間都只有一條邊鹦筹，極少數(shù)情況下秋秤，兩個頂點之間有多條邊介衔，稱之為重邊（multiedge）恨胚。在極特殊情況下，還會存在連接到頂點自身的邊炎咖，稱之為自邊（self-edge）赃泡。既沒有自邊也沒有重邊的圖稱之為簡單網(wǎng)絡(luò)（simple network）或簡單圖（simple graph），存在重邊的網(wǎng)絡(luò)稱之為重圖（multigraph）乘盼。相關(guān)概念示例如下：
網(wǎng)絡(luò)表示
無向網(wǎng)絡(luò)
對于一個包含?n?個頂點的無向圖升熊，可以用整數(shù)?1?到?n?對各個頂點進行標(biāo)注。如果用?(i,j)?表示頂點?i?和頂點?j?之間的邊绸栅，那么通過給定?n?的值及所有邊的列表就能表示一個完整的網(wǎng)絡(luò)级野，這種表示方法稱之為邊列表（edge list）。
相比于邊列表粹胯，鄰接矩陣（adjacency matrix）可以更好地表示網(wǎng)絡(luò)蓖柔。一個簡單圖的鄰接矩陣?A?中元素?Aij?的含義如下：
如果頂點和頂點之間存在一條邊其他(1)Aij={1如果頂點?i?和頂點?j?之間存在一條邊0其他
對于一個沒有自邊的網(wǎng)絡(luò)，其鄰接矩陣有兩個特點：
鄰接矩陣對角線上的元素取值均為零矛双。
鄰接矩陣是對稱的。
加權(quán)網(wǎng)絡(luò)
對于加權(quán)網(wǎng)絡(luò)（weighted network）和賦值網(wǎng)絡(luò)（valued network）可以將鄰接矩陣中對應(yīng)元素的值設(shè)定為相應(yīng)的權(quán)重的方式來進行表示蟆豫。
有向網(wǎng)絡(luò)
有向網(wǎng)絡(luò)（directed network）或有向圖（directed graph）有時簡稱為 digraph议忽，在這類網(wǎng)絡(luò)中，每條邊都有方向十减，從一個頂點指向另一個頂點栈幸，稱之為有向邊（directed edge）。
注意：?有向網(wǎng)絡(luò)的鄰接矩陣中元素?Aij=1?時表示存在從頂點?j?到頂點?i?的邊帮辟。雖然表示方法有些出人意料速址，但在數(shù)據(jù)計算上會帶來極大的方便。
超圖
在某些類型的網(wǎng)絡(luò)中由驹，一些邊會同時連接多個頂點芍锚。例如：創(chuàng)建一個社會網(wǎng)絡(luò)，用來表示一個大規(guī)模社區(qū)中的各個家庭。每個家庭都可能會有兩名或多名成員并炮，因此表示這些家庭之間關(guān)系的做好方法就是使用一種廣義邊來同時連接多個頂點默刚。這樣的邊稱之為超邊（hyperedge），含有超邊的網(wǎng)絡(luò)稱之為超圖（hypergraph）逃魄。下圖 (a) 表示一個小型超圖荤西，其中超邊用環(huán)的形式表示。
當(dāng)一個網(wǎng)絡(luò)中的頂點因為某種群組之間的關(guān)系被連接在一起時伍俘，可以使用超圖來表示這個網(wǎng)絡(luò)邪锌，在社會學(xué)中，這樣的網(wǎng)絡(luò)稱之為隸屬網(wǎng)絡(luò)癌瘾。對于超圖觅丰，可于采用二分圖的方式進行表示，通過引入 4 個新的頂點代表 4 個群組柳弄，在頂點及其所屬群組之間通過邊連接舶胀，如上圖 (b) 所示。
二分網(wǎng)絡(luò)
群組內(nèi)成員之間的關(guān)系可以用超圖中的超邊表示碧注，也可以等價地用更方便的二分圖（bipartite network）表示嚣伐。這種網(wǎng)絡(luò)中有兩類頂點，一類頂點代表原始頂點萍丐，另一類頂點則表示原始頂點所屬的群組轩端。
二分網(wǎng)絡(luò)中，與鄰接矩陣等價的是一個矩形矩陣逝变，稱之為關(guān)聯(lián)矩陣（incidence matrix）基茵。如果?n?代表人數(shù)或網(wǎng)絡(luò)中的成員數(shù)目，g?是群組的數(shù)目壳影，那么關(guān)聯(lián)矩陣?B?是一個?g×n?的矩陣拱层，其元素?Bij?的取值含義如下：
如果頂點屬于群組其他(2)Bij={1如果頂點?j?屬于群組?i0其他
研究統(tǒng)一類型頂點之間的直接聯(lián)系可以通過對二分網(wǎng)絡(luò)進行單模投影（one-mode projection），推導(dǎo)出同類頂點之間的直接聯(lián)系宴咧，如下圖所示根灯。
樹
樹（tree）是連通的、無向的且不包含閉合循環(huán)的網(wǎng)絡(luò)掺栅，如下圖所示烙肺。
連通是指任意兩個頂點之間都存在一條相互可達的路徑。一個網(wǎng)絡(luò)可能有兩個或多個部分組成氧卧，每個部分相互之間不連通桃笙，如果任意單獨的部分都為樹，則稱這個網(wǎng)絡(luò)為森林（forest）沙绝。
由于樹沒有閉合循環(huán)搏明，因此任意兩個頂點之間有且只有一條相連的路徑鼠锈。如果一個樹有?n?個頂點，那么它有且僅有?n?1?條邊熏瞄。
度
圖中頂點的度（degree）是指與其直接相連的邊數(shù)目脚祟。將頂點?i?的度表示為?ki，對于有?n?個頂點構(gòu)成的無向圖强饮，可利用鄰接矩陣將度表示為：
(3)ki=∑j=1nAij
在無向圖中由桌，每個邊都有兩端，如果一共有?m?條邊邮丰，那么就有?2m?個邊的端點行您。同時，邊的端點數(shù)與所有頂點度的總和相等：
(4)2m=∑j=1nki
即
(5)m=12∑i=1nki=12∑ijAij
無向圖中頂點度的均值?c?為：
(6)c=1n∑i=1nki
綜上可得：
(7)c=2mn
在一個簡單圖中剪廉，可能的邊數(shù)的最大值是?(n2)=12n(n?1)?個娃循。圖的連通度（connectance）或密度（density）ρ?是所有圖中實際出現(xiàn)的邊的數(shù)目與邊數(shù)最大值之間的比值：
(8)ρ=m(n2)=2mn(n?1)=cn?1
在有向圖中，每個頂點有兩個度：入度（in-degree）是連接到該頂點的入邊的數(shù)目斗蒋，出度（out-degree）是出邊數(shù)目捌斧。當(dāng)從頂點?j?到?i?有一條邊時，鄰接矩陣中對應(yīng)的元素?Aij=1泉沾，則入度和出度記為：
(9)kiin=∑j=1nAij,kjout=∑i=1nAij
在有向圖中捞蚂，邊的數(shù)目?m?等于入邊的端點數(shù)總和，也等于出邊的端點數(shù)總和跷究，有：
(10)m=∑i=1nkiin=∑j=1nkjout=∑ijAij
每個有向圖的入度的均值?cin?和出度的均值?cout?是相等的：
(11)cin?=1n∑i=1nkiin?=1n∑j=1nkjout?=cout?
簡化后有：
(12)c=mn
路徑
網(wǎng)絡(luò)中的路徑是指由一組頂點構(gòu)成的序列姓迅，序列中每兩個連續(xù)頂點都通過網(wǎng)絡(luò)中的邊連接在一起，路徑長度等于該路徑經(jīng)過的邊的數(shù)目（而非頂點的數(shù)目）俊马。從頂點?j?到頂點?i?存在長度為?r?的路徑總數(shù)為：
(13)Nij(r)=[Ar]ij
其中丁存，[?]ij?表示矩陣中的第?i?行、第?j?列的元素柴我。
測地路徑（geodesic path）解寝，簡稱為最短路徑（shortest path），即兩個頂點間不存在更短路徑的路徑艘儒。圖的直徑（diameter）是指圖中任意一對相互連接的頂點之間的最長測地路徑長度聋伦。歐拉路徑（Eulerian path）是經(jīng)過網(wǎng)絡(luò)中的所有邊且每條邊只經(jīng)過一次的路徑。哈密頓路徑（Hamiltonian path）是訪問網(wǎng)絡(luò)的所有頂點且每個頂點只訪問一次的路徑彤悔。
分支
如果一個網(wǎng)絡(luò)中兩個頂點之間不存在路徑嘉抓，則稱這個網(wǎng)絡(luò)是非連通（disconnected）的索守，如果網(wǎng)絡(luò)中任意兩個頂點之間都能找到一條路徑晕窑，則稱這個網(wǎng)絡(luò)是連通（connected）的。
網(wǎng)絡(luò)中的子群稱為分支（component）卵佛。分支是網(wǎng)絡(luò)中頂點的子集杨赤，該子集中任何兩個頂點之間至少存在一條路徑敞斋，在保證該性質(zhì)的前提下，網(wǎng)絡(luò)中其他頂點都不能被添加到這個子集中疾牲。在保證一個給定性質(zhì)的前提下植捎，不能再向它添加其他頂點，就稱其為最大子集（maximal subset）阳柔。
連通度
如果兩條路經(jīng)除了起點和終點外焰枢，不共享其他任何頂點，那么這兩條路徑是頂點獨立（vertex-independent）的舌剂。如果兩條路徑是頂點獨立的济锄，那么也是邊獨立的，反之則不成立霍转。
兩個頂點之間的獨立路徑數(shù)稱為頂點之間的連通度（connectivity）荐绝，如果明確考慮邊還是頂點，則需利用邊連通度（edge connectivity）及頂點連通度（vertex connectivity）的概念避消。
子圖
令原圖表示為?G=(V,E)低滩，其中，V?是圖中所有頂點的集合岩喷，E?是圖中所有邊的集合恕沫，有：
子圖（subgraph）：G′?中所有頂點和邊均包含于原圖?G?中，即?E′∈E,V′∈V均驶。
生成子圖（spanning subgraph）：G′?中頂點同原圖?G?相同昏兆，且?E′∈E。
導(dǎo)出子圖（induced subgraph）：G′?中妇穴，V′∈V爬虱，同時對于?V′?中任意一個頂點，只要在原圖?G?中有對應(yīng)的邊腾它，則也應(yīng)包含在?E′?中跑筝。
Motif
Motif?2?被定義為反復(fù)出現(xiàn)的重要連接模式。這些模式在真實的網(wǎng)絡(luò)中要比隨機網(wǎng)絡(luò)中出現(xiàn)的更加頻繁瞒滴，如下圖所示：
Motif 的顯著性定義為：
(14)Zi=Nireal?Nˉirandstd(Nirand)
其中曲梗，Nireal?為模式在真實圖中出現(xiàn)的次數(shù)，Nirand?為模式在隨機圖中出現(xiàn)的次數(shù)妓忍。
Graphlets
Graphlets 是對 Motif 的擴展虏两，Motif 是從全局的角度發(fā)現(xiàn)模式，而 Graphlets 是從局部角度出發(fā)世剖。Graphlets 是連接的非同構(gòu)子圖定罢，這里要求子圖為導(dǎo)出子圖。下圖展示了節(jié)點數(shù)為 2 至 5 的所有 Graphlets：
更多關(guān)于 Motif 和 Graphlets 的細節(jié)請參見?3?4?旁瘫。
測度和度量
中心性
度中心性
中心性（centrality）是研究“網(wǎng)絡(luò)中哪些頂點是最重要或最核心的祖凫？”這個問題的一個概念琼蚯。網(wǎng)絡(luò)中心性的最簡單的測度是頂點的度，即與頂點相連的邊的數(shù)量惠况。有時為了強調(diào)度作為中心性測度的用途遭庶，在社會學(xué)中也稱之為度中心性（degree centrality）。
特征向量中心性
度中心性可自然地擴展為特征向量中心性（eigenvector centrality）稠屠÷退可以將度中心性理解為給某頂點所有鄰居頂點賦予一個“中心性值”，但并非所有連接頂點的值都是相同的权埠。很多情況下赐俗，一個頂點會由于連接到一些本身很重要的點，而使自身的重要性得到提升弊知，這就是特征向量中心性的本質(zhì)阻逮。
對于每個頂點?i，假設(shè)其中心性為?xi秩彤。對于所有?i叔扼，可以設(shè)其初始值?xi=1，利用該值可以計算出另一個更能體現(xiàn)中心性的值?xi′漫雷，將?xi′?定義為?i?所有鄰居頂點的中心性之和：
(15)xi′=∑jAijxj
重復(fù)該過程可以得到更好的估計值瓜富，重復(fù)?t?步后，中心性?x(t)?的計算公式如下：
(16)x(t)=Atx(0)
當(dāng)?t→∞?時降盹，中心性向量的極限與鄰接矩陣中的主特征向量成正比与柑。因此，可以等價地認為中心性?x?滿足：
(17)Ax=κ1x
其中蓄坏，κ1?為矩陣?A?的特征值中的最大值价捧。
特征向量中心性對于有向圖和無向圖都適用。在有向圖中涡戳，鄰接矩陣是非對稱的结蟋，因此網(wǎng)絡(luò)有兩類特征向量，通常情況下我們選擇右特征向量來定義中心性渔彰。因為在有向網(wǎng)絡(luò)中嵌屎，中心性主要是由指向頂點的頂點，而不是由頂點指向的頂點賦予的恍涂。
Katz 中心性
Katz 中心性解決了特征向量中心性中節(jié)點中心性可能為零的問題宝惰。通過為網(wǎng)絡(luò)中每個頂點賦予少量的“免費”中心性，可以定義：
(18)xi=α∑jAijxj+β
其中再沧，α?和?β?是正常數(shù)尼夺。使用矩陣表示可以寫成：
(19)x=αAx+β1
其中，1?代表向量?(1,1,1,?)。重新整理有?x=β(I?αA)?11汞斧，由于只關(guān)心相對值，通呈惭啵可以設(shè)置?β=1粘勒，則有：
(20)x=(I?αA)?11
PageRank
Katz 中心性有一個不足，被一個 Katz 中心性較高的頂點指向的頂點具有較高的 Katz 中心性屎即，但如果這個中心性較高的頂點指向大量頂點庙睡，那么這些大量被指向的頂點也會擁有較高的中心性，但這種估計并非總是恰當(dāng)?shù)募祭Ｔ谛碌闹行男灾谐伺悖切┲赶蚝芏嗥渌旤c的頂點，即使本身的中心性很高雕擂，但也只能傳遞給它指向的每個頂點少量的中心性啡邑，定義為：
(21)xi=α∑jAijxjkjout?+β
其中，kjout?為頂點的出度井赌，當(dāng)?kjout=0?時可以將其設(shè)定為任何一個非零值谤逼，都不會影響計算結(jié)果。利用矩陣的形式仇穗，可以表示為：
(22)x=αAD?1x+β1
其中流部，D?為對角矩陣，Dii=max(kjout,1)纹坐。同之前一樣枝冀，β?只是整個公式的因子，設(shè)置?β=1耘子，有：
(23)x=(I?αAD?1)?11
該中心性即為?PageRank果漾。
上述 4 種中心性的區(qū)別和聯(lián)系如下表所示：
帶有常數(shù)項不帶常數(shù)項
除以出度x=(I?αAD?1)?11
PageRank
x=AD?1x
度中心性
不除出度x=(I?αA)?11
Katz 中心性
x=κ1?1Ax
特征向量中心性
接近度中心性
接近度中心性（closeness centrality）用于度量一個頂點到其他頂點的平均距離。
(24)Ci=1?i=n∑jdij
其中谷誓，dij?表示從頂點?i?到?j?的測地路徑長度跨晴，即路徑中邊的總數(shù)，?i?表示從?i?到?j?的平均測地距離片林。在大多數(shù)網(wǎng)絡(luò)中端盆，頂點之間的測地距離一般都較小，并且隨著網(wǎng)絡(luò)規(guī)模的增長费封，該值只是以對數(shù)級別速度緩慢增長焕妙。
在不同分支中的兩個頂點之間的測地距離定義為無窮大，則?Ci?為零弓摘。為了解決這個問題籽慢，最常見的方法是只計算同一分支內(nèi)部的頂點的平均測地距離。新的定義使用頂點之間的調(diào)和平均測地距離：
(25)Ci′=1n?1∑j(≠i)1dij
公式中排除了?j=i?的情況优质，因為?dii=0。結(jié)果也稱之為調(diào)和中心性（harmonic centrality）研叫。
介數(shù)中心性
介數(shù)中心性（betweenness centrality）描述了一個頂點在其他頂點之間路徑上的分布程度。假設(shè)在網(wǎng)絡(luò)中每兩個頂點之間璧针，在每個單位時間內(nèi)以相等的概率交換信息嚷炉，信息總是沿著網(wǎng)絡(luò)中最短測地路徑傳播，如果有多條最短測地路徑則隨機選擇探橱。由于消息是沿著最短路徑以相同的速率傳播申屹，因此經(jīng)過某個頂點的消息數(shù)與經(jīng)過該頂點的測地路徑數(shù)成正比。測地路徑數(shù)就是所謂的介數(shù)中心性隧膏，簡稱介數(shù)哗讥。
定義?nsti?為從?s?到?t?經(jīng)過?i?的測地路徑數(shù)量，定義?gst?為從?s?到?t?的測地路徑總數(shù)胞枕，那么頂點?i?的介數(shù)中心性可以表示為：
(26)xi=∑stnstigst
高介數(shù)中心性的頂點由于控制著其他頂點之間的消息傳遞杆煞，在網(wǎng)絡(luò)中有著很強的影響力。刪除介數(shù)最高的頂點腐泻，也最有可能破壞其他頂點之間的通信索绪。
不同中心性的可視化如下圖所示：
不同中心性可視化?By Tapiocozzo, CC BY-SA 4.0
其中，A：介數(shù)中心性贫悄；B：接近度中心性瑞驱；C：特征向量中心性；D：度中心性窄坦；E：調(diào)和中心性唤反；F：Katz 中心性。
傳遞性
傳遞性（transitivity）在社會網(wǎng)絡(luò)中的重要性要比其他網(wǎng)絡(luò)中重要得多鸭津。在數(shù)學(xué)上彤侍，對于關(guān)系“°”，如果?a°b?和?b°c逆趋，若能推出?a°c盏阶，則稱?°?具有傳遞性。
完全傳遞性值出現(xiàn)在每一個分支都是全連通的子圖或團的網(wǎng)絡(luò)中闻书。團（clique）是指無向圖網(wǎng)絡(luò)中的一個最大頂點子集名斟，在該子集中任何兩個頂點之間都有一條邊直接連接。完全傳遞性沒有太多的實際意義魄眉，而部分傳遞性卻很有用砰盐。在很多網(wǎng)絡(luò)中，u?認識?v?且?v?認識?w坑律，并不能保證?u?認識?w岩梳，但兩者之間相互認識的概率很大。
如果?u?也認識?w，則稱該路徑是閉合的冀值。在社會網(wǎng)絡(luò)術(shù)語中也物，稱?u,v,w?這 3 個頂點形成一個閉合三元組（closed triad）。我們將聚類系數(shù)（clustering coefficient）定義為網(wǎng)絡(luò)中所有長度為 2 的路徑中閉合路徑所占的比例：
長度為的路徑中閉合路徑數(shù)長度為的路徑數(shù)(27)C=長度為 2 的路徑中閉合路徑數(shù)長度為 2 的路徑數(shù)
其取值范圍在 0 到 1 之間列疗。社會網(wǎng)絡(luò)的聚類系數(shù)比其他網(wǎng)絡(luò)偏高滑蚯。
對于頂點?i，定地單個頂點的聚類系數(shù)為：
頂點的鄰居頂點中直接相連的頂點對數(shù)頂點的鄰居頂點對總數(shù)(28)Ci=頂點 i 的鄰居頂點中直接相連的頂點對數(shù)頂點 i 的鄰居頂點對總數(shù)
Ci?也稱為局部聚類系數(shù)（local clustering coefficient）作彤，該值代表了?i?的朋友之間互為朋友的平均概率。
相互性
聚類系數(shù)觀察的是長度為 3 的循環(huán)乌逐，長度為 2 的循環(huán)的頻率通過相互性（reciprocity）來度量竭讳，該頻率描述了兩個頂點之間相互指向的概率。
相似性
社會網(wǎng)絡(luò)分析的另一個核心概念是頂點之間的相似性浙踢。構(gòu)造網(wǎng)絡(luò)相似性的測度有兩種基本方法：結(jié)構(gòu)等價（structural equivalence）和規(guī)則等價（regular equivalence）绢慢，如下圖所示：
結(jié)構(gòu)等價
針對無向網(wǎng)絡(luò)中，最簡單和最顯而易見的結(jié)構(gòu)等價測度就是計算兩個頂點的共享鄰居頂點數(shù)洛波。在無向網(wǎng)絡(luò)中胰舆，頂點?i?和?j?的共享鄰居頂點數(shù)表示為?nij，有：
(29)nij=∑kAikAkj
利用余弦相似度可以更好的對其進行度量蹬挤。將鄰接矩陣的第?i?和第?j?行分別看成兩個向量缚窿，然后將這兩個向量之間的夾角余弦值用于相似性度量，有：
(30)σij=cos?θ=∑kAikAkj∑kAik2ΣkAjk2
假設(shè)網(wǎng)絡(luò)是不帶權(quán)重的簡單圖焰扳，上式可以化簡為：
(31)σij=∑kAikAkjkikj=nijkikj
其中倦零，ki?是頂點?i?的度。余弦相似度的取值范圍為從 0 到 1吨悍，1 表示兩個頂點之間擁有完全相同的鄰居節(jié)點扫茅。
皮爾遜相關(guān)系數(shù)通過同隨機選擇鄰居頂點條件下共享鄰居頂點數(shù)的期望值進行比較的方式進行計算，得到的標(biāo)準(zhǔn)的皮爾遜相關(guān)系數(shù)為：
(32)rij=∑k(Aik??Ai?)(Ajk??Aj?)∑k(Aik??Ai?)2∑k(Ajk??Aj?)2
上式的取值范圍從 -1 到 1育瓜，數(shù)值越大表明兩者之間越相似葫隙。
規(guī)則等價
規(guī)則等價的頂點不必共享鄰居頂點，但是兩個頂點的鄰居頂點本身要具有相似性躏仇。一些簡單的代數(shù)測度思想如下：定義一個相似性值?σij恋脚，若頂點?i?和?j?各自的鄰居頂點?k?和?l?本身具有較高的相似性，則?i?和?j?的相似性也較高焰手。對于無向網(wǎng)絡(luò)慧起，有以下公式：
(33)σij=α∑klAikAjlσkl
或者利用矩陣性質(zhì)表示為?σ=αAσA。
同質(zhì)性
在社會網(wǎng)絡(luò)中册倒，人們傾向于選擇那些他們認為與其自身在某些方面相似的人作為朋友蚓挤，這種傾向性稱為同質(zhì)性（homophily）或同配混合（assortative mixing）。
依據(jù)枚舉特征的同配混合
假設(shè)有一個網(wǎng)絡(luò)，其頂點根據(jù)某個枚舉特征（例如：國籍灿意、種族估灿、性別等）分類，且該特征的取值是一個有限集合缤剧。如果網(wǎng)絡(luò)中連接相同類型頂點之間的邊所占比例很大馅袁，那么該網(wǎng)絡(luò)就是同配的。量化同配性簡單的方法是觀測這部分邊占總邊數(shù)的比例荒辕，但這并不是很好的度量方法汗销，因為如果所有頂點都是同一個類型，那么測度值就是 1抵窒。
好的測度可以通過首先找出連接同類頂點的邊所占的比例弛针，然后減去在不考慮頂點類型時，隨機連接的邊中李皇，連接兩個同類頂點的邊所占比例的期望值的方式得到削茁。常用的測度為模塊度（modularity）：
(34)Q=12m∑ij(Aij?kikj2m)δgigi
其中，ki?為頂點?i?的度掉房，gi?為頂點?i?的類型茧跋，m?為總邊數(shù)，δij?為克羅內(nèi)克函數(shù)卓囚。該值嚴格小于 1瘾杭，如果同類頂點之間邊數(shù)的實際值大于隨機條件下的期望值，則該值為正數(shù)哪亿，否則為負數(shù)富寿，值為正說明該網(wǎng)絡(luò)是同配混合的。
依據(jù)標(biāo)量特征的同配混合
如果根據(jù)標(biāo)量特征（例如：年齡锣夹、收入等）來度量網(wǎng)絡(luò)中的同質(zhì)性页徐。由于該類特征具有確定的順序，因此根據(jù)標(biāo)量的數(shù)值银萍，不僅可以指出兩個頂點在什么情況下是完全相同的变勇，也可以指出它們在真么情況下是近似相同的。
令?xi?為頂點?i?的標(biāo)量值贴唇，(xi,xj)?為網(wǎng)絡(luò)中每一條邊?(i,j)?的兩個端點的值搀绣，利用協(xié)方差可以得到同配系數(shù)：
(35)r=∑ij(Aij?kikj/2m)xixj∑ij(kiδij?kikj/2m)xixj
該系數(shù)在全同配混合網(wǎng)絡(luò)中取最大值 1，在全異配混合網(wǎng)絡(luò)中取最小值 -1戳气，值 0 意味著邊兩端的頂點值是非相關(guān)的链患。
依據(jù)度的同配混合
依據(jù)度的同配混合是依據(jù)標(biāo)量特征的同配混合的一個特例。依據(jù)度的同配混合網(wǎng)絡(luò)中瓶您，高度數(shù)頂點傾向于與其他高度數(shù)頂點相連麻捻，而低度數(shù)頂點傾向于與其他低度數(shù)頂點相連纲仍。
在同配網(wǎng)絡(luò)中，度大的頂點傾向于聚集在一起的網(wǎng)絡(luò)中贸毕，我們希望得到網(wǎng)絡(luò)中這些度大的頂點構(gòu)成的頂點塊或核郑叠，它們周圍是一些度小的頂點構(gòu)成的低密度邊緣（periphery）。這種核心/邊緣結(jié)構(gòu)（core/periphery structure）是社會網(wǎng)絡(luò)的普遍特征明棍。
上圖 (a) 給出了一個小型的同配混合網(wǎng)絡(luò)乡革，其核心/邊緣結(jié)構(gòu)明顯，上圖 (b) 給出了一個小型異配混合網(wǎng)絡(luò)摊腋，通常不具備核心/邊緣結(jié)構(gòu)沸版，但頂點的分布更加均勻。
贊 賞
「真誠贊賞兴蒸，手留余香」
Newman, M. E. J. (2014)?網(wǎng)絡(luò)科學(xué)引論. 電子工業(yè)出版社.??
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002). Network motifs: simple building blocks of complex networks.?Science, 298(5594), 824-827.??
Jain, D., & Patgiri, R. (2019, April). Network Motifs: A Survey. In?International Conference on Advances in Computing and Data Sciences?(pp. 80-91). Springer, Singapore.??
Henderson, K., Gallagher, B., Eliassi-Rad, T., Tong, H., Basu, S., Akoglu, L., … & Li, L. (2012, August). Rolx: structural role extraction & mining in large graphs. In?Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining?(pp. 1231-1239).??
