大規模圖數據可達性索引技術研究

趙星

（陜西財經職業技術學院 陜西 咸陽 712000）

大規模圖數據可達性索引技術研究

趙星

（陜西財經職業技術學院 陜西 咸陽 712000）

針對當前SNS社區網絡的的不斷深入發展，大規模圖數據可達索引技術開始被廣泛的應用在社交網絡中，從而提高對數據索引的精準度。本文針對可達索引技術應用的社交網絡中，存在著確定性和不確定性的圖數據。針對確定性查詢中存在著很大的噪聲，引入信息熵的方式，從而提高了圖片檢索的效率，使得語義表達更為的精確。

SNS；可達索引；不確定性；查詢；信息熵

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

1 社交網絡與子圖查詢

1.1 社交網絡

圖1 社交網絡Fig.1 Social networks

1.2 子圖查詢

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

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

2.1 信息熵

熵理論最早是由美國的數學家所提出,通過它來對信息的

不確定度進行測定,并根據信息源來對其不確定進行相關的計算。對此,熵的公式則可表示為：

2.2 本文設計思路

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

2.3 信息熵的引入

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

在數據圖當中,任何的事件其都存在著一定的信息量,并且在社交網絡當中認為不相鄰的節點是相互獨立發生的。用x表示節點,而x1,x2,……,xm表示相鄰節點當中其符合條件的相關的點。則有：

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

在數據圖庫D當中,任何的一個節點的信息熵：

其中,在數據圖庫D當中,節點是非常多的,因此,通過節點的數量x→∞,從而可以將公式(3)表示為：

3 算法設計

在對子圖的查詢中,其主要涉及到4個不同的函數的應用,包括EntropyMatch函數、Entropy函數、selectVertex函數和substituteVertex函數,其整體的算法設計則為：

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

圖2 子圖查詢算法設計Fig.2 Algorithm design subgraph query

Entropy函數則主要是對上述集合z,R(z)中的點進行匹配,并通過調用函數retrieveNeighbors,從而可有效的遍歷出相鄰節點中符合條件的查詢點,而其篩選的條件則是以平均信息熵作為標準,當小于該平均信息熵的時候,則retrieveNeighbors函數的值為空。

selectVertex函數則主要是從信息熵的結合中選出其中的信息熵最大的點m,并調用其中的算法substituteVertex函數。再將符合條件的點全部篩選到集合A當中。

4 算法驗證

4.1 社交網絡子圖查詢模型驗證

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

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

要找到該部喜劇,則通過Entropy函數對其中的可能的查詢點進行搜索。則有圖5的模型。

圖4 遍歷點FrancisFig.4 Traverse point Francis

由此通過上述對算法的運行,從而得到結果。

4.2 查詢效率驗證

為驗證該算法在查詢的速率,采用C語言作為開發語言。同時本文將該算法與傳統的SubDue算法進行比較,從而可以得到如圖5所示的在不同尺寸的子圖查詢結果。

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

5 結束語

針對大規模數據圖可達性索引技術在社交網絡中的應用,就是一個NP問題,對此,本文結合對信息熵的定義,通過引入信息熵度量的方式,實現了對節點的度量,并通過實驗驗證其在查詢效率方面的提高,由此可以看出該技術在大數據的應用方面具有非常廣闊的空間,必將成為未來發展的一種趨勢。

[1]富麗貞,孟小峰.大規模圖數據可達性索引技術：現狀與展望[J].計算機研究與發展,2015(1)：116-129.

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

[3]吳剛.RDF圖數據管理的關鍵技術研究[D].北京：清華大學, 2008.

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

[5]馮端,馮步云.熵[M].北京：科學出版社,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稿件編號：201503176

趙 星(1982—)，男，陜西咸陽人，講師。研究方向：計算機相關技術及教學。