用於粗化圖的系統和方法

2023-04-23 02:44:41

專利名稱：用於粗化圖的系統和方法
技術領域：
本發明涉及圖的粗化。更具體地說，本發明涉及對圖進行粗化以 便能夠快速、準確地發現社區的系統和方法。
背景技術：
在現實世界中，諸如社會網絡(如銀行、金融服務、保險、保健 行業的網絡)、生命科學網絡(如蛋白質交互反應網絡)、計算機網 絡(如全球資訊網、網際網路)等的許多數據都可以被模擬為圖。而且，這 些圖中大多數都顯示出了社區結構(即， 一組頂點)，其中在同一組 頂點中彼此之間的連接較為稠密，而不同組頂點之間的連接則較為稀 疏。通過發現這些社區而理解和分析各種網絡是非常有用的。例如， 就社會網絡來說，大部分網絡是龐大而又未知的，依靠人的認知能力 是難以掌握這樣的網絡中的群體信息，如電信公司保留的個人通信記 錄可以構成一個通訊網絡。通過社區檢測，我們可以通過計算機預測 出實際的功能群體。這些功能群體可以用來分析群體的特點和它們之 間的聯繫，為其制定特殊的銷售、廣告、經營等方面的策略。數據挖 掘的意義就是為了分析和預測。以下，為了更好地理解網絡和社區的關係，我們給出一個關於計 算機網絡的實例。對於一個包含多個網頁的網絡而言，每個網頁可被 看作一個頂點，各個網頁之間的超連結可被看作邊，而通過對網絡中 的網頁進行合理的分區，則可以找到該網絡中的權威社團。網絡的權 威社團表示的是網絡中內容相同或相近的網頁的集合，它可以用來幫 助用戶去瀏覽和搜索其所需要的信息，使這個過程更加的高效便捷.隨著信息技術的快速發展，許多研究人員開發了從網絡中發現各種社區的不同解決方案。2004年提出的Modularity Q方法被視為評估社區結構屬性的重要手段。有關Modularity Q方法的詳細信息，可 參見M. E. J. Newman and M. Girvan， Finding and Evaluating Community Structure in Network, Physical Review E series, 2004。 同 時，Newman等採用Modularity Q方法來評估由各種中間狀態的方法 發現的社區質量。但這種方法是費時的並且限於處理10000個頂點以 下的社區。Modularity Q方法中的啟發式算法(例如，貪心算法)分 區質量較低，難以找到全局最優解，因此並不總是能對各種圖進行良 好的分區。此後，又有一些新的基於鐠的方法被提出(例如，參見S.White and P. Smyth, A Spectral Clustering Approach To Finding communities in Graphs. Proceedings of the SIAM International Conference on Data Mining, Newport Beach, 2005以及M. E. J.Newman, Modularity and Community Structure in Networks, PNAS. 0601602103,2006),以便提升檢測到的社區的質量。但是，在這些新 的方法中，大型矩陣計算以及降階近似非常耗費時間和空間。儘管它 們相比於Modularity Q方法更為有效，但是仍然不能解決在大圖情況 下存在的瓶頸問題。由此可見，面對數據大小不斷增長的當前趨勢，不可避免地需要 設計一種能夠高質量、快速地發現社區的可縮放系統和方法.發明內容考慮到現有技術存在的上述問題，本發明提出了一種可縮放的系 統和方法，其使用多層框架(multilevel paradigm)來快速和準確地 粗化圖(graph)，所述粗化的圖能夠容易地被細化為高質量社區。根據本發明的第一方面，提供一種用於對圖進行粗化的方法，所 述圖包括多個頂點，所述方法包括a)對一個當前頂點計算所述當前 頂點與其各鄰接頂點間的合併模塊性增益值；b)計算所述當前頂點與其各鄰接頂點間的相似性值；c)基於計算的合併模塊性增益值和相 似性值，確定所述當前頂點是否可與其鄰接頂點合併，並且在確定可合併時進行合併.根據本發明的笫二方面，提供一種用於對圖進行粗化的系統，所述圖包括多個頂點，所述系統包括初始粗化裝置，用於對一個當前 頂點計算所述當前頂點與其各鄰接頂點間的合併模塊性增益值；偏差調整裝置，計算所述當前頂點與其各鄰接頂點間的相似性值；其中所 述系統基於計算的合併模塊性增益值和相似性值，確定所述當前頂點 是否可與其鄰接頂點合併，並且在確定可合併時進行合併。在本發明中，通過將模塊性引入多層框架，首先基於模塊性逐步 粗化圖，然後使用相似性手段，避免在不同社區的邊界線上的頂點的 粗化，因而能夠根據模塊性值和相似性值來快速和準確地粗化圖，並 隨後在細化過程期間逐級細化頂點的群集。


