尹丹++高宏

摘要： 信息網(wǎng)絡(luò)是一種由圖建模的網(wǎng)絡(luò)，包含頂點(diǎn)和邊兩個(gè)元素。其中頂點(diǎn)代表現(xiàn)實(shí)世界中的實(shí)體對象，邊代表實(shí)體之間的聯(lián)系。實(shí)體以及相互之間的聯(lián)系就構(gòu)成了信息網(wǎng)絡(luò)。信息網(wǎng)絡(luò)廣泛存在于現(xiàn)實(shí)世界中，如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、道路網(wǎng)絡(luò)、知識庫等。信息網(wǎng)絡(luò)是無所不在的。在現(xiàn)實(shí)世界中，信息網(wǎng)絡(luò)通常被假定為同構(gòu)的，即網(wǎng)絡(luò)中頂點(diǎn)的類型是相同的，頂點(diǎn)之間的關(guān)系類型也是相同的。然而，大多數(shù)真實(shí)世界的網(wǎng)絡(luò)是異構(gòu)的，即頂點(diǎn)和關(guān)系的類型是不同的。異構(gòu)信息網(wǎng)是包括多種類型頂點(diǎn)和多種類型的邊的信息網(wǎng)。異構(gòu)信息網(wǎng)可以在很多領(lǐng)域中構(gòu)建得到，如社交網(wǎng)絡(luò)、電子商務(wù)、在線電影數(shù)據(jù)庫等許多數(shù)據(jù)庫應(yīng)用中。因此，異構(gòu)信息網(wǎng)能夠很好地表達(dá)現(xiàn)實(shí)世界中不同類型實(shí)體和實(shí)體之間復(fù)雜的關(guān)系。全面介紹了異構(gòu)信息網(wǎng)的現(xiàn)有研究工作，并對該領(lǐng)域未來可能的發(fā)展方向進(jìn)行了總結(jié)和展望。

關(guān)鍵詞：異構(gòu)信息網(wǎng)； 數(shù)據(jù)挖掘； 查詢

中圖分類號： TP311.1

文獻(xiàn)標(biāo)志碼： A

文章編號： 2095-2163（2016）06-0094-04

0引言

信息網(wǎng)絡(luò)是一種由圖建模的數(shù)學(xué)模型，其中包含頂點(diǎn)和邊兩個(gè)元素。頂點(diǎn)代表現(xiàn)實(shí)世界中的實(shí)體對象，邊代表實(shí)體之間的聯(lián)系，實(shí)體以及實(shí)體之間的聯(lián)系就構(gòu)成了信息網(wǎng)絡(luò)。隨著信息技術(shù)的發(fā)展，越來越多的領(lǐng)域開始關(guān)注于數(shù)據(jù)對象之間錯(cuò)綜復(fù)雜的關(guān)系。例如，生物信息學(xué)領(lǐng)域中研究基因、酶、蛋白質(zhì)之間復(fù)雜的調(diào)控、代謝與交互關(guān)系；互聯(lián)網(wǎng)搜索領(lǐng)域中研究網(wǎng)頁與網(wǎng)頁之間超鏈接的關(guān)系；社會學(xué)和商業(yè)領(lǐng)域中研究人與人之間的社會關(guān)系。隨著信息技術(shù)的發(fā)展，特別是互聯(lián)網(wǎng)技術(shù)的發(fā)展，各種應(yīng)用領(lǐng)域的信息量都呈爆炸性增長趨勢。在現(xiàn)實(shí)應(yīng)用中積累了大量的圖數(shù)據(jù)，例如生物信息學(xué)中的基因調(diào)控網(wǎng)絡(luò)、酶代謝網(wǎng)絡(luò)、蛋白質(zhì)交互網(wǎng)絡(luò)；互聯(lián)網(wǎng)領(lǐng)域的網(wǎng)頁拓?fù)浣Y(jié)構(gòu)圖、郵件通訊關(guān)系圖；在線社交網(wǎng)站中用戶之間的社會關(guān)系圖；城市的道路交通網(wǎng)絡(luò)、供水排水網(wǎng)絡(luò)等。信息網(wǎng)絡(luò)廣泛存在于現(xiàn)實(shí)世界中，如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、道路網(wǎng)絡(luò)、知識庫等。信息網(wǎng)絡(luò)上的查詢和挖掘問題也具有重要的研究意義。

