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

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

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

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