本站小編為你精心準備了用戶需求下信息網(wǎng)絡(luò)拓撲維上卷模型研究參考范文，愿這些范文能點燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

摘要：

隨著信息網(wǎng)絡(luò)的發(fā)展，信息網(wǎng)絡(luò)拓撲維上卷逐漸成為本領(lǐng)域的一個熱點，同時它的應(yīng)用價值也隨之提升。對給定節(jié)點不上卷，其他節(jié)點上卷到指定層次的方法來滿足用戶的特定需求。提出滿足用戶需求的信息網(wǎng)絡(luò)拓撲維上卷模型。主要貢獻有：（1）首次提出有效上卷代價的概念，（2）首次實現(xiàn)用戶的特定需求上卷，（3）設(shè)計信息網(wǎng)絡(luò)的拓撲維上卷算法。實驗證明該算法能夠滿足用戶的特定需求，實現(xiàn)指定拓撲維上卷操作，具有很強的實用價值。

關(guān)鍵詞：

信息網(wǎng)絡(luò)；特定需求；拓撲維；上卷

引言

信息網(wǎng)絡(luò)在日常生活中隨處可見，小到數(shù)十個節(jié)點組成的科研合作者網(wǎng)絡(luò)，大到百億級節(jié)點的社交網(wǎng)絡(luò)，信息網(wǎng)絡(luò)反映現(xiàn)實生活中各種類型的關(guān)系，如今對信息網(wǎng)絡(luò)的研究正日益成為一種熱點和趨勢。根據(jù)用戶指定的需求對信息網(wǎng)絡(luò)進行上卷操作，則可以挖掘出某些節(jié)點與其他社會團體之間的聯(lián)系，有助于對這些節(jié)點進行有目的的推送或者其他操作。信息網(wǎng)絡(luò)（InfoNetwork）是JiaweiHan和PhilipSYu等在EDBT2009和SIGMOD2010上正式提出和倡導(dǎo)的新概念[1-2]。它是對現(xiàn)實生活中問題和數(shù)據(jù)一般性的抽象，在日常生活中可以接觸一些信息網(wǎng)絡(luò)的實例，例如：蛋白質(zhì)網(wǎng)絡(luò)[3-4]、交通網(wǎng)絡(luò)[5]、通信網(wǎng)絡(luò)[6]、合作者網(wǎng)絡(luò)[7]、社交網(wǎng)絡(luò)[7-8]等，這些信息網(wǎng)絡(luò)的規(guī)模有大有小。目前對信息網(wǎng)絡(luò)的主要研究正越來越成為一個熱門方向，主要涉及到的領(lǐng)域有：信息網(wǎng)絡(luò)的可視化、在線分析處理、數(shù)據(jù)立方的構(gòu)建等。例如：文獻[9]提出了組件式信息網(wǎng)絡(luò)可視化框架（InformationNetworksVi-sualizationFramework，INVF），文獻[10][11]主要對信息網(wǎng)絡(luò)數(shù)據(jù)集進行面向主題、多維、多層次的在線分析處理（OnlineAnalyticalProcessing，OLAP），在傳統(tǒng)OLAP技術(shù)無法滿足上述處理情況下，提出了面向信息網(wǎng)絡(luò)的在線圖處理（OnlineGraphicProcessing，OLGP）模型，文獻[12]主要是從信息網(wǎng)絡(luò)的底層數(shù)據(jù)庫實現(xiàn)的角度提出了面向主題的、集成的信息網(wǎng)絡(luò)數(shù)據(jù)組織方案，以及具有一般性的多維信息網(wǎng)絡(luò)數(shù)據(jù)倉庫模型，與本文具有較強相關(guān)性的是文獻[13]和[14]，其中文獻[13]的主要工作是信息網(wǎng)絡(luò)樞紐節(jié)點的發(fā)現(xiàn)，提出基于拓撲維異步上卷的單位間樞紐點發(fā)現(xiàn)框架和算法，優(yōu)化了傳統(tǒng)算法的時間和空間復(fù)雜度較高的弱點，文獻[14]是利用信息網(wǎng)絡(luò)的拓撲維異步上卷提出基于額外窗口（AW）的信息網(wǎng)絡(luò)Top-k接近中心度核心節(jié)點挖掘算法。前人的工作主要存在著以下問題：①主要偏向于拓撲維上卷的應(yīng)用，沒有涉及算法的設(shè)計與實現(xiàn)。在部分工作中只是簡單進行暴力的剪枝操作，很多數(shù)據(jù)丟失。②只是對信息網(wǎng)絡(luò)的出度和入度較大的節(jié)點進行上卷。只考慮了某些中心節(jié)點或者樞紐節(jié)點，沒有對整個信息網(wǎng)絡(luò)加以深入研究。③不能根據(jù)用戶的特定需求進行有目的性的上卷操作，擴展性較差。只根據(jù)拓撲維進行上卷操作，而沒有對用戶的需求進行分析。基于前人工作的不足之處，本文的主要貢獻有：①根據(jù)信息網(wǎng)絡(luò)拓撲維上卷的性質(zhì)，首次提出了有效上卷代價概念。對于不同規(guī)模的數(shù)據(jù)集，根據(jù)其拓撲結(jié)構(gòu)，以及有效上卷代價可以預(yù)估其算法執(zhí)行時間，提出假設(shè)。②設(shè)計并實現(xiàn)了基于信息網(wǎng)絡(luò)拓撲維的上卷算法，并對算法的性能進行了優(yōu)化。③根據(jù)用戶特定需求有目的性的拓撲維上卷即可以對單一節(jié)點進行上卷，也可以對特定的模型進行上卷，滿足用戶的多重需求。

