一種基於圖節點特徵預計算的超大規模電商網絡分區優化方法及裝置與流程

2023-11-11 02:42:43 2

1.本發明涉及超大規模電商網絡的圖計算領域，更具體地說，涉及一種基於圖節點特徵預計算的超大規模電商網絡分區優化方法及裝置，為一種針對多維度多尺度立方體構成的超大規模電商網絡的分布式圖資料庫存儲優化技術。


背景技術：

2.隨著網際網路技術的飛速發展，傳統商業活動的各個環節逐漸電子化、網絡化，人們的日常生活中湧現出了許多與電商網絡相關的應用，如拼多多、淘寶和京東等。超大規模的電商網絡中往往包含著豐富的數據信息，挖掘這些信息能夠產生巨大的社會效益和經濟效益。因此，對電商網絡進行數據挖掘成為了當今社會的一大研究熱點。
3.在研究領域中，這些電商網絡通常用圖結構來表示，圖中的節點表示電商網絡中的實體，節點的特徵向量表徵實體的多維信息，圖中的邊代表實體之間的關係。隨著時間的推移，網絡的拓撲結構及節點表徵不斷發生改變，網絡的規模呈指數級增長，因此需要採用分布式系統存儲網絡的節點信息，同時對新增的流數據進行動態的劃分和更新。
4.由於圖計算中的大量算法都是以邊進行迭代計算的，因此子圖之間的邊的數量必須儘可能的少，以降低不同節點之間的通信代價。而且，為了提高分布式圖資料庫存儲引擎的計算效率，還需要確保分布式伺服器各分區的節點數量相對均衡。目前以節點為中心的圖劃分技術大多只適用於靜態網絡或規模較小的動態網絡，在長尾特徵顯著的超大規模電商網絡中存在明顯的不足，因為冪律圖中的高度節點會顯著增加與分布式伺服器各分區節點的通信代價。此外，對於節點信息豐富的超大規模動態電商網絡來說，這些方法並未對節點的特徵進行充分利用。


技術實現要素：

