[發(fā)明專利]一種社交網(wǎng)絡(luò)社區(qū)的索引和查詢方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010856250.0
• 申請(qǐng)日: 2020-08-24
• 公開（公告）號(hào): CN112052400B
• 公開（公告）日: 2021-12-28
• 發(fā)明（設(shè)計(jì)）人: 徐建
• 申請(qǐng)（專利權(quán)）人: 杭州電子科技大學(xué)
• 主分類號(hào): G06F16/9536
• 分類號(hào): G06F16/9536;G06Q50/00;G06F16/951
• 代理公司: 杭州君度專利代理事務(wù)所(特殊普通合伙) 33240
• 代理人: 朱月芬

1.一種社交網(wǎng)絡(luò)社區(qū)的索引和查詢方法，其特征在于針對(duì)社交網(wǎng)絡(luò)中用戶所屬社區(qū)的查詢特點(diǎn)，通過構(gòu)建樹形索引結(jié)構(gòu)，提供一種高效的檢索方法，在構(gòu)建索引結(jié)構(gòu)后，之后的查詢中不需要再次遍歷用戶所屬的所有社區(qū)，通過訪問樹形索引即可返回查詢結(jié)果；具體步驟如下：步驟(1)、社交網(wǎng)絡(luò)的抽象；步驟(2)、k-核心社區(qū)的樹形索引的構(gòu)建；步驟(3)、建立社交網(wǎng)絡(luò)圖頂點(diǎn)-樹節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系；步驟(4)、用戶頂點(diǎn)u所屬社區(qū)的查詢；

步驟(1)所述的社交網(wǎng)絡(luò)的抽象，具體實(shí)現(xiàn)如下：

將一個(gè)社交網(wǎng)絡(luò)圖G(V,E)中的所有用戶及用戶之間的關(guān)系抽象，用頂點(diǎn)的集合V表示用戶；用戶之間的關(guān)系表示為兩個(gè)頂點(diǎn)之間的邊，用邊的集合E來表示；

步驟(2)所述的k-核心社區(qū)的樹形索引的構(gòu)建，具體實(shí)現(xiàn)如下：

對(duì)于社交網(wǎng)絡(luò)圖G(V,E)中的任一頂點(diǎn)v，頂點(diǎn)v的核心號(hào)碼是指在所有包含頂點(diǎn)v的k-核心社區(qū)中，最大的k值作為該頂點(diǎn)v的核心號(hào)碼；

樹形索引的構(gòu)建步驟包括社交網(wǎng)絡(luò)圖G中k-核心社區(qū)的解構(gòu)，即分解社交網(wǎng)絡(luò)圖G，獲得社交網(wǎng)絡(luò)圖G中所有頂點(diǎn)的核心號(hào)碼；然后從根節(jié)點(diǎn)的0-核心社區(qū)出發(fā)，依次構(gòu)建樹形索引；

所述的社交網(wǎng)絡(luò)圖G中k-核心社區(qū)的解構(gòu)的具體實(shí)現(xiàn)如下：

k-核心社區(qū)的解構(gòu)的基本過程是在社交網(wǎng)絡(luò)圖G中，按照頂點(diǎn)的度數(shù)，迭代刪除所有度數(shù)小于k的頂點(diǎn)，以及該頂點(diǎn)相鄰的邊，那么剩下的圖就是k-核心社區(qū)；

所述剩下的圖所包含的頂點(diǎn)的核心號(hào)碼就至少大于等于k；

2-1-1使用列表Core表示每個(gè)頂點(diǎn)的核心號(hào)碼，列表Core中元素格式為(v,ck),其中v表示頂點(diǎn)，ck表示頂點(diǎn)v的核心號(hào)碼；初始化列表Core為空；

使用數(shù)組degree存儲(chǔ)遍歷到的頂點(diǎn)的當(dāng)前度數(shù)，例如degree[v]表示遍歷到的頂點(diǎn)v的當(dāng)前度數(shù)；

2-1-2統(tǒng)計(jì)社交網(wǎng)絡(luò)圖G中所有頂點(diǎn)的度數(shù)；并對(duì)所有頂點(diǎn)根據(jù)其度數(shù)進(jìn)行升序排序；

