【摘要】：隨著社交網(wǎng)絡(luò)的流行,對其進行頻繁子圖挖掘的需求越來越強烈.大數(shù)據(jù)時代的到來,社交網(wǎng)絡(luò)規(guī)模不斷擴大,頻繁子圖挖掘工作變得愈發(fā)困難.在實際應(yīng)用中,往往并不需要精確地挖掘出頻繁子圖,采樣的方法在保證一定準確率的前提下能夠顯著提高頻繁子圖挖掘的效率.現(xiàn)有采樣算法大多是根據(jù)節(jié)點的度進行采樣,不適用于頻繁子圖挖掘.提出了一種基于頻繁邊的采樣算法DIMSARI(distributed Monte Carlo sampling algorithm based on random jump and graph induction),在蒙特卡羅算法的基礎(chǔ)上增加了根據(jù)頻繁邊進行隨機跳的操作,并對其結(jié)果進行了圖感應(yīng)操作,進一步增加了算法的準確性,并在理論上證明了該方法的無偏性.實驗結(jié)果顯示:使用DIMSARI算法采樣后進行頻繁子圖挖掘,準確性比現(xiàn)有其他的采樣算法有較大的提高,在不同的采樣率下采樣后的子圖的節(jié)點度都保持更小的歸一化均方偏差.
[Abstract]:With the popularity of social networks, the demand for frequent subgraph mining is becoming more and more intense. With the arrival of big data era, the scale of social network continues to expand, and it becomes more and more difficult to mine the frequent sub-graph. In practical applications, it is often not necessary to mine frequent subgraphs accurately. The sampling method can significantly improve the efficiency of frequent subgraphs mining on the premise of ensuring a certain accuracy. Most of the existing sampling algorithms are based on the degree of nodes and are not suitable for frequent subgraph mining. In this paper, a sampling algorithm based on frequent edges (DIMSARI (distributed Monte Carlo sampling algorithm based on random jump and graph induction),) is proposed. Based on Monte Carlo algorithm, the random hop operation based on frequent edges is added, and the graph induction operation is carried out on the results. The accuracy of the algorithm is further improved, and the unbiased property of the method is proved theoretically. The experimental results show that the accuracy of frequent sub-graph mining using DIMSARI algorithm is much higher than that of other sampling algorithms, and the node degree of sub-graph sampled at different sampling rates keeps a smaller normalized mean square deviation.
【作者單位】： 寧波大學(xué)信息科學(xué)與工程學(xué)院;
【基金】：國家自然科學(xué)基金項目(61572266,61472194) 浙江省自然科學(xué)基金項目(Y16F020003) 寧波市自然科學(xué)基金項目(2017A610114)~~
【分類號】：TP301.6

【相似文獻】

相關(guān)期刊論文 前10條

1 章立亮,周瓊;光柵圖形反走樣的加權(quán)區(qū)域采樣算法[J];寧德師專學(xué)報(自然科學(xué)版);2002年01期

2 曹鵬;李博;栗偉;趙大哲;;基于概率分布估計的混合采樣算法[J];控制與決策;2014年05期

3 余純;張?zhí)珮s;;基于硬件實現(xiàn)的粒子濾波重采樣算法研究[J];自動化技術(shù)與應(yīng)用;2013年02期

4 張秀麗,李萍,陸光華;高精度軟件同步采樣算法[J];電力系統(tǒng)及其自動化學(xué)報;2005年04期

5 趙豐;湯磊;張武;趙宗貴;;一種高實時性粒子濾波重采樣算法[J];系統(tǒng)仿真學(xué)報;2009年18期

6 馮馳;趙娜;王萌;;一種改進殘差重采樣算法的研究[J];哈爾濱工程大學(xué)學(xué)報;2010年01期

7 李蘊奇;李小明;何杰;鐘鳴;;關(guān)于吉布斯采樣算法識別MOTIF的研究[J];才智;2010年31期

8 郭建林;李愛玲;;一種大尺度Gauss模糊的快速采樣算法[J];中國科學(xué):信息科學(xué);2011年10期

9 黃�；�;劉冉;張華;張昭;;基于不同重采樣算法的RFID指紋定位[J];計算機應(yīng)用;2013年02期

10 馮馳;王萌;汲清波;;粒子濾波器重采樣算法的分析與比較[J];系統(tǒng)仿真學(xué)報;2009年04期

相關(guān)碩士學(xué)位論文 前4條

1 王柯翔;基于LWE問題的采樣算法及應(yīng)用研究[D];北京交通大學(xué);2017年

2 鄧俊;濾波重要性采樣算法的研究與實現(xiàn)[D];天津大學(xué);2007年

3 王朝;基于ARMS的并行采樣算法的設(shè)計與實現(xiàn)[D];天津大學(xué);2008年

4 崔承勛;基于GH-distance的自適應(yīng)性采樣算法[D];天津大學(xué);2009年

，

本文編號：2432631