劉松，李川

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

基于用戶需求的信息網(wǎng)絡(luò)拓?fù)渚S上卷模型的研究

劉松，李川

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

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

信息網(wǎng)絡(luò)；特定需求；拓?fù)渚S；上卷

0 引言

信息網(wǎng)絡(luò)在日常生活中隨處可見，小到數(shù)十個(gè)節(jié)點(diǎn)組成的科研合作者網(wǎng)絡(luò)，大到百億級節(jié)點(diǎn)的社交網(wǎng)絡(luò)，信息網(wǎng)絡(luò)反映現(xiàn)實(shí)生活中各種類型的關(guān)系，如今對信息網(wǎng)絡(luò)的研究正日益成為一種熱點(diǎn)和趨勢。根據(jù)用戶指定的需求對信息網(wǎng)絡(luò)進(jìn)行上卷操作，則可以挖掘出某些節(jié)點(diǎn)與其他社會(huì)團(tuán)體之間的聯(lián)系，有助于對這些節(jié)點(diǎn)進(jìn)行有目的的推送或者其他操作。

信息網(wǎng)絡(luò)（InfoNetwork）是Jiawei Han和Philip S Yu等在EDBT2009和SIGMOD2010上正式提出和倡導(dǎo)的新概念[1-2]。它是對現(xiàn)實(shí)生活中問題和數(shù)據(jù)一般性的抽象，在日常生活中可以接觸一些信息網(wǎng)絡(luò)的實(shí)例，例如：蛋白質(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ò)的主要研究正越來越成為一個(gè)熱門方向，主要涉及到的領(lǐng)域有：信息網(wǎng)絡(luò)的可視化、在線分析處理、數(shù)據(jù)立方的構(gòu)建等。例如：文獻(xiàn)[9]提出了組件式信息網(wǎng)絡(luò)可視化框架（Information Networks Vi-sualization Framework，INVF），文獻(xiàn)[10][11]主要對信息網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行面向主題、多維、多層次的在線分析處理（Online Analytical Processing，OLAP），在傳統(tǒng)OLAP技術(shù)無法滿足上述處理情況下，提出了面向信息網(wǎng)絡(luò)的在線圖處理（Online Graphic Processing，OLGP）模型，文獻(xiàn)[12]主要是從信息網(wǎng)絡(luò)的底層數(shù)據(jù)庫實(shí)現(xiàn)的角度提出了面向主題的、集成的信息網(wǎng)絡(luò)數(shù)據(jù)組織方案，以及具有一般性的多維信息網(wǎng)絡(luò)數(shù)據(jù)倉庫模型，與本文具有較強(qiáng)相關(guān)性的是文獻(xiàn)[13]和[14]，其中文獻(xiàn)[13]的主要工作是信息網(wǎng)絡(luò)樞紐節(jié)點(diǎn)的發(fā)現(xiàn)，提出基于拓?fù)渚S異步上卷的單位間樞紐點(diǎn)發(fā)現(xiàn)框架和算法，優(yōu)化了傳統(tǒng)算法的時(shí)間和空間復(fù)雜度較高的弱點(diǎn)，文獻(xiàn)[14]是利用信息網(wǎng)絡(luò)的拓?fù)渚S異步上卷提出基于額外窗口（AW）的信息網(wǎng)絡(luò)Top-k接近中心度核心節(jié)點(diǎn)挖掘算法。

前人的工作主要存在著以下問題：

①主要偏向于拓?fù)渚S上卷的應(yīng)用，沒有涉及算法的設(shè)計(jì)與實(shí)現(xiàn)。在部分工作中只是簡單進(jìn)行暴力的剪枝操作，很多數(shù)據(jù)丟失。

②只是對信息網(wǎng)絡(luò)的出度和入度較大的節(jié)點(diǎn)進(jìn)行上卷。只考慮了某些中心節(jié)點(diǎn)或者樞紐節(jié)點(diǎn)，沒有對整個(gè)信息網(wǎng)絡(luò)加以深入研究。

③不能根據(jù)用戶的特定需求進(jìn)行有目的性的上卷操作，擴(kuò)展性較差。只根據(jù)拓?fù)渚S進(jìn)行上卷操作，而沒有對用戶的需求進(jìn)行分析。

基于前人工作的不足之處，本文的主要貢獻(xiàn)有：

①根據(jù)信息網(wǎng)絡(luò)拓?fù)渚S上卷的性質(zhì)，首次提出了有效上卷代價(jià)概念。對于不同規(guī)模的數(shù)據(jù)集，根據(jù)其拓?fù)浣Y(jié)構(gòu)，以及有效上卷代價(jià)可以預(yù)估其算法執(zhí)行時(shí)間，提出假設(shè)。

