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

　　

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