2-1-3若社交網(wǎng)絡(luò)圖G非空，取社交網(wǎng)絡(luò)圖G中升序排序后度數(shù)最小的頂點(diǎn)v，進(jìn)行以下操作：

將當(dāng)前頂點(diǎn)v的當(dāng)前度數(shù)degree[v]賦值到頂點(diǎn)v的核心號(hào)碼ck，插入Core列表，即在Core列表中插入(v,degree[v])；

對(duì)于頂點(diǎn)v的每個(gè)鄰接頂點(diǎn)u進(jìn)行以下操作：

如果degree[u]degree[v]則degree[u]＝degree[u]-1，即確定頂點(diǎn)v的核心號(hào)碼后，其鄰接頂點(diǎn)u的度數(shù)減1；

從社交網(wǎng)絡(luò)圖G中刪除頂點(diǎn)v，重新對(duì)頂點(diǎn)集合V中所有頂點(diǎn)按度數(shù)排序，重復(fù)步驟2-1-3‘

所述的構(gòu)建k-核心社區(qū)的樹形索引的具體實(shí)現(xiàn)如下：

2-2-1將Core列表按每個(gè)元素的核心號(hào)碼進(jìn)行升序排序；

2-2-2初始化根節(jié)點(diǎn)root，根節(jié)點(diǎn)包含信息(0,Vk0，Vk0-else)；其中，0表示根節(jié)點(diǎn)的k值為0，Vk0是社交網(wǎng)絡(luò)圖G中所有k-核心號(hào)碼為0的頂點(diǎn)集合，Vk0-else為所有k-核心號(hào)碼非0的頂點(diǎn)集合；

初始化臨時(shí)樹節(jié)點(diǎn)node，節(jié)點(diǎn)包含信息(q,Vkq，Vkq-else)；其中，q表示臨時(shí)樹節(jié)點(diǎn)node的k核心號(hào)碼值為q，Vqk是社交網(wǎng)絡(luò)圖G中所有k-核心號(hào)碼為q的頂點(diǎn)集合，Vkq-else為所有k-核心號(hào)碼非q的頂點(diǎn)集合；

2-2-3初始化隊(duì)列nodeQueueA；

2-2-4將根節(jié)點(diǎn)root推入隊(duì)列nodeQueueA中；

2-2-5當(dāng)隊(duì)列nodeQueueA非空時(shí)，進(jìn)行以下操作：

使用臨時(shí)樹節(jié)點(diǎn)node保存隊(duì)列彈出的頭部元素nodeQueueA.pop()；

對(duì)樹節(jié)點(diǎn)node包含的節(jié)點(diǎn)集合node.Vk-else中所有節(jié)點(diǎn)，在社交網(wǎng)絡(luò)圖G中查找由這些頂點(diǎn)構(gòu)成的連通子圖,得到連通子圖集合{Gsub1,Gsub2,…Gsubn}；

對(duì)連通子圖集合{Gsub1,Gsub2,…Gsubn}中子圖根據(jù)順序進(jìn)行以下操作：

①取子圖Gsubi中所有頂點(diǎn)，并將所有頂點(diǎn)按其k-核心號(hào)碼進(jìn)行排序；其中i為自然數(shù)，取值為1，2…n中的一個(gè)值；

②將所以頂點(diǎn)中的最小k-核心號(hào)碼值,設(shè)置為臨時(shí)變量i；

生成一個(gè)新的樹節(jié)點(diǎn)node-sub，該樹節(jié)點(diǎn)node-sub包含信息(i,Vki，Vki-else)，此處樹節(jié)點(diǎn)node-sub的i值就是前述最小k-核心號(hào)碼值，集合Vki包含子圖Gsubi中核心號(hào)碼為i的所有頂點(diǎn)，集合Vki-else包含這個(gè)連通子圖中核心號(hào)碼非i的頂點(diǎn)；

③將新生成樹節(jié)點(diǎn)node-sub置為樹節(jié)點(diǎn)node的子節(jié)點(diǎn)；

④然后將樹節(jié)點(diǎn)node-sub推入隊(duì)列；