這些圖數(shù)據(jù)的規(guī)模還在不斷快速增長，其中蘊(yùn)含了大量有用的知識。挖掘和處理圖數(shù)據(jù)可以得到這些有用的信息幫助用戶分析決策。截至2009年9月，全球最大的社交網(wǎng)絡(luò)Facebook已有3億多個(gè)頂點(diǎn)。這些大規(guī)模圖數(shù)據(jù)承載了海量信息。用戶根本無法通過視覺觀察或手工方法來理解和分析。并且，現(xiàn)實(shí)世界中實(shí)體不僅僅是單純的一種類型，而是多種類型的實(shí)體同時(shí)存在一個(gè)網(wǎng)絡(luò)中；再有，聯(lián)系也不僅僅存在于同一類型的實(shí)體內(nèi)部，在不同類型的實(shí)體之間同樣也存在著關(guān)系。異構(gòu)多屬性圖是包含多種類型頂點(diǎn)和多種類型邊的圖，其中每種類型頂點(diǎn)具有一組屬性。如生物網(wǎng)絡(luò)、社交媒體網(wǎng)絡(luò)、在線分享網(wǎng)絡(luò)等。在圖數(shù)據(jù)規(guī)模爆炸式增長的同時(shí)，圖數(shù)據(jù)的形式也越來越復(fù)雜。因此，海量圖數(shù)據(jù)模型中蘊(yùn)含著大量有用的知識與信息，亟需從不同維度和不同粒度上對其進(jìn)行研究提取、挖掘分析。

[BT4]1異構(gòu)信息網(wǎng)

[BT5]1.1異構(gòu)信息網(wǎng)的概念

在現(xiàn)實(shí)世界中，信息網(wǎng)絡(luò)通常被假定為同構(gòu)的，即網(wǎng)絡(luò)中頂點(diǎn)的類型是相同的（如用戶），頂點(diǎn)之間的關(guān)系類型也是相同的（如朋友關(guān)系）。然而，大多數(shù)真實(shí)世界的網(wǎng)絡(luò)是異構(gòu)的，即頂點(diǎn)和關(guān)系的類型是不同的。例如，在醫(yī)療保健網(wǎng)絡(luò)中，頂點(diǎn)可以是病人、醫(yī)生、醫(yī)療檢查、疾病、藥物、醫(yī)院、治療等。把頂點(diǎn)全部看作一種類型，也就是同構(gòu)信息網(wǎng)絡(luò)，可能導(dǎo)致丟失重要的語義信息。因此，對具有豐富信息和復(fù)雜結(jié)構(gòu)的異構(gòu)信息網(wǎng)進(jìn)行分析和挖掘研究是非常重要的。下面將給出異構(gòu)信息網(wǎng)的形式化定義。

異構(gòu)信息網(wǎng)是一個(gè)有向圖G=（V，E，T，R，V，E，A，D，A），其中V是頂點(diǎn)集合，EV×V是邊集合，T是頂點(diǎn)的類型集合，R是邊的類型集合。V：V→T是頂點(diǎn)類型映射函數(shù)，E：E→R是邊類型的映射函數(shù)。A是頂點(diǎn)的屬性集合，D是A的域。A：T→A是從頂點(diǎn)類型到屬性的映射函數(shù)。

[BT5]1.2異構(gòu)信息網(wǎng)的應(yīng)用

異構(gòu)信息網(wǎng)可以從交互的大規(guī)模數(shù)據(jù)中構(gòu)建得來，例如社交網(wǎng)絡(luò)、科學(xué)網(wǎng)絡(luò)、工程及商業(yè)應(yīng)用等，下面文中則給出幾個(gè)例子用以具體說明。

1）社交媒體網(wǎng)。 Twitter也可以被看做一個(gè)異構(gòu)信息網(wǎng)絡(luò)，其中包含頂點(diǎn)類型有用戶、推文、標(biāo)簽和詞語。2個(gè)用戶可以互相關(guān)注，用戶可以發(fā)布或回復(fù)推文，推文可以使用詞語、并包含某些標(biāo)簽。Flickr是一個(gè)圖片分享網(wǎng)站，也可以被看成異構(gòu)信息網(wǎng)。其實(shí)現(xiàn)結(jié)構(gòu)中包含的頂點(diǎn)類型有：圖片、用戶、標(biāo)簽、分組和評論。用戶可以上傳圖片，圖片包含某些標(biāo)簽、圖片屬于某個(gè)分組，用戶可以對圖片發(fā)表評論，圖片可以有不同的評論。

