趙星

（陜西財(cái)經(jīng)職業(yè)技術(shù)學(xué)院 陜西 咸陽 712000）

大規(guī)模圖數(shù)據(jù)可達(dá)性索引技術(shù)研究

趙星

（陜西財(cái)經(jīng)職業(yè)技術(shù)學(xué)院 陜西 咸陽 712000）

針對(duì)當(dāng)前SNS社區(qū)網(wǎng)絡(luò)的的不斷深入發(fā)展，大規(guī)模圖數(shù)據(jù)可達(dá)索引技術(shù)開始被廣泛的應(yīng)用在社交網(wǎng)絡(luò)中，從而提高對(duì)數(shù)據(jù)索引的精準(zhǔn)度。本文針對(duì)可達(dá)索引技術(shù)應(yīng)用的社交網(wǎng)絡(luò)中，存在著確定性和不確定性的圖數(shù)據(jù)。針對(duì)確定性查詢中存在著很大的噪聲，引入信息熵的方式，從而提高了圖片檢索的效率，使得語義表達(dá)更為的精確。

SNS；可達(dá)索引；不確定性；查詢；信息熵

在實(shí)踐應(yīng)用中,給定圖上的兩個(gè)不同的頂點(diǎn),其分別為u和v,通過可達(dá)性的查詢(u→v),從而解決在圖當(dāng)中,存在著從u再到v的一條路徑。因此,可達(dá)性查詢是有向圖上一類當(dāng)中最為基本的查詢,而當(dāng)圖的規(guī)模在非常小的時(shí)候,通常采用深度優(yōu)先遍歷算法,或者可達(dá)性傳遞閉包算法來處理。但是,隨著現(xiàn)代社會(huì)信息的不斷增加,傳統(tǒng)的DFS算法查詢效率已經(jīng)不能滿足現(xiàn)代人們的需求,其需要耗費(fèi)大量的時(shí)間和空間。以此,可達(dá)性索引技術(shù)開始出現(xiàn)。該技術(shù)已經(jīng)出現(xiàn)即被廣泛的應(yīng)用在了計(jì)算機(jī)的各個(gè)不同范圍,如SNS社交、路由規(guī)劃、軟件工程等各個(gè)方面。通過加速圖上的其他的算法,從而提高對(duì)圖片檢索的精準(zhǔn)度,提高人們的搜索效率。而子圖查詢作為可達(dá)索引技術(shù)應(yīng)用的一種,如何對(duì)其中的數(shù)據(jù)圖進(jìn)行精準(zhǔn)的查詢,對(duì)此,本文對(duì)子圖查詢?cè)谏缃痪W(wǎng)絡(luò)中的應(yīng)用進(jìn)行了深入的探討。

1 社交網(wǎng)絡(luò)與子圖查詢

1.1 社交網(wǎng)絡(luò)

圖1 社交網(wǎng)絡(luò)Fig.1 Social networks

1.2 子圖查詢

所謂的子圖查詢就是定義一個(gè)圖數(shù)據(jù)庫D和一個(gè)查詢圖q,通過查詢輸出在該數(shù)據(jù)庫當(dāng)中包含q的所有圖片的集合,也就是。而由于查詢到的圖q其在結(jié)構(gòu)上通常是隨機(jī)的。因此,針對(duì)子圖查詢處理,其最為重要的步驟則為如何在數(shù)據(jù)圖當(dāng)中找到同構(gòu)圖。由此,針對(duì)子圖同構(gòu)的檢測(cè),其本質(zhì)就是一個(gè)NP的問題,對(duì)此,為解決這個(gè)問題,通常采用驗(yàn)證機(jī)制來完成,如通過特征或者是提取特定結(jié)構(gòu)的方式。

2 基于信息熵的確定圖子圖匹配

2.1 信息熵

熵理論最早是由美國的數(shù)學(xué)家所提出,通過它來對(duì)信息的

不確定度進(jìn)行測(cè)定,并根據(jù)信息源來對(duì)其不確定進(jìn)行相關(guān)的計(jì)算。對(duì)此,熵的公式則可表示為：

2.2 本文設(shè)計(jì)思路

