【正文】 定義 設(shè) aC 是劃分 P 的某個社區(qū)，inaC表示在 aC 內(nèi)部的連邊數(shù)目，outaC表示 aC 和其它社區(qū)之間的連邊。因此社區(qū)內(nèi)部分裂的小社區(qū)之間的互連性要比和其它社區(qū)分裂的小社區(qū)之間的互連性要來的大。通過 前面一節(jié)的討論，初次劃分從直觀上來說就是，將社區(qū)之間連接去掉，并且也將社區(qū)內(nèi)部分裂成了很多小社區(qū)，由于 CEA 優(yōu)先去掉最優(yōu)可能是連接社區(qū)之間的邊，但是它并不保證不會移除掉社區(qū)內(nèi)部的邊，所以所獲得的初次劃分對圖的劃分相對于最佳的社區(qū)劃分對圖的劃分更加精細(xì)，所以我們需要將初次劃分里面的一個個的更小的社區(qū)進(jìn)行合并，用來獲得最佳的劃分結(jié) 構(gòu)。 證畢 執(zhí)行 CEA 的時間復(fù)雜度也是 ? ?Ok m? 。 證明： 首先根據(jù) CEA 的定義 ，顯然， c 中任意節(jié)點的度都大于等于 1 的。 根據(jù)定義 ，它優(yōu)先去掉最優(yōu)可能是連接社區(qū)之間的邊，但是它并不保證不會移除掉社區(qū)內(nèi)部的邊，所以根據(jù)定義 進(jìn)行執(zhí)行得到的初次劃分是相對最佳的社區(qū)劃分精度更小的劃分。 根據(jù)定義 ，去邊過程的執(zhí)行并不會像 GN 算法那樣直接移除掉原來網(wǎng)絡(luò)中的所有的邊，它能夠保證圖中任意一個節(jié)點肯定至少能夠保留一條連接以該節(jié)點為端點的邊。 定義 ije 是 E 中的邊，如果從 E 中移除該邊不會使 ije 的頂點的度降為 0，則去掉 ije ；反之，保留 ije 。這樣做，一方面沒有將所有的邊都移除，仍然保留了一部分邊，減少了算法的執(zhí)行步驟；另一方面，以邊密度作為去邊的依據(jù)，相比 GN 算法大大的減少了算法的時間復(fù)雜 度。 考慮節(jié)點 v 是給定的一個網(wǎng)絡(luò) G 中的一個節(jié)點，以 v 為端點的邊的集合為 vE ，vE 中邊的邊密度越大的邊就可以反映出 v 更希望通過這條邊與其它節(jié)點進(jìn)行抱團(tuán)。在上一節(jié)的討論中，通過社區(qū)之間的邊和社區(qū)內(nèi)部的邊與其相鄰節(jié)點的關(guān)系，引出了邊密度的概念。 證畢 計算圖中所有的邊的邊密度的計算復(fù)雜度是 ? ?Ok m? ，相比計算邊介數(shù)的復(fù)雜度要低兩個數(shù)量級。 ,ij ik jkK k A A k n i j V? ? ? ? 其中 A 是圖 G 的鄰接矩陣。 定理 在圖 G 中，與邊 ije 的頂點 i 或者 j 相鄰的所有節(jié)點的集合 ijK 可以表 21 示成： ? ?| 1 。 定義 在圖 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ù)目中的比重。 對于給定的一個網(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 中的互連性要來的差。然而，由于在移除邊的過程中需要不斷的更新邊介數(shù)，而計算邊介數(shù)的時間復(fù)雜度為 O(n3)。 邊密度計算 GN 算法使用邊介數(shù)來辨別衡量出社區(qū)內(nèi)部的邊和連接社區(qū)之間的邊，在圖中，某條邊的邊介數(shù)表示圖中所有兩點之間的最短路徑通過該邊的次數(shù)。 對于 OP 劃分的粒度過細(xì)的問題，論文引入了模塊之間吸引度的概念，按照各個被分裂模塊之間的吸引度進(jìn)行模塊之 間的合并。 接下來，按照邊密度從小到大依次地從原網(wǎng)絡(luò)中將邊移除，并且在進(jìn)行某條邊的移除之前，會先判斷將該邊移除之后，當(dāng)前網(wǎng)絡(luò)中的所有節(jié)點的度是否都還大于等于 1，如果移除該邊會導(dǎo)致當(dāng)前網(wǎng)絡(luò)中的某個節(jié)點的度降為 0，則不將該邊移除，進(jìn)行下一條邊的移除。 為了能夠衡量出社區(qū)內(nèi)部的邊和連接社區(qū)之間的邊之間的區(qū)別，論文首先提出了邊密度的概念。 模塊度函數(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)確性。在劃分固定的前提下，設(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ù)。這個隨機網(wǎng)絡(luò)的構(gòu)造方法為：保持每個 頂點的社團(tuán)屬性不變，頂點間的邊根據(jù)頂點的度隨機連接。 為了克服上述方程的弊端并且能夠量化的描述劃分的優(yōu)劣程度， Girvan 和 Newman 定義了模塊度函數(shù) ［ 15］ 。針對一個好的劃分的時候，由于劃分出的子圖內(nèi)部的邊數(shù)較多，上面的方程會得到一個較大的值，反之，方程的值將較小。假設(shè)有一個劃分，將原始圖形劃分為多個圖，其中節(jié) 18 點 v 所屬的子圖記為 vC ，則考慮如下的方程： ? ? ? ?, 1 ,2ij i jij ij i jijijijA c c A c cAV? ??? ?? （ ） 在上面的方程中，當(dāng) ijcc? 時 ? ?,ijcc?為 1，否則為 0。此時，需要對劃分進(jìn)行定量化的描述，這個描述可以區(qū)分出劃分之間的優(yōu)劣。 模塊度的基本概念 利用社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法對網(wǎng)絡(luò)圖進(jìn)行社區(qū)結(jié)構(gòu)的劃分，就是將 網(wǎng)絡(luò)圖分割成一系列的子圖，最佳的劃分是使所有的子圖都滿足社區(qū)結(jié)構(gòu)的定義。除上述提到的社團(tuán)定義以外，還有多種其他定義方式，文獻(xiàn) [25]進(jìn)行了更為詳細(xì)的介紹。社團(tuán)與社團(tuán)由這些有重疊歸屬的頂點相連。這種定義允許社團(tuán)間存在重疊性 ［ 26］ 。 3? 派系是指子圖中的任意兩個頂點 ,最多通過兩個中介點就能連通。這是要求最強的一種定義，它可以通過弱化連接條件進(jìn)行拓展，形成 n?派 系 。 另一類關(guān)于社區(qū)結(jié)構(gòu)的定義則是以連通性為標(biāo)準(zhǔn)，被稱為派系 ［ 26］ 。弱社區(qū)的定義 ［ 23,24］ 為：子圖 V 中所有節(jié)點與 V 內(nèi)部節(jié)點的度的和要大于 V 中所有節(jié)點與 V 外部節(jié)點連接的度的和。有學(xué)者就提出了強社區(qū)和弱社區(qū)的定義。在這個定義中提到的“稠密”和“稀疏”都是相對抽象的概念，并沒有 一個明確的量化的判斷標(biāo)準(zhǔn)，因此在探索網(wǎng)絡(luò)圖的社區(qū)結(jié)構(gòu)的過程中無法使用其來進(jìn)行社區(qū)結(jié)構(gòu)的探測。 ECAA算法一方面規(guī)避基于模塊度最優(yōu)的社區(qū)發(fā)現(xiàn)算法出現(xiàn)的的分辨率限制問題，另一方面該算法的執(zhí)行時間復(fù)雜度接近線性時間，提高了社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)效率。接下 來詳細(xì)地分析了新的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法 —— ECAA的具體步驟。 本章首先介紹了社區(qū)結(jié)構(gòu)的基本概念和經(jīng)典社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法的社區(qū)結(jié)構(gòu)劃分優(yōu)劣的評判準(zhǔn)則 —— 模塊度的概念。 16 第三章 基于邊密度的復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法 概述 GN 算法和 NF 算法是經(jīng)典的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法，在網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)質(zhì)量上有著不俗的表現(xiàn)，但是對于復(fù)雜網(wǎng)絡(luò)來說，其性能仍 然不能滿足系統(tǒng)的要求，其中 GN 算法的時間復(fù)雜度是 ? ?3ON ， NF 算法的時間復(fù)雜度是? ?? ?O N N E??。并對現(xiàn)有算法的不足之處進(jìn)行了相應(yīng)的分析。接下來介紹了FDA 和 FR 兩種用于網(wǎng)絡(luò)圖布局的力導(dǎo)引算法。 本章小結(jié) 本章對復(fù)雜網(wǎng)絡(luò)圖的可視化技術(shù)涉及到的相關(guān)概念進(jìn)行了介紹。其次，第二個事實是現(xiàn)實圖中的節(jié)點通常不會只屬于某一個社區(qū)。為了降低研究的時間復(fù)雜度，該語義網(wǎng)絡(luò)中的邊通過用戶指定的一個閥值來進(jìn)行修剪。舉個例子，文獻(xiàn) [22]中的模型為在線社會網(wǎng)絡(luò)用戶評論（ HTML 格式）萃取出的語義信息構(gòu)建了一個帶權(quán)語義網(wǎng)絡(luò)。不幸的是，在現(xiàn)實中的網(wǎng)絡(luò)中的圖一般都不是簡單圖。在文獻(xiàn)[16]中指出該算法在 42 分鐘內(nèi)處理了含有 56 276 個節(jié)點的網(wǎng)絡(luò)，而使用 GN 算法需要花費 3 到 5 年的時間，說明 NF 算法是一個性能很優(yōu)秀的社區(qū)發(fā)現(xiàn)算法，但其時間復(fù)雜度仍然有提升的空間。最多能夠進(jìn)行 1n? 次這樣的操作； 4. 選擇使 Q 函數(shù)值達(dá)到最大時的層次作為對原網(wǎng)絡(luò)的社區(qū)劃分。該算法過程如下： 1. 初始時，將網(wǎng)絡(luò)中每一個節(jié)點都看成一個獨立的社區(qū)，此時，每一個社區(qū)內(nèi)只有一個節(jié)點。 圖 GN 算法得到的空手道俱樂部社團(tuán)結(jié)構(gòu)劃分的 樹狀圖及對應(yīng)的模塊化函數(shù)值 [19] GN 算法有著非常好的社區(qū)發(fā)現(xiàn)性能 [19]，但是它的時間復(fù)雜度是 ? ?2Omn? ，因此無法將其用于規(guī)模較大的復(fù)雜網(wǎng)絡(luò)。這樣，對于網(wǎng)絡(luò)圖中社區(qū)結(jié)構(gòu)的劃分顯然會產(chǎn)生很重要的影響。這個時候，如果不重新計算各個邊的邊介數(shù)，那么，剩下的這條邊根據(jù)其上一次計算的邊介數(shù)數(shù)值可能不會被立即從網(wǎng)絡(luò)圖中移除。以一個例子來說：假設(shè)有一個包含兩個社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)圖，并且只有兩條邊進(jìn)行連接。 算法中包含的重新計算網(wǎng)絡(luò)圖中剩下邊的邊介數(shù)這個步驟是非常有必要的。通過 連接社區(qū)之間的邊的邊介數(shù)一般性來講要比社區(qū)之內(nèi)的邊的邊介數(shù)要高的原因， GN 算法采取每次去掉網(wǎng)絡(luò)中邊介數(shù)最高的邊，直到網(wǎng)絡(luò)中所有的邊全部移除，然后再取去邊過程中使模塊度函數(shù)的值達(dá)到最大時的劃分作為社區(qū)劃分。對于網(wǎng)絡(luò)圖中的某條邊，該邊的邊介數(shù)指的是 網(wǎng)絡(luò)圖中任意兩點的最短距離所通過該邊的次數(shù) 。如果能夠找到標(biāo)識出社區(qū)之間連邊的這種特性的標(biāo)準(zhǔn)，那就可以通過這個標(biāo)準(zhǔn)，找出所有的這些邊，并將其移除，那么網(wǎng)絡(luò)圖中剩下的部 分就是被分割出來的社區(qū)了。根據(jù)網(wǎng)絡(luò)圖中對于社區(qū)結(jié)構(gòu)的定義知道，社區(qū)內(nèi)部的節(jié)點之間連接緊密，而社區(qū)之間的節(jié)點之間連接稀疏 ［ 15,19］ 。 GN 算法由 Girvan 和 Newman 在 2020 年在文獻(xiàn) [15]中被提出 。接下來將介紹其中一部分最有名的社區(qū)結(jié)構(gòu)探測方 法。在通過凝聚節(jié)點和移除邊兩種方式來進(jìn)行社區(qū)結(jié)構(gòu)發(fā)現(xiàn)的時候可以建立起一個層次化的樹結(jié)構(gòu)，這類算法的特點在于關(guān)注網(wǎng)絡(luò)連通形成的拓?fù)浣Y(jié)構(gòu)，并應(yīng)用拓?fù)浣Y(jié)構(gòu)的特性刻畫頂點和連邊，劃分網(wǎng)絡(luò)中的社團(tuán)。 圖 社區(qū)網(wǎng)絡(luò)結(jié)構(gòu)示意圖 社區(qū)探測是社會網(wǎng)絡(luò)研究工作中的一項重要課題。模塊度函數(shù)的值越大，表示社區(qū)結(jié)構(gòu)越明顯，在實際網(wǎng)絡(luò)中，該值一般在 到 之間。它是指網(wǎng) 絡(luò)中的頂點可以分成組 ,組內(nèi)頂點間的連接比較稠密 ,組間頂點的連接比較稀疏 ［ 1522］ 。針對某一層進(jìn)行可視化布局一方面加快了處理速度，另一方面減少了畫布上展示的節(jié)點數(shù)目，而且用戶可以通過上鉆和下鉆操作對感興趣的某一部分進(jìn)行更高精度的觀察和分析。 11 復(fù)雜網(wǎng)絡(luò)圖的化簡 網(wǎng)絡(luò)圖的層次化模型 直接使用傳統(tǒng)的布局算法對圖直接運算產(chǎn)生布局結(jié)果的做法已不適應(yīng)圖的規(guī)模的不斷增大：其一，布局大量節(jié)點耗時過長，超過了用戶的忍耐極限；其二，大量的節(jié)點和連邊直接展示在有限的布局畫板上，使得用戶無法從其中獲得有效的信息，失去了圖可視化的原有目的。19a u va u vuvf p pe u d isp e u d isp f p pe n dfo r v in V d o b e g inv p o s v p o s p p v d isp te n dt c o o l te n d??? ? ? ???? 圖 FR 算法偽代碼 FR 算法得益于出色的模型選擇，所以能夠畫出相當(dāng)優(yōu)美的圖形。14151 6 . : . * m i n ( . , ) 。1 2 . . : . .r u vfo r i to ite ra tio n s d o b e g info r v in V d o b e g inv d ispfo r u in V d oif u v th e n b e g inv p o s u p o sv d isp v d isp f p pe n de n dfo r e in E d oe v p o s e u p o se v d isp e v d isp????? ? ?? ? ? ?? ? ??? ? ?? ?。7 . : . 。算法偽代碼見圖 ： ? ?A L GOR I T HM F R