復雜網絡深度重疊結構的發現

摘要： 為了更好地了解網絡，以相似度為基礎，讓節點選擇多個相似節點形成相似節點對，通過蒙卡模擬結果提出了基于最大節點相似度和度的配對算法發現了網絡的重疊社團結構。利用多級最相似度繼續優化社團結構，找出了網絡社團的深層重疊結構和子社團結構。提出的算法從真實網絡形成社團的原因出發發現了網絡的重疊結構，并且進一步優化社團結構，發現了網絡的深層重疊社團結構和其中的子社團結構。

關鍵詞： 復雜網絡；社團結構；深度重疊結構；子社團結構

中圖分類號： TP391;O157文獻標識碼： A

Discovery of Deep Overlapping Structures in Complex Networks

GAO Feng

（College of Science， China Three Gorges University， Yichang 443002，China）

Abstract：In order to better understand the network， based on the similarity， let the nodes select multiple similar nodes to form similar node pairs. Through the Monte Carlo simulation results， a pairing algorithm based on the maximum node similarity and degree is proposed to discover the overlapping community structure of the network. Using multi-level most similarity to continue to optimize the community structure， find out the deep overlapping structure and sub-community structure of the network community. The proposed algorithm discovers the overlapping structure of the network based on the reason why the real network forms a community， and further optimizes the community structure， discovering the deep overlapping community structure of the network and its sub-community structure.

Keywords： complex network; community structure; deep overlapping structure; sub-community structure

0 引言

網絡已成為理解系統間的相互作用（包括對生物有機體和人類社會中多種現象的研究）的一種關鍵性手段［14］。為了了解復雜系統中節點的結構及不同節點對于網絡功能的影響，復雜網絡已經在各個領域引起了相當大的關注。復雜網絡將個體抽象成節點，節點間的相互作用關系理解成連邊，利用復雜網絡的方法為復雜系統的分析提供了上帝視角。通過復雜網絡模型，科學家可以利用圖論、統計物理、控制論、矩陣論等研究、分析復雜系統的結構、功能和動力學特征，最終實現對系統的干預和控制［45］。

社團結構對于不同的網絡有著不同的作用，從2002年Girvan和Newman［6］基于復雜網絡的邊介數提出GN算法開始，來自各個領域的學者圍繞社團檢測開展了深入研究。Macropol等［7］提出了一種基于重復隨機游走（RRW），用于發現功能模塊，例如，在大規模蛋白質網絡中復合物或通路，RRW考慮了網絡拓撲結構、邊權和網絡之間的遠程交互關系。Li J等［8］采用深度搜索和面包搜索相結合的算法提取小團，然后通過一定的規則，將這些團合并成一個更大的子圖，所提出的算法成功地找到了重疊頂點和橋接頂點社區。Mahdi等［9］提出了IEDC算法，通過集成框架進行一般社區檢測，以提取重疊和非重疊的社區結構，而無需假設網絡上的先前結構連接。

本文首先從社團的節點相似度角度去研究復雜網絡社團結構的劃分算法，然后根據數據深度優化模型發現社團的深度重疊結構，這個方法同時解釋了網絡的重疊結構和社團中的子社團結構，對實際的網絡結構有很好的解釋分析效果，具有一定的現實意義。

1 算法：基于最大節點的度和相似度配對算法

隨著科學研究進程，越來越多的研究說明大多數復雜網絡具有社團結構，這也就產生了一個新的研究方向，尋找復雜網絡中具有相似特點或關系密切的小社團。這些小社團普遍具有內部聯系密切，外部關聯稀疏的特點。本文提出了一種算法，來揭示復雜網絡的重疊結構。該算法分析了自然網絡中社團的形成。社團的形成是由于個體具有相似或相同的性質，這也說明社團是因為個體的自然選擇形成的。在該算法中定義節點間的相似度為個體之間相同的鄰居數：

Sij=Aij1+∑kAik*Akj（1）

其中，Aij等于0或1，Aij=1表示節點i和節點j之間存在連邊，相反Aij=0則表示節點i和節點j之間不存在連邊。根據個體最有可能選擇與其相似或者滿足其期望的個體形成社團，定義節點之間的相似度Sij。相似度Sij保證了兩個個體如果相連，它們的相似度大于1，即它們之間一定存在對方作為鄰居，同時個體只會選擇與它直接相連的個體。