2）物聯(lián)網(wǎng)。在智能家居、交通、物流、農(nóng)業(yè)等物聯(lián)網(wǎng)中，都可以構(gòu)建出異構(gòu)信息網(wǎng)。例如，在智能家居網(wǎng)絡(luò)中，頂點(diǎn)類型有用戶、智能終端（空調(diào)、熱水器、音響等）、智能控制系統(tǒng)、傳感器節(jié)點(diǎn)、手機(jī)或電腦。用戶通過手機(jī)或電腦遠(yuǎn)程發(fā)送命令給智能控制系統(tǒng)，智能控制系統(tǒng)將命令發(fā)送給相應(yīng)的傳感器節(jié)點(diǎn)，傳感器節(jié)點(diǎn)再根據(jù)用戶的需求發(fā)送命令給指定的智能終端對其進(jìn)行操作。

3）文獻(xiàn)信息網(wǎng)絡(luò)。從DBLP中提取的計(jì)算機(jī)科學(xué)文獻(xiàn)信息就是一個(gè)典型的異構(gòu)信息網(wǎng)，其中包含4種類型頂點(diǎn)：論文、會議、作者和關(guān)鍵詞。每篇論文對應(yīng)一個(gè)作者集合、一個(gè)會議和一組關(guān)鍵詞，構(gòu)成了3種類型的關(guān)系。同時(shí)，在論文之間還存在引用關(guān)系。

4）醫(yī)療健康網(wǎng)絡(luò)。 醫(yī)療健康系統(tǒng)也可以被看成一個(gè)異構(gòu)信息網(wǎng)，其中包含的頂點(diǎn)類型有醫(yī)生、病人、疾病、治療和設(shè)備。病人患有某種疾病，該疾病可以采取特定的治療方案，使用某種設(shè)備，此外，病人也需要由特定的醫(yī)生負(fù)責(zé)。

異構(gòu)信息網(wǎng)可以在很多領(lǐng)域中構(gòu)建得到，如社交網(wǎng)絡(luò)、電子商務(wù)、社交媒體等許多數(shù)據(jù)庫應(yīng)用中。異構(gòu)信息網(wǎng)包含多種類型的頂點(diǎn)和多種類型的邊，每種類型頂點(diǎn)包含一組屬性。例如，用戶的屬性可以是其編號、姓名、年齡、城市等。

2異構(gòu)信息網(wǎng)研究現(xiàn)狀

除了異構(gòu)信息網(wǎng)上復(fù)雜的結(jié)構(gòu)信息，頂點(diǎn)的屬性信息對于挖掘異構(gòu)信息網(wǎng)也發(fā)揮著至關(guān)重要的作用。信息網(wǎng)上現(xiàn)有大多數(shù)研究成果都是基于同構(gòu)信息網(wǎng)的，比如社交網(wǎng)絡(luò)[1]上的排序、社團(tuán)發(fā)現(xiàn)、鏈接預(yù)測、影響力傳播等。然而，這些方法都不能直接用于異構(gòu)信息網(wǎng)上。這不僅因?yàn)檫B接不同類型頂點(diǎn)之間的不同類型的邊所具有的語義不同，也是因?yàn)楫悩?gòu)信息網(wǎng)包含了比同構(gòu)網(wǎng)絡(luò)更豐富的信息。同構(gòu)信息網(wǎng)可以通過在異構(gòu)信息網(wǎng)上的投影得到，但是卻丟失了大量的信息。例如，作者合作網(wǎng)絡(luò)可以從更復(fù)雜的異構(gòu)的文獻(xiàn)信息網(wǎng)絡(luò)中投影得到。然而，這種投影操作丟失了有用的信息，如該論文的主題以及該論文作者合作的其它論文等。另外，在原始的異構(gòu)信息網(wǎng)中蘊(yùn)藏著豐富的信息，需要設(shè)計(jì)有效的數(shù)據(jù)挖掘方法用來探索這些有用的信息。