傳統(tǒng)針對(duì)數(shù)據(jù)的存儲(chǔ)標(biāo)準(zhǔn)是以RDF作為標(biāo)準(zhǔn),通過在語義web、信息網(wǎng)絡(luò)等當(dāng)中引入帶標(biāo)簽的邊表示節(jié)點(diǎn)之間的關(guān)系,形成結(jié)構(gòu)更為復(fù)雜、信息量更為豐富的圖數(shù)據(jù)結(jié)構(gòu),以此子圖查詢被廣泛的應(yīng)用在各個(gè)領(lǐng)域。而在RDF領(lǐng)域,針對(duì)子圖匹配的算法和結(jié)構(gòu)進(jìn)行優(yōu)化的方法很多,如在匹配算法上面,采用通過一種統(tǒng)計(jì)的啟發(fā)式算法。但是很多的算法其主要都是集中在靜態(tài)消耗測(cè)算方面,并因?yàn)樾枰獙?duì)鄰節(jié)點(diǎn)進(jìn)行統(tǒng)計(jì),而消耗了大量的時(shí)間,特別是當(dāng)前一些圖當(dāng)中存在的大量的冪函數(shù)分布的圖數(shù)據(jù),更是需要耗費(fèi)大量的時(shí)間遍歷其鄰節(jié)點(diǎn),從而導(dǎo)致其查詢的效率非常的低下。因此,結(jié)合相關(guān)的計(jì)算機(jī)知識(shí),本文則借助信息熵在對(duì)信息進(jìn)行度量當(dāng)中的作用,將其中的信息熵作為啟發(fā)式匹配的依據(jù),提出了基于信息熵的子圖匹配算法,將條件信息熵作為啟發(fā)式匹配的依據(jù),減少鄰接點(diǎn)的匹配次數(shù),提高子圖查詢的效率。其具體的思想為：1)將信息熵引入到當(dāng)前的圖數(shù)據(jù)的查詢當(dāng)中,并以此建立以信息熵作為基本標(biāo)準(zhǔn)的一個(gè)動(dòng)態(tài)測(cè)算的模型了；2)通過該動(dòng)態(tài)模型,提出本文的子圖匹配算法；3)通過實(shí)驗(yàn)的對(duì)比,對(duì)該算法的有效性進(jìn)行驗(yàn)。

2.3 信息熵的引入

頁巖油又稱“人造石油”，與天然石油相比，頁巖油中含有較多的不飽和烴及硫、氮、氧等非烴類有機(jī)化合物。目前，頁巖油只是作為燃料油直接銷售，未經(jīng)二次加工，從資源利用、環(huán)境保護(hù)和經(jīng)濟(jì)效益方面來看都不盡合理。通過分析頁巖油及各餾分的性質(zhì)發(fā)現(xiàn)，可對(duì)頁巖油全餾分直接加氫精制，即在高溫高壓和催化劑存在的條件下，將頁巖油餾分在氫壓下除掉其中的硫、氮、氧等非烴類化合物及金屬雜質(zhì)，并將不飽和組分進(jìn)行加氫飽和，以生產(chǎn)化工產(chǎn)品和清潔燃料。

在數(shù)據(jù)圖當(dāng)中,任何的事件其都存在著一定的信息量,并且在社交網(wǎng)絡(luò)當(dāng)中認(rèn)為不相鄰的節(jié)點(diǎn)是相互獨(dú)立發(fā)生的。用x表示節(jié)點(diǎn),而x1,x2,……,xm表示相鄰節(jié)點(diǎn)當(dāng)中其符合條件的相關(guān)的點(diǎn)。則有：

同理,根據(jù)公式(2)則有：

在數(shù)據(jù)圖庫D當(dāng)中,任何的一個(gè)節(jié)點(diǎn)的信息熵：

其中,在數(shù)據(jù)圖庫D當(dāng)中,節(jié)點(diǎn)是非常多的,因此,通過節(jié)點(diǎn)的數(shù)量x→∞,從而可以將公式(3)表示為：

3 算法設(shè)計(jì)

在對(duì)子圖的查詢中,其主要涉及到4個(gè)不同的函數(shù)的應(yīng)用,包括EntropyMatch函數(shù)、Entropy函數(shù)、selectVertex函數(shù)和substituteVertex函數(shù),其整體的算法設(shè)計(jì)則為：

在本算法設(shè)計(jì)中,EntropyMatch函數(shù)的作用是首先對(duì)數(shù)據(jù)圖中的各個(gè)查詢點(diǎn)的條件熵進(jìn)行確定,從而在大量的節(jié)點(diǎn)中查找到可能匹配的點(diǎn),用z,R(z)來表示其可能存在的查詢的點(diǎn)。

圖2 子圖查詢算法設(shè)計(jì)Fig.2 Algorithm design subgraph query

Entropy函數(shù)則主要是對(duì)上述集合z,R(z)中的點(diǎn)進(jìn)行匹配,并通過調(diào)用函數(shù)retrieveNeighbors,從而可有效的遍歷出相鄰節(jié)點(diǎn)中符合條件的查詢點(diǎn),而其篩選的條件則是以平均信息熵作為標(biāo)準(zhǔn),當(dāng)小于該平均信息熵的時(shí)候,則retrieveNeighbors函數(shù)的值為空。

