子圖
- 基于Spark平臺的惡意軟件最大頻繁子圖挖掘方法
022）0 引言子圖挖掘（subgraph mining）是圖數(shù)據(jù)挖掘的一個重要分支，它已經(jīng)成為數(shù)據(jù)挖掘中的一個研究熱點［1］，旨在從大規(guī)模復(fù)雜圖數(shù)據(jù)中發(fā)現(xiàn)有意義的子圖模式。隨著社交網(wǎng)絡(luò)、互聯(lián)網(wǎng)、生物信息學(xué)等領(lǐng)域的快速發(fā)展，大量的圖數(shù)據(jù)已經(jīng)成為現(xiàn)代科學(xué)研究的重要來源，在社交網(wǎng)絡(luò)中可以發(fā)現(xiàn)社交網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)、關(guān)系網(wǎng)絡(luò)等信息，在推進(jìn)系統(tǒng)中可以發(fā)現(xiàn)用戶間的相關(guān)關(guān)系、用戶興趣等信息，從而提高推薦系統(tǒng)的準(zhǔn)確性，在網(wǎng)絡(luò)安全中可以發(fā)現(xiàn)網(wǎng)絡(luò)攻擊行為、惡意軟件等信息。但是
現(xiàn)代計算機(jī) 2023年14期2023-09-25
- 雙網(wǎng)絡(luò)中影響力凝聚子圖發(fā)現(xiàn)算法
系緊密連接的凝聚子圖[2-3]，這些凝聚子圖中往往包含著人們需要的重要信息.由于大規(guī)模真實網(wǎng)絡(luò)中凝聚子圖數(shù)量眾多，因此尋找具有影響力（重要性）的凝聚子圖成為當(dāng)前的熱點問題，有重要現(xiàn)實意義[4-9].目前，許多影響力圖模型已經(jīng)被提出.首先，針對圖中單個影響力結(jié)點，MIPPLA 模型[10]和EDBC 模型[11]被提出.隨后，文獻(xiàn)[12-16]提出不同算法用于發(fā)現(xiàn)圖中影響力凝聚子圖.但文獻(xiàn)[12-16]所提算法往往僅限于解決單網(wǎng)絡(luò)中影響力凝聚子圖計算問題.隨
計算機(jī)研究與發(fā)展 2023年9期2023-09-22
- 包含所有固定階數(shù) k 樹的一類圖
新的圖包含G作為子圖。關(guān)鍵詞：k樹；完全圖；子圖中圖分類號：O157.5??文獻(xiàn)標(biāo)識碼：A一、介紹本文所研究的圖都是簡單圖。在本文中，一個圖的階數(shù)是指這個圖的頂點的個數(shù)。我們用Pm、Km和Km，n表示m階路、m階完全圖以及m+n階完全二部圖。用Km表示m階完全圖的補(bǔ)圖。設(shè)H、G為兩個簡單圖，記E（H，G）={uv|u∈V（H），v∈V（G）}。H∪G表示頂點集為V（H）∪V（G），邊集為E（H）∪E（G）的圖。H∨G表示頂點集為V（H）∪V（G），邊集為E
科技風(fēng) 2023年11期2023-05-30
- 禁用子圖為P3∪mP2的圖色數(shù)上界
滿足其所有的導(dǎo)出子圖的色數(shù)和團(tuán)數(shù)也相等。與此同時，Berge提出了兩個關(guān)于完美圖的猜想（弱完美圖猜想和強(qiáng)完美圖猜想）。弱完美圖猜想是：一個圖是完美圖當(dāng)且僅當(dāng)其補(bǔ)圖是完美圖，隨后被Lovász[4]證明，稱為完美圖定理。強(qiáng)完美圖猜想是：一個圖是完美圖當(dāng)且僅當(dāng)其本身和其補(bǔ)圖都不含長度大于等于5的奇長圈為導(dǎo)出子圖，在2006年被Chudnovsky等[5]證明，稱為強(qiáng)完美圖定理?；谕昝缊D的定義，Gyárfás[6]提出了圖的色界函數(shù)的概念，即：什么樣的圖存在以
商洛學(xué)院學(xué)報 2022年4期2022-09-21
- Top-k頻繁子圖挖掘的差分隱私保護(hù)算法
得非常流行。頻繁子圖挖掘是圖挖掘中一個重要且有趣的問題，其目標(biāo)是提取給定數(shù)據(jù)集中的出現(xiàn)次數(shù)高于指定閾值的子圖[1]。頻繁子圖挖掘的應(yīng)用非常廣泛，推薦系統(tǒng)就是最常見的應(yīng)用，通過對瀏覽痕跡的挖掘，推斷用戶的購買意向，從而進(jìn)行相關(guān)的推薦。同時，在軟件工程、生物化學(xué)、金融等領(lǐng)域，頻繁子圖挖掘都有非常廣闊的應(yīng)用前景[2-3]。盡管頻繁子圖挖掘具有很高的實際應(yīng)用價值，但是在挖掘和發(fā)布子圖時都存在著隱私泄露的風(fēng)險[4]。假設(shè)有一個醫(yī)療保健的圖數(shù)據(jù)庫D，D中的每條記錄表示
計算機(jī)技術(shù)與發(fā)展 2022年5期2022-05-30
- 基于旅客-航班異構(gòu)網(wǎng)絡(luò)的旅客同行子圖抽取
言民航旅客同行子圖抽取旨在從旅客-航班異構(gòu)網(wǎng)絡(luò)中抽取具有潛在同行關(guān)系的旅客子圖，其本質(zhì)是根據(jù)部分旅客出行具有相似性的特點對旅客進(jìn)行劃分，使得子圖內(nèi)部連接緊湊，子圖外部連接稀疏。旅客-航班異構(gòu)網(wǎng)絡(luò)是由描述旅客選擇航班關(guān)系的旅客-航班二部圖，以及描述航班相似性的航班同構(gòu)網(wǎng)絡(luò)構(gòu)成。民航旅客同行子圖具有廣泛的應(yīng)用，例如：發(fā)現(xiàn)潛在同行旅客，為具有潛在同行的旅客預(yù)留座位；發(fā)現(xiàn)旅客潛在出行意圖，為具有相同出行意圖的旅客進(jìn)行航班推薦；通過對危險旅客及其同行旅客的監(jiān)控，為
計算機(jī)應(yīng)用與軟件 2022年2期2022-02-19
- 包含所有固定階數(shù)2樹作為子圖的圖的構(gòu)造
個頂點的2樹作為子圖。關(guān)鍵詞：2樹;完全圖;子圖中圖分類號：O157.5??文獻(xiàn)標(biāo)識碼：AConstructing?graphsto?containing?every?2tree?as?a?subgraph?with?prescribed?sizeZeng?Deyan?Zhai?DongyangInstitute?of?Technology，?University?of?Sanya?HainanSanya?572022Abstract：A?simple?g
科技風(fēng) 2021年28期2021-10-18
- 無K3子圖的圖中1-因子計數(shù)
，可以解決無K3子圖的圖中1-因子計數(shù)．1 定義和引理定義1令S(n)={Ki：1≤i≤n}，n≥1，并且Ki是有i個頂點的完全圖，如果M是圖G的一個子圖，且M的任意分支都同構(gòu)于S(n)={Ki：1≤i≤n}的某一元素，那么M叫作圖G的一個S(n)-子圖，如果M是圖G的一個生成子圖，那么M叫作圖G的一個S(n)-因子．恰有k個分支的S(n)-因子的個數(shù)記為N(G，k)．S(n)-因子計數(shù)的表示公式如下．圖論中分支分析方法公式如下：2 主要結(jié)果用f(G)記圖
大連理工大學(xué)學(xué)報 2021年5期2021-09-24
- 關(guān)于2樹子圖的一些性質(zhì)
022)1 2樹子圖用Km，Km,n，Pk分別表示頂點數(shù)為m的完全圖，m×n階完全二部圖，頂點數(shù)為k的路。設(shè)v∈V(G),X?V(G)，用G[X]和NX(v)分別表示在G中由點集X誘導(dǎo)的子圖和頂點v在點集X中的所有鄰點構(gòu)成的集合。記G-v=G[V(G)/v]，G-X=G[V(G)/X]。文中未定義的標(biāo)記參見文獻(xiàn)[1]。圖1 7階2樹星圖T(7)Fig.1 7 vertices 2-tree star map T(7)若n≥3，定義F(n)是在F(n-1)的
黑龍江科學(xué) 2021年14期2021-08-06
- 一類笛卡兒乘積圖的PM-緊鄰性質(zhì)
),則稱H是G的子圖.稱不包含圈的圖為無圈圖或森林,稱連通的無圈圖為樹.用Pn表示n個頂點的路,Cn表示n個頂點的圈,Tn為n個頂點的樹.在完全二部圖G(X,Y)中,|X|= 1 或|Y|= 1 時,稱這個圖為星圖,用Sn表示n+ 1 個頂點的星圖.若Vi?V,VVi表示從V中刪去Vi.以V(G)的非空子集Vi為頂點集,兩端點均在Vi中的全部邊所組成的子圖,稱G由Vi導(dǎo)出的子圖,記為G[Vi].對圖G中的2 度頂點依次收縮兩條與其關(guān)聯(lián)的邊稱為該2 度頂點的
閩南師范大學(xué)學(xué)報(自然科學(xué)版) 2021年2期2021-06-29
- 異構(gòu)屬性網(wǎng)絡(luò)中統(tǒng)計顯著密集子圖發(fā)現(xiàn)算法研究
則本文研究的密集子圖(Densest Subgraph，DS)是圖G中最稠密或具有最高密度的子圖[1].而密集子圖發(fā)現(xiàn)可以解決現(xiàn)實生活中的許多問題，比如它可以被用于事件檢測，生物分析以及社區(qū)發(fā)現(xiàn)等方面.具體地，在事件檢測方面，發(fā)現(xiàn)的密集子圖是社交網(wǎng)絡(luò)中的“稠密部分”，可代表一個事件[2]；在生物分析方面，密集子圖可以幫助生物學(xué)的研究人員鑒定基因組DNA[3]和基因注釋圖[4]中的調(diào)控基序；在社區(qū)發(fā)現(xiàn)方面，密集子圖可以在社交媒體中找到具有相同興趣的社區(qū)[5]
小型微型計算機(jī)系統(tǒng) 2021年10期2021-02-28
- 可滿著色圖的一種結(jié)構(gòu)
)，則A0的生成子圖是GC，其他Ai(i=1,2,…,p)的生成子圖都是完全圖Kn。結(jié)論2vijv(i+1)j∈E(Mp(G)C),(i=0,1,…,p-1;j=1,2,…,n)。結(jié)論3若v0jv0k∈E(Mp(G)C)，則vijv(i+1)k∈E(Mp(G)C)，(i=0,1,…,p-1;1≤j,k≤n)由此，得到定理1的證明:情況1當(dāng)GC中有一條Hamilton路，不妨設(shè)為v01v02…v0n。則可以用如下方法找到Mp(G)C的一條Hamilton路:
上海電機(jī)學(xué)院學(xué)報 2020年6期2021-01-07
- 基于相鄰基準(zhǔn)子圖灰度統(tǒng)計相關(guān)的快速互信息匹配算法*
配過程中相鄰基準(zhǔn)子圖間灰度統(tǒng)計特征之間的相關(guān)性，通過差量法減少每一個匹配位置互信息的計算量來加快匹配速度。與已有的以灰度壓縮、特征提取或采取優(yōu)化搜索策略等快速互信息匹配方法相比，該方法既沒有減少參與匹配的像素數(shù)，也無需對圖像灰度等級進(jìn)行處理，不會對匹配精度造成影響。1 圖像熵及互信息匹配圖像熵描述了圖像信源的平均信息量，反映了圖像灰度的統(tǒng)計信息，相似的兩幅圖像其圖像熵也相近。利用互信息進(jìn)行圖像匹配的實質(zhì)是：當(dāng)兩幅圖像在空間位置配準(zhǔn)時，其重疊部分所對應(yīng)像素對
彈箭與制導(dǎo)學(xué)報 2020年6期2020-03-29
- 不含H子圖的圖上的最大割下界
G)表示G的二部子圖包含的最大邊數(shù)。給定一個正整數(shù)m，令f(m)表示所有具有m條邊的圖G的f(G)的最小值。經(jīng)典的最大割問題旨在尋找f(m)的值，該問題有非常廣泛的應(yīng)用價值，被應(yīng)用于復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)分析、大規(guī)模集成電路設(shè)計(VLSI)，同時也在統(tǒng)計物理學(xué)中用來研究處理自旋玻璃(Spin glass)狀態(tài)的重要模型之一。猜想0.1[7]. 對于任意給定的圖H，存在常數(shù)ε(H)>0，使得f(m,H)≥m/2+Ω(m3/4+ε)。提高猜想0.1中下界的誤差項非常
福建工程學(xué)院學(xué)報 2020年1期2020-03-26
- 一種大規(guī)模時序語義網(wǎng)絡(luò)中突發(fā)持續(xù)性事件搜索算法
序圖中的突發(fā)持續(xù)子圖，突發(fā)持續(xù)子圖表示的是一個稠密子圖在很短的時間出現(xiàn)，并且持續(xù)一段時間。換句話來說，我們旨在時序圖中搜索出在很短時間內(nèi)發(fā)生且具有持續(xù)性的稠密連通子圖。在時序圖中搜索出突發(fā)持續(xù)子圖可以幫助我們應(yīng)對生活中許多實際問題。例如，在緊急事件檢測方面，突發(fā)持續(xù)子圖可用于通信網(wǎng)絡(luò)中緊急事件檢測[4]，在商業(yè)協(xié)作方面，突發(fā)持續(xù)子圖可以找到在商業(yè)協(xié)作網(wǎng)絡(luò)中最親密的合作關(guān)系，幫助我們找到新的商業(yè)機(jī)會[5]。目前為止，時序圖中稠密子圖挖掘問題[6,7,8,9]
電子技術(shù)與軟件工程 2020年24期2020-03-16
- 基于Spark 的大規(guī)模單圖頻繁子圖算法
繁軌跡挖掘和頻繁子圖的研究也主要針對于社交網(wǎng)絡(luò)，但發(fā)現(xiàn)學(xué)生頻繁消費行為特征［3］、解決學(xué)生人際關(guān)系問題，以及預(yù)防惡劣事件的發(fā)生，不僅對構(gòu)建和諧校園環(huán)境有著十分重要的作用，也給一卡通建設(shè)提供了可參照的標(biāo)準(zhǔn)。目前頻繁子圖的研究主要集中在圖集的研究，像社交網(wǎng)絡(luò)或萬維網(wǎng)鏈接圖等，應(yīng)用于校園卡消費數(shù)據(jù)的研究則不多見，而單圖數(shù)據(jù)并不適合被劃分為圖集再操作，主要因為大規(guī)模單圖的頂點數(shù)量經(jīng)常在百萬級別以上，遠(yuǎn)超圖集中的單個圖，這樣最后得到的頻繁模式子［4～6］圖規(guī)模也遠(yuǎn)比
計算機(jī)與數(shù)字工程 2019年10期2019-11-12
- 面向子圖匹配的社會網(wǎng)絡(luò)隱私保護(hù)方法*
，在云平臺內(nèi)進(jìn)行子圖匹配[1-4]時保護(hù)隱私信息是非常重要的。K-自同構(gòu)算法[5]是傳統(tǒng)的社會網(wǎng)絡(luò)隱私保護(hù)算法，這種方法在處理大規(guī)模社會網(wǎng)絡(luò)圖時，處理效率會大幅度下降[6]而且不能保證較高的數(shù)據(jù)可用性。傳統(tǒng)的K-自同構(gòu)算法在原始圖中添加噪聲邊，使原始圖中的每個節(jié)點都有至少有k-1 個對稱節(jié)點。如圖1 是社會網(wǎng)絡(luò)原始圖，在原始圖的基礎(chǔ)上添加3 條噪聲邊，同時根據(jù)表1對原始圖的標(biāo)簽進(jìn)行標(biāo)簽分組泛化[7]后使原始圖轉(zhuǎn)換成2-自同構(gòu)圖，如圖2。可以看出K-自同構(gòu)算
計算機(jī)與生活 2019年9期2019-09-14
- 交叉立方體的最大導(dǎo)出子圖與擁塞
立方體的最大導(dǎo)出子圖，而后利用交叉立方體的最大導(dǎo)出子圖估計交叉立方體嵌入一維陣列光網(wǎng)絡(luò)的擁塞，并通過此擁塞證明了張靜所提出的在一維陣列波分復(fù)用光網(wǎng)絡(luò)中實現(xiàn)半雙工或全雙工交叉立方體通信模式所需波長數(shù)的最優(yōu)性。參考文獻(xiàn)：[1]YangX，EvansDJ，MegsonGM.Thelocallytwistedcubes[J].InternationalJournalofComp-uterMathematics，2005，82（4）：401-413.[2]EfeK.
科技風(fēng) 2019年13期2019-06-11
- 臨界完全圖Ramsey數(shù)
或存在單色的紅色子圖G，或存在單色的藍(lán)色子圖H.實際上，在Ramsey數(shù)的研究中，并不需要完全圖的所有邊即可找到單色的紅色子圖G或單色的藍(lán)色子圖H.因此，Hook等[1]首先在文獻(xiàn)[1]中提出臨界星圖Ramsey數(shù)r*(G,H)并確定了一些臨界星圖Ramsey數(shù).下面給出臨界星圖Ramsey數(shù)的定義.定義1設(shè)r=r(G,H)為Ramsey數(shù)，臨界星圖Ramsey數(shù)r*(G,H)定義為最小的正整數(shù)n，使得圖Kr-K1,r-1-n的任意紅藍(lán)二邊著色或存在單色的
同濟(jì)大學(xué)學(xué)報（自然科學(xué)版） 2019年2期2019-04-02
- 不含3K1和K1+C4為導(dǎo)出子圖的圖色數(shù)上界?
對于G的任一導(dǎo)出子圖H都有色數(shù)?χ（H）和團(tuán)數(shù) ω（H），則稱圖 G 稱為完美圖［1］。對于給定圖H，如果圖G不含與H同構(gòu)的圖為導(dǎo)出子圖，則稱圖G是 H-free的（不含 H為導(dǎo)出子圖）。Gyárfás［2］在此基礎(chǔ)上，提出了用 f（ω）表示圖的色數(shù)上界的概念，并給出猜想：設(shè)F是一個森林，對于每一個F-free的圖G，都存在整數(shù)函數(shù)f（x，y）使得 χ（G）≤f（F，ω（G））。關(guān)于此猜想的一些特殊情形的結(jié)論可參閱文獻(xiàn)［3～12］。設(shè)G1和G2為兩個圖，它
計算機(jī)與數(shù)字工程 2019年3期2019-03-26
- 哈密爾頓-連通圖的拉普拉斯譜充分條件
成的圖，且不為其子圖。(5.2.1)若Gc是由Hc添加兩條邊構(gòu)成的圖，則或(5.2.2)若Gc是由Hc添加3條或3條以上的邊構(gòu)成的圖，則由(5.2.1)推論1知Gc只可能是由或添加邊構(gòu)成的圖，且有，矛盾。(7)若 H=K4∨(K1,3+K2)，則 Hc=4K1+((K1+K3)∨ 2K1)，且，e(Hc)=11，由 引 理 2得，則 有 110=n(2n-9)≥這樣Hc=Gc,即G=H=K4∨(K1,3+K2)，或Hc是Gc的真生成子圖，即Gc是由Hc添加
安慶師范大學(xué)學(xué)報(自然科學(xué)版) 2019年3期2019-03-15
- 時序網(wǎng)絡(luò)的頻繁演化模式挖掘
數(shù)據(jù)集中發(fā)現(xiàn)頻繁子圖。但目前大量工作的焦點集中于如何在靜態(tài)圖中挖掘出頻繁子圖，而對具有時間維度的動態(tài)網(wǎng)絡(luò)中的頻繁模式挖掘的研究較少。信息網(wǎng)絡(luò)通常隨著時間進(jìn)行演化，在此時，我們稱它為動態(tài)信息網(wǎng)絡(luò)。在一個信息網(wǎng)絡(luò)中，一個新連接的形成、現(xiàn)存連接的消失或者連接屬性的改變這些現(xiàn)象廣泛存在。簡單地說，對應(yīng)到一個社會網(wǎng)絡(luò)，這些現(xiàn)象表現(xiàn)為個體之間關(guān)系的建立或者解除（朋友、親人等），或者從一種關(guān)系轉(zhuǎn)變?yōu)榱硪环N關(guān)系（朋友-＞親人）。特別地，這些關(guān)系的建立是基于現(xiàn)存的關(guān)系之上，
現(xiàn)代計算機(jī) 2019年2期2019-03-02
- 禁用子圖為C4和K1∪P4的圖色數(shù)上界
E(G)}所構(gòu)成子圖稱為U的導(dǎo)出子圖，記為G[U]。使得G[U]為完全圖的頂點子集U稱為圖G的團(tuán)，階數(shù)最大的團(tuán)稱為G的最大團(tuán)，最大團(tuán)的階數(shù)稱為G的團(tuán)數(shù)，記為ω(G)。如果對于圖G任意一個導(dǎo)出子圖H，都有χ(H)與ω(H)相等，則稱圖G為完美圖。在完美圖概念的基礎(chǔ)上，Gyárfás[2]利用圖團(tuán)數(shù)的函數(shù)f(ω)來表示圖的色數(shù)上界。由于對于任意圖G都有χ(G)≥ω(G)，因此，完美圖就是以f(x)=x為色數(shù)界的圖類。Gyárfás[2]給出猜想：令F為一森林，
商洛學(xué)院學(xué)報 2019年2期2019-02-21
- 一類特殊連通圖的性質(zhì)
′)是圖G的一個子圖.對于頂點集V(G)的任意非空子集S，那么稱以S為頂點集合，以兩個端點都在集合S中的所有的邊的集合構(gòu)成的子圖為G的由S導(dǎo)出的子圖，極為G[S]，稱集合NG(v)={uV(G)；uvE(G)}為點v在圖G中的鄰域.我們稱完全二部圖K1,3為爪.令H是一個給定的圖，如果G不包含H的導(dǎo)出子圖，則圖G被稱為無H的.那么H被稱為G的一個禁用子圖.對于一個圖類，如果對于每一個H∈，G都是無H的，那么圖G被稱為無的.一般的，我們通常從圖的參數(shù)角度去研
太原師范學(xué)院學(xué)報(自然科學(xué)版) 2019年1期2019-01-19
- 求解最大團(tuán)問題的并行多層圖劃分方法
無序樹同構(gòu)問題、子圖同構(gòu)問題等都可以轉(zhuǎn)化為最大團(tuán)問題，在實踐中也有廣泛的應(yīng)用，如圖像處理[2]、生物計算[3]、信號傳輸[4]、社會網(wǎng)絡(luò)分析[5]、故障診斷[6]等，對最大團(tuán)問題的研究具有較高的理論價值和現(xiàn)實意義。在大數(shù)據(jù)時代下，實際圖中節(jié)點的海量性和分析的復(fù)雜性，對最大團(tuán)問題的研究在速度和精度上都提出了更高的要求，而目前有關(guān)求解最大團(tuán)的相關(guān)算法比如回溯法[7]、分支限界法[8]、蟻群算法[9]、順序貪婪算法[10]和遺傳算法[11]等，都無法直接用于大型
計算機(jī)應(yīng)用 2018年12期2019-01-07
- 大規(guī)模網(wǎng)絡(luò)圖中4節(jié)點子圖數(shù)量快速估計算法
在大型復(fù)雜網(wǎng)絡(luò)的子圖集合中,存在著大量包含3～5個節(jié)點的小型無向子圖,這類子圖能夠反映復(fù)雜網(wǎng)絡(luò)的一些基礎(chǔ)結(jié)構(gòu)特性,對此類子圖的數(shù)量進(jìn)行挖掘分析,在生物學(xué)[1-2]、社會學(xué)、社交網(wǎng)絡(luò)[3-6]和萬維網(wǎng)分析[7-8]等領(lǐng)域都有著重要作用。例如,可以將具有特定功能的氨基酸團(tuán)定義為蛋白質(zhì)結(jié)構(gòu)網(wǎng)絡(luò)圖中的一類小型無向子圖[1-2],對這類子圖進(jìn)行數(shù)量統(tǒng)計,是認(rèn)定蛋白結(jié)構(gòu)、推定未知蛋白功能性質(zhì)等工作的前提;類似地,將小規(guī)模用戶之間的關(guān)系抽象為在線社交網(wǎng)絡(luò)中的一類小型無向
西安交通大學(xué)學(xué)報 2018年12期2018-12-12
- 基于圖編碼的網(wǎng)絡(luò)拓?fù)湔Z義挖掘*
來說，圖中的某些子圖或子結(jié)構(gòu)具有顯著的特征，這個“特征”可以是多種多樣的，如稠密性特征可以對應(yīng)到派系（Clique），相似性特征可以反映到二部圖（Bipartite）上，相對稠密度則可以定義社區(qū)或社團(tuán)（Community）的概念。子結(jié)構(gòu)和子圖指的是同一個對象，只不過在強(qiáng)調(diào)子圖的結(jié)構(gòu)方面時也稱子圖為子結(jié)構(gòu)。在社交網(wǎng)絡(luò)或者更多網(wǎng)絡(luò)中，子結(jié)構(gòu)包含了圖中點的一些語義信息，這是由于不同的結(jié)構(gòu)類型具有不同的意義，蘊(yùn)含了不同的連接模式信息。此外，局部的子結(jié)構(gòu)通過一些重疊
通信技術(shù) 2018年11期2018-11-07
- 關(guān)于l-路和圖的超歐拉性
則稱H是G的一個子圖。如果VH=VG，則稱H是G的一個生成子圖。對于G中任意一個點v，用G-v表示從圖G中刪去點v及其所關(guān)聯(lián)的邊所得到的G的子圖，稱為G的點刪除子圖。對于G中任意一條邊e，用G-e表示從圖G中刪去邊e所得到的G的子圖，稱為G的邊刪除子圖。如果一個圖G包含一條閉跡使得EW=EG,則稱G是歐拉圖。如果一個圖G包含一條閉跡使得VW=VG,或包含一個生成歐拉子圖，則稱G是超歐拉圖。定義1 在圖G中，如果對于每一個點v∈VG，滿足點刪除子圖G-v是超
西華師范大學(xué)學(xué)報（自然科學(xué)版） 2018年3期2018-09-26
- 面向高層次綜合的自定義指令自動識別方法
的缺點。2)針對子圖枚舉，結(jié)合搜索樹設(shè)計了一種基于節(jié)點刪除技術(shù)的深度優(yōu)先(Depth-First based on Node Deletion technique, DFND)搜索算法，可靈活修改圖大小、連通性等約束條件。3)針對子圖選擇，提出了基于最少子圖數(shù)目的選擇(Minimum number of matches based subgraph Selection, MS)算法、基于關(guān)鍵路徑的子圖選擇(Critical paths based subg
計算機(jī)應(yīng)用 2018年7期2018-08-27
- 標(biāo)簽零模型及子圖分布算法應(yīng)用研究
法有兩類,一類是子圖分布算法,另一類是頻繁子圖挖掘算法.用于圖分類的子圖分布算法的相關(guān)研究最早起源于生物學(xué)與社會網(wǎng)絡(luò)等領(lǐng)域,其目的是檢測圖的非平凡特性用于發(fā)現(xiàn)不同圖之間的異同,在生物學(xué)研究中,通過檢測兩組蛋白質(zhì)交互網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的不同可以發(fā)現(xiàn)兩者功能上的差異.例如通過把要檢測物質(zhì)的化學(xué)結(jié)構(gòu)和已知的致癌癥物質(zhì)抽象成圖比對,就可以初步判斷要檢測物質(zhì)是否致癌.國外對用于圖分類的子圖分布算法研究已經(jīng)有很多,一般是基于一定的圖模型,將現(xiàn)實世界中的網(wǎng)絡(luò)抽象為圖并建模,
小型微型計算機(jī)系統(tǒng) 2018年5期2018-07-04
- 2樹的獨立數(shù)
設(shè)表示由X誘導(dǎo)的子圖，Gx和GX分別表示由誘導(dǎo)的子圖，表示x的鄰點集。我們用表示階完全圖，表示的補(bǔ)圖，“+”表示兩個圖的交。本文未注釋的標(biāo)記參考[1]。圖是2樹當(dāng)且僅當(dāng)G=K3，或者G中存在一個度為2的點v，使得與v相鄰的兩個點也相鄰，且Gv是一個2樹。我們把2樹中度為2的點稱為耳朵，顯然，一個2樹至少有兩個耳朵。關(guān)于2樹還有下面的性質(zhì)：二、證明為了證明定理1.1，我們首先證明下面的引理：[1] Bondy J A, Murty U S R． Graph
數(shù)學(xué)大世界 2018年7期2018-03-29
- 具有禁止子圖的有向圖是超歐拉有向圖的條件
畫出包含生成歐拉子圖的無向圖,同時,他們表示這個問題是非常困難的.Pulleyblank[3]在1979年證明了判定一個無向圖(甚至包含平面無向圖)是否是超歐拉的是NP-完全的.截至今日,已經(jīng)有大量關(guān)于超歐拉無向圖的研究,例如Catlin的研究[4]和他的更新版[5].禁止誘導(dǎo)子有向圖一直是被廣泛研究的話題.給定一個有向圖K和一個有向圖D,如果對于D的任意一個子圖H,若滿足H≌K,則|A(D〈V(H)〉)|>|A(H)|+1,則稱D不含K子圖.一直在被深入
商丘師范學(xué)院學(xué)報 2018年3期2018-03-20
- 譜極值圖論的最新進(jìn)展和相關(guān)問題
n類型，包括完全子圖、線性森林、圈、二部圖以及圖子式等鄰接譜和無符號拉普拉斯譜的最新研究成果，同時介紹該領(lǐng)域的尚未解決的猜想和相關(guān)問題.Turán類型問題；禁用子圖；譜半徑；無符號拉普拉斯譜半徑論文考慮的圖都是有限無向簡單圖.令G=(V(G),E(G))是一個簡單圖，其中V(G)為頂點集，E(G)為邊集.用e(G)表示圖G的邊數(shù).給定兩個點無交的簡單圖G和H,G∪H表示G和H的不交并.kG表示k個同構(gòu)圖G的不交并，G∨H表示由G∪H通過添加所有的連接G中的
安徽大學(xué)學(xué)報（自然科學(xué)版） 2018年1期2018-03-01
- Spark環(huán)境下基于頻繁邊的大規(guī)模單圖采樣算法
行，對其進(jìn)行頻繁子圖挖掘的需求越來越強(qiáng)烈.大數(shù)據(jù)時代的到來，社交網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，頻繁子圖挖掘工作變得愈發(fā)困難.在實際應(yīng)用中，往往并不需要精確地挖掘出頻繁子圖，采樣的方法在保證一定準(zhǔn)確率的前提下能夠顯著提高頻繁子圖挖掘的效率.現(xiàn)有采樣算法大多是根據(jù)節(jié)點的度進(jìn)行采樣，不適用于頻繁子圖挖掘.提出了一種基于頻繁邊的采樣算法DIMSARI(distributed Monte Carlo sampling algorithm based on random jump
計算機(jī)研究與發(fā)展 2017年9期2017-09-15
- 子圖估算PageRank網(wǎng)頁排序算法研究
的形式，動態(tài)構(gòu)建子圖，由子圖迭代計算出PageRank值的上下限。理論分析和實驗結(jié)果表明：該算法不僅可以保證結(jié)果的準(zhǔn)確性，還可以更快地找到用戶所需網(wǎng)頁數(shù)。關(guān)鍵詞：web圖數(shù)據(jù)；網(wǎng)頁排序；PageRank算法；MapReduce；子圖DOI：10.15938/j.jhust.2017.02.022中圖分類號： TP301文獻(xiàn)標(biāo)志碼： A文章編號： 1007-2683（2017）02-0117-07Abstract：The traditional PageRa
哈爾濱理工大學(xué)學(xué)報 2017年2期2017-06-10
- 概率頻繁模式挖掘算法研究綜述
圍繞圖集中的頻繁子圖挖掘算法、單圖中的頻繁子圖挖掘算法兩個方面展開討論，對概率頻繁模式挖掘算法進(jìn)行了研究以及綜述，并在此基礎(chǔ)上提出了一些筆者自己的見解，希望能夠?qū)窈蟮母怕暑l率模式挖掘算法的研究提供一些理論建議?！娟P(guān)鍵詞】概率頻繁模式 挖掘算法現(xiàn)階段，已有越來越多高效的算法被研發(fā)出來，用于對圖集進(jìn)行挖掘，其中也不乏有一些算法是用作對單圖中的模式進(jìn)行挖掘的，由于這些算法的應(yīng)用對象有所差別，因此他們的效果也存在一定的差異。而針對任何一個實際存在的問題，最大的挑
電子技術(shù)與軟件工程 2017年8期2017-05-10
- 禁用子圖為2K2和K1+C4的圖的色數(shù)
于圖G的任一導(dǎo)出子圖H，如果其色數(shù)χ(H)與團(tuán)數(shù)ω(H)相等，則將圖G稱為完美圖。在完美圖的基礎(chǔ)上，Gyárfás[1]提出了用函數(shù) f(ω)表示圖的色數(shù)上界的概念，完美圖就是以f(ω)=x為色數(shù)界的圖類。對于給定的圖H，如果圖G不含與H同構(gòu)的導(dǎo)出子圖，則稱H是圖G的禁用子圖或者圖 G是 H-free 的。在文獻(xiàn)[1]中，Gyárfás給出猜想：令F為一森林，則對于每一個F-free的圖G，都存在整數(shù)函數(shù) f(x,y)使得 χ(G)≤f(F,ω(G))。關(guān)
商洛學(xué)院學(xué)報 2017年6期2017-04-14
- 隨機(jī)網(wǎng)絡(luò)的連通率研究
能存在孤立節(jié)點和子圖。對隨機(jī)圖尤其是其連通性的研究有助于更深入地了解具有隨機(jī)連接特性及節(jié)點對等特性的真實網(wǎng)絡(luò)。文章采用理論與仿真相結(jié)合的方法，重點研究隨機(jī)圖的連通性和隨機(jī)圖連通率的計算方法，揭示了隨機(jī)圖在演化過程中的形態(tài)變化，表明隨機(jī)圖中樹結(jié)構(gòu)的廣泛存在。研究還發(fā)現(xiàn)，在巨大連通子圖形成前，隨機(jī)圖的子圖大小呈冪律分布。本研究結(jié)果為復(fù)雜網(wǎng)絡(luò)相關(guān)的實證研究和性質(zhì)復(fù)雜的網(wǎng)絡(luò)相變態(tài)研究提供了理論依據(jù)。隨機(jī)圖；連通率；子圖0 引言自20世紀(jì)60年代ERD?S P和Ré
網(wǎng)絡(luò)安全與數(shù)據(jù)管理 2016年19期2016-11-15
- 模糊團(tuán)的一個注記
圖論中，團(tuán)導(dǎo)出的子圖是完全的，然而根據(jù)現(xiàn)有模糊團(tuán)的定義，模糊團(tuán)導(dǎo)出的模糊子圖不一定是完全的.這篇注記修正模糊團(tuán)的概念，以保證其導(dǎo)出的模糊子圖是完全的，并給出模糊團(tuán)和極大模糊團(tuán)的刻畫.模糊圖;模糊團(tuán);完全性圖論中的圖由若干給定的點及連接2點的邊構(gòu)成，是對象集合及對象與對象之間關(guān)系的數(shù)學(xué)表示.在圖論中，這些對象以及對象間的關(guān)系都是分明的，然而在實際問題中，對象或?qū)ο箝g的關(guān)系往往存在不清晰、不確定的情形，因此需要模糊化的數(shù)學(xué)表示.自L.A.Zadeh［1］提出模
四川師范大學(xué)學(xué)報（自然科學(xué)版） 2016年3期2016-06-05
- 稠密k-子圖問題的雙非負(fù)松弛
稠密k-子圖問題的雙非負(fù)松弛郭傳好,單而芳(上海大學(xué)管理學(xué)院管理科學(xué)與工程系,上海200444 )摘要：稠密k-子圖問題是組合優(yōu)化里面一類經(jīng)典的優(yōu)化問題,其在通常情況下是非凸且NP-難的。本文給出了求解該問題的一個新凸松弛方法-雙非負(fù)松弛方法,并建立了問題的相應(yīng)雙非負(fù)松弛模型,而且證明了其在一定的條件下等價于一個新的半定松弛模型。最后,我們使用一些隨機(jī)例子對這些模型進(jìn)行了數(shù)值測試,測試的結(jié)果表明雙非負(fù)松弛的計算效果要優(yōu)于等價的半定松弛。關(guān)鍵詞：組合優(yōu)化;雙
運籌與管理 2015年5期2016-01-18
- 幾類圖的無符號Laplace矩陣的行列式
)，則稱H是G的子圖,如果H是G的子圖,并且V(H)=V(G),則稱H是G的生成子圖.定義1.5如果圖G的一個頂點和邊的交替序列v0e1v1e2v2…vm-1emvm使得對1≤i≤m，邊ei的兩個端點是vi-1和vi，則稱該序列為G的一條路徑.又如果邊e1,e2,…,em互不相同，則稱該路徑為G的一條跡（或叫鏈）.頂點互不相同的跡稱為G的一條路.路中邊的條數(shù)稱為該路的長度,圖G中u,v兩點的距離是指以u與v為起止點的u-v路的最短路長，記為dG(u,v).
赤峰學(xué)院學(xué)報·自然科學(xué)版 2015年7期2015-11-18
- 簡單圖的子圖及其性質(zhì)研究
000)簡單圖的子圖及其性質(zhì)研究周麗霞(無錫城市職業(yè)技術(shù)學(xué)院 會計系，江蘇 無錫 214000)給出圖論中關(guān)于子圖的定義,并得到子圖的一些性質(zhì)。通過定理闡述子圖與其導(dǎo)出子圖的同構(gòu)性、子圖與哈密爾頓圖的關(guān)系,并證明和舉例。圖論;子圖;同構(gòu);哈密爾頓圖本文給出了子圖的定義,并研究了子圖的一些性質(zhì)和它與其導(dǎo)出子圖的一些關(guān)系。本文所引用的定義及符號詳見文獻(xiàn)[1],文章所涉及的圖均為無端點圖。在圖論中,自環(huán)是兩端連接著同一端點的邊。既不含平行邊又不含自環(huán)的圖稱為簡單
鎮(zhèn)江高專學(xué)報 2015年3期2015-07-18
- 基于雙索引的子圖查詢算法
3)基于雙索引的子圖查詢算法陸慧琳,黃 博(復(fù)旦大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院智能信息處理重點實驗室,上海200433)傳統(tǒng)的子圖查詢算法大多只在圖數(shù)據(jù)庫上進(jìn)行一次挖掘算法,即在圖數(shù)據(jù)庫上建立穩(wěn)定的數(shù)據(jù)庫索引后將不再對索引進(jìn)行更新。隨著查詢興趣的改變或數(shù)據(jù)庫的頻繁更新,原有的數(shù)據(jù)庫索引將不再能提供有用的信息來減少查詢過程中候選圖的數(shù)量。為此,提出一種雙索引的子圖查詢算法,同時在數(shù)據(jù)庫和查詢流上挖掘頻繁子圖并建立索引。子圖查詢和查詢流索引的建立同步進(jìn)行,即使查詢興
計算機(jī)工程 2015年1期2015-06-27
- 支持增量圖數(shù)據(jù)的超圖查詢算法研究
成直至單個頂點的子圖，然后從單個頂點的子圖開始求它到查詢圖的子圖同構(gòu)，直到求出數(shù)據(jù)圖到查詢圖的子圖同構(gòu)結(jié)果，算法在數(shù)據(jù)圖增加時只需將新加入的數(shù)據(jù)圖進(jìn)行分解即可，不必重新計算。通過分析證明，所提算法時間和空間復(fù)雜度不隨數(shù)據(jù)圖的增加而呈線性增長，節(jié)省了大量時間和空間代價。增量圖數(shù)據(jù);超圖查詢;算法;子圖同構(gòu)引言圖作為一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)被應(yīng)用到各個領(lǐng)域中，因此圖查詢[1]作為圖數(shù)據(jù)庫管理的基本工具受到越來越多的關(guān)注。圖結(jié)構(gòu)數(shù)據(jù)的復(fù)雜性決定了圖查詢的難度。圖查詢問
四川輕化工大學(xué)學(xué)報(自然科學(xué)版) 2015年3期2015-06-06
- 不含某些圖作為導(dǎo)出子圖的圖的色數(shù)
含某些圖作為導(dǎo)出子圖的圖的色數(shù)段 芳（新疆師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，新疆烏魯木齊830054）Erodo¨s證明了對于任意一個圖G，χ（G）－ω（G）可以任意大。因此，對一般圖而言，其色數(shù)不一定能找到一個與團(tuán)數(shù)有關(guān)的上界。文章主要討論一類特殊的F－free圖的色數(shù)和團(tuán)數(shù)的關(guān)系。設(shè)圖G＝（V，E）是一個不含K1，k+1+e、C4和C4+e為導(dǎo)出子圖的連通圖，不是星圖和奇圈。若α（G）≥k≥3，則χ（G）≤（k（k－1）／2）ω（G）。色數(shù)；團(tuán)數(shù)；F－free圖文
新疆師范大學(xué)學(xué)報(自然科學(xué)版) 2015年1期2015-05-25
- 不含3K1+K2 和C4 為導(dǎo)出子圖的圖的色數(shù)
點集和由A導(dǎo)出的子圖。設(shè)α(G)、ω(G)、χ(G)分別表示圖G的獨立數(shù)，團(tuán)數(shù)和頂點色數(shù)[1]（簡稱為色數(shù)）。顯然有χ(G)≥ω(G)，并且由文獻(xiàn)[2-3]中Erdos 的經(jīng)典結(jié)論，可知圖的色數(shù)和團(tuán)數(shù)之差χ(G)-ω(G)可以任意大。一個圖G稱為完美圖，如果對于圖G的任意導(dǎo)出子圖H，都有χ(H)=ω(H)。完美圖的概念應(yīng)用廣泛，信息論里的Shannon Capacity與其密切相關(guān)：一個圖的Shannon Capacity 總是介于團(tuán)數(shù)和色數(shù)之間，所以完美
計算機(jī)工程與應(yīng)用 2015年19期2015-04-16
- 不含2K2為導(dǎo)出子圖的圖的染色
不含2K2為導(dǎo)出子圖的圖的染色王曉（商洛學(xué)院數(shù)學(xué)與計算機(jī)應(yīng)用學(xué)院，陜西商洛726000）利用強(qiáng)完美圖定理，得到不含{2K2、C4、C5}為導(dǎo)出子圖的圖是完美圖。進(jìn)而證明了每一個不含{2K2、C4}為導(dǎo)出子圖的圖是(ω(G)+1)可著色的，并且給出一類滿足不含{2K2、C4}為導(dǎo)出子圖且χ(G)=ω(G)+1的圖類，其中ω(G)和χ(G)分別為圖G的團(tuán)數(shù)和色數(shù)。色數(shù)；團(tuán)數(shù)；導(dǎo)出子圖設(shè)χ(G)，ω(G)分別表示圖G的頂點色數(shù)和團(tuán)數(shù)，顯然對于任一圖G，有χ(G)
商洛學(xué)院學(xué)報 2015年2期2015-04-10
- 一種基于特征子圖的不確定圖分類算法
結(jié)構(gòu)圖中尋找頻繁子圖，這樣的子圖可以用來判斷其他分子化合物是否有毒．目前，圖分類的方法主要包括基于頻繁子圖的分類方法［1－4］和基于圖核函數(shù)的分類方法［5－6］，它們在一定程度上解決了圖分類問題．然而由于硬件條件、人為原因和環(huán)境等因素的影響，圖結(jié)構(gòu)中存在大量的不確定性，不確定圖不同節(jié)點之間的聯(lián)系是以一定概率存在的，因此不能簡單地采用以往的分類方法來處理不確定圖分類．而現(xiàn)實中的應(yīng)用對不確定圖的分類提出需求，例如，人類大腦不同區(qū)域功能之間聯(lián)系就存在不確定性，通
陜西師范大學(xué)學(xué)報（自然科學(xué)版） 2014年5期2014-10-29
- 章魚圖的IC-著色和IC-指數(shù)
)→?和G的一個子圖H，定義f(H)=∑v∈V(H)f(v)，特別的將f(G)記作S(f)。如果對于任意整數(shù)k∈{1,2,3,…,f(G)}?[1,f(G)]存在G的一個連通子圖H，使得f(H)=k,則稱f為圖G的一個IC-著色。并定義M(G)=max{f(G) f為圖G的一個IC-著色}為圖G的IC-指數(shù)，并且稱適合f(G)=M(G)的IC-著色f為圖G的一個極大IC-著色。圖的IC-著色問題來源自數(shù)論中郵票問題［2-4］，自從提出以來，得到了廣泛的研究
華東交通大學(xué)學(xué)報 2014年4期2014-07-20
- 關(guān)于圈對完全圖的多色Ramsey數(shù)
稱為圖G的點導(dǎo)出子圖，記為G［V'］．用Γ(u)表示u的鄰域，即u的所有鄰點構(gòu)成的集合，由Γ(u)產(chǎn)生的點誘導(dǎo)子圖記為G'［Γ(u)］．如果E'?E(G)，則以E'為邊集，以E'中邊的所有端點為頂點集組成的圖，稱為圖G的邊導(dǎo)出子圖，記為G［E'］．分別用G1，G2，…，Gm表示圖，(k+1)色Ramsey數(shù)rk+1(C2m，…，C2m，Kn)是指滿足如下條件的正整數(shù)N:當(dāng)用(k+1)色c1，c2，…，ck+1給完全圖KN邊著色時，總存在某個 j∈{1，2，
鄭州大學(xué)學(xué)報（理學(xué)版） 2014年1期2014-03-20
- 最小權(quán)重有向頻繁子圖挖掘
最小支持度的頻繁子圖是人們感興趣的。當(dāng)前圖挖掘的熱點在于有向圖，即在大量的有向頻繁圖中挖掘出一種性質(zhì)更優(yōu)的圖。本文介紹一類特殊的頻繁子圖—最小權(quán)重有向頻繁子圖，它滿足最小支持度閾值，并且所包含的邊和頂點的權(quán)重之和在所有同構(gòu)子圖中是最小的，本文提出的挖掘方法用于處理此類頻繁子圖，在廠區(qū)鐵路運輸分析研究中有實際應(yīng)用。根據(jù)廠區(qū)鐵路分布規(guī)模小、運輸密度高的特點，用加權(quán)有向圖表示某廠區(qū)鐵路線路網(wǎng)結(jié)構(gòu)，不同標(biāo)記頂點表示不同類型的車間，不同標(biāo)記的有向邊表示不同的廠區(qū)鐵路
鐵路計算機(jī)應(yīng)用 2013年7期2013-11-26
- 圖G（p，q）的生成子圖的構(gòu)造與計數(shù)
，若G的一個生成子圖T是樹，則稱T為G的生成樹。圖的生成樹不是唯一的。但任何連通圖至少有一顆生成樹。所有生成樹中具有最小數(shù)的生成樹稱為最小生成樹，求最小生成樹是實際問題的需要，例如“為了把若干城市連接起來，設(shè)計最短通信線路”，“為了解決若干居民點供水，要求設(shè)計最短的自來水管線路”等等。1 基本思路定義1 設(shè)G（p,q）為p個頂和q個邊的任意連通圖，則G（p,q）中任意p-1個邊所導(dǎo)出的S（G）個子圖稱為生成子圖。定義2 設(shè)圖G(p,q)中存在S(G)個生成
科技視界 2013年23期2013-08-22
- 一類Snark與k-圈的卡式積圖的連通性①
的圖。若H是G的子圖，記作H?G。以上的基本概念在［4］中有介紹。命題1 (H.-J.Lai［5］):對任意 Abel群A，＜A＞是一族連通圖滿足:(1)K1∈ ＜A ＞;(2)若 e∈E(G)，且 G∈＜A＞，則G/e∈＜A＞;(3)若 H?G，且 H，G/H∈ ＜A＞，則 G∈＜A＞;(4)若|A|≥n+1，則 Cn∈ ＜A ＞;(5)若G［v，X］∈ ＜A ＞ ，則 G∈ ＜A ＞。命題2 (M.Devos［6］):對任意 n≥1，則有W2n∈＜Z3
華北科技學(xué)院學(xué)報 2011年3期2011-12-26
- 頻繁子圖挖掘算法的若干問題
10012)頻繁子圖挖掘算法的若干問題楊 盛(長沙礦山研究院, 湖南長沙 410012)介紹了基于頻繁子圖挖掘算法的思想及其相關(guān)算法,提出了頻繁子圖挖掘算法的一些問題,對所挖掘圖的存儲方式進(jìn)行了討論,重點介紹了隱式存儲方式及其優(yōu)點。在頻繁子圖挖掘一般步驟的基礎(chǔ)上,提出了通過構(gòu)建頻繁子圖決策樹 (FSDT)來實現(xiàn)挖掘算法的預(yù)處理問題,最后初步提出寬度優(yōu)先子圖同構(gòu)法 (BFSI)來實現(xiàn)頻繁子圖決策樹 (FSDT)。頻繁子圖;圖存儲方式;預(yù)處理;頻繁子圖決策樹在
采礦技術(shù) 2011年5期2011-11-15
- 一類笛卡爾積圖的連通性
的圖.若H是G的子圖，記作H?G.以上的基本概念在[4]中有介紹.命題 1 （H.-J.Lai[5]）：對任意 Abel群 A，＜A＞是一族連通圖滿足：（1）K1∈＜A＞；（2）若 e∈E(G),且 G∈＜A＞，則 G/e∈＜A＞；（3）若 H?G 且 H，G/H∈＜A＞，則 G∈＜A＞；（4）若|A|≥n+1,則 Cn∈＜A＞；（5）若 G[v,X]∈＜A＞，則 G∈＜A＞.命題 2 （M.Devos[6]）：對?n≥1，則有 W2n∈＜Z3＞.若H?G
巢湖學(xué)院學(xué)報 2011年3期2011-08-15
- λ5－最優(yōu)圖的鄰域交條件
．設(shè)H是G的一個子圖，令?（H）表示恰好有一個端點在H上的邊的數(shù)目．定義ξk＝ξk（G）＝min｛?（H）∶H是G的k階連通子圖｝．如果λk（G）＝ξk（G），則稱G是λk－最優(yōu)的．在λk－最優(yōu)圖的鄰域交條件方面，已有：定理1［3］設(shè)G是階至少為4的一個連通圖，對G中任意一對不相鄰頂點u，v，若u，v均不在三角形上，有｜N（u）∩N（v）｜≥2，若u或v在三角形上，有｜N（u）∩N（v）｜≥3，則G是λ2－最優(yōu)的．定理2［4］設(shè)G是一個λ3－連通圖，對G中
山西大學(xué)學(xué)報（自然科學(xué)版） 2011年2期2011-04-12
- 求最大完全子圖的啟發(fā)式著色算法
09)求最大完全子圖的啟發(fā)式著色算法李建新1,2(1.宿州學(xué)院計算機(jī)科學(xué)與技術(shù)系,人工智能與數(shù)據(jù)挖掘研究室,安徽宿州234000; 2.合肥工業(yè)大學(xué)計算機(jī)與信息學(xué)院,安徽合肥230009)本文提出了一種求最大完全子圖的啟發(fā)式著色算法.該算法通過為頂點著色將已知無向圖劃分為極大完全子圖的并集,再根據(jù)各極大完全子圖中頂點的多少選取最大完全子圖.隨后為提高算法執(zhí)行效率,又對該算法提出了一種精簡措施.最后將該算法運用于一集成電路測試數(shù)據(jù)編碼壓縮實驗中,證明了該算法
滁州學(xué)院學(xué)報 2010年2期2010-09-16