②設(shè)計(jì)并實(shí)現(xiàn)了基于信息網(wǎng)絡(luò)拓?fù)渚S的上卷算法，并對算法的性能進(jìn)行了優(yōu)化。

③根據(jù)用戶特定需求有目的性的拓?fù)渚S上卷即可以對單一節(jié)點(diǎn)進(jìn)行上卷，也可以對特定的模型進(jìn)行上卷，滿足用戶的多重需求。

1 問題定義

定義1信息網(wǎng)絡(luò)（InfoNetwork）信息網(wǎng)絡(luò)是基于圖定義，假設(shè)G=表示一個(gè)圖結(jié)構(gòu)，其中V=代表圖中所有的節(jié)點(diǎn)集合，E=代表圖中所有的邊集合。信息網(wǎng)絡(luò)分為同構(gòu)信息網(wǎng)絡(luò)和異構(gòu)信息網(wǎng)絡(luò)，節(jié)點(diǎn)V的類型相同并且邊E代表單一屬性的為同構(gòu)信息網(wǎng)絡(luò)。節(jié)點(diǎn)V的類型不同并且E代表不同屬性的為異構(gòu)信息網(wǎng)絡(luò)。

在日常生活中，信息網(wǎng)絡(luò)隨處可見，如圖1所示的是一個(gè)異構(gòu)的作戰(zhàn)信息網(wǎng)絡(luò)。每個(gè)節(jié)點(diǎn)代表不同的類型，有作戰(zhàn)人員、電腦、手槍、坦克，而且節(jié)點(diǎn)與節(jié)點(diǎn)之間的邊有各自不同的屬性。而圖2的合作者網(wǎng)絡(luò)則是一個(gè)典型的同構(gòu)信息網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)代表一個(gè)作者，而作者-作者之間的邊代表者兩個(gè)作者合作發(fā)表過論文。本文采用的是同構(gòu)信息網(wǎng)絡(luò)進(jìn)行試驗(yàn)。

定義2信息維（Information Dimension）設(shè)圖數(shù)據(jù)庫中待分析圖結(jié)構(gòu)為G（V，E）=G（V，θ（ID））。其中，V是圖中點(diǎn)的集合，E表示邊的集合，函數(shù)θ為圖G的邊信息決定函數(shù)。設(shè)變量ID={I1，I2，…，Im}是OLGP中待考察的維度集合，其中i=1，2，…，m。這m個(gè)信息屬性構(gòu)成的維度集合只能決定圖的邊集，不能改變圖的拓?fù)浣Y(jié)構(gòu)，稱ID為信息維集合。

通過圖3可以發(fā)現(xiàn)在對（1）與（2）進(jìn)行信息聚集操作時(shí)，信息網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)并未發(fā)生改變。

圖2 合作者網(wǎng)絡(luò)[ACM]

圖3 信息維聚集操作

定義3拓?fù)渚S（Topological Dimension）設(shè)變量TD={T1，T2，…，Tn}是刻畫OLGP中圖中心度量拓?fù)浣Y(jié)構(gòu)的一個(gè)集合。一個(gè)圖可表示為G（V，E）=G（準(zhǔn)（TD），δ（TD）），其中函數(shù)準(zhǔn)為點(diǎn)拓?fù)錄Q定函數(shù)，函數(shù)δ為邊拓?fù)錄Q定函數(shù)。這n個(gè)拓?fù)鋵傩詷?gòu)成的拓?fù)渚S決定圖的點(diǎn)集合和邊集合，從而決定圖的拓?fù)浣Y(jié)構(gòu)，稱TD為拓?fù)渚S集合。

通過圖4發(fā)現(xiàn)在對節(jié)點(diǎn)進(jìn)行上卷操作時(shí)，在信息網(wǎng)絡(luò)中形成新的節(jié)點(diǎn)和邊，從而引起信息網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的變化。

圖4 拓?fù)渚S上卷

定義3有效上卷代價(jià)（Effective cost roll-up）對信息網(wǎng)絡(luò)G=進(jìn)行上卷操作時(shí)，面臨的一個(gè)怎么進(jìn)行節(jié)點(diǎn)的聚集和生成所需上卷后節(jié)點(diǎn)的問題，則定義有效上卷代價(jià)p。

其中v∈V為信息網(wǎng)絡(luò)中所有的節(jié)點(diǎn)個(gè)數(shù)，v'為滿足用戶上卷到指定維度后的節(jié)點(diǎn)數(shù)，p越大則進(jìn)行拓?fù)渚S上卷操作所消耗的時(shí)間越大。

對信息網(wǎng)絡(luò)進(jìn)行特定需求的上卷操作在對恐怖組織進(jìn)行有效制裁、校企合作、進(jìn)出口公司與合作國家的關(guān)系趨勢預(yù)測等方面都具有極其重要的意義，對于用戶指定的上卷層次，需要解決的問題：

