[發(fā)明專利]一種基于社區(qū)結(jié)構(gòu)的子圖匹配方法及裝置

有效

• 申請?zhí)枺?/td>: 201810836811.3
• 申請日: 2018-07-26
• 公開（公告）號: CN109063089B
• 公開（公告）日: 2021-04-23
• 發(fā)明（設(shè)計）人: 王朝坤;樓昀愷
• 申請（專利權(quán)）人: 清華大學(xué)
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 北京中強智尚知識產(chǎn)權(quán)代理有限公司 11448
• 代理人: 黃耀威

1.一種應(yīng)用于社交網(wǎng)絡(luò)基于社區(qū)結(jié)構(gòu)的子圖匹配方法，其特征在于，包括：

導(dǎo)入包含代表三個互相認識的人的目標模式的文件，基于所導(dǎo)入的文件，分析目標模式的結(jié)構(gòu)，找出目標模式中互相匹配等價的子圖；

根據(jù)社交網(wǎng)絡(luò)的數(shù)據(jù)生成以社區(qū)作為結(jié)點的超圖，計算每個社區(qū)中各結(jié)點與本社區(qū)的各鄰接社區(qū)間的邊數(shù)；

在所述社交網(wǎng)絡(luò)中各社區(qū)內(nèi)部，利用預(yù)設(shè)子圖匹配算法，分別找出各社區(qū)內(nèi)所有互相認識的三個人構(gòu)成的子圖，獲得社區(qū)內(nèi)子圖匹配結(jié)果；

在所述社交網(wǎng)絡(luò)中所有社區(qū)之間，利用預(yù)設(shè)子圖匹配算法，在所述超圖上對目標模式進行結(jié)點可重復(fù)的子圖匹配，將得到的分配方案存儲在預(yù)設(shè)表中，當所述預(yù)設(shè)表內(nèi)的元素數(shù)量大于預(yù)設(shè)閾值時，對于所述預(yù)設(shè)表中的每個分配方案s基于所計算的每個社區(qū)中各結(jié)點與本社區(qū)的各鄰接社區(qū)間的邊數(shù)和所找出的目標模式中互相匹配等價的子圖進行處理，判斷s中被分配到所述社交網(wǎng)絡(luò)中各社區(qū)的目標模式的結(jié)點數(shù)量是否大于該社區(qū)中的結(jié)點數(shù)量，判斷s是否可以通過匹配等價關(guān)系轉(zhuǎn)換成索引值更小的分配方案，以及對于s中被分配到相同社區(qū)的目標模式中的結(jié)點，兩兩計算目標模式中它們在除本社區(qū)之外的其它各社區(qū)中的公共一跳鄰居數(shù)來進行剪枝，找出跨社區(qū)的所有互相認識的三個人構(gòu)成的子圖，獲得社區(qū)間子圖匹配結(jié)果；

將所述社區(qū)內(nèi)子圖匹配結(jié)果和社區(qū)間子圖匹配結(jié)果進行匯總，獲得目標模式與所述網(wǎng)絡(luò)圖的子圖匹配結(jié)果，即獲得所述社交網(wǎng)絡(luò)中所有互相認識的三個人。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述導(dǎo)入包含目標模式的文件，基于所導(dǎo)入的文件，分析目標模式的結(jié)構(gòu)，找出目標模式中互相匹配等價的子圖，包括：

導(dǎo)入包含目標模式的文件，解析所述目標模式中的結(jié)點和邊及相關(guān)屬性；

基于解析出的所述目標模式中的結(jié)點和邊及相關(guān)屬性，分析目標模式的結(jié)構(gòu)，找出目標模式中互相匹配等價的子圖。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，在所述社交網(wǎng)絡(luò)中各社區(qū)內(nèi)部，利用預(yù)設(shè)子圖匹配算法，分別找出各社區(qū)的與目標模式相匹配的子圖，獲得社區(qū)內(nèi)子圖匹配結(jié)果，包括：

并行地在所述社交網(wǎng)絡(luò)中各社區(qū)內(nèi)部，利用預(yù)設(shè)子圖匹配算法，分別找出各社區(qū)的與目標模式相匹配的子圖，獲得社區(qū)內(nèi)子圖匹配結(jié)果。