[發(fā)明專利]一種基于社區(qū)結(jié)構(gòu)的內(nèi)外比度量方法及社區(qū)發(fā)現(xiàn)方法

有效

• 申請?zhí)枺?/td>: 201510526277.2
• 申請日: 2015-08-25
• 公開（公告）號: CN105337759B
• 公開（公告）日: 2018-12-25
• 發(fā)明（設(shè)計）人: 張大方;李果;謝鯤;李彥彪;黃潭龍
• 申請（專利權(quán)）人: 湖南大學
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 長沙正奇專利事務所有限責任公司 43113
• 代理人: 馬強;王娟

1.一種基于社區(qū)結(jié)構(gòu)的內(nèi)外比度量方法，其特征在于，包括以下步驟：

1)輸入子網(wǎng)絡(luò)結(jié)構(gòu)G＝(V,E)，V和E分別為子網(wǎng)絡(luò)中的點和邊的集合；定義該子網(wǎng)絡(luò)結(jié)構(gòu)的內(nèi)點、內(nèi)邊、外點、外邊；其中，內(nèi)點數(shù)量>＝4；內(nèi)邊、外邊、外點的數(shù)量均大于0；內(nèi)點是子網(wǎng)絡(luò)結(jié)構(gòu)中的所有點；內(nèi)邊是子網(wǎng)絡(luò)結(jié)構(gòu)中的所有邊，內(nèi)邊的兩個端點都在子網(wǎng)絡(luò)結(jié)構(gòu)內(nèi)；外點是子網(wǎng)絡(luò)結(jié)構(gòu)中內(nèi)點的所有鄰節(jié)點；外邊是子網(wǎng)絡(luò)結(jié)構(gòu)的所有鄰邊，外邊僅有一個端點在子網(wǎng)絡(luò)結(jié)構(gòu)內(nèi)；

2)定義內(nèi)外比：內(nèi)比InnerRatio＝內(nèi)邊的數(shù)量/內(nèi)點的數(shù)量，外比OuterRatio＝外邊的數(shù)量/外點的數(shù)量，內(nèi)外比IOR＝內(nèi)比/外比；

3)根據(jù)內(nèi)外比判斷所述子網(wǎng)絡(luò)結(jié)構(gòu)是否為社區(qū)：如果內(nèi)外比IOR值大于1，即內(nèi)比大于外比，則判斷出該子網(wǎng)絡(luò)結(jié)構(gòu)是社區(qū)。

2.一種基于權(quán)利要求1所述度量方法的社區(qū)發(fā)現(xiàn)方法，其特征在于，包括以下步驟：

1)輸入整個網(wǎng)絡(luò)結(jié)構(gòu)N＝(V’,E’)，V’和E’分別為網(wǎng)絡(luò)中的點和邊的集合；

2)對于所述網(wǎng)絡(luò)結(jié)構(gòu)N＝(V’,E’)中的所有節(jié)點，使用鄰節(jié)點比較方法生成一組初始子網(wǎng)絡(luò)結(jié)構(gòu)；使用鄰節(jié)點比較方法生成一組初始子網(wǎng)絡(luò)結(jié)構(gòu)的具體過程包括：

a)計算網(wǎng)絡(luò)結(jié)構(gòu)N＝(V’,E’)中每個節(jié)點的鄰節(jié)點數(shù)量，把網(wǎng)絡(luò)結(jié)構(gòu)N＝(V’,E’)中的所有節(jié)點，按照其鄰節(jié)點數(shù)量從多到少進行倒序排列；

b)依次對每一個節(jié)點，都加入其鄰節(jié)點，組成一個子網(wǎng)絡(luò)結(jié)構(gòu)，即網(wǎng)絡(luò)中每一個節(jié)點都對應生成一個子網(wǎng)絡(luò)結(jié)構(gòu)，形成一組子網(wǎng)絡(luò)結(jié)構(gòu)；

c)步驟b)得到的子網(wǎng)絡(luò)結(jié)構(gòu)進行去重，再對每個子網(wǎng)絡(luò)結(jié)構(gòu)中的內(nèi)點，按鄰節(jié)點數(shù)量進行倒序排序；

3)對于步驟2)生成的第一個子網(wǎng)絡(luò)結(jié)構(gòu)G＝(V,E)，利用權(quán)利要求1所述方法計算該子網(wǎng)絡(luò)結(jié)構(gòu)的內(nèi)外比IOR值，如果所述內(nèi)外比IOR值<＝1，判斷出該子網(wǎng)絡(luò)結(jié)構(gòu)不是社區(qū)，記錄該子網(wǎng)絡(luò)結(jié)構(gòu)到已檢查子網(wǎng)絡(luò)結(jié)構(gòu)的集合中，檢測下一個子網(wǎng)絡(luò)結(jié)構(gòu)；

4)如果步驟3)中子網(wǎng)絡(luò)結(jié)構(gòu)G＝(V,E)的內(nèi)外比IOR值>1，判斷出該子網(wǎng)絡(luò)結(jié)構(gòu)是社區(qū)，先將該子網(wǎng)絡(luò)結(jié)構(gòu)記錄到已發(fā)現(xiàn)的社區(qū)集合中，再采用雙向迭代方法，一個方向是通過依次增加外點來構(gòu)成新的子網(wǎng)絡(luò)結(jié)構(gòu)，即對于該社區(qū)，如果有n個外點，則生成n個新的子網(wǎng)絡(luò)結(jié)構(gòu)，再進入步驟5)；另一個方向是依次減少內(nèi)點來生成新的子網(wǎng)絡(luò)結(jié)構(gòu)，即依次去掉每個內(nèi)點，如果該社區(qū)有m個內(nèi)點，則生成m個新的子網(wǎng)絡(luò)結(jié)構(gòu)，再進入步驟5)；

5)對于上述新的子網(wǎng)絡(luò)結(jié)構(gòu)，先去掉與已檢查子網(wǎng)絡(luò)結(jié)構(gòu)集合中重復的部分，再判斷是否有新的社區(qū)生成；

6)重復步驟4)和步驟5)，直到?jīng)]有新的子網(wǎng)絡(luò)結(jié)構(gòu)和社區(qū)產(chǎn)生；

7)對產(chǎn)生的所有社區(qū)按內(nèi)外比IOR值大小進行倒序排序，把內(nèi)部聯(lián)系緊密程度最高的社區(qū)排在最前面；IOR值越大，說明社區(qū)內(nèi)部的緊密程度越高。