本文以23節點的網絡為例，網絡結構如圖1所示，根據相似度定義計算任意兩節點的相似度Sij。每個節點選擇相似度最大的節點形成相似節點對，同樣地這些節點可以存在多個選擇，形成多個節點對如表1所示。從相似度最大的相似節點對開始構建社團，當最大相似度相同時，優先考慮節點度大的節點形成的節點對，認為相似節點對是一個單向選擇關系，將節點i加入到節點j所有社團中，因為節點19的多個選擇，這樣也就形成了重疊的社團結構。然后重復上個步驟到最后一個相似節點對。

每個節點選擇相似度最大的節點形成相似節點對后，按照節點相似度大小進行排序形成社團，當可以用隨機的方式選擇節點。23節點的網絡中，節點通過選擇最大相似度形成節點對后，隨機選擇節點對形成社團的順序運行一萬次，統計用這個模型得到的網絡社團結構的結果。如圖2為出現概率最大的劃分結果（其中相同形狀的節點屬于同一社團，紅色六邊形的節點表示重疊節點），圖3為出現頻率第二大的結果。如圖4，圖5所示，當隨機選擇不同的順序時，會有不同的分組結果。但是其中以最大相似度排序后形成的社團結構相同的結果出現的次數最多，這也說明了對于真實自然的網絡，社團的形成會優先選擇最大相似度大的節點對先形成社團，同樣由于順序不同網絡會具有社團結構的多樣化。

真實網絡可能由于不同的選擇順序形成不同程度的重疊社團現象，為了定量描述這些網絡的重疊社團劃分好壞，這里引入網絡的擴展模塊度EQ［10］。EQ是基于模塊度提出的用來評價重疊社團劃分好壞的參數，當每個頂點只屬于一個社區時，EQ降為模塊度Q，當所有節點都屬于同一個社區時，EQ為0。另外EQ值越高，表示社區結構重疊越明顯。EQ的計算公式為

EQ=12m∑i∑v∈Ci，w∈Ci1OvOwAvw－kvkw2m（2）

其中，m=12∑vwAvw為網絡的總邊數，kv為節點v的度，Ov為節點v所在的社團數量，計算所有不同的社團劃分EQ的大小，因為絕大多數社團結構出現的概率很小，這里只取出現次數最多的6個社團劃分結果，如表2所示可以看出本文中的模型劃分社團結構的出現概率和EQ最大。

基于節點的度和相似度配對算法認為所有節點只能選擇最相似節點形成相似節點對，這樣可以揭示實際社團的重疊結構，但是對于不同網絡來說這種選擇可能是更深層的，節點也可以選擇相似度不是那么大的節點同樣形成節點對。我們讓節點可以選擇更多不同相似度的節點形成節點對，進一步更新本文的社團結構，找到重疊程度更大的社團結構。

2 深層重疊結構

對于真實網絡來講，讓所有的節點去選擇最大相似度節點形成節點對，然后根據節點對形成社團。但是對于實際網絡個體可能不僅僅只選擇最相似的節點，同樣的也會選擇其他相似度較小的節點形成節點對，但是這些節點對只會讓劃分的社團數量減少，社團的重疊性增加。為了找到重疊程度更大的結構，本文利用多級相似度進一步優化社團，算法流程如圖6所示。

根據本文的算法得到了最相似節點對形成的社團后，計算各個節點與社團的聯系度，社團的聯系度為該節點與各個社團中所有的連邊條數。從圖8中可以看19號節點與社團3中的20號、21號和22號直接相連，與社團4中的13號、14號和16號節點直接相連，所以19號節點與社團3和社團4的聯系度都為3。圖7給出了所有節點的社團聯系度。

從圖7（其社團結構的劃分情況見圖8一級相似度社團劃分）看到，19號節點與社團3和社團4的聯系度相同，所以在第一步用最大相似度劃分社團時只發現了19號節點為重疊節點。但是9號、17號、18號節點都和兩個或多個社團聯系度相近，它們可能也是重疊的節點。用最相似節點對算法并沒有發現它們，可能是使用數據的深度不夠，網絡中的個體不僅僅只會選擇最相似的節點形成社團，如果只用最相似節點對可能會丟掉了一些重要的信息。鑒于此，本文引入二級最大相似度，進一步改進劃分的社團。讓節點選擇第二相似的節點形成節點對，按照上文的步驟進行。劃分結果如圖9所示。

當同時使用一級最大相似度和二級最大相似度后，原來的社團5{17，18}消失了，變成了社團3和社團4的重疊節點，17號和18號節點對于社團3和社團4的聯系密切并且聯系度相似，在二級相似度的作用下17號和18號節點順利地進入到兩個社團中。在社團3和社團4中我們認為，并不是所有的節點聯系一樣密切，由于17號節點和18號節點是通過二級最大相似度進入的，所以明顯在這兩個社團中17號和18號他們兩個關系更加親密。將原來處于同一社團的節點加入到另一個相同社團中形成的結構稱為這個社團的子社團，如{17，18}。