相比傳統(tǒng)同構(gòu)信息網(wǎng)上的研究，異構(gòu)信息網(wǎng)上的研究工作才獲發(fā)展起步。但在最近幾年，越來越多的工作開始關(guān)注異構(gòu)信息網(wǎng)方面的研究。異構(gòu)信息網(wǎng)上現(xiàn)有的研究工作還都比較零散，也未形成規(guī)模體系，主要有聚簇[2–7]、基于排序的分類[8- 9]、頂點(diǎn)的相似性搜索[10- 11]、關(guān)系預(yù)測[12-14]、子圖查詢[15- 16]、社區(qū)發(fā)現(xiàn)[17]、實(shí)體識別[18]、無結(jié)構(gòu)查詢[19]等。下面，文中將分別介紹這些已有的研究成果。

2.1異構(gòu)信息網(wǎng)上聚簇問題的研究

Rankclus[2]將DBLP網(wǎng)絡(luò)構(gòu)建成二分圖，根據(jù)排序?qū)⑾嗤愋偷亩c(diǎn)進(jìn)行聚集。信息網(wǎng)絡(luò)的分析中，文獻(xiàn)[4， 7]根據(jù)用戶選擇的頂點(diǎn)類型和簇的種子頂點(diǎn)，對該類型的頂點(diǎn)進(jìn)行聚簇。文獻(xiàn)[6]在頂點(diǎn)屬性不完整的情況下，基于頂點(diǎn)的屬性和不同類型的關(guān)系，對網(wǎng)絡(luò)進(jìn)行聚簇。系統(tǒng)通過學(xué)習(xí)得到不同類型的關(guān)系的權(quán)重，將用戶指定的屬性集合帶有權(quán)重的不同類型關(guān)系合并，建立一個(gè)概率模型，用于訓(xùn)練出最符合用戶需求的聚簇結(jié)果。文獻(xiàn)[5]以網(wǎng)絡(luò)中的一種類型頂點(diǎn)為中心，根據(jù)元路徑將網(wǎng)絡(luò)分解成為若干個(gè)路徑圖。元路徑是不同類型頂點(diǎn)構(gòu)成的序列，表示了頂點(diǎn)由不同的關(guān)系連接起來。例如元路徑“作者-論文-作者”代表作者之間的合作關(guān)系，元路徑“作者-論文-會議-論文-作者”表示在同一個(gè)會議發(fā)表過論文的作者。通過學(xué)習(xí)得到每個(gè)路徑圖的權(quán)重，將所有路徑圖加權(quán)得到統(tǒng)一的路徑圖。在該路徑圖上對頂點(diǎn)進(jìn)行聚簇。

2.2異構(gòu)信息網(wǎng)上分類問題的研究

RankClass[8]把排序與分類相結(jié)合，對異構(gòu)信息網(wǎng)進(jìn)行更好的分析。該方法把頂點(diǎn)進(jìn)行分類，在每個(gè)分類內(nèi)對頂點(diǎn)進(jìn)行排序。例如，對于DBLP 異構(gòu)信息網(wǎng)，先把會議頂點(diǎn)按照領(lǐng)域進(jìn)行分類，在每個(gè)領(lǐng)域內(nèi)對頂點(diǎn)進(jìn)行排序，可以使用戶很清楚地了解每個(gè)領(lǐng)域內(nèi)影響較大的會議。這種排序與分類相結(jié)合的方法，要好于對頂點(diǎn)進(jìn)行全局的排序。分類對頂點(diǎn)進(jìn)行排序提高了排序的質(zhì)量，優(yōu)秀的排序結(jié)果也使分類更為準(zhǔn)確。GNetMine[9]研究異構(gòu)信息網(wǎng)絡(luò)上只有一部分頂點(diǎn)具有標(biāo)簽，通過將頂點(diǎn)分類，得到所有頂點(diǎn)的標(biāo)簽問題。通過衡量無標(biāo)簽頂點(diǎn)與帶有標(biāo)簽頂點(diǎn)之間鏈接關(guān)系的一致性，把無標(biāo)簽頂點(diǎn)與其相關(guān)的帶有標(biāo)簽頂點(diǎn)劃為同一類，得到所有類型頂點(diǎn)的標(biāo)簽。

[BT5]2.3異構(gòu)信息網(wǎng)上頂點(diǎn)相似/相關(guān)性問題的研究