1問題定義

1.1預(yù)備知識

定義1信息網(wǎng)絡(luò)（InfoNetwork）信息網(wǎng)絡(luò)是基于圖定義，假設(shè)G=<V，E>表示一個圖結(jié)構(gòu)，其中V=<V1，V2，…，Vn>代表圖中所有的節(jié)點集合，E=<E1，E2，…，En>代表圖中所有的邊集合。信息網(wǎng)絡(luò)分為同構(gòu)信息網(wǎng)絡(luò)和異構(gòu)信息網(wǎng)絡(luò)，節(jié)點V的類型相同并且邊E代表單一屬性的為同構(gòu)信息網(wǎng)絡(luò)。節(jié)點V的類型不同并且E代表不同屬性的為異構(gòu)信息網(wǎng)絡(luò)。在日常生活中，信息網(wǎng)絡(luò)隨處可見，如圖1所示的是一個異構(gòu)的作戰(zhàn)信息網(wǎng)絡(luò)。每個節(jié)點代表不同的類型，有作戰(zhàn)人員、電腦、手槍、坦克，而且節(jié)點與節(jié)點之間的邊有各自不同的屬性。而圖2的合作者網(wǎng)絡(luò)則是一個典型的同構(gòu)信息網(wǎng)絡(luò)，每個節(jié)點代表一個作者，而作者-作者之間的邊代表者兩個作者合作發(fā)表過論文。本文采用的是同構(gòu)信息網(wǎng)絡(luò)進行試驗。定義2信息維（InformationDimension）設(shè)圖數(shù)據(jù)庫中待分析圖結(jié)構(gòu)為G（V，E）=G（V，θ（ID））。其中，V是圖中點的集合，E表示邊的集合，函數(shù)θ為圖G的邊信息決定函數(shù)。設(shè)變量ID={I1，I2，…，Im}是OLGP中待考察的維度集合，其中i=1，2，…，m。這m個信息屬性構(gòu)成的維度集合只能決定圖的邊集，不能改變圖的拓撲結(jié)構(gòu)，稱ID為信息維集合。通過圖3可以發(fā)現(xiàn)在對（1）與（2）進行信息聚集操作時，信息網(wǎng)絡(luò)的拓撲結(jié)構(gòu)并未發(fā)生改變。定義3拓撲維（TopologicalDimension）設(shè)變量TD={T1，T2，…，Tn}是刻畫OLGP中圖中心度量拓撲結(jié)構(gòu)的一個集合。一個圖可表示為G（V，E）=G（準（TD），δ（TD）），其中函數(shù)準為點拓撲決定函數(shù)，函數(shù)δ為邊拓撲決定函數(shù)。這n個拓撲屬性構(gòu)成的拓撲維決定圖的點集合和邊集合，從而決定圖的拓撲結(jié)構(gòu)，稱TD為拓撲維集合。通過圖4發(fā)現(xiàn)在對節(jié)點進行上卷操作時，在信息網(wǎng)絡(luò)中形成新的節(jié)點和邊，從而引起信息網(wǎng)絡(luò)的拓撲定義3有效上卷代價（Effectivecostroll-up）對信息網(wǎng)絡(luò)G=<V，E>進行上卷操作時，面臨的一個怎么進行節(jié)點的聚集和生成所需上卷后節(jié)點的問題，則定義有效上卷代價p。p=∑|v'|/∑|v|（1）其中v∈V為信息網(wǎng)絡(luò)中所有的節(jié)點個數(shù)，v'為滿足用戶上卷到指定維度后的節(jié)點數(shù)，p越大則進行拓撲維上卷操作所消耗的時間越大。

