亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于節(jié)點相似性分組與圖壓縮的圖摘要算法

        2023-10-21 08:37:06宏宇陳鴻昶張建朋黃瑞陽
        計算機應(yīng)用 2023年10期
        關(guān)鍵詞:壓縮率集上校正

        宏宇,陳鴻昶,張建朋*,黃瑞陽

        基于節(jié)點相似性分組與圖壓縮的圖摘要算法

        宏宇1,陳鴻昶2,張建朋2*,黃瑞陽2

        (1.鄭州大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院,鄭州 450002; 2.信息工程大學(xué) 信息技術(shù)研究所,鄭州 450002)( ? 通信作者電子郵箱j_zhang_edu@sina.com)

        針對當前圖摘要方法壓縮率較高,圖壓縮算法無法直接被用于下游任務(wù)分析的問題,提出一種圖摘要與圖壓縮的融合算法,即基于節(jié)點相似性分組與圖壓縮的圖摘要算法(GSNSC)。首先,初始化節(jié)點為超節(jié)點,并根據(jù)相似度對超節(jié)點分組;其次,將每個組的超節(jié)點合并,直到達到指定次數(shù)或指定節(jié)點數(shù);再次,在超節(jié)點之間添加超邊和校正邊以恢復(fù)原始圖;最后,對于圖壓縮部分,判斷對每個超節(jié)點的鄰接邊壓縮和摘要的代價,并選擇二者中代價較小的執(zhí)行。在Web-NotreDame、Web-Google和Web-Berkstan等6個數(shù)據(jù)集上進行了圖壓縮率和圖查詢實驗。實驗結(jié)果表明,在6個數(shù)據(jù)集上,與SLUGGER(Scalable Lossless sUmmarization of Graphs with HiERarchy)算法相比,所提算法的壓縮率至少降低了23個百分點;與SWeG(Summarization of Web-scale Graphs)算法相比,所提算法的壓縮率至少降低了13個百分點;在Web-NotreDame數(shù)據(jù)集上,所提算法的度誤差比SWeG降低了41.6%。以上驗證了所提算法具有更好的圖壓縮率和圖查詢準確度。

        圖摘要;圖壓縮;圖查詢;超邊;最小描述長度

        0 引言

        圖數(shù)據(jù)可以用于建模實體和實體之間的復(fù)雜關(guān)系,在現(xiàn)實世界中應(yīng)用廣泛,如社交網(wǎng)絡(luò)、蛋白質(zhì)分子網(wǎng)絡(luò)、合作關(guān)系網(wǎng)絡(luò)和通信網(wǎng)絡(luò)等。許多計算問題都可以轉(zhuǎn)換成圖上的計算問題,從而利用圖上的相關(guān)技術(shù)解決問題。圖有很多下游任務(wù),如模式挖掘、社區(qū)發(fā)現(xiàn)、圖查詢和可視化等,服務(wù)于解決現(xiàn)實問題;然而,隨著數(shù)據(jù)規(guī)模的爆炸式增長,用于分析的圖數(shù)據(jù)也越來越復(fù)雜多樣,難以存儲和分析,解決這些問題已經(jīng)成為當前研究的熱點和難點。

        目前用于解決圖數(shù)據(jù)量大問題的技術(shù)包括圖壓縮和圖摘要(Graph summarization)技術(shù)。圖摘要技術(shù)[1-11]將具有較高相似度的節(jié)點合并成超節(jié)點,減少節(jié)點和邊的數(shù)量以降低圖的復(fù)雜度,主要方法有基于節(jié)點分組的方法[5-7]、基于邊分組的方法[2]和基于稀疏化的方法[1]等。圖壓縮技術(shù)[4,12-16]將圖數(shù)據(jù)以存儲占用更低的壓縮方式存儲,主要方法有基于頂點重排序的方法[12-13]和基于鄰接矩陣的方法[14]等。這兩類技術(shù)的側(cè)重點不同,圖摘要技術(shù)側(cè)重于保存圖的結(jié)構(gòu)信息,它的輸出是一個更為抽象緊湊的圖,因此可以直接用于下游任務(wù)分析;圖壓縮技術(shù)則是以各種方式最大限度地降低圖數(shù)據(jù)在磁盤空間或內(nèi)存空間的存儲占用,由于圖壓縮技術(shù)并不關(guān)注圖的結(jié)構(gòu)信息,因此在降低存儲空間方面,圖壓縮效果更好,但是圖壓縮產(chǎn)生的圖并不能直接使用,需要先對壓縮后的圖進行解碼操作。

        通過對比兩種技術(shù)的特點可以發(fā)現(xiàn),圖摘要雖然能夠降低圖的復(fù)雜度,但為了能夠恢復(fù)原始圖和保存結(jié)構(gòu)特征,它的效果比圖壓縮的效果差;而圖壓縮雖然能夠更好地降低圖的消耗,但是不能直接用于分析。

        針對以上問題,本文提出一種基于節(jié)點相似性分組與圖壓縮的圖摘要算法(Graph Summarization algorithm based on Node Similarity grouping and graph Compression, GSNSC),結(jié)合了圖摘要與圖壓縮的優(yōu)勢。

        本文的主要工作如下:

        1)提出了一種基于節(jié)點相似性分組與圖壓縮的圖摘要算法(GSNSC)。首先通過將節(jié)點分組聚合成超節(jié)點的方式產(chǎn)生較小的輸出摘要圖,其次壓縮摘要圖中的超邊和校正邊,降低圖的壓縮率,減少運行時間。所提算法不僅能夠降低圖的存儲空間占用,而且還能直接用于挖掘和分析。

        2)在真實數(shù)據(jù)集上進行實驗,實驗結(jié)果表明,所提算法比現(xiàn)有的圖摘要算法具有更好的壓縮率和更低的運行時間。針對圖查詢設(shè)計了相關(guān)實驗,驗證了所提算法具有較好的查詢準確度。

        1 相關(guān)工作

        1.1 圖摘要

        圖摘要又叫作圖概要,是一種降低大規(guī)模圖的復(fù)雜度和描述長度的技術(shù)。它通過一些策略(如合并多個節(jié)點成一個超節(jié)點、去掉不重要的邊等)創(chuàng)建一個摘要圖,在降低圖的成本的同時也保存了圖的結(jié)構(gòu)特征,使得到的摘要圖能夠更容易地支持圖模式挖掘、可視化和鄰域查詢等下游任務(wù)。

        圖1 例子示意圖

        1.2 圖壓縮

        圖壓縮也是降低圖規(guī)模的一種方法,和圖摘要的區(qū)別是它不關(guān)注圖的結(jié)構(gòu)信息和語義信息,它的目標是盡可能地降低圖的存儲空間占用,使得大圖數(shù)據(jù)可以存儲在較小的磁盤空間上,以解決圖數(shù)據(jù)量較大的問題。目前圖壓縮的研究還處于起步階段[4],這些方法大多壓縮節(jié)點的邊,其中較為常用的是基于節(jié)點重排的方法。由于真實的圖通常都是非常稀疏的,如在社交網(wǎng)絡(luò)中,節(jié)點代表用戶,邊代表用戶之間的好友關(guān)系,圖中的節(jié)點數(shù)可能達到上千萬甚至上億,而每個節(jié)點的好友關(guān)系可能僅有幾十或者幾百條。圖壓縮可以在不改變圖結(jié)構(gòu)的情況下壓縮節(jié)點的稀疏鄰邊,因此當使用鄰接表壓縮邊時,節(jié)點的排序非常重要。通過節(jié)點重排算法可以更好地降低圖的壓縮率,每個節(jié)點的鄰邊以鄰接表保存,其次利用編碼技術(shù)壓縮節(jié)點的鄰邊??梢钥闯觯瑘D壓縮技術(shù)的目的是降低圖數(shù)據(jù)的存儲空間占用,并不保留圖的結(jié)構(gòu)特征,因此單純的圖壓縮技術(shù)產(chǎn)生的壓縮圖不是圖的結(jié)構(gòu),不能直接用于分析,必須進行解碼操作。本文的目標不僅是降低圖的存儲空間占用,而且還能直接用于挖掘和分析,因此需要結(jié)合圖摘要技術(shù)改進算法。

        文獻[14]中利用鄰接矩陣的特征提出了2-tree,2-tree能很好地壓縮鄰接矩陣,實現(xiàn)較好的時間/空間均衡,但2-tree還面臨以下問題:2-tree中還存在大量的同構(gòu)子樹;2-tree只能壓縮稀疏圖;2-tree只能表示靜態(tài)圖,不能向其中增加或者刪除邊。針對上述問題,文獻[21]中把多值決策圖(Multiple-valued Decision Diagram, MDD)和2-tree結(jié)合,提出了2-MDD,利用MDD的刪除規(guī)則和化簡規(guī)則合并相同子圖。

        2 問題定義

        在本文研究中,創(chuàng)建摘要圖采用最小描述長度(Minimum Description Length, MDL)原則[22],MDL原則的目的是尋找最好的損失模型,使得模型和編碼數(shù)據(jù)的損失最小。本文通過最小描述長度創(chuàng)建摘要圖和壓縮圖,問題定義如下:

        表1 符號及含義

        3 算法基本原理

        本文算法使用的代價模型分兩部分組成,分別是對邊進行圖摘要方式存儲的代價模型和對邊進行圖壓縮方式存儲的代價模型。對節(jié)點進行圖摘要的損失如下:

        壓縮超節(jié)點相連的超邊時的損失如下:

        通過式(1)可以得出合并一對節(jié)點的收益為:

        其中為合并和之后的節(jié)點。合并超節(jié)點對的收益表示相較于合并之前,合并之后圖的總消耗的降低量,該值越大說明收益越高。

        3.1 算法描述

        2)合并階段。合并第1)步產(chǎn)生的每個組。計算超節(jié)點的合并收益時需要查找所有其他超節(jié)點,選出最佳的那個超節(jié)點與之合并,但是這樣會非常浪費時間,因此采取分組合并的方式降低時間復(fù)雜度。

        首先根據(jù)超節(jié)點的shingle值(見3.2節(jié))將超節(jié)點劃分成多個組,每個組內(nèi)的超節(jié)點都比較相似,即有很多個公共鄰居,將這些節(jié)點合并會使得合并前后的總體邊數(shù)量大幅降低。分組后只需要對每個組內(nèi)的超節(jié)點計算合并收益,不必搜索整個超節(jié)點集,大幅縮小了查找范圍。合并完成后,執(zhí)行以下操作:

        編碼 將滿足條件的超節(jié)點之間連接超邊并更新校正邊集,對于每個超節(jié)點的所有鄰接超邊,比較壓縮存儲或者摘要存儲的消耗,選擇存儲消耗更小的方式存儲。

        GSNSC的偽代碼如算法1所示。

        算法1 GSNSC。

        while(<) do

        合并每個組

        3.2 分組階段

        分組階段的偽代碼如算法2所示。

        算法2 分組階段。

        3.3 合并階段

        合并階段的偽代碼如算法3所示。

        算法3 合并階段。

        while(||>1 &&<) do

        隨機采樣中任意節(jié)點對

        3.4 編碼階段

        當處理所有超節(jié)點后,再壓縮校正邊集。具體步驟為:首先遍歷原始圖中的每一個節(jié)點,獲取每一個節(jié)點的所有校正邊,其次計算該節(jié)點的鄰邊壓縮存儲消耗和摘要存儲消耗,如果壓縮需要的存儲代價更小,則選擇壓縮,以段的方式存儲;否則以節(jié)點對的方式存儲。至此算法結(jié)束,返回摘要壓縮圖和校正邊集合。

        編碼階段的偽代碼如算法4所示。

        算法4 編碼階段。

        6) else

        11) else

        15) 壓縮

        17) else

        3.5 算法時間復(fù)雜度分析

        3.6 算法空間復(fù)雜度分析

        4 實驗與結(jié)果分析

        4.1 實驗設(shè)置

        1)數(shù)據(jù)集。

        實驗使用的數(shù)據(jù)集如表2所示。Web-Berkstan數(shù)據(jù)集(http://snap.stanford.edu/data/)中節(jié)點代表來自berkely.edu 和stanford.edu的頁面,邊代表它們之間的連接。類似地,Web-Google和Web-NotreDame數(shù)據(jù)集中的節(jié)點分別代表谷歌和諾特丹大學(xué)網(wǎng)站的頁面。DBLP數(shù)據(jù)集中,節(jié)點代表論文作者,邊代表兩個作者之間有合作關(guān)系。Skitter數(shù)據(jù)集為Internet拓撲圖,追蹤路線從幾個分散的來源到數(shù)百萬個目的地。Youtube數(shù)據(jù)集為在線社交網(wǎng)絡(luò)數(shù)據(jù)集。

        表2 數(shù)據(jù)集描述

        2)環(huán)境設(shè)置。

        GSNSC代碼運行在一個Intel Xeon CPU E5-2650 v4 @ 2.20 GHz的linux服務(wù)器上,其中包含4個CPU,每個CPU12核,語言為C++。

        3)評價指標。

        4.2 對比算法

        針對壓縮率對比實驗,對比算法如下。

        1)DPGS[6]。原算法的損失函數(shù)是編碼長度而不是邊和節(jié)點的數(shù)量,實驗中采用本文中的損失函數(shù)。

        2)SWeG[5]。該算法采用和本文算法相同的分組方式,但是在合并步驟上有所不同。

        3)GREEDY[3]。該算法是圖摘要的經(jīng)典貪心算法。

        4)GreedyCS[4]。和本文算法類似,該算法也是采用圖摘要和圖壓縮結(jié)合的方法降低圖的規(guī)模。

        5)SLUGGER[18]。該算法貪婪地將節(jié)點合并為超節(jié)點,同時維護和利用它們的層次結(jié)構(gòu)。

        4.3 壓縮率和運行時間實驗

        不同算法的壓縮率和運行時間實驗結(jié)果對比如表3所示,其中:OOT代表運行時間太久或內(nèi)存超過限制,屬于無效數(shù)據(jù);壓縮率為輸出圖與輸入圖大小的比值,值越小,效果越好。設(shè)置閾值分別為0.1、0.2和0.3(SLUGGER無閾值區(qū)分),對比每種算法的實驗結(jié)果。對于同一數(shù)據(jù)集的同一個方法,當越大時,效果越差,這是因為越大,合并節(jié)點的門檻就越高,節(jié)點越不容易被合并,因此輸出圖中的節(jié)點數(shù)和邊數(shù)就越多,導(dǎo)致壓縮率更高。與SLUGGER相比,GSNSC的壓縮率至少降低了23個百分點;與SweG相比,壓縮率至少降低了13個百分點。通過每個數(shù)據(jù)集上的結(jié)果可以看出,GSNSC的壓縮率效果明顯優(yōu)于其他對比算法,原因是該算法相較于其他對比算法,不僅壓縮摘要圖中的超邊,還壓縮了用于恢復(fù)原圖的校正邊集,后者對壓縮率降低做出最大貢獻,這是因為校正邊集通??偸沁h大于超邊集,兩個超節(jié)點之間最多有一條超邊,但是可以有多條校正邊。對于不同的數(shù)據(jù)集,同種方法壓縮率相差較大;從結(jié)果可以看出,圖的密度越低,壓縮率就越好。

        表3 不同算法在6個數(shù)據(jù)集上的實驗結(jié)果對比

        4.4 θ和壓縮率的關(guān)系

        圖2展示了在Web-NotreDame數(shù)據(jù)集下測試的和壓縮率之間的關(guān)系??梢钥闯?,當值為0.05時壓縮率最低,當值逐漸變大,壓縮率也在不斷升高;這是由于越大,節(jié)點合并的閾值就越高,因此效果越差。

        圖2 Web-NotreDame數(shù)據(jù)集上和壓縮率的關(guān)系

        4.5 T和壓縮率的關(guān)系

        圖3展示了在Web-NotreDame數(shù)據(jù)集上,當=0.2時迭代次數(shù)和壓縮率之間關(guān)系的實驗結(jié)果。可以看出,在的取值為1到5時,壓縮率下降較快;這是由于此時太小,每次循環(huán)合并的節(jié)點數(shù)是有限的,因此每增加1,壓縮率就大幅下降。當>5時,越往后壓縮率不斷上下浮動并趨于穩(wěn)定,這很大程度上是由于算法運行具有隨機性。

        圖3 Web-NotreDame數(shù)據(jù)集上T和壓縮率的關(guān)系(θ=0.2)

        4.6 圖查詢

        通過期望鄰接矩陣對圖進行查詢將會比在原始圖上更快,這是因為摘要圖中的節(jié)點數(shù)很少,因此鄰接矩陣相較于原始圖更小,因此查詢效率更高,本文從圖查詢的準確度方面評估摘要圖的好壞。

        對比GSNSC、DPGS和SweG這3種算法在Web-NotreDame數(shù)據(jù)集上的度誤差,在Web-NotreDame和Web-Google數(shù)據(jù)集上的鄰接誤差,實驗結(jié)果如表4所示??梢钥闯?,GSNSC的度誤差和鄰接誤差更低,與SweG相比,度誤差降低了41.6%,說明GSNSC在針對圖查詢的準確率上優(yōu)于其他對比算法。

        表4 不同數(shù)據(jù)集上3種算法的度誤差和鄰接誤差對比

        5 結(jié)語

        本文結(jié)合圖摘要和圖壓縮的優(yōu)勢,提出一種圖摘要和圖壓縮的融合算法(GSNSC),用于壓縮大規(guī)模圖數(shù)據(jù)。經(jīng)過理論分析和實驗驗證,結(jié)果表明所提算法具有較好的效果,所提融合算法具有一定的可行性。然而,本文算法目前只適用于簡單靜態(tài)同質(zhì)圖,還無法適用于異質(zhì)圖、屬性圖和動態(tài)圖等。未來可以通過設(shè)置損失函數(shù)等方法,將本文算法擴充至屬性圖,根據(jù)不同節(jié)點的類型擴充至異質(zhì)圖,加入時間屬性擴充至動態(tài)圖。

        [1] LEE K, JO H, KO J, et al. SSumM: sparse summarization of massive graphs[C]// Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2020: 144-154.

        [2] MACCIONI A, ABADI D J. Scalable pattern matching over compressed graphs via dedensification[C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2016: 1755-1764.

        [3] NAVLAKHA S, RASTOGI R, SHRIVASTAVA N. Graph summarization with bounded error[C]// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2008: 419-432.

        [4] SEO H, PARK K, HAN Y, et al. An effective graph summarization and compression technique for a large-scaled graph[J]. The Journal of Supercomputing, 2020, 76(10): 7906-7920.

        [5] SHIN K, GHOTING A, KIM M, et al. SWeG: lossless and lossy summarization of web-scale graphs[C]// Proceedings of the 2019 World Wide Web Conference. Republic and Canton of Geneva: International World Wide Web Conferences Steering Committee, 2019: 1679-1690.

        [6] ZHOU H, LIU S, LEE K, et al. DPGS: degree-preserving graph summarization[C]// Proceedings of the 2021 SIAM International Conference on Data Mining. Philadelphia, PA: SIAM, 2021:280-288.

        [7] ZHU L, GHASEMI-GOL M, SZEKELY P, et al. Unsupervised entity resolution on multi-type graphs[C]// Proceedings of the 2016 International Semantic Web Conference, LNCS 9981. Cham: Springer, 2016: 649-667.

        [8] TIAN Y, HANKINS R A, PATEL J M. Efficient aggregation for graph summarization[C]// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2008: 567-580.

        [9] YONG Q, HAJIABADI M, SRINIVASAN V, et al. Efficient graph summarization using weighted LSH at billion-scale[C]// Proceedings of the 2021 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2021: 2357-2365.

        [10] UR R S, NAWAZ A, ALI T, et al. g-Sum: a graph summarization approach for a single large social network[J]. EAI Endorsed Transactions on Scalable Information Systems, 2021, 8(32): No.e2.

        [11] SACENTI J A P, FILETO R, WILLRICH R. Knowledge graph summarization impacts on movie recommendations[J]. Journal of Intelligent Information Systems, 2022, 58(1): 43-66.

        [12] BOLDI P, SANTINI M, VIGNA S. Permuting web graphs[C]// Proceedings of the 2009 International Workshop on Algorithms and Models for the Web-Graph, LNCS 5427. Berlin: Springer, 2009: 116-126.

        [13] HERNáNDEZ C, NAVARRO G. Compressed representations for Web and social graphs[J]. Knowledge and Information Systems, 2014, 40(2): 279-313.

        [14] BRISABOA N R, LADRA S, NAVARRO G.2-trees for compact Web graph representation[C]// Proceedings of the 2009 International Symposium on String Processing and Information Retrieval, LNCS 5721. Berlin: Springer, 2009: 18-30.

        [15] FRANCISCO A P, GAGIE T, K?PPL D, et al. Graph compression for adjacency-matrix multiplication[J]. SN Computer Science, 2022, 3(3): No.193.

        [16] EMAMZADEH ESMAEILI NEJAD A, JAHROMI M Z, TAHERI M. Graph compression based on transitivity for neighborhood query[J]. Information Sciences, 2021, 576: 312-328.

        [17] YANG S, YANG Z, CHEN X, et al. Distributed aggregation-based attributed graph summarization for summary-based approximate attributed graph queries[J]. Expert Systems with Applications, 2021, 176: No.114921.

        [18] LEE K, KO J, SHIN K. SLUGGER: lossless hierarchical summarization of massive graphs[C]// Proceedings of the IEEE 38th International Conference on Data Engineering. Piscataway: IEEE, 2022: 472-484.

        [19] KE X, KHAN A, BONCHI F. Multi-relation graph summarization[J]. ACM Transactions on Knowledge Discovery from Data, 2022, 16(5): No.82.

        [20] KANG S, LEE K, SHIN K. Personalized graph summarization: formulation, scalable algorithms, and applications[C]// Proceedings of the IEEE 38th International Conference on Data Engineering. Piscataway: IEEE, 2022: 2319-2332.

        [21] 董榮勝,張新凱,劉華東,等. 大規(guī)模圖數(shù)據(jù)的2-MDD表示方法與操作研究[J]. 計算機研究與發(fā)展, 2016, 53(12):2783-2792.(DONG R S, ZHANG X K, LIU H D, et al. Representation and operations research of2-MDD in large-scale graph data[J]. Jouanal of Computer Research and Development, 2016, 52(12):2783-2792.)

        [22] RISSANEN J. Modeling by shortest data description[J]. Automatica, 1978, 14(5): 465-471.

        [23] BRODER A Z, CHARIKAR M, FRIEZE A M, et al. Min-wise independent permutations[J]. Journal of Computer and System Sciences, 2000, 60(3): 630-659.

        [24] LeFEVRE K , TERZI E. GraSS: graph structure summarization[C]// Proceedings of the 2010 SIAM International Conference on Data Mining. Philadelphia, PA: SIAM, 2010: 454-465.

        Graph summarization algorithm based on node similarity grouping and graph compression

        HONG Yu1, CHEN Hongchang2, ZHANG Jianpeng2*, HUANG Ruiyang2

        (1,,450002,;2,,450002,)

        To solve the problem that the current graph summarization methods have high compression ratios and the graph compression algorithms cannot be directly used in downstream tasks, a fusion algorithm of graph summarization and graph compression was proposed, which called Graph Summarization algorithm based on Node Similarity grouping and graph Compression (GSNSC). Firstly, the nodes were initialized as super nodes, and the super nodes were grouped according to the similarity. Secondly, the super nodes of each group were merged until the specified number of times or nodes were reached. Thirdly, super edges and corrected edges were added between the super nodes for reconstructing the original graph. Finally, for the graph compression part, the cost of compressing and summarizing the adjacent edges of each super node were judged, and the less expensive one in these two was selected to execute. Experiments of graph compression ratio and graph query were conducted on six datasets such as Web-NotreDame, Web-Google and Web-Berkstan. Experimental results on six datasets show that, the proposed algorithm has the compression ratio reduced by at least 23 percentage points compared with SLUGGER (Scalable Lossless sUmmarization of Graphs with HiERarchy) algorithm, and the compression ratio decreased by at least 13 percentage points compared with SWeG (Summarization of Web-scale Graphs) algorithm. Experimental results on Web-NotreDame dataset show that the degree error of the proposed algorithm is reduced by 41.6% compared with that of SWeG algorithm. The above verifies that the proposed algorithm has better graph compression ratio and graph query accuracy.

        graph summarization; graph compression; graph query; super edge; Minimum Description Length (MDL)

        1001-9081(2023)10-3047-07

        10.11772/j.issn.1001-9081.2022101535

        2022?10?17;

        2023?01?31;

        國家自然科學(xué)基金資助項目(62002384);中國博士后科學(xué)基金資助項目(2020M683760)。

        宏宇(1998—),男,河北廊坊人,碩士研究生,主要研究方向:圖數(shù)據(jù)挖掘; 陳鴻昶(1964—),男,河南新密人,教授,博士生導(dǎo)師,博士,主要研究方向:大數(shù)據(jù)分析、通信與信息系統(tǒng); 張建朋(1988—),男,河北廊坊人,助理研究員,博士,主要研究方向:大數(shù)據(jù)分析; 黃瑞陽(1986—),男,福建漳州人,副研究員,博士,主要研究方向:知識圖譜、文本挖掘。

        TP391

        A

        2023?01?31。

        This work is partially supported by National Natural Science Foundation of China (62002384), China Postdoctoral Science Foundation (2020M683760).

        HONG Yu, born in 1998, M. S. candidate. His research interests include graph data mining.

        CHEN Hongchang, born in 1964, Ph. D., professor. His research interests include big data analysis, communication and information systems.

        ZHANG Jianpeng, born in 1988, Ph. D., research assistant. His research interests include big data analysis.

        HUANG Ruiyang, born in 1986, Ph. D., associate research fellow. His research interests include knowledge graph, text mining.

        猜你喜歡
        壓縮率集上校正
        Cookie-Cutter集上的Gibbs測度
        劉光第《南旋記》校正
        國學(xué)(2020年1期)2020-06-29 15:15:30
        鏈完備偏序集上廣義向量均衡問題解映射的保序性
        水密封連接器尾部接電纜的優(yōu)化設(shè)計
        纏繞墊片產(chǎn)品質(zhì)量控制研究
        一類具有校正隔離率隨機SIQS模型的絕滅性與分布
        復(fù)扇形指標集上的分布混沌
        機內(nèi)校正
        多載波通信系統(tǒng)中CQI無損壓縮法研究
        分布式多視點視頻編碼在應(yīng)急通信中的應(yīng)用
        久久精品国产亚洲av热九| 中文字幕乱伦视频| 久久精品国产日本波多麻结衣| 亚洲无线码1区| 亚洲国产最新免费av| 亚洲精品成人无限看| 一本无码人妻在中文字幕免费| 国产一级淫片免费播放电影| 亚洲产在线精品亚洲第一页| 日本在线精品一区二区三区| 久久精品国产网红主播| 国产午夜精品理论片| 男女男生精精品视频网站| 久久久国产精品123| 亚洲а∨精品天堂在线| 免费无遮挡无码视频在线观看| 国产精品久久国产三级国| 少妇精品亚洲一区二区成人| 国产真实偷乱视频| 9久9久女女热精品视频免费观看| 久久亚洲综合亚洲综合| 欧美a级在线现免费观看| 色噜噜狠狠色综合成人网| 欧美日韩国产乱了伦| av手机免费在线观看高潮| 日产学生妹在线观看| 一国产区在线观看| 亚洲精品成人久久av| 亚洲av无码国产精品色软件| 亚洲 暴爽 av人人爽日日碰| 久久91精品国产91久久麻豆| 中文字幕高清不卡视频二区| 亚洲精品久久久久中文字幕| 欧美国产高清| 国内揄拍国内精品久久| 韩国三级在线观看久| 人人妻人人澡人人爽欧美一区| a级毛片100部免费看| 一区二区视频观看在线| 国产内射一级一片内射高清视频1 成人av一区二区三区四区 | 久久久久久久人妻无码中文字幕爆|