基于元路徑的異構(gòu)信息網(wǎng)上的搜索技術(shù)在最近兩年得到了關(guān)注與重視。Pathsim[10]提出計(jì)算2個(gè)同類型頂點(diǎn)在給定元路徑情況下的相似性的方法。2個(gè)頂點(diǎn)通過不同的元路徑連接表示不同的含義，其相似性也不相同。信息網(wǎng)上現(xiàn)有的相似性所有工作大多數(shù)都集中在同構(gòu)信息網(wǎng)上。這些工作都忽略了頂點(diǎn)由不同類型的關(guān)系連接，具有的含義不同。進(jìn)一步地，給定查詢頂點(diǎn)，Pathsim能夠有效地計(jì)算出與查詢相似度最高的k個(gè)頂點(diǎn)，效率遠(yuǎn)遠(yuǎn)高于PageRank和SimRank. HeteSim[11]提出異構(gòu)信息網(wǎng)上同類型或不同類型頂點(diǎn)之間相關(guān)性的度量。衡量不同類型頂點(diǎn)之間的相似性是十分有意義的。如作者J.F. Naughton與會議SIGMOD相關(guān)程度比會議KDD大，青少年更喜歡電影哈利波特，而不是肖申克的救贖。這種不同類型頂點(diǎn)的相關(guān)性研究有著大范圍的廣泛應(yīng)用，例如推薦系統(tǒng)、聚簇和協(xié)同過濾。該方法描述的頂點(diǎn)相關(guān)性是基于搜索路徑的，2個(gè)頂點(diǎn)通過特定的元路徑相連。不同的搜索路徑含義不同，導(dǎo)致2個(gè)頂點(diǎn)的相關(guān)程度也將出現(xiàn)不同變化。因此相關(guān)性的度量函數(shù)也是不對稱的。

[BT5]2.4異構(gòu)信息網(wǎng)上鏈接預(yù)測問題的研究

異構(gòu)信息網(wǎng)上的鏈接預(yù)測問題已然面世推出了一些重點(diǎn)研究成果。PathPredict[12]提出了異構(gòu)信息網(wǎng)上預(yù)測合作關(guān)系的方法。文章用4種度量函數(shù)：路徑個(gè)數(shù)、標(biāo)準(zhǔn)化路徑個(gè)數(shù)、隨機(jī)游走、對稱隨機(jī)游走，來計(jì)算2個(gè)頂點(diǎn)在所有元路徑上的相似性。通過監(jiān)督模型去訓(xùn)練出不同結(jié)構(gòu)特征的預(yù)測權(quán)重，得到統(tǒng)一的預(yù)測模型。大多數(shù)的鏈接預(yù)測工作都是集中在同構(gòu)網(wǎng)上，并且只關(guān)注鏈接是否發(fā)生，而無法預(yù)測發(fā)生的時(shí)間。針對這個(gè)問題，文獻(xiàn)[13]提出一種鏈接預(yù)測模型，并給出鏈接發(fā)生的未來時(shí)間，如作者將于某年在會議上發(fā)表論文，用戶在某個(gè)時(shí)間將會對電影做出評論等。Anchoring[14]對多個(gè)異構(gòu)信息網(wǎng)之間的用戶進(jìn)行鏈接預(yù)測。單個(gè)用戶可能在多個(gè)社交網(wǎng)絡(luò)上都擁有注冊賬號，這篇文章就是為了識別不同的社交網(wǎng)絡(luò)之間哪些賬號是屬于同一個(gè)用戶的。通過用戶在社交網(wǎng)絡(luò)上展現(xiàn)的個(gè)人信息、活動時(shí)間、地點(diǎn)和文本信息，清晰確認(rèn)并識別賬戶的對應(yīng)關(guān)系。當(dāng)一個(gè)人剛剛注冊某個(gè)社交網(wǎng)站時(shí)，利用這種鏈接預(yù)測方法，就可以對其推薦符合標(biāo)準(zhǔn)預(yù)期的理想朋友。

2.5異構(gòu)信息網(wǎng)上子圖查詢問題的研究

文獻(xiàn)[15]研究異構(gòu)信息網(wǎng)上搜索結(jié)構(gòu)和語義都相似的子圖。為了提高效率，利用離線的索引生成候選子圖，進(jìn)一步遞歸剪枝對候選子圖進(jìn)行驗(yàn)證。文獻(xiàn)[16]研究給定查詢的模式，計(jì)算top-k相似子圖的方法。為了解決這個(gè)問題，文章提出2種低代價(jià)索引：圖拓?fù)渌饕妥畲笤窂剿饕?。利用這2種索引，對候選的子圖進(jìn)行剪枝，快速計(jì)算得到查詢結(jié)果。

