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

劉松，李川

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

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

劉松，李川

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

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

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

0 引言

信息網(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）是Jiawei Han和Philip S Yu等在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ò)可視化框架（Information Networks Vi-sualization Framework，INVF），文獻[10][11]主要對信息網(wǎng)絡(luò)數(shù)據(jù)集進行面向主題、多維、多層次的在線分析處理（Online Analytical Processing，OLAP），在傳統(tǒng)OLAP技術(shù)無法滿足上述處理情況下，提出了面向信息網(wǎng)絡(luò)的在線圖處理（Online Graphic Processing，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ù)渚S異步上卷的單位間樞紐點發(fā)現(xiàn)框架和算法，優(yōu)化了傳統(tǒng)算法的時間和空間復(fù)雜度較高的弱點，文獻[14]是利用信息網(wǎng)絡(luò)的拓?fù)渚S異步上卷提出基于額外窗口（AW）的信息網(wǎng)絡(luò)Top-k接近中心度核心節(jié)點挖掘算法。

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

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

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

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

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

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

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

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

1 問題定義

定義1信息網(wǎng)絡(luò)（InfoNetwork）信息網(wǎng)絡(luò)是基于圖定義，假設(shè)G=表示一個圖結(jié)構(gòu)，其中V=代表圖中所有的節(jié)點集合，E=代表圖中所有的邊集合。信息網(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信息維（Information Dimension）設(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)成的維度集合只能決定圖的邊集，不能改變圖的拓?fù)浣Y(jié)構(gòu)，稱ID為信息維集合。

通過圖3可以發(fā)現(xiàn)在對（1）與（2）進行信息聚集操作時，信息網(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（V，E）=G（準(zhǔn)（TD），δ（TD）），其中函數(shù)準(zhǔn)為點拓?fù)錄Q定函數(shù)，函數(shù)δ為邊拓?fù)錄Q定函數(shù)。這n個拓?fù)鋵傩詷?gòu)成的拓?fù)渚S決定圖的點集合和邊集合，從而決定圖的拓?fù)浣Y(jié)構(gòu)，稱TD為拓?fù)渚S集合。

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

圖4 拓?fù)渚S上卷

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

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

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

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

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

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

表1 恐怖成員的個人信息

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

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

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

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

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

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

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

算法1實現(xiàn)了對信息網(wǎng)絡(luò)中用戶關(guān)注的節(jié)點不進行上卷操作，其他所有節(jié)點均上卷到指定的維度。在現(xiàn)實生活中的信息網(wǎng)絡(luò)（如：合作者網(wǎng)絡(luò)），當(dāng)查看某個節(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做出了改進：

圖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 實驗

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

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

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

目前國內(nèi)外針對用戶特定需求的信息網(wǎng)絡(luò)拓?fù)渚S上卷的研究尚屬空白區(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所示。

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

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

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

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

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

4 結(jié)語

本文主要根據(jù)信息網(wǎng)絡(luò)的拓?fù)浣Y(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ò)中。

圖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].計算機科學(xué)與探索，2013，7（12）：1104-1114.

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

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

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

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

[14]曾衛(wèi)，李川，唐常杰，等.復(fù)雜空航信息網(wǎng)絡(luò)樞紐節(jié)點的高效發(fā)現(xiàn)[J].華中科技大學(xué)學(xué)報:自然科學(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].計算機科學(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-），男，江蘇淮安人，碩士，研究方向為信息網(wǎng)絡(luò)、數(shù)據(jù)挖掘、分布式計算

2016-02-17

2016-03-10

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