selectVertex函數(shù)則主要是從信息熵的結(jié)合中選出其中的信息熵最大的點(diǎn)m,并調(diào)用其中的算法substituteVertex函數(shù)。再將符合條件的點(diǎn)全部篩選到集合A當(dāng)中。

4 算法驗(yàn)證

4.1 社交網(wǎng)絡(luò)子圖查詢模型驗(yàn)證

本文以圖3作為子圖查詢的模型,假如其中名叫做Francis嘗試去搜索一個(gè)喜劇的名字,而該部電影的名字是通過該社交網(wǎng)絡(luò)中Peter的一個(gè)朋友給推薦的。其中?表示為變量,?u表示主人公Francis在Peter的聚會(huì)之上所遇到的人。

圖3 子查詢模型Fig.3 Sub query model

要找到該部喜劇,則通過Entropy函數(shù)對(duì)其中的可能的查詢點(diǎn)進(jìn)行搜索。則有圖5的模型。

圖4 遍歷點(diǎn)FrancisFig.4 Traverse point Francis

由此通過上述對(duì)算法的運(yùn)行,從而得到結(jié)果。

4.2 查詢效率驗(yàn)證

為驗(yàn)證該算法在查詢的速率,采用C語言作為開發(fā)語言。同時(shí)本文將該算法與傳統(tǒng)的SubDue算法進(jìn)行比較,從而可以得到如圖5所示的在不同尺寸的子圖查詢結(jié)果。

圖5 不同算法查詢時(shí)間Fig.5 Different algorithms for query time

5 結(jié)束語

針對(duì)大規(guī)模數(shù)據(jù)圖可達(dá)性索引技術(shù)在社交網(wǎng)絡(luò)中的應(yīng)用,就是一個(gè)NP問題,對(duì)此,本文結(jié)合對(duì)信息熵的定義,通過引入信息熵度量的方式,實(shí)現(xiàn)了對(duì)節(jié)點(diǎn)的度量,并通過實(shí)驗(yàn)驗(yàn)證其在查詢效率方面的提高,由此可以看出該技術(shù)在大數(shù)據(jù)的應(yīng)用方面具有非常廣闊的空間,必將成為未來發(fā)展的一種趨勢(shì)。

[1]富麗貞,孟小峰.大規(guī)模圖數(shù)據(jù)可達(dá)性索引技術(shù)：現(xiàn)狀與展望[J].計(jì)算機(jī)研究與發(fā)展,2015(1)：116-129.

[2]包佳佳,田偉.大規(guī)模圖上標(biāo)簽集約束路徑的集合查詢[J].計(jì)算機(jī)科學(xué),2013(4)：172-176,192.

[3]吳剛.RDF圖數(shù)據(jù)管理的關(guān)鍵技術(shù)研究[D].北京：清華大學(xué), 2008.

[4]劉勇,李建中,朱敬華.一種新的基于頻繁閉顯露模式的圖分類方法[J].計(jì)算機(jī)研究與發(fā)展,2007,44(7)：1169-1176.

[5]馮端,馮步云.熵[M].北京：科學(xué)出版社,1992.

[6]H Shang,Y Zhang,X Lin,et al.Taming Verification Hardness：An Efficient Algorithm for Testing Subgraph Isomorphism[C]. In Proceedings of the International Conference on Very Large Data Bases,2008：364-375.

[7]Matthias Brocheler,Andrea Pugliese,V.S.Subrahmanian.A budget-based algorithm for efficient subgraph matching on huge networks[C].International Conference on Data Engineering,2011：94-99.

[8]CE Shannon.Mathematical theory of communication[J].Bell System Technical Journal,1948(27)：379-423.

Technical mass index study reachability graph data

ZHAO Xing
(1.Shannxi Technical College of Finance and Economics,Xianyang 712000,China)

In view of the current SNS-depth development of community networks,large-scale map data up indexing technology began to be widely used in the social network,thereby improving the accuracy of the data index.In this paper,indexing technology applications up to a social network,there is a certainty and uncertainty of map data.For deterministic queries exist in a loud noise,information entropy manner,thereby improving the efficiency of image retrieval,so that a more precise semantic representation.

SNS；up index；uncertainty；inquiry；information entropy

TN99

：A

:1674-6236(2015)23-0152-03

2015-03-12稿件編號(hào)：201503176

趙 星(1982—)，男，陜西咸陽人，講師。研究方向：計(jì)算機(jī)相關(guān)技術(shù)及教學(xué)。