節點間依賴度的社團結構劃分范文

本站小編為你精心準備了節點間依賴度的社團結構劃分參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《物理學報》2014年第十二期

1方法的描述

1.1主要思想在大量的實驗和觀察中發現,在劃分社團結構的過程中,一個節點的劃分往往依賴于和它有最多公共鄰居的鄰居節點,或者依賴于它的大多數鄰居節點的劃分.

1.2基本概念1)節點對節點的依賴度節點a對它的鄰居點b的依賴度Da,b定義為其中na,b表示節點a和節點b的共同鄰居的數目,ka表示節點a的度.稱節點a為起始節點,節點b為終止節點.2)節點對社團的依賴度節點a對社團C的依賴度Da,C定義為其中na,C表示社團C中節點a的鄰居的數目.3)依賴節點如果節點b是節點a的一個鄰居節點,并且節點a對節點b的依賴度不小于節點a對它的其他鄰居節點的依賴度,則稱節點b是節點a的一個依賴節點,稱a對b的依賴度為節點a的最大依賴度.4)節點對社團的條件依賴度節點a對社團C的條件依賴度Dam,C定義為5)社團的公共節點如果一個節點對幾個社團有著相同的依賴度和條件依賴度,那么稱這個節點是這幾個社團的公共節點.

1.3實現步驟以下結合對著名的Zachary空手道俱樂部人際關系網絡[29](圖3顯示了該網絡的原始狀態)的社團劃分過程來說明本文的社團劃分方法.1)去除復雜網絡中度為1的節點,并將它們鄰居的度減1,直到該復雜網絡中不再存在度為1的節點.在復雜網絡中劃分社團結構時,度為1的節點必然和它的惟一鄰居歸于同一社團,而它的存在對它的鄰居的歸屬沒有任何影響,因此,在劃分社團之前可先將這類節點去除.在空手道俱樂部網絡中,去掉度為1的節點12,并將節點1的度減1。2)計算復雜網絡中所有節點的最大依賴度,并在這些最大依賴度中找到最大值Dm.找到這個最大值Dm所對應的所有起始節點(這些節點須具有惟一的依賴節點),將它們分別和各自的依賴節點組成小的社團.這些依賴節點稱為社團的初始節點.表1給出了空手道俱樂部網絡中各節點的最大依賴度,在本步中Dm的值為1,表2顯示了這本步得到的2個社團.3)對于社團的初始節點或者未劃分到社團的節點s,如果s對現存的某個社團的依賴度大于0.5,則將節點s吸收進這個社團;如果節點s對它的鄰居的最大依賴度不小于上步中的Dm,且s對于某個社團的條件依賴度大于0.5,則將節點s吸收進這個社團.如果節點s是某個社團的初始節點,則將節點s所在社團中的所有節點吸收進這個社團中.表3顯示了經過本步驟得到的社團的結果,13和27兩個節點對兩個社團的依賴度分別大于0.5,被吸收進對應社團.4)重復步驟3),直到沒有節點被吸收進社團.此時,從未劃分到社團的節點和社團的初始節點的依賴度中找到最大值,將對應于該最大依賴度的具有惟一依賴節點的起始節點s吸收進社團(如果終止節點屬于這個社團),或者將節點s和終止節點組成一個小的社團(終止節點不在一個社團中).在對空手道俱樂部網絡的劃分中,本步驟的最大依賴度為0.917,對應于節點33對節點34的依賴度,將節點33吸收進社團2.5)重復步驟4),直到沒有節點被吸收進社團并且沒有新的社團成立.6)此時社團外的節點與它們的鄰居關系不夠緊密或者具有一定的歧義性.在空手道俱樂部網絡中,此時社團外的節點為6,7,10,17.計算社團外節點對現存社團的依賴度和條件依賴度,并從這些依賴度和條件依賴度中找到最大值,將對應的節點(這些節點須具有對應于該最大值的惟一的社團)吸收進相應的社團中.如果有節點滿足步驟3)的條件,則執行步驟3).直到沒有節點被吸收進社團為止.表4顯示了本步驟后空手道俱樂部社團的結果.7)對于現存的社團,如果社團規模過小(例如社團中節點數目少于網絡中節點總數目的5%),則將該社團中的節點依照上述步驟重新劃分入現存的滿足條件的其他社團.在對空手道俱樂部網絡的劃分過程中,沒有出現規模過小的社團.8)對于未劃分到社團的節點,根據步驟5)可知它們滿足公共節點的定義,屬于與它們相連的社團的公共節點.在空手道俱樂部網絡中,節點10作為社團1和社團2的公共節點而存在.重新計算所有節點對現存社團的依賴度和條件依賴度,確保所有節點對它所處的社團的依賴度大于對其他社團的依賴度,或者在依賴度相等的情況下有最大的條件依賴度,否則,將不滿足條件的節點以及受它歸屬影響的節點重新劃分到合適的社團.經過以上步驟,再將步驟1)中的度為1的節點劃歸它們鄰居所在的社團中,即可得到該復雜網絡的一種社團劃分.對空手道俱樂部網絡,度為1的節點12屬于社團1,其他節點的劃分與表4保持一致,節點10是兩個社團的公共節點.