1.2問題定義

對信息網(wǎng)絡(luò)進行特定需求的上卷操作在對恐怖組織進行有效制裁、校企合作、進出口公司與合作國家的關(guān)系趨勢預(yù)測等方面都具有極其重要的意義，對于用戶指定的上卷層次，需要解決的問題：問題1.對特定節(jié)點不上卷，其他節(jié)點上卷；問題2.對特定社團不上卷，其他節(jié)點上卷；問題3.對特定模式不上卷，其他節(jié)點上卷。本文主要解決問題1，下面以制裁恐怖組織為例，表1假設(shè)為每個成員的個人信息，每個人共4個維度，每個維度的取值代表該成員上卷到本維度的值，如：將恐怖組織成員謝里夫上卷到維度3，則該成員上卷后的取值為C3。圖5為情報機構(gòu)獲取的恐怖組織關(guān)系網(wǎng)中部分成員之間的合作關(guān)系。當需要找到本•拉登與上卷層級為3（假定為公司名）的聯(lián)系時，則需要對信息網(wǎng)絡(luò)圖中除本拉登以外的其他所有節(jié)點進行上卷，找出它們之間的關(guān)系，如圖6所示。通過它們之間的聯(lián)系，反恐部門可以對這些公司進行經(jīng)濟等方面的制裁。

2拓撲維異步算法

2.1信息網(wǎng)絡(luò)拓撲維上卷框架

圖7給出了信息網(wǎng)絡(luò)拓撲維上卷的框架，由信息網(wǎng)絡(luò)拓撲圖和節(jié)點信息維度的映射，得到基于用戶特定需求的拓撲維上卷后的信息網(wǎng)絡(luò)拓撲圖。

2.2信息網(wǎng)絡(luò)拓撲維上卷算法設(shè)計

基于對信息網(wǎng)絡(luò)拓撲維上卷框架的理解，本文設(shè)計了信息網(wǎng)絡(luò)拓撲維上卷算法：算法1實現(xiàn)了對信息網(wǎng)絡(luò)中用戶關(guān)注的節(jié)點不進行上卷操作，其他所有節(jié)點均上卷到指定的維度。在現(xiàn)實生活中的信息網(wǎng)絡(luò)（如：合作者網(wǎng)絡(luò)），當查看某個節(jié)點與其他機構(gòu)之間的聯(lián)系時，根據(jù)文獻[15]六度空間理論，可能只需要查看該節(jié)點在信息網(wǎng)絡(luò)中第n跳范圍內(nèi)的所有機構(gòu)而非查看整個信息網(wǎng)絡(luò)，n越大所需的時間越多。本文設(shè)置n=3。算法2對算法1做出了改進：

3實驗

3.1數(shù)據(jù)集

本文在DBLP數(shù)據(jù)集上進行實驗，表1是數(shù)據(jù)集的簡單概述，根據(jù)數(shù)據(jù)集的具體情況，隨機生成了拓撲的維度，表2詳細描述了預(yù)處理后的數(shù)據(jù)集。DBLP合作網(wǎng)絡(luò)，兩位作者之間有邊則代表兩個作者有合作關(guān)系。

3.2實驗結(jié)果