對(duì)上述所有子圖進(jìn)行步驟①～步驟④的操作，將樹節(jié)點(diǎn)node包含的頂點(diǎn)集合node.Vk-else置空；

所述步驟(3)建立社交網(wǎng)絡(luò)圖頂點(diǎn)-樹節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系，具體實(shí)現(xiàn)如下：

使用一個(gè)有序列表MAP存儲(chǔ)社交網(wǎng)絡(luò)圖頂點(diǎn)-樹節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系，對(duì)步驟(2)中構(gòu)建的樹形索引進(jìn)行深度優(yōu)先遍歷，獲得社交網(wǎng)絡(luò)圖頂點(diǎn)-樹節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系后，向列表MAP添加該對(duì)應(yīng)關(guān)系；

從根節(jié)點(diǎn)root出發(fā)對(duì)樹形索引進(jìn)行深度優(yōu)先遍歷，具體實(shí)現(xiàn)為：

3-1初始化堆棧nodeStack；

3-2初始化臨時(shí)樹節(jié)點(diǎn)node；

3-3將根節(jié)點(diǎn)root壓入堆棧；

3-4當(dāng)堆棧nodeStack非空時(shí)執(zhí)行以下操作：

3-4-1使用臨時(shí)樹節(jié)點(diǎn)node保存堆棧頂部值nodeStack.top；

3-4-2遍歷臨時(shí)樹節(jié)點(diǎn)node中社交網(wǎng)絡(luò)圖的頂點(diǎn)，為每個(gè)頂點(diǎn)在列表MAP中添加社交網(wǎng)絡(luò)圖頂點(diǎn)-樹節(jié)點(diǎn)對(duì)應(yīng)關(guān)系；

3-4-3彈出堆棧頂部元素：nodeStack.pop()；

3-4-4遍歷臨時(shí)樹節(jié)點(diǎn)node的孩子節(jié)點(diǎn)，如果一個(gè)序號(hào)為i的孩子節(jié)點(diǎn)child_i非空，則壓入堆棧nodeStack：nodeStack.push(node-child_i)；

3-5完成遍歷以后，以頂點(diǎn)ID為關(guān)鍵字對(duì)列表MAP進(jìn)行排序；

所述步驟(4)所述的用戶頂點(diǎn)u所屬社區(qū)的查詢，具體實(shí)現(xiàn)如下：

4-1初始化臨時(shí)樹節(jié)點(diǎn)node；

4-2查詢列表MAP，獲得頂點(diǎn)u在樹形索引中的節(jié)點(diǎn)位置，并將該節(jié)點(diǎn)位置賦予臨時(shí)樹節(jié)點(diǎn)node；

4-3對(duì)臨時(shí)樹節(jié)點(diǎn)node進(jìn)行廣度優(yōu)先遍歷，返回以臨時(shí)樹節(jié)點(diǎn)node為根節(jié)點(diǎn)的子樹中包含的所有頂點(diǎn)的并集，執(zhí)行以下操作：

4-3-1初始化隊(duì)列nodeQueue；

4-3-2初始化臨時(shí)樹節(jié)點(diǎn)node；

4-3-3初始化返回值k＝node.k；

4-3-4初始化返回的頂點(diǎn)集合

4-3-5將臨時(shí)樹節(jié)點(diǎn)node推入隊(duì)列nodeQueue；

4-3-6當(dāng)隊(duì)列nodeQueue非空時(shí)執(zhí)行以下操作：

使用臨時(shí)樹節(jié)點(diǎn)node保存彈出的隊(duì)列頭部元素nodeQueue.pop()；

合并臨時(shí)樹節(jié)點(diǎn)node包含的頂點(diǎn)至集合V_u；

遍歷臨時(shí)樹節(jié)點(diǎn)node的孩子節(jié)點(diǎn)，如果一個(gè)序號(hào)為i的孩子節(jié)點(diǎn)child_i非空，則壓入隊(duì)列nodeQueue：nodeQueue.push(node-child_i)；

4-4返回頂點(diǎn)u的k值和所屬的社區(qū)所包含的頂點(diǎn)集合V_u。