[BT5]2.6異構(gòu)信息網(wǎng)上社區(qū)發(fā)現(xiàn)問題的研究

文獻(xiàn)[17]提出動態(tài)異構(gòu)信息網(wǎng)上社區(qū)發(fā)現(xiàn)的方法。該方法為異構(gòu)信息網(wǎng)建立社區(qū)模型，每個(gè)社區(qū)包含網(wǎng)絡(luò)上所有類型的頂點(diǎn)和邊。用Dirichlet混合模型為每個(gè)時(shí)間窗上的網(wǎng)絡(luò)社區(qū)實(shí)現(xiàn)建模，能夠自動確定社區(qū)的實(shí)現(xiàn)數(shù)量并考慮前一時(shí)刻的社區(qū)對現(xiàn)在時(shí)刻的影響。利用Gibbs采樣方法推理出該模型。在該模型上解決符合網(wǎng)絡(luò)演變規(guī)律的社區(qū)發(fā)現(xiàn)問題。

2.7異構(gòu)信息網(wǎng)上實(shí)體識別問題的研究

SHINE[18]提出了異構(gòu)信息網(wǎng)上實(shí)體識別方法。該文結(jié)合實(shí)體普及模型和實(shí)體目標(biāo)模型，對異構(gòu)信息網(wǎng)上的實(shí)體識別進(jìn)行建模。實(shí)體普及模型依賴于內(nèi)容，例如，名字是“Wei Wang”的老師比名字是“Wei Wang”的學(xué)生發(fā)表的論文數(shù)量多。實(shí)體目標(biāo)模型確定元路徑的概率，通過期望最大化算法自動學(xué)習(xí)元路徑的權(quán)重。

2.8異構(gòu)信息網(wǎng)上無結(jié)構(gòu)查詢問題的研究

GQBE[19]提出在用戶不知道網(wǎng)絡(luò)的頂點(diǎn)類型和結(jié)構(gòu)情況下，只給出查詢的元組示例，計(jì)算與查詢相近的結(jié)果。如查詢示例為，查詢結(jié)果可能是，，表示了創(chuàng)立人與公司的關(guān)系。該方法構(gòu)建基于輸入的最大查詢圖，生成查詢圖的晶格。在晶格上得到top-k相似的查詢結(jié)果。SLQ研究用戶在不了解網(wǎng)絡(luò)結(jié)構(gòu)的情況下，無需給出準(zhǔn)確的查詢形式，通過轉(zhuǎn)換函數(shù)，查找網(wǎng)絡(luò)中符合查詢的匹配。由于轉(zhuǎn)換函數(shù)的代價(jià)不同，應(yīng)用條件隨機(jī)場得到匹配結(jié)果關(guān)于轉(zhuǎn)換代價(jià)的打分函數(shù)，最終輸出最佳匹配的top-k個(gè)結(jié)果。

3異構(gòu)信息網(wǎng)的未來和挑戰(zhàn)

異構(gòu)信息網(wǎng)的應(yīng)用日趨寬泛普及，隨著信息技術(shù)、特別是互聯(lián)網(wǎng)技術(shù)的發(fā)展，各種應(yīng)用領(lǐng)域的信息量都已呈現(xiàn)爆炸性增長趨勢。傳統(tǒng)技術(shù)雖然推出了眾多研究成果，但卻大多集中在同構(gòu)網(wǎng)絡(luò)上。

異構(gòu)信息網(wǎng)上在線分析處理問題的研究對于異構(gòu)信息網(wǎng)上知識的提取是至關(guān)重要的?，F(xiàn)有的信息網(wǎng)絡(luò)在線處理算法都很簡單，缺乏對具體模型定義、執(zhí)行過程分析（時(shí)間、空間、I/O、能耗）、核心步驟優(yōu)化等層面的深入研究。從立方體計(jì)算、物化到OLAP操作，以及復(fù)雜的冰山立方體計(jì)算等，但卻并不適用于圖數(shù)據(jù)。