為了找到更深層次的重疊結構和更多的子社團結構，本文引入更多的最大相似度去劃分社團，對于社團劃分過程具體思路與二級最大相似度相似，按照本文提出的算法的步驟進行劃分社團，社團結構演化結果如圖8～圖11所示。具體的算法流程：

第1步：找到所有節點的最相似節點，其中單個節點可能存在多個最相似節點形成節點對。

第2步：對于所有節點對按照相似度大小和節點度的大小排序，將節點對視為單向選擇關系，節點對的相似度和節點的度越大越快形成社團。最大相似度形成節點對用完后得到一級重疊社團結構。

第3步：根據相似度大小讓所有節點選擇相似度第二大的節點形成新的節點對，按照第1步、第2步重新更新社團結構。利用第二大相似度更新社團得到新二級社團結構。

第4步：利用節點間的不同相似度依次得到更深層次的社團結構。

從圖10得到3號、4號節點分別通過三級、四級最大相似度加入社團4，由圖7可以看出，3號節點對于社團2和社團4的聯系度差異小于3號節點與社團2和社團4的聯系度差異，這也說明了節點對于多個社團聯系度差異越小，那么這個節點的重疊性就越明顯。這里定義區分不同的重疊節點類型，按照這些重疊節點是在第幾級最大相似度被發現出來的，如19號節點為一級重疊節點，17號、18號、9號、7號、8號節點為二級重疊節點。不同級數的重疊節點代表兩個社團之間因為這些節點的重疊性不同。

如圖9利用二級最大相似度更新社團后，發現17號，18號節點同時加入到了社團3和社團4中，讓社團3和社團4重疊程度變大，并且對于社團3來講17號，18號節點就是社團的子社團結構。同樣的17號，18號也是社團4的子社團結構。處于同一社團的節點比其他社團節點的聯系密切，對于社團中存在的子社團結構它們的親近程度要大于和其他同一社團的節點。

隨著相似度級數增加數據深度越深，可用的最大相似度節點對數量就越少，這是由于只有小部分節點的相似節點對比較多，并且越到后面節點對數據對于社團結構的影響就越小。當到最后一級的相似節點對用完后得到的社團結構就是這個網絡最可能存在重疊度最大的穩定結構。

3 真實網絡的應用結果

本文選取4個真實網絡，如表3所示，美國跆拳道俱樂部（34節點），海豚社交網絡（62節點），美國足球比賽網絡（115節點），Hamsterster社會網絡（2 426節點），將算法應用到這個網絡中得到了一些結果。對于大多數的網絡只需要利用較少的相似度級數，就能找到EQ最大的社團結構，但是對于級數的增加可以找到網絡深層次的社團結構更多的重疊節點更大規模的子社團結構。

將本文的算法應用到Hamsterster社會網絡中得到了網絡的深度重疊結構。圖12a可以看出級數越大相似節點數越少，因為節點選擇相似節點形成節點對，在真實網絡中只有少部分節點的度較大，這少部分節點可以有多級選擇形成節點對，其他節點的選擇就會很少。同時當級數增加時，網絡的社團也在合并使得社團數目減少，但是只有前幾級節點對數據對于社團數目影響較大，后面就不改變社團的數目了，這也說明了只需要少部分相似節點對級數就可以讓網絡的社團結構達到穩定的深度重疊狀態。

從圖12b中容易看出Hamsterster社會網絡中級數增大社團的節點數目、重疊節點比例以及與該社團有重疊的社團比例同時增多，并且在十級相似度之后這3個都趨于一個穩定值。對于得到的深度重疊結構看到它重疊節點的比例達到了80%左右，社團中幾乎大部分節點都是與其他社團的重疊節點，對于真實網絡來說大部分的個體都會有多個選擇，這也導致了社團的重疊率比較大。

圖13是最大的一個社團隨著級數增加發現的子社團，其中圖13a給出了第2，3，4和5級相似節點對發現的子社團規模，圖13b為第2級子社團節點在前一級所屬的社團，亮點表示屬于這一社團，在第2級中發現了65個子社團，其中最大的子社團有20個節點同屬于上一級相同的社團，同一社團中的節點聯系密切，屬于同一社團的子社團具有更密切的關系。所以對于重疊網絡中的子社團發現具有一定的意義。

