[發明專利]一種基于全局劃分和局部擴展的網絡重疊社團檢測方法

無效

• 申請號: 200810041958.X
• 申請日: 2008-08-21
• 公開（公告）號: CN101344940A
• 公開（公告）日: 2009-01-14
• 發明（設計）人: 魏芳
• 申請（專利權）人: 魏芳
• 主分類號: G06Q10/00
• 分類號: G06Q10/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬Web和數據庫技術領域，具體涉及一種基于全局劃分和局部擴展的網絡重疊社團結構檢測方法。

背景技術

許多網絡系統都表現了社團結構的特征，如社會網絡和生物群落等，簡要地說，社團是整個網絡中那些聯系相對緊密的結點的集合。近年來，社團結構識別技術引起了物理、應用數學和計算機科學等領域的廣泛關注。

已經提出的方法大都關注地是網絡的劃分，應用最小割邊劃分原則把網絡結構劃分成幾個不相交的子網絡。許多方法的檢測規則是網絡中的每個結點最多只能劃分到一個社團，基于這樣的規則，就無法找到有重疊結點的社團。這樣的劃分有時是不合理的，因為在現實生活中的很多情況下重疊結點是很有必要的，比如在社會網絡中，一個人因為代表不同的利益因而可以在不同的社團中充當不同的角色，如果我們要對社會網絡進行劃分，這個人在不同的社團中都應該存在。所以針對這種情形，應該提出新的方法來進行社團發現。

發明內容

本發明的目的在于提出了一種基于全局劃分和局部擴展的網絡重疊社團結構檢測方法，該方法引入了用種子結點來發現社團且允許不同的社團內有重復的結點。

一種基于全局劃分和局部擴展的網絡重疊社團檢測方法DOCS，它是這樣實現的：

該方法引入了用種子結點來發現社團且允許不同的社團內有重復的結點，

具體步驟為：

第一步，我們應用譜劃分方法生成種子集合，并用這些種子來產生重疊社團結構，這個經典方法從網路結構的全局角度和社團結構的全局屬性來產生最優種子；

第二步，根據產生的種子，從局部最優角度對社團進行擴展。我們利用模塊函數Q來衡量社團每一步要擴展的結點，對每一個掃描到的結點，我們計算此結點加入后對模塊Q的貢獻和模塊間的重疊率，比較這兩個衡量標準，我們給出一個定理來決定要加入和刪除的結點；

第三步是社團擴展終止條件。當掃描的結點的規范化概率低于特定閾值時或社團間的重疊率超過用戶的容許值時算法停止。

本發明利用全局信息來尋找種子結點，并從局部最優角度用隨機行進方法來進行社團擴展，在隨機行進中我們并不考慮當前要擴展的結點是否已經屬于其它社團，所以我們得到的不同社團中允許有重復的結點，這樣就可以預防重要信息的丟失。

附圖說明

圖1為描述一個新的結點被加入到候選社團的過程。

具體實施方式

1.與本發明有關的一些概念和定義。

【1】網絡模型：

本發明中，網絡可以建模成圖G＝(V，E)，其中V是圖中結點集合，E是圖中邊的集合。我們用A＝(A_ij)_n×n來表示網絡關聯矩陣，其中

我們用D＝(D_ij)_n×n來表示對角矩陣，其中D_ij＝∑_k?A_ik，如果i＝j，其它情況下D_ij＝0。

矩陣A和D是基礎矩陣，其它矩陣如拉普拉斯矩陣L和轉換矩陣P都可由這兩個矩陣得到，其中L＝D-A，P＝D^-1?A。

【2】邊緣邊(割)：

一個社團S的邊緣邊B(S)是這樣的邊，其中邊的一個端點在S中，另一個端點在其它社團中，形式化定義如下：

B(S)={{u,v}|{u,v}∈E,u∈S,v∉S},]]>

且|B(S)|表示社團S的割的大小。

【3】模塊度：

如果網絡被劃分成P_k，其中k是劃分的社團的個數，則模塊度函數Q形式化定義如下：