當(dāng)前，大規(guī)模的信息網(wǎng)絡(luò)上的挖掘和分析工作已有大量的研究人員在開展理論和技術(shù)上的各類探討，但卻仍無法從不同的維度和粒度上為用戶分析決策提供有效的視圖，以及靈活的在線分析處理。時(shí)下的在線處理技術(shù)缺乏對信息網(wǎng)絡(luò)方體格、方體、方體單元詳細(xì)定義，對于其空間爆炸式增長缺乏可行性技術(shù)解決方案；而且，現(xiàn)有技術(shù)也缺乏對物化方式、實(shí)現(xiàn)算法等的深入研究（對于信息網(wǎng)絡(luò)而言，中間結(jié)果的表示和重用對在線信息網(wǎng)絡(luò)處理的性能至關(guān)重要），缺乏對時(shí)間性能、空間開銷等的切實(shí)充分考慮；現(xiàn)有的信息網(wǎng)絡(luò)OLAP技術(shù)在處理大規(guī)模數(shù)據(jù)方面缺乏良好的數(shù)據(jù)組織、中間結(jié)果物化、高效OLAP算法等性能需求的必須解除設(shè)施。在實(shí)際問題中，用戶關(guān)注的目標(biāo)常常是復(fù)雜的信息網(wǎng)絡(luò)度量，并且只關(guān)注那些度量大于給定閾值的立方體，如冰山立方體。迄今為止，這方面的研究工作幾乎是零起步、全空白；

隨著數(shù)據(jù)規(guī)模的日益增大，信息網(wǎng)絡(luò)的增長尤其巨大。如何解決信息網(wǎng)絡(luò)立方體中的海量空間開銷即已成為首要關(guān)鍵問題，在每個(gè)立方體單元中存儲的都是一個(gè)子圖，而不是傳統(tǒng)數(shù)據(jù)立方體中的聚集值，這就給立方體物化過程提出了現(xiàn)實(shí)巨大挑戰(zhàn)；

巨量的信息網(wǎng)絡(luò)除了消耗海量的存儲空間外，在其上的巨量計(jì)算時(shí)間也給研究帶來了嚴(yán)峻挑戰(zhàn)，尤其是對于復(fù)雜信息網(wǎng)絡(luò)度量。通常情況下，立方體計(jì)算需要多次遍歷信息網(wǎng)絡(luò)，這就大大降低了在線處理的效率。如何與用戶進(jìn)行快速交互、且高效實(shí)現(xiàn)在線處理已經(jīng)成為研究學(xué)界亟待解決的重要問題。

挖掘帶有噪聲的、不確定的異構(gòu)信息網(wǎng)。異構(gòu)信息網(wǎng)的數(shù)據(jù)往往是由多個(gè)數(shù)據(jù)源集成而來，而每個(gè)數(shù)據(jù)源的質(zhì)量不盡相同。數(shù)據(jù)往往帶有噪聲，同時(shí)部分?jǐn)?shù)據(jù)也是不確定的。因此，研究帶有噪聲的、不確定的異構(gòu)信息網(wǎng)上的挖掘問題對于異構(gòu)信息網(wǎng)的實(shí)際應(yīng)用則表現(xiàn)出其獨(dú)特意義及實(shí)用價(jià)值。

4結(jié)束語

隨著大數(shù)據(jù)時(shí)代的到來，數(shù)據(jù)的形式也越來越復(fù)雜。隨著信息網(wǎng)絡(luò)的飛速發(fā)展，如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、道路網(wǎng)絡(luò)、知識庫等，異構(gòu)信息網(wǎng)應(yīng)運(yùn)而生。大多數(shù)真實(shí)世界的網(wǎng)絡(luò)都是異構(gòu)的，即頂點(diǎn)和關(guān)系的類型是不同的。異構(gòu)信息網(wǎng)是包括多種類型頂點(diǎn)和多種類型的邊的信息網(wǎng)。異構(gòu)信息網(wǎng)可以在很多領(lǐng)域中構(gòu)建得到，如社交網(wǎng)絡(luò)、電子商務(wù)、在線電影數(shù)據(jù)庫等許多數(shù)據(jù)庫應(yīng)用中。異構(gòu)信息網(wǎng)能夠很好地表達(dá)現(xiàn)實(shí)世界中不同類型實(shí)體以及實(shí)體之間的復(fù)雜關(guān)系。異構(gòu)信息網(wǎng)上的挖掘問題對于復(fù)雜數(shù)據(jù)形式的分析是十分重要的。本文系統(tǒng)介紹了異構(gòu)信息網(wǎng)上廣泛的應(yīng)用背景和現(xiàn)有的研究工作，并提出未來的進(jìn)一步發(fā)展方向，期望有更多的研究者投身到這一領(lǐng)域的學(xué)術(shù)關(guān)注和研究中。

