[發(fā)明專利]一種基于滑動(dòng)窗口的大規(guī)模動(dòng)態(tài)圖劃分方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201910583072.6
• 申請(qǐng)日: 2019-07-01
• 公開(kāi)（公告）號(hào): CN110309371A
• 公開(kāi)（公告）日: 2019-10-08
• 發(fā)明（設(shè)計(jì)）人: 崔煥慶;榮炫宇;賈瑞生;魏永山;張峰;徐強(qiáng)
• 申請(qǐng)（專利權(quán)）人: 山東科技大學(xué)
• 主分類號(hào): G06F16/901
• 分類號(hào): G06F16/901
• 代理公司: 青島智地領(lǐng)創(chuàng)專利代理有限公司 37252
• 代理人: 種艷麗

1.一種基于滑動(dòng)窗口的大規(guī)模動(dòng)態(tài)圖劃分方法，其特征在于：包括如下步驟：

步驟1：增加頂點(diǎn)；具體包括如下步驟：

輸入為待增加頂點(diǎn)的集合S_vertex、當(dāng)前K個(gè)分區(qū)P_i(i＝1，2，…，K)的各個(gè)分區(qū)的頂點(diǎn)集合；

步驟1.1：置指定|W_vertex|的上限為L(zhǎng)_vertex；

其中，W_vertex為將被劃分的候選頂點(diǎn)集合，其頂點(diǎn)來(lái)自S_vertex；

步驟1.2：取N＝min{|S_vertex|，L_vertex-|W_vertex|}，即|S_vertex|和L_vertex-|W_vertex|的最小值，將S_vertex中的前N個(gè)頂點(diǎn)增加到W_vertex中，并從S_vertex中刪除這些頂點(diǎn)；

步驟1.3：如果則輸出劃分結(jié)果，并結(jié)束劃分流程；否則轉(zhuǎn)步驟1.4；

步驟1.4：取v＝argmax{d_u|u∈W_vertex，du是頂點(diǎn)u的度數(shù)即與u相鄰接的頂點(diǎn)的個(gè)數(shù)}，即取W_vertex中度數(shù)最大的頂點(diǎn)v，如果有多個(gè)度數(shù)相同且度數(shù)最大的頂點(diǎn)，則任取其中一個(gè)；

步驟1.5：取V＝Q＝R＝{v}；V為被選中劃分到某分區(qū)的頂點(diǎn)集合，Q為頂點(diǎn)隊(duì)列；R為與V中的頂點(diǎn)相鄰的所有頂點(diǎn)的集合；

步驟1.6：若則轉(zhuǎn)步驟1.8；否則從取Q中取出第1個(gè)頂點(diǎn)u，并從Q中刪除該頂點(diǎn)；

步驟1.7：取R＝RU{w|(u，w)是圖的一條邊}，然后轉(zhuǎn)步驟1.6；

步驟1.8：取

步驟1.9：對(duì)每個(gè)分區(qū)P_i(i＝1，2，…，K)，計(jì)算其中，C_i為將頂點(diǎn)或邊劃分到第i個(gè)分區(qū)的代價(jià)；是擁有最多頂點(diǎn)的分區(qū)的頂點(diǎn)個(gè)數(shù)，α為計(jì)算C_i時(shí)分區(qū)負(fù)載和割邊數(shù)量的權(quán)重系數(shù)，0＜α＜1；

用于衡量分區(qū)負(fù)載情況，用戶衡量割邊數(shù)量；

步驟1.10：取m＝argmin{C_i|i＝1，2，…，K}，即C_m是所有{C_i|i＝1，2，…，K}中的最小值；

步驟1.11：將V中的所有頂點(diǎn)劃分到分區(qū)P_m中；P_m為與最小值C_m對(duì)應(yīng)的分區(qū)；

步驟1.12：取W_vertex＝W_vertex-V，然后轉(zhuǎn)步驟1.2；

步驟2：增加邊；具體包括如下步驟：

輸入為待增加邊的集合S_edge、當(dāng)前K個(gè)分區(qū)P_i(i＝1，2，…，K)的各個(gè)分區(qū)的頂點(diǎn)集合；

前提：S_edge中邊的所有頂點(diǎn)都已經(jīng)劃分完畢；

步驟2.1：置指定|W_edge|的上限為L(zhǎng)_edge；

步驟2.2：取N＝min{|S_edge|，L_edge-|W_edge|}，即|S_edge|和L_edge-|W_edge|的最小值，將S_edge中的前N條邊增加到W_edge中，并從S_edge中刪除這些邊；

步驟2.3：如果則輸出劃分結(jié)果，并結(jié)束劃分流程；否則轉(zhuǎn)步驟2.4；

步驟2.4：對(duì)每個(gè)在W_edge中的頂點(diǎn)v，取E_v＝{u|(u，v)∈W_edge}；E_v為與頂點(diǎn)v相鄰接的且屬于W_edge的頂點(diǎn)集合；

步驟2.5：取v＝argmax{|E_v|}，即取W_edge中鄰接頂點(diǎn)個(gè)數(shù)最多的頂點(diǎn)v，如果有多個(gè)滿足條件的頂點(diǎn)，則任取其中一個(gè)；

步驟2.6：取T＝{w|(v，w)是圖的一條邊}；T為與W_edge中的某個(gè)頂點(diǎn)相關(guān)聯(lián)的所有頂點(diǎn)的集合；

步驟2.7：對(duì)每個(gè)分區(qū)P_i(i＝1，2，…，K)，如果v∈P_i，則否則其中max_{j＝1，2，…，K}{|P_j|}是擁有最多頂點(diǎn)的分區(qū)的頂點(diǎn)個(gè)數(shù)；

步驟2.8：取m＝argmin{C_i|i＝1，2，…，K}，即C_m是所有{C_i|i＝1，2，…，K}中的最小值；

步驟2.9：將v轉(zhuǎn)移到分區(qū)P_m中；

步驟2.10：對(duì)于E_v中的每一條邊(u，v)，u∈P_i，v∈P_j，若i≠j，則將(u，v)劃分到P_i和P_j中；否則將(u，v)劃分到P_i中；

步驟2.11：W_edge＝W_edge-E_v，轉(zhuǎn)步驟2.2。