問題1.對特定節(jié)點(diǎn)不上卷，其他節(jié)點(diǎn)上卷；

問題2.對特定社團(tuán)不上卷，其他節(jié)點(diǎn)上卷；

問題3.對特定模式不上卷，其他節(jié)點(diǎn)上卷。

表1 恐怖成員的個(gè)人信息

本文主要解決問題1，下面以制裁恐怖組織為例，表1假設(shè)為每個(gè)成員的個(gè)人信息，每個(gè)人共4個(gè)維度，每個(gè)維度的取值代表該成員上卷到本維度的值，如：將恐怖組織成員謝里夫上卷到維度3，則該成員上卷后的取值為C3。

圖5為情報(bào)機(jī)構(gòu)獲取的恐怖組織關(guān)系網(wǎng)中部分成員之間的合作關(guān)系。當(dāng)需要找到本·拉登與上卷層級為3（假定為公司名）的聯(lián)系時(shí)，則需要對信息網(wǎng)絡(luò)圖中除本拉登以外的其他所有節(jié)點(diǎn)進(jìn)行上卷，找出它們之間的關(guān)系，如圖6所示。通過它們之間的聯(lián)系，反恐部門可以對這些公司進(jìn)行經(jīng)濟(jì)等方面的制裁。

圖5 恐怖組織成員關(guān)系

圖6 本·拉登與所有公司之間的聯(lián)系

2 拓?fù)渚S異步算法

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

基于對信息網(wǎng)絡(luò)拓?fù)渚S上卷框架的理解，本文設(shè)計(jì)了信息網(wǎng)絡(luò)拓?fù)渚S上卷算法：

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

圖7 信息網(wǎng)絡(luò)拓?fù)渚S上卷框架

Algorithm 1：拓?fù)渚S上卷算法

輸入：合作者網(wǎng)絡(luò)G=

特定的查詢query=（node，topo）

輸出：上卷后的新信息網(wǎng)絡(luò)G’

步驟：

Algorithm 2：拓?fù)渚S上卷算法

輸入：合作者網(wǎng)絡(luò)G=

特定的查詢query=（node，topo）

輸出：上卷后的新信息網(wǎng)絡(luò)G’

步驟：

3 實(shí)驗(yàn)

本文在DBLP數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，表1是數(shù)據(jù)集的簡單概述，根據(jù)數(shù)據(jù)集的具體情況，隨機(jī)生成了拓?fù)涞木S度，表2詳細(xì)描述了預(yù)處理后的數(shù)據(jù)集。

DBLP coauthor-ship（http://konect.uni-koblenz.de/ networks/dblp_coauthor）：DBLP合作網(wǎng)絡(luò)，兩位作者之間有邊則代表兩個(gè)作者有合作關(guān)系。

表2 數(shù)據(jù)集預(yù)處理結(jié)果

目前國內(nèi)外針對用戶特定需求的信息網(wǎng)絡(luò)拓?fù)渚S上卷的研究尚屬空白區(qū)，大多數(shù)的研究人員都是對整個(gè)數(shù)據(jù)集進(jìn)行上卷操作，不能滿足用戶的特點(diǎn)需求。本文主要做了兩組試驗(yàn)：

（1）信息網(wǎng)絡(luò)不同維度的上卷操作

（2）優(yōu)化上述操作，指定跳數(shù)

對于（1），本文根據(jù)算法1進(jìn)行實(shí)驗(yàn)，運(yùn)用文獻(xiàn)[16]和文獻(xiàn)[17]提到的Java開源JUNG包，繪制的實(shí)驗(yàn)結(jié)果如圖8所示，圖中紅點(diǎn)為用戶特定查詢節(jié)點(diǎn)，其他顏色的點(diǎn)分別代表數(shù)據(jù)集中除了查詢節(jié)點(diǎn)以外其他節(jié)點(diǎn)上卷到指定維度的節(jié)點(diǎn)集，上卷到各個(gè)維度所需時(shí)間以及進(jìn)行不同跳數(shù)上卷效果曲線如圖9所示。

圖8 信息網(wǎng)絡(luò)拓?fù)渚S上卷結(jié)果

圖9 信息網(wǎng)絡(luò)拓?fù)渚S上卷效果和耗時(shí)

通過圖9，發(fā)現(xiàn)隨著維度的增大進(jìn)行上卷所需斷邊以及生產(chǎn)新邊的次數(shù)就越多，有效上卷代價(jià)p就越大，耗時(shí)必然越大。

表3 不同跳數(shù)間上卷效果和耗時(shí)比較