參考文獻(xiàn)：

[1] AGGARWAL C C. Social network data analytics[M]. New York： Springer， 2011.

[2] SUN Y， HAN J， ZHAO P， et al. RankClus： integrating clustering with ranking for heterogeneous information network analysis[C]//Proceedings of International Conference on Extending Database Technology： Advances in Database Technology. New York， USA： ACM， 2009：565-576.

[3] SUN Y ，YU Y， HAN J. Rankingbased clustering of heterogeneous information networks [JP3]with star network schema[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York， USA： ACM， 2009：797-806.[JP]

[4] SUN Y， NORICK B， HAN J， et al. Integrating metapath selection with userguided object clustering in heterogeneous information networks[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York， USA： ACM， 2012：1348-1356.

[5] YANG Z， LING L， DAVID B. Integrating vertexcentric clustering with edgecentric clustering for meta path graph analysis[C]//Proceedings of ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York， USA： ACM， 2015：1563-1572.

[6] SUN Y， AGGARWAL C C， HAN J. Relation strengthaware clustering of heterogeneous information networks with incomplete attributes[J]. Endowment of Very Large DataBases， 2012， 5（5）：394-405.

[7] SUN Y， NORICK B， HAN J， et al. PathSelClus： Integrating metapath selection with user-guided object clustering in Heterogeneous information networks[J]. ACM Transactions on Knowledge Discovery from Data， 2013， 7（3）：1-23.

[8] JI M， HAN J， DANILEVSKY M. Rankingbased classification of heterogeneous information networks[C]//Proceedings of ACM SIGKDD Int. Conference on Knowledge Discovery and Data Mining. New York， USA： ACM ， 2011：1298-1306.

[9] JI M， SUN Y， DANILEVSKY M， et al. Graph regularized transductive classification on heterogeneous information networks[C]//Proceedings of European Conference Machine Learning and Principles and Practice of Knowledge Discovery in Databases. Springer Berlin Heidelberg， 2010：570-586.

[10] SUN Y， HAN J， YAN X， et al. Pathsim： Meta pathbased topk similarity search in heterogeneous information networks[C]//Proceedings of Very Large Databases Endowment. New York， USA： ACM， 2011：992-1003.

[11] SHI C， KONG X， YU P S， et al. Relevance search in heterogeneous networks[C]//Proceedings of international conference on extending database technology. New York， USA： ACM， 2012：180-191.

[12] SUN Y， BARBER R， GUPTA M. Coauthor relationship prediction in heterogeneous bibliographic networks[C]//International Conference on Advances in Social Networks Analysis and Mining. Piscataway， NJ： IEEE， 2011：121-128.

[13] SUN Y， HAN J， AGGARWAL C C， et al. When will it happen？ Relationship prediction in heterogeneous information networks[C]//Proceedings of ACM International Conference on Web Search and Data Mining. New York， USA： ACM， 2012：663-672.

[14] KONG X， ZHANG J， YU P S. Inferring anchor links across multiple heterogeneous social networks[C]//Proceedings of ACM International Conference on Information & Knowledge Management. New York， USA： ACM， 2013：179-188.

[15] YU X， SUN Y， ZHAO P， et al. Querydriven discovery of semantically similar substructures in heterogeneous networks[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2012：1500-1503.

[16] GUPTA M， GAO J， YAN X. Topk interesting subgraph discovery in information networks[C]//Proceedings of IEEE International Conference on Data Engineering. Piscataway， NJ： IEEE， 2014：820-831.

[17] SUN Y， TANG J， HAN J， et al. Community evolution detection in dynamic heterogeneous information networks[C]//Proceedings of the Eighth Workshop on Mining and Learning with Graphs MLG at KDD. New York， USA： ACM， 2010：137-146.

[18] SHEN W， HAN J， WANG J. A probabilistic model for linking named entities in web text with heterogeneous information networks[C]//Proceedings of ACM SIGMOD International conference on Management of Data. New York， USA： ACM， 2014：1199-1210.

[19] YANG S， WU Y， SUN H. Schemaless and structureless graph querying[J]. Endowment of Very Large Databases， 2014， 7（8）：565-576.