圖14展現了最大的一個社團和其他社團的重疊情況，其中圓圈里面的數字表示節點數的大小，這里只考慮與最大社團重疊的社團。當一個社團與最大社團有重疊時，它們之間就會有連邊，連邊的權重表示兩個社團重疊的節點數目。圖14a是第一級相似節點對最大社團的重疊情況，圖14b為最后一級相似節點對最大社團的重疊情況（忽略了重疊節點數小于十的社團）。比較第一級和最后一級明顯看到最大的社團重疊程度增大了很多，這也是網絡的深度重疊結構。

4 結論

本文從真實網絡形成社團的原因出發，假設社團的形成是節點選擇最相似節點的結果，并且具有更大相似度和度的節點對會優先形成社團，每一個節點可以對多個社團有選擇權力，發現了網絡中社團的重疊結構，合理地說明了重疊節點的物理意義。然后通過增加相似度級數，利用多級最相似度繼續優化社團，找出了網絡中的深度重疊結構和重疊社團的子社團結構，解釋了網絡是由節點對到小社團再到交疊社團的一個演變過程。本文的模型揭示了網絡的深度重疊結構，并發現了社團的子結構，對實際網絡結構有很好的解釋分析效果。

本文的模型對于無權無向網絡的重疊社團結構發現具有很好的效果，后續會嘗試對于有權重有方向的網絡進行重疊社團劃分，同時會嘗試擴大網絡的規模，加入對人工基準網絡［1113］的研究和分析。當然本文的模型給出了復雜網絡的深度重疊結構，提供了一種新的社團發現思路，對于社團中去尋找更小的子社團，屬于同一社團的節點會被更細致地進行劃分，這種方式可以讓我們更深入地了解社團結構。更深層次的網絡結構是接下來要進一步研究的內容。

參考文獻：

［1］PAWAN K， RAVINS D. Formalising and detecting community structures in real world complex networks［J］.Journal of Systems Science amp; Complexity，2021，34（1）：180205.

［2］李輝，陳福才，張建朋，等. 復雜網絡中的社團發現算法綜述［J］. 計算機應用研究，2021，38（6）：16111618.

LI H，CHEN F，ZHANG J， et al. Survey of community detection algorithms in complex network［J］. Application Research of Computers，2021，38（6）：16111618.

［3］CHENG F， WANG C， ZHANG X， et al. A local-neighborhood information based overlapping community detection algorithm for large-scale complex networks［J］. IEEE/ACM Transactions on Networking， 2021，29（2）： 543556.

［4］CHAKRABORTY S， MUHURI S， Das D. Detection of constant member and overlapping community from dynamic literary network［J］. Social Network Analysis and Mining，2021，11（1）：77.

［5］李永寧， 吳曄， 張倫. 動態社團發現研究綜述［J］. 復雜系統與復雜性科學， 2021， 18（2）： 18.

LI Y， WU Y， ZHANG L. A review of dynamic community detection［J］. Complex Systems and Complexity Science， 2021， 18（2）： 18.

［6］NEWMAN M， GIRVAN M. Finding and evaluating community structure in networks［J］.Physical Review E， 2004， 69（2）：026113.

［7］KATHY M， TOLGA C， AMBUJ K. RRW： repeated random walks on genome-scale protein networks for local cluster discovery［J］. BMC Bioinformatics， 2009， 10（1）： 283.

［8］LI J， WANG X， CUI Y. Uncovering the overlapping community structure of complex networks by maximal cliques［J］. Physica A： Statistical Mechanics and Its Applications， 2014， 415（1）： 398406.

［9］HAJIABADI M，ZARE H， Bobarshad H. IEDC： An integrated approach for overlapping and non-overlapping community detection［J］. Knowledge-Based Systems， 2017， 123（1）：188199.

［10］ NICOSIA V， MANGIONI G， CARCHIOLO V， et al. Extending the definition of modularity to directed graphs with overlapping communities［J］. Journal of Statistical Mechanics Theory amp; Experiment， 2009， 2009（3）：31663168.

［11］ LIU H， LI G. Overlapping community detection method based on network representation learning and density peaks［J］.IEEE Access， 2020， 8（99）：1.

［12］ SHI P， HE K， BINDEL D， et al. Locally-biased spectral approximation for community detection［J］. Knowledge-Based Systems， 2019， 164（1）：459472.

［13］ DEVI J C， POOVAMMAL E. An analysis of overlapping community detection algorithms in social networks［J］. Procedia Computer Science， 2016， 89：349358.

（責任編輯 李 進）