目前國內(nèi)外針對用戶特定需求的信息網(wǎng)絡(luò)拓撲維上卷的研究尚屬空白區(qū)，大多數(shù)的研究人員都是對整個數(shù)據(jù)集進行上卷操作，不能滿足用戶的特點需求。本文主要做了兩組試驗：（1）信息網(wǎng)絡(luò)不同維度的上卷操作（2）優(yōu)化上述操作，指定跳數(shù)對于（1），本文根據(jù)算法1進行實驗，運用文獻[16]和文獻[17]提到的Java開源JUNG包，繪制的實驗結(jié)果如圖8所示，圖中紅點為用戶特定查詢節(jié)點，其他顏色的點分別代表數(shù)據(jù)集中除了查詢節(jié)點以外其他節(jié)點上卷到指定維度的節(jié)點集，上卷到各個維度所需時間以及進行不同跳數(shù)上卷效果曲線如圖9所示。通過圖9，發(fā)現(xiàn)隨著維度的增大進行上卷所需斷邊以及生產(chǎn)新邊的次數(shù)就越多，有效上卷代價p就越大，耗時必然越大。由于上卷整個數(shù)據(jù)集耗時太多，并且在實際生活中某個節(jié)點只要相鄰的n跳范圍內(nèi)的其他節(jié)點具有強關(guān)聯(lián)性。為了優(yōu)化算法1，本文提出了算法2，具體實驗的結(jié)果如圖10所示，根據(jù)實驗結(jié)果發(fā)現(xiàn)當n=3時，上卷所得的結(jié)果與遍歷整個數(shù)據(jù)的結(jié)果非常的接近，耗時較之提高幾個數(shù)量級，其中表3是上卷到維度1時不同跳數(shù)的耗時比較，證明了算法2的有效性。

4結(jié)語

本文主要根據(jù)信息網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，本文首次提出了有效上卷代價的概念并提出了假設(shè)，實驗室也很好的驗證了假設(shè)。本文針對用戶特定的需求，對某個特定節(jié)點不進行上卷，網(wǎng)絡(luò)中的其他節(jié)點均上卷到指定的維度，為此本文設(shè)計了信息網(wǎng)絡(luò)上卷算法，并在根據(jù)現(xiàn)實情況以及算法耗時過多的情況優(yōu)化了算法，能在減少耗時的基礎(chǔ)上很好地完成了算法，達到了預(yù)定目的。本文目前只是解決了對在節(jié)點的層次上進行上卷，進一步的工作主要會集中在對特定社團和特定模式進行上卷，并考慮更為復(fù)雜的信息網(wǎng)絡(luò)中。

參考文獻：

[9]李洋濤，李川，吳詩極，等.INVF：面向信息網(wǎng)絡(luò)的可視化框架與算法[J].計算機科學與探索，2013，7（12）：1104-1114.

[10]李川，趙磊，唐常杰，等.GraphOLAPing的建模、設(shè)計與實現(xiàn)[J].軟件學報，2011，22（2）:258-268.

[11]徐洪宇，李川，唐常杰.在線圖處理：面向信息網(wǎng)絡(luò)的在線分析處理[J].計算機科學與探索，2012，6（9）:97-110

[12]聶章艷，李川，唐常杰，等.面向OLGP的多維信息網(wǎng)絡(luò)數(shù)據(jù)倉庫模型設(shè)計[J].計算機科學與探索，2014，8（1）:51-60.

[13]楊尚乾，李川，唐常杰，等.基于拓撲維上卷的空航信息網(wǎng)絡(luò)樞紐節(jié)點發(fā)現(xiàn)[J].華中科技大學學報:自然科學版，2012（S1）:280-283.

[14]曾衛(wèi)，李川，唐常杰，等.復(fù)雜空航信息網(wǎng)絡(luò)樞紐節(jié)點的高效發(fā)現(xiàn)[J].華中科技大學學報:自然科學版，2012（S1）:280-283

[16]王柏，吳巍，徐超群，等.復(fù)雜網(wǎng)絡(luò)可視化研究綜述[J].計算機科學，2007:17-2.

作者：劉松 李川 單位：四川大學計算機學院