5.針對現有技術的不足和改進需求，本發明提供了一種基於圖節點特徵預計算的超大規模電商網絡分區優化方法及裝置，在使用分布式圖資料庫存儲引擎提高設備復用率的前提下，引入了一類針對多維度多尺度立方體構成的超大規模動態電商網絡的節點劃分方法，通過充分利用超大規模動態電商網絡中節點的多維信息，使該超大規模電商網絡中的同質節點儘可能被劃分至同一分布式伺服器分區，通過計算節點度相似度得分使該超大規模電商網絡中的高度節點儘可能與其鄰居分布在同一分布式伺服器分區，通過計算分布式伺服器各分區的負載代價均衡分區負載，從而提高分布式伺服器各分區的劃分質量，提高該超大規模電商網絡在後續的圖計算任務中的計算效率。
6.本發明解決技術問題所採用的技術方案如下：第一方面，本發明提供了一種基於圖節點特徵預計算的超大規模電商網絡分區優化方法，該方法包括如下步驟：
7.(1)獲取初始時刻的電商網絡圖數據g(v,e)，其中，v＝(v1,v2,
…
,vn)表示網絡中的實體集合，vn表示第n個實體，e＝(e1,e2,
…
,em)表示實體之間的連接狀態集合，em表示第m
種狀態；第i個待劃分的實體為圖中第i個節點其中，id表示實體的唯一編碼，enumi表示實體的枚舉特徵，包括國籍、性別、職業，數量為l1，scalari表示實體的標量特徵，包括年齡、收入，數量為l2；
8.(2)獲取分布式伺服器各分區的最大負載c＝(c1,c2,
…
,ck)，k為分布式伺服器的分區數量；
9.(3)初始化分布式伺服器各分區的負載p＝(p1,p2,
…
,pk)均為0、分布式伺服器各分區的中心節點集合s＝(s1,s2,
…
,sk)為空；
10.(4)根據初始時刻的電商網絡圖數據g(v,e)得到表示節點間關係的鄰接矩陣a；
11.(5)基於鄰接矩陣a，計算電商網絡中l1個枚舉特徵的模塊度並將模塊度最大的枚舉特徵記為enum；
12.(6)基於鄰接矩陣a，計算電商網絡中l2個標量特徵的同配係數並將同配係數最大的標量特徵記為scalar；
13.(7)對於電商網絡中的一個節點vi，執行以下操作：
14.(7.1)任意選擇一個分布式伺服器分區pj，若|pj|＜cj，則計算節點vi在該分布式伺服器分區的劃分質量得分；否則重新執行步驟(7.1)，直至得到節點vi到所有未滿載的分布式伺服器分區的劃分質量得分；
15.(7.2)若所有未滿載的分布式伺服器分區的劃分質量得分僅包含一個最大值，則將節點vi劃分至得分最高的目標分布式伺服器分區p
des
，否則從得分最高的多個分布式伺服器分區中隨機選擇一個作為節點vi的目標分布式伺服器分區p
des
；
16.(7.3)若目標分布式伺服器分區p
des
負載的節點個數小於3，則轉入步驟(8)；否則更新p
des
的中心節點集合s
des
；
17.(8)不斷重複步驟(7)，直至電商網絡中的所有節點劃分完畢；
18.(9)對於任意新增的邊流數據，對新增數據中的節點執行步驟(7)，實現對電商網絡的維護和更新。
19.進一步地，所述電商網絡為多維度多尺度立方體構成的億級超大規模電商網絡。
20.進一步地，步驟(5)中，任意一個枚舉特徵的模塊度計算方式如下：
[0021][0022]
其中，qh表示該超大規模電商網絡在第h個枚舉特徵上同類節點之間的連接程度，di表示節點vi在鄰接矩陣a中的度，μi表示節點vi在第h個枚舉特徵的類型，類型用整數值1到t1表示，t1是節點第h個枚舉特徵的類型總數，δ(μi,μj)是克羅內克函數，其係數值為
[0023]
進一步地，步驟(6)中，任意一個標量特徵的同配係數計算方式如下：
[0024][0025]
其中，rb表示該超大規模電商網絡在第b個標量特徵上同類節點之間的連接程度，di表示節點vi在鄰接矩陣a中的度，xi表示節點vi在第b個標量特徵的值，δ(xi,xj)是克羅內
克函數，其係數值為
[0026]
進一步地，步驟(7.1)中，劃分質量得分的計算方式如下：
[0027]
score(vi,p)＝max{sim
enum
(vi,vj)+sim
scalar
(vi,vj)-sim
degree
(vi,vj)}+αγ|p|
γ-1
；
[0028]
其中，p表示分布式伺服器的分區，sim
enum
(vi,vj)和sim
scalar
(vi,vj)分別表示兩個節點在枚舉特徵enum和標量特徵scalar上的相似度，計算方式如下：
[0029][0030]
其中，fi表示點vi在特徵f上的向量表示，特徵f表示枚舉特徵enum或標量特徵scalar；
[0031]
劃分質量得分中的sim
degree
(vi,vj)表示兩個節點在節點度方面的相似度，計算方式如下：
[0032][0033]
其中，d表示對節點vi和vj隨機選擇的鄰居節點個數，a
id
表示鄰接矩陣a中行坐標為i且縱坐標為d的值，表示鄰接矩陣中第i行元素的均值
[0034]
劃分質量得分中的其中，γ是調節分區負載對劃分質量得分的影響力係數。
[0035]
進一步地，步驟(7.1)中：若當前分布式伺服器分區的負載為0，則節點vi在該分布式伺服器分區的劃分質量得分僅包含負載代價得分αγ|pi|
γ-1
；
[0036]
若當前分布式伺服器分區的負載節點個數大於0且小於3，則節點vj在該分布式伺服器分區的劃分質量得分為節點vj到該分布式伺服器分區所有節點的劃分質量得分的均值；
[0037]
若當前分布式伺服器分區的負載節點個數大於等於3，則節點vj在該分布式伺服器分區的劃分質量得分為節點vj到該分布式伺服器分區所有中心節點的劃分質量得分的均值。
[0038]
進一步地，步驟(7.4)中，更新分區p
des
的中心節點集合s
des
採用dbscan算法，具體步驟如下：
[0039]
a)設置該算法中minpts的值為半徑為1；
[0040]
b)對於分區內的任意節點，若該節點的鄰居節點數量大於等於則將該點加入當前分區的中心節點集合；
[0041]
c)重複執行步驟(b)，直至遍歷完當前分區內的所有節點。
[0042]
第二方面，本發明還提供了一種基於圖節點特徵預計算的超大規模電商網絡分區優化裝置，包括存儲器和一個或多個處理器，所述存儲器中存儲有可執行代碼，所述處理器執行所述可執行代碼時，用於實現所述的基於圖節點特徵預計算的超大規模電商網絡分區
優化方法的步驟。
[0043]
第三方面，本發明還提供了一種計算機可讀存儲介質，其上存儲有程序，該程序被處理器執行時，實現所述的基於圖節點特徵預計算的超大規模電商網絡分區優化方法的步驟。
[0044]
本發明的有益效果：
[0045]
本發明的優勢在於通過對超大規模動態電商網絡使用分布式圖資料庫存儲引擎，有效節省伺服器的消耗，極大降低時延，提高計算吞吐量效率；針對超大規模動態電商網絡豐富的節點信息設計全新的質量打分函數，保證分布式伺服器各分區的劃分質量，提高分布式圖資料庫存儲引擎的計算效率。相較於傳統基於單機的圖資料庫存儲方法，基於分布式圖資料庫存儲引擎的方法能夠有效解決超大規模電商網絡的內存瓶頸問題，提高計算吞吐量效率和資料庫安全性；相較於傳統基於節點的圖劃分方法，本方法充分利用了超大規模動態電商網絡的節點信息，提高劃分準確率，降低計算複雜度。
附圖說明
[0046]
為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖做簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動前提下，還可以根據這些附圖獲得其他附圖。
[0047]
圖1為本發明提供的基於圖節點特徵預計算的超大規模電商網絡分區優化方法的流程圖。
[0048]
圖2為本發明提供的基於圖節點特徵預計算的超大規模電商網絡分區優化裝置的結構圖。
具體實施方式
[0049]
下面結合附圖和實施例，對本發明作進一步詳細描述，以下實施例用於說明本發明，但不用來限制本發明的範圍。
[0050]
如圖1，本發明的實施例提供的一種基於圖節點特徵預計算的超大規模電商網絡分區優化的方法的具體實施過程如下：
[0051]
(1)獲取超大規模電商網絡的數據信息，及分布式伺服器各分區的最大負載，具體步驟如下：
[0052]
獲取初始時刻的電商網絡圖數據g(v,e)，其中，v＝(v1,v2,
…
,v
10000
)表示網絡中的實體集合，e＝(e1,e2,
…
,e
500000
)表示實體之間的連接狀態集合；每個待劃分的實體可表示為節點vi＝{id,enum1,enum2,enum3,scalar1,scalar2}，其中，id表示實體的唯一編碼，enumi分別表示實體的枚舉特徵：國籍、性別、職業；scalari分別表示實體的標量特徵：年齡、收入；
[0053]
獲取分布式伺服器各分區的最大負載c＝(c1,c2,
…
,c8)，即分布式伺服器的分區數量為8；
[0054]
(2)數據初始化：
[0055]
初始化分布式伺服器各分區的負載p＝(p1,p2,
…
,p8)均為0、分布式伺服器各分區
的中心節點集合s＝(s1,s2,
…
,s8)為空；
[0056]
(3)在預劃分階段，使用初始時刻的電商網絡圖信息提取該網絡的同質枚舉特徵和同質標量特徵，具體步驟如下：
[0057]
(3.1)根據初始時刻的電商網絡圖數據g(v,e)，得到如下表示節點間關係的10000階鄰接矩陣a；
[0058][0059]
(3.2)計算該電商網絡中3個枚舉特徵的模塊度q＝(q1,q2,q3)，任意一個枚舉特徵的模塊度計算方式如下：
[0060][0061]
其中，qh表示該超大規模電商網絡在第h個枚舉特徵上同類節點之間的連接程度，di表示節點vi在鄰接矩陣a中的度，μi表示節點vi在第h個枚舉特徵的類型，類型用整數值1到t1表示，t1是節點第h個枚舉特徵的類型總數，δ(μi,μj)是克羅內克函數，其係數值為
[0062]
計算後得到模塊度最大的枚舉特徵「職業」；
[0063]
(3.3)計算該電商網絡中l2個標量特徵的同配係數r＝(r1,r2)，任意一個標量特徵的同配係數計算方式如下：
[0064][0065]
其中，rb表示該超大規模電商網絡在第b個標量特徵上同類節點之間的連接程度，di表示節點vi在鄰接矩陣a中的度，xi表示節點vi在第b個標量特徵的值，δ(xi,xj)是克羅內克函數，其係數值為
[0066]
計算後得到同配係數最大的標量特徵「年齡」；
[0067]
(4)對電商網絡中的任意一個節點執行以下操作：
[0068]
(4.1)對於每個尚未滿載的分布式伺服器分區，計算節點vi在該分布式伺服器分區的劃分質量得分，計算方式如下：
[0069]
score(vi,p)＝max{sim
enum
(vi,vj)+sim
scalar
(vi,vj)-sim
degree
(vi,vj)}+αγ|p|
γ-1
[0070]
其中，p表示分布式伺服器的分區，sim
enum
(vi,vj)和sim
scalar
(vi,vj)分別表示兩個節點在枚舉特徵「職業」和標量特徵「年齡」上的相似度，計算方式如下：
[0071][0072]
其中，fi表示點vi在特徵f上的向量表示，特徵f表示枚舉特徵enum或標量特徵scalar；
[0073]
劃分質量得分中的sim
degree
(vi,vj)表示兩個節點在節點度方面的相似度，計算方式如下：
[0074][0075]
其中，d表示對節點vi和vj隨機選擇的鄰居節點個數，a
id
表示鄰接矩陣a中行坐標為i且縱坐標為d的值，表示鄰接矩陣中第i行元素的均值
[0076]
在計算節點vj在該分布式伺服器分區的劃分質量得分時，採用如下規則：
[0077]
若當前分布式伺服器分區的負載為0，則節點vi在該分布式伺服器分區的劃分質量得分僅包含負載代價得分αγ|pi|
γ-1
；
[0078]
若當前分布式伺服器分區的負載節點個數大於0且小於3，則節點vj在該分布式伺服器分區的劃分質量得分為節點vj到該分布式伺服器分區所有節點的劃分質量得分的均值；
[0079]
若當前分布式伺服器分區的負載節點個數大於等於3，則節點vj在該分布式伺服器分區的劃分質量得分為節點vj到該分布式伺服器分區所有中心節點的劃分質量得分的均值；
[0080]
(4.2)若該節點到每個尚未滿載的分布式伺服器分區的劃分質量得分僅包含一個最大值，則將節點劃分至得分最高的分布式伺服器分區p
des
，否則從得分最高的多個分布式伺服器分區中隨機選擇一個作為該節點的目標分布式伺服器分區p
des
；
[0081]
(4.3)若分布式伺服器分區p
des
負載的節點個數小於3，則轉入步驟(4.4)；否則使用dbscan算法更新p
des
的中心節點集合s
des
，具體步驟如下：
[0082]
(a)設置該算法中minpts的值為半徑為1；
[0083]
(b)對於分布式伺服器分區內的任意節點，若該節點的鄰居節點數量大於等於則將該點加入當前分布式伺服器分區的中心節點集合；
[0084]
(c)重複執行步驟(b)，直至遍歷完當前分布式伺服器分區內的所有節點；
[0085]
(4.4)不斷重複步驟(4)，直至網絡中的所有節點劃分完畢；
[0086]
(5)在動態維護階段，對於新增的上億條邊流數據，對數據中千萬級節點執行步驟(4)，完成對億級超大規模電商網絡的維護和更新。
[0087]
超大規模電商網絡中的實體蘊含著豐富的信息，使用多維度多尺度立方體進行表徵，能夠有效捕捉網絡信息，從而提高後續數據挖掘的結果的準確性。同時，使用該結構表徵實體確定了以點為中心的分布式存儲結構。目前，以點為中心的圖劃分技術在長尾特徵顯著的超大規模電商網絡中存在明顯的不足，因為冪律圖中的高度節點會顯著增加分區節點的通信代價。因此，本發明設計了一個全新的劃分質量得分函數，在該函數中通過計算新增節點與分布式伺服器分區中心節點的兩類同質特徵相似度得分使同質節點儘可能被劃分至同一分區，通過計算節點度相似度得分的負值使高度節點儘可能與其鄰居分布在同一分區，通過計算負載代價均衡分區負載，從而在降低通信代價的情況下有效提高分區的計算效率。
[0088]
對於超大規模電商網絡而言，網絡規模呈指數級增長，初期的網絡規模相對較小。因此，通過計算初期網絡最顯著的枚舉特徵和標量特徵，可以大大減少後續節點對特徵匹配度的計算量。此外，當分布式伺服器分區節點達到一定規模時，使用分布式伺服器分區的中心節點集代替分布式伺服器分區的所有節點也能有效降低節點對匹配度的計算代價。
[0089]
與前述基於圖節點特徵預計算的超大規模電商網絡分區優化方法的實施例相對應，本發明還提供了基於圖節點特徵預計算的超大規模電商網絡分區優化裝置的實施例。
[0090]
參見圖2，本發明實施例提供的一種基於圖節點特徵預計算的超大規模電商網絡分區優化裝置，包括存儲器和一個或多個處理器，所述存儲器中存儲有可執行代碼，所述處理器執行所述可執行代碼時，用於實現上述實施例中的基於圖節點特徵預計算的超大規模電商網絡分區優化方法。
[0091]
本發明基於圖節點特徵預計算的超大規模電商網絡分區優化裝置的實施例可以應用在任意具備數據處理能力的設備上，該任意具備數據處理能力的設備可以為諸如計算機等設備或裝置。裝置實施例可以通過軟體實現，也可以通過硬體或者軟硬體結合的方式實現。以軟體實現為例，作為一個邏輯意義上的裝置，是通過其所在任意具備數據處理能力的設備的處理器將非易失性存儲器中對應的電腦程式指令讀取到內存中運行形成的。從硬體層面而言，如圖2所示，為本發明基於圖節點特徵預計算的超大規模電商網絡分區優化裝置所在任意具備數據處理能力的設備的一種硬體結構圖，除了圖2所示的處理器、內存、網絡接口、以及非易失性存儲器之外，實施例中裝置所在的任意具備數據處理能力的設備通常根據該任意具備數據處理能力的設備的實際功能，還可以包括其他硬體，對此不再贅述。
[0092]
上述裝置中各個單元的功能和作用的實現過程具體詳見上述方法中對應步驟的實現過程，在此不再贅述。
[0093]
對於裝置實施例而言，由於其基本對應於方法實施例，所以相關之處參見方法實施例的部分說明即可。以上所描述的裝置實施例僅僅是示意性的，其中所述作為分離部件說明的單元可以是或者也可以不是物理上分開的，作為單元顯示的部件可以是或者也可以不是物理單元，即可以位於一個地方，或者也可以分布到多個網絡單元上。可以根據實際的需要選擇其中的部分或者全部模塊來實現本發明方案的目的。本領域普通技術人員在不付出創造性勞動的情況下，即可以理解並實施。
[0094]
本發明實施例還提供一種計算機可讀存儲介質，其上存儲有程序，該程序被處理器執行時，實現上述實施例中的基於圖節點特徵預計算的超大規模電商網絡分區優化方法。
[0095]
所述計算機可讀存儲介質可以是前述任一實施例所述的任意具備數據處理能力的設備的內部存儲單元，例如硬碟或內存。所述計算機可讀存儲介質也可以是任意具備數據處理能力的設備的外部存儲設備，例如所述設備上配備的插接式硬碟、智能存儲卡(smart media card，smc)、sd卡、快閃記憶體卡(flash card)等。進一步的，所述計算機可讀存儲介質還可以既包括任意具備數據處理能力的設備的內部存儲單元也包括外部存儲設備。所述計算機可讀存儲介質用於存儲所述電腦程式以及所述任意具備數據處理能力的設備所需的其他程序和數據，還可以用於暫時地存儲已經輸出或者將要輸出的數據。
[0096]
上述實施例用來解釋說明本發明，而不是對本發明進行限制，在本發明的精神和
權利要求的保護範圍內，對本發明作出的任何修改和改變，都落入本發明的保護範圍。