1.4復雜度分析對于一個包含n個節點和m條邊的復雜網絡,本文算法在實現過程中,步驟1)所需的時間復雜度為O(n).步驟2)計算節點的最大依賴度所需的時間復雜度為O(mn),為便于步驟2)和步驟4)從大到小取用,將網絡中所有節點的最大依賴度排序,所需時間復雜度為O(nlog2n).將一個度為k的節點吸收進社團最多需要計算k次節點對社團的依賴度,每次計算的時間復雜度為O(k),故總的時間復雜度為O(k2),將所有節點吸收進社團的時間復雜度為O(nk2).網絡中節點的平均度為2m/n,而對于稀疏網絡,O(m)等價于O(n),故本文算法的時間復雜度為O(n2).

2實驗結果與分析

在對Zachary空手道俱樂部人際關系網絡的實驗中,本算法得到了和實際情況完全一致的兩個社團,如圖4所示.而由于節點10和兩個社團都分別有一條邊相連,符合關于社團公共節點的定義,將它劃分為這兩個社團的公共節點.Lusseau等在新西蘭對62只寬吻海豚的生活習性進行了長時間的觀察,他們研究發現這些海豚的交往呈現出特定的模式,并構造了包含有62個結點的社會網絡[30].如果某兩只海豚經常一起頻繁活動,那么網絡中相應的兩個結點之間就會有一條邊存在.本文算法將海豚社會網絡劃分為4個社團,如圖5所示,節點39為它所連接的兩個社團的公共節點.美國足球隊網絡(文獻[5]中的一個例子)中,每個節點代表了參加美國2000年橄欖球賽季的高校代表隊,連接兩個節點的邊表示對應的兩支球隊之間至少曾有過一場比賽.美國足球隊網絡包含了115個節點和614條邊.本文算法將該網絡劃分為7個社團,如圖6所示,紅色線條將網絡劃分為7個部分.在對空手道俱樂部網絡的劃分中,前文提到的譜平分法[10,11],GN算法[14],Tyler等在GN算法基礎上提出的新算法[31]等,都將節點3作為爭議節點劃分到了錯誤的社團中.表面上看,節點3和兩邊的社團都有同樣數目的邊相連,但是實際上,以節點1為中心的社團中節點3的鄰居間的聯系更為緊密,節點3對節點1的依賴度更高,故將節點3劃分到節點1的社團中.節點10和兩個社團分別有一條邊相連而被劃分為公共節點,本文所得的結果更加符合實際情況和社團結構的定義.在文獻[14]中提出了一種得到普遍認同的、對社團結構劃分質量的評價標準:模塊度Q值,Q值較大,表明該算法所做劃分較好.表5是本算法和其他一些算法對海豚社會網絡和美國足球隊網絡所做劃分的Q值的比較.從表5可以看出,本文算法在這些復雜網絡尤其是節點層次明顯的網絡的社團劃分上有相當不錯的表現。

3結論

本文提出了一種新的基于節點間依賴度的在復雜網絡中劃分社團結構的方法,定義了節點對它的鄰居的依賴度以及節點對社團的依賴度和條件依賴度.首先找到具有惟一依賴節點且最大依賴度不小于其它節點的節點,將它和它的依賴節點組成社團,然后對社團的依賴度和條件依賴度滿足要求的節點吸收進社團或者繼續組成新的社團,直到所有節點都被劃分到社團.算法的設計使得劃分得到的社團中,每個節點對它所在社團的依賴度都不會小于它對其他社團的依賴度,也就是說,任何節點都和它的盡可能多的鄰居劃分到同一個社團,和任何節點相連的邊都盡可能多的成為社團內部的邊,使得結果更符合社團結構的定義.通過對3個經典實際網絡的測試,本文算法都取得了不錯的結果,而算法的時間復雜度為O(n2),達到了較高的水準。

作者：王興元趙仲祥單位：大連理工大學電子信息與電氣工程學部