基于用戶需求的信息網絡拓撲維上卷模型的研究

劉松，李川

（四川大學計算機學院，成都 610065）

基于用戶需求的信息網絡拓撲維上卷模型的研究

劉松，李川

（四川大學計算機學院，成都 610065）

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

信息網絡；特定需求；拓撲維；上卷

0 引言

信息網絡在日常生活中隨處可見，小到數十個節點組成的科研合作者網絡，大到百億級節點的社交網絡，信息網絡反映現實生活中各種類型的關系，如今對信息網絡的研究正日益成為一種熱點和趨勢。根據用戶指定的需求對信息網絡進行上卷操作，則可以挖掘出某些節點與其他社會團體之間的聯系，有助于對這些節點進行有目的的推送或者其他操作。

信息網絡（InfoNetwork）是Jiawei Han和Philip S Yu等在EDBT2009和SIGMOD2010上正式提出和倡導的新概念[1-2]。它是對現實生活中問題和數據一般性的抽象，在日常生活中可以接觸一些信息網絡的實例，例如：蛋白質網絡[3-4]、交通網絡[5]、通信網絡[6]、合作者網絡[7]、社交網絡[7-8]等，這些信息網絡的規模有大有小。

目前對信息網絡的主要研究正越來越成為一個熱門方向，主要涉及到的領域有：信息網絡的可視化、在線分析處理、數據立方的構建等。例如：文獻[9]提出了組件式信息網絡可視化框架（Information Networks Vi-sualization Framework，INVF），文獻[10][11]主要對信息網絡數據集進行面向主題、多維、多層次的在線分析處理（Online Analytical Processing，OLAP），在傳統OLAP技術無法滿足上述處理情況下，提出了面向信息網絡的在線圖處理（Online Graphic Processing，OLGP）模型，文獻[12]主要是從信息網絡的底層數據庫實現的角度提出了面向主題的、集成的信息網絡數據組織方案，以及具有一般性的多維信息網絡數據倉庫模型，與本文具有較強相關性的是文獻[13]和[14]，其中文獻[13]的主要工作是信息網絡樞紐節點的發現，提出基于拓撲維異步上卷的單位間樞紐點發現框架和算法，優化了傳統算法的時間和空間復雜度較高的弱點，文獻[14]是利用信息網絡的拓撲維異步上卷提出基于額外窗口（AW）的信息網絡Top-k接近中心度核心節點挖掘算法。

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

①主要偏向于拓撲維上卷的應用，沒有涉及算法的設計與實現。在部分工作中只是簡單進行暴力的剪枝操作，很多數據丟失。

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

③不能根據用戶的特定需求進行有目的性的上卷操作，擴展性較差。只根據拓撲維進行上卷操作，而沒有對用戶的需求進行分析。

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

①根據信息網絡拓撲維上卷的性質，首次提出了有效上卷代價概念。對于不同規模的數據集，根據其拓撲結構，以及有效上卷代價可以預估其算法執行時間，提出假設。

②設計并實現了基于信息網絡拓撲維的上卷算法，并對算法的性能進行了優化。

③根據用戶特定需求有目的性的拓撲維上卷即可以對單一節點進行上卷，也可以對特定的模型進行上卷，滿足用戶的多重需求。

1 問題定義

定義1信息網絡（InfoNetwork）信息網絡是基于圖定義，假設G=表示一個圖結構，其中V=代表圖中所有的節點集合，E=代表圖中所有的邊集合。信息網絡分為同構信息網絡和異構信息網絡，節點V的類型相同并且邊E代表單一屬性的為同構信息網絡。節點V的類型不同并且E代表不同屬性的為異構信息網絡。

在日常生活中，信息網絡隨處可見，如圖1所示的是一個異構的作戰信息網絡。每個節點代表不同的類型，有作戰人員、電腦、手槍、坦克，而且節點與節點之間的邊有各自不同的屬性。而圖2的合作者網絡則是一個典型的同構信息網絡，每個節點代表一個作者，而作者-作者之間的邊代表者兩個作者合作發表過論文。本文采用的是同構信息網絡進行試驗。

定義2信息維（Information Dimension）設圖數據庫中待分析圖結構為G（V，E）=G（V，θ（ID））。其中，V是圖中點的集合，E表示邊的集合，函數θ為圖G的邊信息決定函數。設變量ID={I1，I2，…，Im}是OLGP中待考察的維度集合，其中i=1，2，…，m。這m個信息屬性構成的維度集合只能決定圖的邊集，不能改變圖的拓撲結構，稱ID為信息維集合。

