社交網(wǎng)絡(luò)中的子圖查詢研究.pdf

1、隨著社交網(wǎng)絡(luò)的不斷發(fā)展,圖數(shù)據(jù)處理的重要地位日益突顯。相對于傳統(tǒng)的數(shù)據(jù)類型,圖數(shù)據(jù)更加復(fù)雜,表達的語義更加豐富。針對如此復(fù)雜的數(shù)據(jù)類型,尋找到高效的查詢處理方法,對于提高社交網(wǎng)絡(luò)的分析效率和圖數(shù)據(jù)的質(zhì)量非常重要。然而,在實際情況中圖往往存在噪聲或者由于對事物的認識存在盲點,圖中存在著不確定性,因此圖數(shù)據(jù)又可以分為確定圖和不確定圖。本文根據(jù)上述兩種圖分別給出針對確定圖的子圖查詢算法和針對不確定圖的子圖查詢算法。
　　首先,對于確定圖

2、的子圖查詢,本文針對以往的算法大多采用靜態(tài)消耗測算模式的問題,根據(jù)信息熵在信息度量中的作用,將條件信息熵作為啟發(fā)式匹配的依據(jù),將信息熵的概念引入到圖數(shù)據(jù)查詢中,建立以信息熵為度量標準的動態(tài)測算模型,并以該動態(tài)測算模型為中心研究并實現(xiàn)了基于信息熵的子圖匹配算法。該算法減少了鄰接點的匹配次數(shù),提高了子圖查詢的效率。實驗表明:基于信息熵的子圖匹配算法具有更高的查詢效率,且在冪函數(shù)分布的數(shù)據(jù)集上效果更明顯。
　　其次,對于不確定圖的子圖查

3、詢,本文研究并實現(xiàn)了一種基于信息熵傳播模型的不確定圖top-k子圖查詢算法。在算法中依據(jù)信息熵在網(wǎng)絡(luò)鄰域關(guān)系度量中的作用,提出了一種信息熵傳播模型。該模型將不確定圖數(shù)據(jù)轉(zhuǎn)換為多維向量,通過設(shè)定閾值剪枝和刪除非潛在匹配的標簽來提高算法的效率。實驗表明,基于信息熵傳播模型的不確定圖top-k子圖查詢具有較低的錯誤率,對于噪聲的干擾具有強魯棒性,且在大數(shù)據(jù)的情況下有更高的效率。
　　最后,在理論研究基礎(chǔ)上,設(shè)計并實現(xiàn)子圖查詢系統(tǒng),以驗證