圖1A和1B圖解說明了使用本發明進行網絡社區檢測的實例。圖2是根據本發明的多層框架理念的示意圖。圖3是根據本發明的系統的框圖。圖4是根據本發明的方法的流程圖。圖5是根據本發明的優選實施方式的方法的流程圖。圖6A-6F是對圖5中方法的各步驟的圖解說明。圖7是根據本發明的系統和方法與現有各種方法在性能評估方面進行對別的柱狀圖。圖8是根據本發明的系統和方法與現有各種方法在模塊性值方面進行對比的圖表。
具體實施方式
在描述本發明的優選實施方式之前，首先參照圖1A和1B描述 使用本發明進行網絡社區檢測(即，對圖進行粗化)的實例。圖1A和1B示出了一個社會網絡的情況。圖1A表示美國大學生 橄欖球比賽2000年秋季常規賽季的比賽分布，其中每個頂點表示一支球隊，兩個球隊之間的邊(即，連接)表示由該邊連接的兩個球隊之間有比賽。圖IB表示通過使用本發明在網絡中發現社區而將網絡劃 分成不同社區的結果.由劃分結果可以看出，與不同社區的成員之間 的比賽量相比，相同社區的成員之間的比賽更為頻繁。就這個實例來 說，社區檢測的意義在於，可以通過賽程表的信息預測到球隊的分區 情況。對於圖1A的網絡，本發明藉助多層框架，通過使用網絡(即， 圖)的模塊性和相似性，對其進行快速、準確的粗化，得到圖1B的 粗化結果。隨後，該圖1B能夠被細化為高質量的社區。圖2圖解說 明了有關多層框架的理念。圖2中左側的橢圓形範圍表示了對圖進行粗化的過程。在圖2中， Go表示原始圖，GrG4分別表示粗化過程中的各層中間圖結果。在該 粗化過程中，逐層地粗化的圖，使圖中的頂點數不斷降低，直到不能 再通過合併任何頂點或簇來增加模塊性增益為止(例如如圖2所示， 達到用G4表示的圖)。應當理解，儘管圖2的粗化過程示出了一個5 層的框架，但是本發明可以根據需要實現具有任意層數的框架。圖2中右側橢圓形範圍表示了通過使用粗化過程中得到的各層中 間圖對粗化的圖進行細化的過程。在細化過程中，有多種經典優化方 法可以改善初始分割的結果，可參見B.W. KernighanandS.Lin, An efficient heuristic procedure for partitioning graphs.醜e// 5^s. 7Vc/t. / ， 49(2):291-308， 1970.以及C. M. Fiduccia and R. M. Mattheyses， A linear-time heuristic for improving network partitions. In 25 "arspages 241-247, New York, NY， USA, 1988. ACM Press。由於對圖進行 細化並非本發明所關心的問題，因此這裡不再進一步詳細說明。接下來，參照圖3描述根據本發明的用於對圖進行粗化的系統 300的示意圖。如圖3所示，該系統300包括初始粗化裝置310和偏 差調整裝置320。在將一個待粗化的圖(即，當前圖)輸入該系統300 時，可以例如通過初始粗化裝置310為圖中的每個頂點分配一個隨機序，以便按照該隨機序訪問圖中的頂點.所述初始粗化裝置310用於 在訪問圖中的一個頂點(即，當前頂點)時，計算該當前頂點與其各 鄰接頂點(即，與該當前頂點具有邊的頂點)之間的合併模塊性增益 值。所述偏差調整裝置320用於計算該當前頂點與其各鄰接頂點之間 的相似性值。所述系統300基於所述合併模塊性增益值和相似性值這 二者來決定是否可將當前頂點與其鄰接頂點之一合併，並且在確定可 合併時進行合併，以實現圖的粗化。系統300是一個遞歸系統，這主要體現在兩個方面。第一，對於 所述當前圖(例如，圖2中的原始圖G。)，系統300會按隨機序訪問 圖中的每個頂點，對每個頂點重複執行上述操作。在已經訪問了當前 圖中的所有頂點後，得到當前一層粗化的中間圖結果(例如，圖2中 的中間圖Gj 。第二，每得到一層粗化的中間圖結果(例如，圖2中 的中間圖Gp G2、 G3)，系統300會對該粗化的圖繼續進行粗化，直 到不能再增加圖的模塊性增益為止(例如，達到圖2中的中間圖G4). 通過使用系統300對圖進行粗化後，可將所述粗化的圖快速、高質量 地還原為原始圖。在以上的描述中，使用了術語"頂點"。應當指出，在原始圖中， 一個"頂點，，只包含該頂點本身；但是在經過粗化的中間圖中， 一個頂 點可能已經包含原始圖上的一個或多個頂點了，並且粗化圖中的邊也 有可能是若干條原始圖中的邊組成的，因此在粗化的圖中的頂點也可 稱為"簇"。根據本發明的一種優選實施方式，通過使用Modularity Q (模塊 性值)公式來計算圖或者子圖內的合併模塊性增益值和相似性值。 Modularity Q公式是用於計算網絡中的社區強度的函數，其是衡量社 區強度(即，社區性好、壞)的指標。但是，應當理解，本發明的實 施並不依賴於使用Modularity Q公式，任何能夠計算網絡中社區強 度、進而得到網絡中各頂點的合併模塊性增益值和相似性值的算法均 適用於本發明。圖4示出了根據本發明的方法的流程圖。圖4的方法從步驟400開始，隨後進入步驟410，計算當前頂點與其各鄰接頂點之間的合併 模塊性增益值。隨後，在步驟420中，進一步計算該當前頂點與其各 鄰接頂點之間的相似性值.接下來，在步驟430中，基於所述合併模 塊性增益值和相似性值這二者來決定是否可將當前頂點與其鄰接頂點 之一合併，並且在確定可合併時進行合併，以實現圖的粗化。該方法 在步驟440中結束。以下將結合圖5和圖6A到6F對根據本發明的方法的優選實施 方式進行詳細說明，其中圖5是才艮據本發明的方法的優選實施方式， 圖6A到6F以直觀方式對圖5中的步驟進行了圖解說明。圖5中的方法以步驟500開始，隨後進入步驟505。在步驟505 中，為圖中的每個頂點生成一個隨機序visit[i(其中i=l，…，n， n 表示當前圖中頂點的總個數)。圖6A是對圖5的步驟505的直觀表 示，在圖6A中示出一個具有8個頂點的圖(假定圖6A所示的圖為原 始圖)。在該圖中分別為每個頂點分配一個隨機序1-8。本領域技術 人員能夠理解，為了便於說明，圖6中只示出了具有8個頂點的圖， 但是該圖可以根據需要具有任意所需數量的頂點。圖5的方法隨後進入步驟510，以判斷是否已訪問了圖中的所有 頂點。如果步驟510的判斷結果為"是"，則該方法進入步驟550，如 下所述。如果步驟510的判斷結果為"否"，則該方法進入步驟515， 以計算隨機序為visit[i的頂點與其各鄰接頂點之間的合併模塊性增益 值，然後選擇最大的合併模塊性增益值並找出其對應的頂點v。這一 步驟在圖6B中進行了圖解說明。在圖6B中，假定首先訪問隨機序為 1的頂點(即，頂點1),於是對頂點1計算與其鄰接的頂點5、 7、 8 的合併模塊性增益值。根據本發明的一種優選實施方式，基於模塊性值(Modularity Q ) 公式計算所述合併模塊性增益值。模塊性值公式(簡稱"Q值公式") 是一個計算圖或者子圖內部的模塊性值的基本函數，如下面的公式(1) 所示。formula see original document page 11(i)在該公式中，Q:頂點visit[i與其鄰接頂點的模塊性。 Aij:圖對應的鄰接矩陣。 C(i):頂點i所在的分區。d(i):頂點i的度(即，與頂點i相連接的邊的數量)Dc:分區c中所有頂點的度的和。Ec:分區c中邊的數量ex/hew:當頂點i和j所屬的分區相同時為1;否則為o。基於上述Q值公式，我們可以進一步求解頂點合併過程後會產 生的模塊性增益。根據本發明的一種優選實施方式，通過使用如下公 式(2)來計算。<在上述公式中，QA:頂點visitil (在本例中為頂點1)的Q值； QB:鄰接頂點(在本例中為頂點5、 7或8)的Q值； Qc:將頂點visit[i!與鄰接頂點合併後的頂點的Q值； AQc:頂點visiti與其鄰接頂點間的合併模塊性增益值。 例如，對於頂點l，在使用公式AQc-Qc-QA-QB計算其與鄰 接頂點5的模塊性增益時，C代表由頂點l和頂點5構成的圖，A代 表由頂點l構成的圖，B代表由頂點5構成的圖。這樣算出來的AQc 值就是頂點l和5之間的合併模塊性增益值。可以採用相同的方式計 算頂點1與頂點7以及與頂點8之間的合併模塊性增益值。如圖6B所示，頂點1與頂點5之間的合併模塊性增益值為0.052， 與頂點7之間的合併模塊性增益值為0.038,與頂點8之間的合併模塊 性增益值為0.031，其中合併模塊性增益值最大的獲益值頂點為頂點5。 接下來，該方法進入步驟520，以判斷頂點1最大的合併模塊性 增益值是否大於0。如果判斷結果為"是"，則方法進入步驟530，否則， 方法進入步驟525，以將該頂點l標記為已訪問的。如圖6B所示，頂點1的所有合併模塊性增益值均大於0，因此 方法進入步驟530，以為頂點l計算其與鄰接頂點(頂點5、 7、 8)的 相似性值，以便選擇並找出對應的相似性值最大的頂點u。根據本發明的一種優選實施方式，仍然通過使用如上公式(2) 來計算相似性值，只是其中Qa、 Qb、 Qc和AQc被賦予與在計算模塊 性增益值時不同的含義。例如對於當前頂點是l的情況，1的鄰接頂點有5、 7、 8,這時 要使用AQC= Qc - QA- QB計算頂點5與頂點1的其他鄰接頂點的相 似性，其中C代表由頂點1、 5、 7、 8構成的圖，A代表由頂點l、 7、 8構成的圖，B代表由頂點5構成的圖。這樣算出來的AQc值就是頂 點1和5之間的相似性值。同理可以計算頂點1和7以及頂點1和8 之間的相似性值。圖6C示出了針對頂點1計算出的各相似性值，其中頂點1與頂 點5、 7、 8的相似性值分別為-0.095、 -0.028、 -0.038，相似性值最大 的頂點是頂點7。接下來，在步驟535中判斷頂點u是否等於頂點v，即合併模塊 性增益值最大的頂點與相似性值最大的頂點是否是同一個頂點。如果"是"，則方法進入步驟540，以合併該兩個頂點u和v，並 將其標記為已訪問，隨後進入步驟545。但是，由圖6B和6C所示的 情形可知，對於頂點l而言，合併模塊性增益值最大的頂點與相似性 值最大的頂點不是同一個頂點，因此步驟535的判斷為"否"，於是方 法直接轉到步驟545。在步驟545中，更新已訪問的頂點的鄰接列表 (例如，調整頂點l的隨機序，以使其隨機序晚於圖中所有其他頂點 的隨機序)，並返回步驟510以判斷圖中是否還存在沒有訪問到的頂 點。通過步驟510中的判斷，接下來對隨機序為2的頂點(即，頂點 2)進行訪問。對頂點2重複執行步驟515至步驟535的操作。其中， 在步驟515計算得到其與鄰接頂點3、 5、 8的合併模塊性增益值分別 為0.063、 0.052、 0.031，其中頂點3的合併模塊性增益值最大(如圖 6D所示)；在步驟530中計算其與鄰接頂點的相似性值，其與鄰接頂 點的相似性值分別為0.028、 0.010和-0.087，其中頂點3的相似性值 也最大(如圖6E所示)。因此，對於頂點2而言，步驟535的判斷 結果應為"是"。於是，圖5的方法進入步驟540，將頂點2和3合併， 同時將這兩個頂點都標記為已訪問的。如圖6E所示，頂點2和3被 合併為一個新的頂點2，。接下來，該方法進入步驟545，以通過在相應的鄰接鍊表中修改鄰接的信息，更新已訪問頂點的鄰接列表.本領 域技術人員理解，更新已訪問頂點的鄰接列表在本領域中是已知的， 因此不再對其進行詳細描述.隨後，本發明的方法再次返回步驟510，以判斷是否已經訪問了 圖中的所有列表。如果尚未訪問圖中的所有列表(步驟510的判斷結 果為"否")，則繼續針對下一個頂點執行上述操作。如此迭代地執行 操作，直到已經訪問了圖中的所有頂點(即，步驟510的判斷結果為 "是，，)為止。在已經訪問了所有頂點的情況下，圖5的方法進入步驟550，以 便計算經過這一輪粗化後得到的當前一層中間圖中的頂點個數m。然 後，在步驟555中，將所述個數m與在上一輪粗化循環後得到的上一 層中間圖中的頂點個數(也就是這一輪粗化開始時的頂點個數)n進 行比較，以確定它們是否相等。在步驟555的判斷結果為"是，，的情況 下，表明粗化過程中前、後兩層中間圖中的頂點個數相同(即，已經 不能進行進一步的粗化)，本發明的方法進入步驟560，以輸出粗化 過程中的所有各層中間圖Gi](即，輸出一個粗化的圖集，例如圖2 中的G!-G4)。在步驟555的判斷結果為"否"的情況下(即，粗化的圖可以進一 步粗化)，則方法返回執行步驟510,該當前一層粗化的圖被遞歸地 送回初始粗化裝置310，繼續給每個粗化圖上的頂點隨機排序，並重 復執行前述初始粗化以及偏差調整等操作。對於圖6的例子，由於是對原始圖進行粗化，得到的粗化的圖為 第一層中間圖，因此在步驟555中是將該第一層中間圖中的頂點個數 m與原始圖中的頂點個數n (n=8)進行比較。在圖6的例子中，m必 然小於8 (因為至少已經將頂點2和3合併為頂點2，)，因此可以對 得到的第 一層粗化中間圖進行進一步的粗化。隨後，根據本發明的方法在步驟565中結束。在本發明中，基於頂點的模塊性和相似性來粗化圖。在所提出的 方法中，首先找出在隨機選擇的頂點周圍的具有最大合併模塊性的鄰接頂點(即，以隨機順序訪問圖中的每個頂點，並將其與模塊性增益 本地最大的鄰接簇或頂點合併)，然後調整隨機序以使用相似性合併 頂點(即，使用頂點的相似性手段調整有可能在社區邊界在線的那些 頂點的序)。這可以避免由隨機訪問序引起的低質量。通過遞歸粗化， 直到不能通過合併任何簇或頂點來增加模塊性增益時輸出粗化的圖 集。這樣粗化的圖可被隨後進一步細化為高質量社區。與目前存在的一些社區發現算法相比，本發明能夠處理頂點數量、邊數量較多的網絡，並快速、準確地發現網絡中的社區。圖7示 出了本發明的系統和方法與現有技術算法在性能評估方面進行對比的 柱狀圖。在圖7中，上部的表列出了本發明採用的實際資料庫的名稱、 該資料庫包括的節點數和邊數，以及該資料庫所屬的應用領域。圖7 中間部分給出了進行對比的各種算法的圖例說明，各種算法從左到右 依次對應於它們在柱狀圖中的排列順序。圖7下部的柱狀圖的水平方 向表示採用的各種資料庫，垂直方向表示各種算法的對數運行時間。應當指出，在圖7中，對於SDM2005(Spec-l)算法、SDM 2005 (Spec-2)算法以及PR. E 2004算法，由於本發明沒有得到其針對蛋白 質交互反應網絡資料庫、KDD論文引用資料庫、全球資訊網資料庫以及因 特網電影資料庫的相應程序數據，因此未能計算其在上述這些資料庫 中的運行時間，這種情況用"無數據，，表示。另外，PNAS 2006 (Power Method)算法和PNAS 2006 (ClaPack)算法已經無法處理KDD論文引 用資料庫、全球資訊網資料庫以及網際網路電影資料庫這樣量級的資料庫， 這種情況用"N/A"表示。因此，從圖7中可以看出，根據本發明的解決方案能夠快速處理 包含大量節點的網絡。圖8示出了根據本發明的解決方案與現有各種算法在模塊性值 (Q值)方面進行對比的圖表。從圖8可以看出，本發明的解決方案 的模塊性值高於目前存在的其他算法，也就是說，本發明在社區發現 的準確度方面優於目前存在的其他算法。本領域技術人員會認識到，可以以方法、系統或電腦程式產品的形式提供本發明的實施例.因此，本發明可採取全硬體實施例、全 軟體實施例，或者組合軟體和硬體的實施例的形式。硬體和軟體的典 型的結合可以是帶有電腦程式的通用計算機系統，當程序被加栽並 被執行時，控制計算機系統，從而可以執行上述的方法。本發明可以嵌入在電腦程式產品中，它包括使此處描述的方法 得以實施的所有特徵。所述電腦程式產品被包含在一個或多個計算機可讀存儲介質(包括，但不限於，磁碟存儲器、CD-ROM、光學存 儲器等)中，所述計算機可讀存儲介質具有包含於其中的計算機可讀 程序代碼。已參考根據本發明的方法、系統及電腦程式產品的流程圖和/ 或方框圖說明了本發明。流程圖和/或方框圖中的每個方框，以及流程 圖和/或方框圖中的方框的組合顯然可由電腦程式指令實現。這些計 算機程序指令可被提供給通用計算機、專用計算機、嵌入式處理器或 者其他可編程的數據處理設備的處理器，以產生一臺機器，從而指令 (所述指令通過計算機或者其他可編程數據處理設備的處理器)產生 用於實現在流程圖和/或方框圖的一個或多個方框中規定的功能的裝 置。這些電腦程式指令也可保存在一個或多個計算機的讀存儲器 中，每個這種存儲器能夠指揮計算機或者其他可編程數據處理設備按 照特定的方式發揮作用，從而保存在計算機可讀存儲器中的指令產生 一種製造產品，所述製造產品包括實現在流程圖和/或方框圖的 一個或 多個方框中規定的功能的指令裝置。電腦程式指令也可被加栽到一個或多個計算機或者其他可編 程數據處理設備上，使得在所述計算機或者其他可編程數據處理設備 上執行一系列的操作步驟，從而在每個這樣的設備上產生計算機實現 的過程，以致在該設備上執行的指令提供用於實現在流程圖和/或方框 圖的一個或多個方框中規定的步驟。以上結合本發明的優選實施方式對本發明的原理進行了說明，但 這些說明只是示例性的，不應理解為對本發明的任何限制。本領域技術人員可以對本發明進行各種改變和變形，而不會背離由隨附權利要 求所限定的本發明的精神和範圍，
權利要求
1.一種用於對圖進行粗化的方法，所述圖包括多個頂點，所述方法包括a)對一個當前頂點計算所述當前頂點與其各鄰接頂點間的合併模塊性增益值；b)計算所述當前頂點與其各鄰接頂點間的相似性值；c)基於計算的合併模塊性增益值和相似性值，確定所述當前頂點是否可與其鄰接頂點合併，並且在確定可合併時進行合併。
2. 根據權利要求l所述的方法，還包括d) 更新已訪問頂點的鄰接列表。
3. 根據權利要求2所述的方法，還包括對圖中的每個頂點迭 代地執行上述步驟a) -d)，直到已經訪問了圖中的所有頂點，得到 當前一層粗化的圖。
4. 根據權利要求3所述的方法，還包括在執行步驟a)之前執 行為每個頂點分配一個隨機序的步驟，並且每得到一層粗化的圖，均 為該層粗化的圖中的每個頂點分配隨機序。
5. 根據權利要求4所述的方法，還包括在當前一層粗化的圖中的頂點個數小於上一層粗化的圖中的頂 點個數時，繼續執行下一層粗化。
6. 根據權利要求4所述的方法，還包括在當前一層粗化的圖中的頂點個數等於上一層粗化的圖中的頂 點個數時，輸出各層粗化的圖的圖集。
7. 根據權利要求l所述的方法，其中基於模塊性值公式計算所 述合併模塊性增益值和相似性值。
8. 根據權利要求7所述的方法，其中步驟a)還包括 通過如下方式計算所述當前頂點與所述其中一個鄰接頂點的合併模塊性增益值AQc:計算由所述當前頂點和所述其中一個鄰接頂點 構成的圖的模塊性值Qc、由所述當前頂點構成的圖的模塊性值QA以及由所迷其中一個鄰接頂點構成的圖的模塊性值QB，並計算AQC-Qc-Qa-Qb，以及在對所述當前頂點的每個鄰接頂點計算了所述合併模塊性增益 值後，確定在各鄰接頂點中所述合併模塊性增益值最大的頂點。
9. 根據前述任一權利要求所述的方法，其中步驟c)還包括通 過獲得合併模塊性增益值最大的鄰接頂點和相似性值最大的鄰接頂 點，來確定所述當前頂點是否可與其鄰接頂點合併。
10. 根據權利要求9所述的方法，其中步驟c)還包括 確定所述合併模塊性增益值最大的鄰接頂點和所述相似性值最大的鄰接頂點是否為同一個鄰接頂點；如果是，則確定所述當前頂點可與所述合併模塊性增益值和相似 性值均為最大的鄰接頂點合併；否則，改變所述當前頂點的隨機序。
11. 根據權利要求8或9所述的方法，其中僅在所述當前頂點有 大於0的合併模塊性增益值的情況下，才執行計算相似性值的步驟。
12. —種用於對圖進行粗化的系統，所述圖包括多個頂點，所述 系統包括初始粗化裝置，用於按照隨機序，對當前頂點計算所述當前頂點 與其各鄰接頂點間的模塊性增益值；偏差調整裝置，計算所述當前頂點與其各鄰接頂點間的相似性值；其中所述系統基於計算的模塊性增益值和相似性值，確定所述當 前頂點是否可與其鄰接頂點合併，並且在確定可合併時進行合併。
13. 根據權利要求12所述的系統，還包括 更新已訪問頂點的鄰接列表的裝置。
14. 根據權利要求12所述的系統，所述初始粗化裝置還包括 為每個頂點分配一個隨機序的裝置。
15. 根據權利要求12所述的系統，其中在當前一層粗化的圖中 的頂點個數小於上一層粗化的圖中的頂點個數時，繼續下一層粗化。
16. 根據權利要求12所述的系統，其中在當前一層粗化的圖中 的頂點個數等於上一層粗化的圖中的頂點個數時，輸出各層粗化的圖 的圖集。
17. 根據權利要求12所述的系統，其中基於模塊性值公式計算 所述合併模塊性增益值和相似性值。
18. 根據權利要求12所述的系統，其中所述初始粗化裝置還包 括裝置，用於通過如下方式計算所述當前頂點與所述其中 一個鄰接頂 點的合併模塊性增益值AQc:計算由所述當前頂點和所述其中一個鄰 接頂點構成的圖的模塊性值Qc、由所述當前頂點構成的圖的模塊性值 QA以及由所述其中一個鄰接頂點構成的圖的模塊性值QB，並用於計 算AQc = Qc-QA-QB,以及用於在對所述當前頂點的每個鄰接頂點計算了所述合併模塊性 增益值後，確定在各鄰接頂點中所述合併模塊性增益值最大的頂點的 裝置。
19. 根據前述任一權利要求所述的系統，其中還包括 通過獲得合併模塊性增益值最大的鄰接頂點和相似性值最大的鄰接頂點，來確定所述當前頂點是否可與其鄰接頂點合併的裝置。
20. 根據權利要求19所述的系統，其中還包括 確定合併模塊性增益值最大的鄰接頂點和相似性值最大的鄰接頂點是否為同 一個鄰接頂點的裝置；響應於確定合併模塊性增益值最大的鄰接頂點和相似性值最大 的鄰接頂點是否為同 一個鄰接頂點，進一步確定所述當前頂點可與所 述合併模塊性增益值和相似性值均為最大的鄰接頂點合併的裝置。
全文摘要
本發明公開了一種用於對圖進行粗化的系統和方法，所述圖包括多個頂點，所述方法包括a)對一個當前頂點計算所述當前頂點與其各鄰接頂點間的合併模塊性增益值；b)計算所述當前頂點與其各鄰接頂點間的相似性值；c)基於計算的合併模塊性增益值和相似性值，確定所述當前頂點是否可與其鄰接頂點合併，並且在確定可合併時進行合併。通過使用本發明，能夠快速、準確地對圖進行粗化。
文檔編號G06Q10/00GK101324937SQ20071011010
公開日2008年12月17日 申請日期2007年6月15日 優先權日2007年6月15日
發明者朱哲敏, 越 潘, 晨 王, 力 馬 申請人:國際商業機器公司