【導(dǎo)讀】信息，對(duì)用戶的工作產(chǎn)生有意義的指導(dǎo)作用。但是隨著需要被處理的網(wǎng)絡(luò)圖的規(guī)。有效的展示成為圖的可視化技術(shù)的研究的重點(diǎn)內(nèi)容。論文針對(duì)課題所研究的對(duì)象和相關(guān)常用的概念的符號(hào)約定進(jìn)行了說(shuō)。算法的設(shè)計(jì)思路和實(shí)現(xiàn)流程，并指出了其各自的特點(diǎn)和缺陷。文引入了邊密度的概念?；贕N算法的邊分裂思路和NF算法的節(jié)點(diǎn)凝聚思路，GN和NF算法，從而提高了算法的執(zhí)行效率。權(quán)節(jié)點(diǎn)網(wǎng)絡(luò)圖的處理；修改節(jié)點(diǎn)越界的處理方式，使布局結(jié)果更加美觀。提供了豐富的輔助操作以獲得更好的用戶體驗(yàn)。每個(gè)模塊可以集成多個(gè)算法，提高了系統(tǒng)的可擴(kuò)展性和可維護(hù)性。

　　

【正文】 新的算法和經(jīng)典算法的性能做了分析比較。 ECAA算法一方面規(guī)避基于模塊度最優(yōu)的社區(qū)發(fā)現(xiàn)算法出現(xiàn)的的分辨率限制問(wèn)題，另一方面該算法的執(zhí)行時(shí)間復(fù)雜度接近線性時(shí)間，提高了社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)效率。 社區(qū)結(jié)構(gòu)的基本概念 針對(duì)網(wǎng)絡(luò)中的存在的社區(qū)結(jié)構(gòu)，到目前為止還沒(méi)有被廣泛認(rèn)可的唯一的定義，基于邊的相對(duì)連接頻數(shù)的定義較為常用：網(wǎng)絡(luò)中的頂點(diǎn)可以分成組 ,組內(nèi)連接稠密而組間連接稀疏 ［ 16,19］ 。在這個(gè)定義中提到的“稠密”和“稀疏”都是相對(duì)抽象的概念，并沒(méi)有 一個(gè)明確的量化的判斷標(biāo)準(zhǔn)，因此在探索網(wǎng)絡(luò)圖的社區(qū)結(jié)構(gòu)的過(guò)程中無(wú)法使用其來(lái)進(jìn)行社區(qū)結(jié)構(gòu)的探測(cè)。從而學(xué)者們?cè)噲D對(duì)網(wǎng)絡(luò)圖中的社區(qū)結(jié)構(gòu)給出一些定量化的定義。有學(xué)者就提出了強(qiáng)社區(qū)和弱社區(qū)的定義。強(qiáng)社區(qū)的定義 ［ 19,20］ 為：對(duì)于子圖 V 中任何一個(gè)節(jié)點(diǎn) v ， v 與 V 內(nèi)部頂點(diǎn)連接的度都大于其與 V 外部頂點(diǎn)連接的度。弱社區(qū)的定義 ［ 23,24］ 為：子圖 V 中所有節(jié)點(diǎn)與 V 內(nèi)部節(jié)點(diǎn)的度的和要大于 V 中所有節(jié)點(diǎn)與 V 外部節(jié)點(diǎn)連接的度的和。此外，還有學(xué)者提出了比 17 強(qiáng)社區(qū)更為嚴(yán)格的社團(tuán)定義 —— LS 集 ［ 25］ ,一個(gè) LS 集是一個(gè)由頂點(diǎn)構(gòu)成的集合，它的任何真子集都滿足強(qiáng)社區(qū)的定義。 另一類關(guān)于社區(qū)結(jié)構(gòu)的定義則是以連通性為標(biāo)準(zhǔn)，被稱為派系 ［ 26］ 。一個(gè)派系是指由 3 個(gè)或 3 個(gè)以上的頂點(diǎn)組成的全連通子圖，即任何兩點(diǎn)之間都直接相連。這是要求最強(qiáng)的一種定義，它可以通過(guò)弱化連接條件進(jìn)行拓展，形成 n?派 系 。例如： n? 派系是指子圖中的任意兩個(gè)頂點(diǎn)不必直接相連，但最多通過(guò)一個(gè)中介點(diǎn)就能夠連通。 3? 派系是指子圖中的任意兩個(gè)頂點(diǎn) ,最多通過(guò)兩個(gè)中介點(diǎn)就能連通。隨著 n 值的增加 ,n? 派系的要求越來(lái)越弱。這種定義允許社團(tuán)間存在重疊性 ［ 26］ 。所謂重疊性是指單個(gè)頂點(diǎn)并非僅僅屬于一個(gè)社團(tuán)，而是可以同時(shí)屬于多個(gè)社團(tuán)。社團(tuán)與社團(tuán)由這些有重疊歸屬的頂點(diǎn)相連。有重疊的社團(tuán)結(jié)構(gòu)問(wèn)題有研究的價(jià)值，因?yàn)樵趯?shí)際系統(tǒng)中，個(gè)體往往同時(shí)具有多個(gè)群體的屬性。除上述提到的社團(tuán)定義以外，還有多種其他定義方式，文獻(xiàn) [25]進(jìn)行了更為詳細(xì)的介紹。本文重點(diǎn)關(guān)注于可以完全分離的社區(qū)結(jié)構(gòu)問(wèn)題，采用較為常用的基于相對(duì)連接頻數(shù)的社團(tuán)結(jié)構(gòu)定義。 模塊度的基本概念 利用社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法對(duì)網(wǎng)絡(luò)圖進(jìn)行社區(qū)結(jié)構(gòu)的劃分，就是將 網(wǎng)絡(luò)圖分割成一系列的子圖，最佳的劃分是使所有的子圖都滿足社區(qū)結(jié)構(gòu)的定義。然而，在實(shí)際情況下，所處理的網(wǎng)絡(luò)圖并不存在一種劃分，使得劃分出的所有子圖都滿足社區(qū)結(jié)構(gòu)的定義，所以，這時(shí)候，社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法需要找出一個(gè)劃分，這個(gè)劃分應(yīng)該最大程度的接近于最佳的劃分。此時(shí)，需要對(duì)劃分進(jìn)行定量化的描述，這個(gè)描述可以區(qū)分出劃分之間的優(yōu)劣。 設(shè)矩陣 A 表示待處理網(wǎng)絡(luò)的鄰接矩陣，其中，矩陣的規(guī)模為 VV? ，并且對(duì)于節(jié)點(diǎn) i 和節(jié)點(diǎn) j ，如果這兩個(gè)節(jié)點(diǎn)之間有邊相連接，則矩陣 A 中的元素 ,ij jiAA都等于 1，否則 ,ij jiAA都等于 0。假設(shè)有一個(gè)劃分，將原始圖形劃分為多個(gè)圖，其中節(jié) 18 點(diǎn) v 所屬的子圖記為 vC ，則考慮如下的方程： ? ? ? ?, 1 ,2ij i jij ij i jijijijA c c A c cAV? ??? ?? （ ） 在上面的方程中，當(dāng) ijcc? 時(shí) ? ?,ijcc?為 1，否則為 0。即當(dāng)節(jié)點(diǎn) i 和節(jié)點(diǎn) j 屬于同一個(gè)團(tuán)的時(shí) ? ?,ijcc?為 1，屬于不同的團(tuán)的時(shí)候 ? ?,ijcc?為 0。針對(duì)一個(gè)好的劃分的時(shí)候，由于劃分出的子圖內(nèi)部的邊數(shù)較多，上面的方程會(huì)得到一個(gè)較大的值，反之，方程的值將較小。但是這個(gè)方程也是有缺陷的，當(dāng)把所有的節(jié)點(diǎn)都劃分為一個(gè)團(tuán)時(shí)，上面的方程會(huì)得到一個(gè)最大的值 1，這顯然是不太合理的。 為了克服上述方程的弊端并且能夠量化的描述劃分的優(yōu)劣程度， Girvan 和 Newman 定義了模塊度函數(shù) ［ 15］ 。模塊度函數(shù)的定義是指網(wǎng)絡(luò)中連接社團(tuán)結(jié)構(gòu)內(nèi)部頂點(diǎn)的邊所占的比例與另外一個(gè)隨機(jī)網(wǎng)絡(luò)中連接社團(tuán)結(jié)構(gòu)內(nèi)部頂點(diǎn)的邊所占比例的期望值相減得到的差值。這個(gè)隨機(jī)網(wǎng)絡(luò)的構(gòu)造方法為：保持每個(gè) 頂點(diǎn)的社團(tuán)屬性不變，頂點(diǎn)間的邊根據(jù)頂點(diǎn)的度隨機(jī)連接。如果社團(tuán)結(jié)構(gòu)劃分得好，則社團(tuán)內(nèi)部連接的稠密程度應(yīng)高于隨機(jī)連接網(wǎng)絡(luò)的期望水平。在劃分固定的前提下，設(shè) ik 為節(jié)點(diǎn) i 的度，則節(jié)點(diǎn) i 和節(jié)點(diǎn) j 之 間連邊的可能性為2ijkkV?，故模塊度函數(shù)可以使用如下公式來(lái)表示： ? ?1 ,22 ijij i jij kkQ A c cVV ????? ? ?????? （ ） 為了計(jì)算的方便，模塊化函數(shù)還有另外一種表示方式，如下： 21 2m sssldQ LL???????????????? （ ） 其中 m 是劃分出社區(qū)的個(gè)數(shù)， sl 是第 s 個(gè)社區(qū)內(nèi)部的邊數(shù)， sd 是第 s 個(gè)社區(qū)中節(jié)點(diǎn)的度 數(shù)和， L 是網(wǎng)絡(luò)中的總邊數(shù)。模塊度函數(shù)的值越大，表示社區(qū)結(jié)構(gòu)越明顯， 19 在實(shí)際網(wǎng)絡(luò)中，該值一般在 到 之間。 模塊度函數(shù)作為判斷社區(qū)劃分效果優(yōu)劣的標(biāo)準(zhǔn)，自提出以來(lái)就得到了廣泛的認(rèn)可，不僅完善了一些原來(lái)就有的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法 ，而且發(fā)展了眾多以模塊度最優(yōu)為標(biāo)準(zhǔn)的新算法，然而 Santo Fortunato 和 Marc Barthelemy 在 2020 年提出并證明了，基于模塊度最優(yōu)的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法執(zhí)行的結(jié)果會(huì)產(chǎn)生分辨率限制的問(wèn)題 ［ 27,28］ ，即某個(gè)本應(yīng)該成為一個(gè)獨(dú)立的社區(qū)，只要當(dāng)其內(nèi)部邊數(shù)目小于2L時(shí)，該社區(qū)就會(huì)和其它社區(qū)進(jìn)行合并使模塊度函數(shù)的值更優(yōu)，從而導(dǎo)致影響結(jié)果的準(zhǔn)確性。 社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法 ECAA 基于經(jīng)典聚類算法中節(jié)點(diǎn)凝聚的思想和邊分裂的思想，論文在接下來(lái)提出了一個(gè)基于邊密度的復(fù)雜網(wǎng)路社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法。 為了能夠衡量出社區(qū)內(nèi)部的邊和連接社區(qū)之間的邊之間的區(qū)別，論文首先提出了邊密度的概念。通過(guò)對(duì)網(wǎng)絡(luò)中所有的邊進(jìn)行其密度的計(jì)算，可以標(biāo)識(shí)出連接社區(qū)之 間的邊的邊密度相對(duì)較小而社區(qū)內(nèi)部的邊的邊密度相對(duì)較大的特征。 接下來(lái)，按照邊密度從小到大依次地從原網(wǎng)絡(luò)中將邊移除，并且在進(jìn)行某條邊的移除之前，會(huì)先判斷將該邊移除之后，當(dāng)前網(wǎng)絡(luò)中的所有節(jié)點(diǎn)的度是否都還大于等于 1，如果移除該邊會(huì)導(dǎo)致當(dāng)前網(wǎng)絡(luò)中的某個(gè)節(jié)點(diǎn)的度降為 0，則不將該邊移除，進(jìn)行下一條邊的移除。直到網(wǎng)絡(luò)中的任何一條邊的移除都會(huì)導(dǎo)致網(wǎng)絡(luò)中有度為 0 的節(jié)點(diǎn)存在，此時(shí)，停止去邊操作，這時(shí)候獲得的劃分稱為 OP 劃分。 對(duì)于 OP 劃分的粒度過(guò)細(xì)的問(wèn)題，論文引入了模塊之間吸引度的概念，按照各個(gè)被分裂模塊之間的吸引度進(jìn)行模塊之 間的合并。最終形成社區(qū)結(jié)構(gòu)并且記錄模塊的合并過(guò)程以形成層次化的網(wǎng)絡(luò)。 邊密度計(jì)算 GN 算法使用邊介數(shù)來(lái)辨別衡量出社區(qū)內(nèi)部的邊和連接社區(qū)之間的邊，在圖中，某條邊的邊介數(shù)表示圖中所有兩點(diǎn)之間的最短路徑通過(guò)該邊的次數(shù)。因此， 20 由于社區(qū)之間的節(jié)點(diǎn)之間的最短路徑必然會(huì)經(jīng)過(guò)連接社區(qū)之間的邊，從而連接社區(qū)之間的邊的邊介數(shù)比社區(qū)內(nèi)部的邊的邊介數(shù)有更大的趨勢(shì)。然而，由于在移除邊的過(guò)程中需要不斷的更新邊介數(shù)，而計(jì)算邊介數(shù)的時(shí)間復(fù)雜度為 O(n3)。顯然，要處理復(fù)雜網(wǎng)絡(luò)圖的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)，需要更加高效的衡量標(biāo)準(zhǔn)。 對(duì)于給定的一個(gè)網(wǎng)絡(luò) G ，如果某條邊 ae 是連接兩個(gè)社區(qū)的邊，那么與該邊相鄰的端點(diǎn)組成的子圖 aG 中的節(jié)點(diǎn)也應(yīng)該大體分屬于兩個(gè)社區(qū)；而如果某條邊 be 是某個(gè)社區(qū)內(nèi)部的邊，那么與該邊相鄰的端點(diǎn)組成的子圖 bG 中的節(jié)點(diǎn)也應(yīng)該大體屬于同一個(gè)社區(qū)；基于社區(qū)內(nèi)部節(jié)點(diǎn)互連概率大于社區(qū)之間節(jié)點(diǎn)的互連概率的社區(qū)的基本定義，那么 aG 中節(jié)點(diǎn)的互連性要比 bG 中的互連性要來(lái)的差?；谶@些認(rèn)識(shí)，接下來(lái)引入邊密度的概念。 定義 在圖 G 中，某條邊 ije 的邊密度 (edge density) ij? 如下定義： 設(shè)與節(jié)點(diǎn) i 或者節(jié)點(diǎn) j 相鄰的所有節(jié)點(diǎn)組成的集合為 ijK ，則 ijK 中 能形成邊的最大數(shù)是： ? ?12ij ijijKKT ??? 其中 ijK 表示 ijK 中的節(jié)點(diǎn)數(shù)， ijR 表示 ijK 中節(jié)點(diǎn)在 G 中實(shí)際的邊的個(gè)數(shù)，則 ijijijRT? ? 某條邊的邊密度的定義反映出了這條邊的兩個(gè)頂點(diǎn)在圖中所構(gòu)成的邊的數(shù)目在頂點(diǎn)的相鄰節(jié)點(diǎn)集合中所能夠構(gòu)成的邊的數(shù)目中的比重。能夠體現(xiàn)出構(gòu)成該邊的兩個(gè)頂點(diǎn)之間的聯(lián)系的緊密程度，相對(duì)于連接社區(qū)之間的邊，其兩個(gè)頂點(diǎn)之間的聯(lián)系相對(duì)較弱，從而使得該邊的邊密度較低。 定理 在圖 G 中，與邊 ije 的頂點(diǎn) i 或者 j 相鄰的所有節(jié)點(diǎn)的集合 ijK 可以表 21 示成： ? ?| 1 。 0 。 ,ij ik jkK k A A k n i j V? ? ? ? 其中 A 是圖 G 的鄰接矩陣。 證明： 充分性，設(shè)節(jié)點(diǎn) p 是 i 或者 j 的相鄰節(jié)點(diǎn)，則 ijA ， ijA 至少有一個(gè)為 1，所以ijpK? ； 必要性， ijpK?? ijpK?? ，則 |1ip jpAA? ，所以 ipA 和 jpA 至少有一個(gè)為 1，即 p與 i 或者 j 相鄰； 綜上所述，原命題的證。 證畢 計(jì)算圖中所有的邊的邊密度的計(jì)算復(fù)雜度是 ? ?Ok m? ，相比計(jì)算邊介數(shù)的復(fù)雜度要低兩個(gè)數(shù)量級(jí)。 去邊策略 在 GN 算法中，通過(guò)每一次移除邊介數(shù)最大的邊直到所有的邊都從網(wǎng)絡(luò)中移除來(lái)獲得社區(qū)結(jié)構(gòu)發(fā)現(xiàn)的層次化樹(shù)。在上一節(jié)的討論中，通過(guò)社區(qū)之間的邊和社區(qū)內(nèi)部的邊與其相鄰節(jié)點(diǎn)的關(guān)系，引出了邊密度的概念。簡(jiǎn)單的考慮社區(qū)內(nèi)部和社區(qū)之間的邊的邊密度是沒(méi)有多大意義的，因?yàn)檫@些邊的邊密 度的大小并沒(méi)有一個(gè)明確的衡量標(biāo)準(zhǔn)。 考慮節(jié)點(diǎn) v 是給定的一個(gè)網(wǎng)絡(luò) G 中的一個(gè)節(jié)點(diǎn)，以 v 為端點(diǎn)的邊的集合為 vE ，vE 中邊的邊密度越大的邊就可以反映出 v 更希望通過(guò)這條邊與其它節(jié)點(diǎn)進(jìn)行抱團(tuán)。因此，設(shè)計(jì)一種去邊策略，如果能夠保留住以 v 為端點(diǎn)的邊的集合中邊密度最大的邊，那么就可以認(rèn)為所有的連接社區(qū)之間的邊都被去掉了。這樣做，一方面沒(méi)有將所有的邊都移除，仍然保留了一部分邊，減少了算法的執(zhí)行步驟；另一方面，以邊密度作為去邊的依據(jù)，相比 GN 算法大大的減少了算法的時(shí)間復(fù)雜 度。 22 基于此，下面給出我們的去邊思路。 定義 ije 是 E 中的邊，如果從 E 中移除該邊不會(huì)使 ije 的頂點(diǎn)的度降為 0，則去掉 ije ；反之，保留 ije 。將這個(gè)過(guò)程稱為去邊過(guò)程，使用 CE（ Cast Edge）表示。 根據(jù)定義 ，去邊過(guò)程的執(zhí)行并不會(huì)像 GN 算法那樣直接移除掉原來(lái)網(wǎng)絡(luò)中的所有的邊，它能夠保證圖中任意一個(gè)節(jié)點(diǎn)肯定至少能夠保留一條連接以該節(jié)點(diǎn)為端點(diǎn)的邊。 定義 將圖中所有邊的邊密度從小到大排序，從邊密度最小的邊開(kāi)始，對(duì)每條邊進(jìn)行 CE，這個(gè)過(guò)程使用 CEA（ Cast Edge All）表示；執(zhí)行完 CEA 獲得的劃分，稱為初次劃分，使用 OP（ Original Partition）表示。 根據(jù)定義 ，它優(yōu)先去掉最優(yōu)可能是連接社區(qū)之間的邊，但是它并不保證不會(huì)移除掉社區(qū)內(nèi)部的邊，所以根據(jù)定義 進(jìn)行執(zhí)行得到的初次劃分是相對(duì)最佳的社區(qū)劃分精度更小的劃分。 定理 設(shè) c 是在 OP 中的任意一個(gè)社區(qū)，則 c 中最多只有一個(gè)節(jié)點(diǎn)的度大于1，其它節(jié)點(diǎn)的度都等于 1。 證明： 首先根據(jù) CEA 的定義 ，顯然， c 中任意節(jié)點(diǎn)的度都大于等于 1 的。下面證明 c中不會(huì)包含兩個(gè)大于 1 的節(jié)點(diǎn)； 假設(shè) c??OP 且 12,v v c? ，其中 12,vv的度大于 1； 如果 12,vv相鄰，那么去掉 12,vv之間的邊，不會(huì)使 12,vv的度都將為 0，也就是說(shuō)， 12,vv之間的邊是通過(guò) CEA 過(guò)程可以去掉的，與 OP 的定義相矛盾； 如果 12,vv不相鄰，但是由于 12,v v c? ，所以 12,vv之間至少有一條路徑可以到達(dá)，所以至少有一個(gè)與 1v 相鄰的節(jié)點(diǎn)的度大于 1，和討論的第一種情況一樣，也是矛 23 盾的； 綜上所述，原命題成立。 證畢 執(zhí)行 CEA 的時(shí)間復(fù)雜度也是 ? ?Ok m? 。 模塊合并 復(fù)雜網(wǎng)絡(luò)研究的核心之一就是化簡(jiǎn)原有網(wǎng)絡(luò)的規(guī)模，在原有網(wǎng)絡(luò)上生成層次化的樹(shù)來(lái)進(jìn)行可視化的研究。通過(guò) 前面一節(jié)的討論，初次劃分從直觀上來(lái)說(shuō)就是，將社區(qū)之間連接去掉，并且也將社區(qū)內(nèi)部分裂成了很多小社區(qū)，由于 CEA 優(yōu)先去掉最優(yōu)可能是連接社區(qū)之間的邊，但是它并不保證不會(huì)移除掉社區(qū)內(nèi)部的邊，所以所獲得的初次劃分對(duì)圖的劃分相對(duì)于最佳的社區(qū)劃分對(duì)圖的劃分更加精細(xì)，所以我們需要將初次劃分里面的一個(gè)個(gè)的更小的社區(qū)進(jìn)行合并，用來(lái)獲得最佳的劃分結(jié) 構(gòu)。 根據(jù)社區(qū)內(nèi)部連邊緊密，社區(qū)之間連邊稀疏的社區(qū)定義。因此社區(qū)內(nèi)部分裂的小社區(qū)之間的互連性要比和其它社區(qū)分裂的小社區(qū)之間的互連性要來(lái)的大。根據(jù)這種想法，我們提出描述這種互連性的社區(qū)吸引度的概念。 定義 設(shè) aC 是劃分 P 的某個(gè)社區(qū)，inaC表示在 aC 內(nèi)部的連邊數(shù)目，outaC表示 aC 和其它社區(qū)之間的連邊