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