由于上卷整個(gè)數(shù)據(jù)集耗時(shí)太多，并且在實(shí)際生活中某個(gè)節(jié)點(diǎn)只要相鄰的n跳范圍內(nèi)的其他節(jié)點(diǎn)具有強(qiáng)關(guān)聯(lián)性。為了優(yōu)化算法1，本文提出了算法2，具體實(shí)驗(yàn)的結(jié)果如圖10所示，根據(jù)實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)當(dāng)n=3時(shí)，上卷所得的結(jié)果與遍歷整個(gè)數(shù)據(jù)的結(jié)果非常的接近，耗時(shí)較之提高幾個(gè)數(shù)量級，其中表3是上卷到維度1時(shí)不同跳數(shù)的耗時(shí)比較，證明了算法2的有效性。

4 結(jié)語

本文主要根據(jù)信息網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，本文首次提出了有效上卷代價(jià)的概念并提出了假設(shè)，實(shí)驗(yàn)室也很好的驗(yàn)證了假設(shè)。本文針對用戶特定的需求，對某個(gè)特定節(jié)點(diǎn)不進(jìn)行上卷，網(wǎng)絡(luò)中的其他節(jié)點(diǎn)均上卷到指定的維度，為此本文設(shè)計(jì)了信息網(wǎng)絡(luò)上卷算法，并在根據(jù)現(xiàn)實(shí)情況以及算法耗時(shí)過多的情況優(yōu)化了算法，能在減少耗時(shí)的基礎(chǔ)上很好地完成了算法，達(dá)到了預(yù)定目的。

本文目前只是解決了對在節(jié)點(diǎn)的層次上進(jìn)行上卷，進(jìn)一步的工作主要會(huì)集中在對特定社團(tuán)和特定模式進(jìn)行上卷，并考慮更為復(fù)雜的信息網(wǎng)絡(luò)中。

圖10 不同跳數(shù)的拓?fù)渚S上卷結(jié)果

[1]HAN Jia-wei，YAN Xi-feng，Yu P S.Scalable OLAP and Mining of Information Network[C].Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology（EDBT 09）.New York，NY，USA:ACM，2009: 1159.

[2]HAN Jia-wei，SUN Yi-zhou，Yu P S，et al.Mining Knowledge from Databases:an Information Network Analysis Approach[C].Proceedings of the 2010 International Conference on Management of Data（SIGMOD 10）.New York，NY，USA:ACM，2010:1251-1252.

[3]Jeong H，Mason S P，Barabasi.A L and Oltvai Z N.Lethality and Centrality in Protein Networks[J].Nature，2001，411:41-42.

[4]Giot L E A，Bader J S，Brouwer C.A Protein Interaction Map of Drosophila Melanogaster[J].Science，2003，302:1727-1736.

[5]Xu X，Hu J，Liu F，Liu L.Scaling and Correlations in Three Bus-transport Networks of China[J].Physica A，2007，374:441-448.

[6]Huberman B A，Lukose R M.An Economics Approach to Hard Computational Problems[J].Science，1997，275:51-54.

[7]luo J.Analysis of Social Network[M].Beijing:Social Sciences Academic Press，2005:152-168

[8]Zhang P P，Chen K，He Y，et al.Model and Empirical Study on Some Collaboration Networks[J].Physica A，2006，360:599-616.

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

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

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

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

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

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

[15]Ergin Elmacioglu，Dongwon Lee On Six Degrees of Separation in DBLP-DB and More，SIGMOD Record，Vol.34，No.2，June 2005

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

[17]JUNG.http://jung.sourceforge.net.

Research on Information Network Topology Model Based on User Demand Volume

LIU Song，LI Chuan

（College of Computer Science，Sichuan University，Chengdu 610065）

With the development of information networks，the network topology information on the volume dimension is becoming a hot spot in the field，while its value also will increase.The main work is for a given node is not on the volume，the volume to a specified level approach on other nodes to meet the specific needs of the user.It proposed to meet the information needs of users on the network topology dimen-sional volume model.The main contribution is：（1）first proposed the concept of the effective cost of the volume,（2）the first time the specific needs of the user on the volume,（3）design the topological dimension algorithm information on the volume of the network.Ex-periments show that our algorithm can meet the specific needs of users to achieve specified operation on a volume topological dimension, with strong value.

Information Network;Specific Requirements;Topological Dimension;Coil

1007-1423（2016）08-0010-07

10.3969/j.issn.1007-1423.2016.08.002

劉松（1989-），男，江蘇淮安人，碩士，研究方向?yàn)樾畔⒕W(wǎng)絡(luò)、數(shù)據(jù)挖掘、分布式計(jì)算

2016-02-17

2016-03-10

李川（1977-），男，河南鄭州人，博士，副教授，研究方向?yàn)閿?shù)據(jù)庫、數(shù)據(jù)挖掘