通過圖3可以發現在對（1）與（2）進行信息聚集操作時，信息網絡的拓撲結構并未發生改變。

圖2 合作者網絡[ACM]

圖3 信息維聚集操作

定義3拓撲維（Topological Dimension）設變量TD={T1，T2，…，Tn}是刻畫OLGP中圖中心度量拓撲結構的一個集合。一個圖可表示為G（V，E）=G（準（TD），δ（TD）），其中函數準為點拓撲決定函數，函數δ為邊拓撲決定函數。這n個拓撲屬性構成的拓撲維決定圖的點集合和邊集合，從而決定圖的拓撲結構，稱TD為拓撲維集合。

通過圖4發現在對節點進行上卷操作時，在信息網絡中形成新的節點和邊，從而引起信息網絡的拓撲結構的變化。

圖4 拓撲維上卷

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

其中v∈V為信息網絡中所有的節點個數，v'為滿足用戶上卷到指定維度后的節點數，p越大則進行拓撲維上卷操作所消耗的時間越大。

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

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

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

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

表1 恐怖成員的個人信息

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

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

圖5 恐怖組織成員關系

圖6 本·拉登與所有公司之間的聯系

2 拓撲維異步算法

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

基于對信息網絡拓撲維上卷框架的理解，本文設計了信息網絡拓撲維上卷算法：

算法1實現了對信息網絡中用戶關注的節點不進行上卷操作，其他所有節點均上卷到指定的維度。在現實生活中的信息網絡（如：合作者網絡），當查看某個節點與其他機構之間的聯系時，根據文獻[15]六度空間理論，可能只需要查看該節點在信息網絡中第n跳范圍內的所有機構而非查看整個信息網絡，n越大所需的時間越多。本文設置n=3。算法2對算法1做出了改進：

圖7 信息網絡拓撲維上卷框架

Algorithm 1：拓撲維上卷算法

輸入：合作者網絡G=

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

輸出：上卷后的新信息網絡G’

步驟：

Algorithm 2：拓撲維上卷算法

輸入：合作者網絡G=

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

輸出：上卷后的新信息網絡G’

步驟：

3 實驗

本文在DBLP數據集上進行實驗，表1是數據集的簡單概述，根據數據集的具體情況，隨機生成了拓撲的維度，表2詳細描述了預處理后的數據集。

DBLP coauthor-ship（http://konect.uni-koblenz.de/ networks/dblp_coauthor）：DBLP合作網絡，兩位作者之間有邊則代表兩個作者有合作關系。

表2 數據集預處理結果

目前國內外針對用戶特定需求的信息網絡拓撲維上卷的研究尚屬空白區，大多數的研究人員都是對整個數據集進行上卷操作，不能滿足用戶的特點需求。本文主要做了兩組試驗：

（1）信息網絡不同維度的上卷操作

（2）優化上述操作，指定跳數

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

圖8 信息網絡拓撲維上卷結果

圖9 信息網絡拓撲維上卷效果和耗時

通過圖9，發現隨著維度的增大進行上卷所需斷邊以及生產新邊的次數就越多，有效上卷代價p就越大，耗時必然越大。

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

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

4 結語

本文主要根據信息網絡的拓撲結構，本文首次提出了有效上卷代價的概念并提出了假設，實驗室也很好的驗證了假設。本文針對用戶特定的需求，對某個特定節點不進行上卷，網絡中的其他節點均上卷到指定的維度，為此本文設計了信息網絡上卷算法，并在根據現實情況以及算法耗時過多的情況優化了算法，能在減少耗時的基礎上很好地完成了算法，達到了預定目的。

本文目前只是解決了對在節點的層次上進行上卷，進一步的工作主要會集中在對特定社團和特定模式進行上卷，并考慮更為復雜的信息網絡中。

圖10 不同跳數的拓撲維上卷結果

[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：面向信息網絡的可視化框架與算法[J].計算機科學與探索，2013，7（12）：1104-1114.

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

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

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

[13]楊尚乾，李川，唐常杰，等.基于拓撲維上卷的空航信息網絡樞紐節點發現[J].華中科技大學學報:自然科學版，2012（S1）:280-283.

[14]曾衛，李川，唐常杰，等.復雜空航信息網絡樞紐節點的高效發現[J].華中科技大學學報:自然科學版，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]王柏，吳巍，徐超群，等.復雜網絡可視化研究綜述[J].計算機科學，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-），男，江蘇淮安人，碩士，研究方向為信息網絡、數據挖掘、分布式計算

2016-02-17

2016-03-10

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