丁連紅 孫斌 時鵬

1)(北京物資學(xué)院信息學(xué)院,北京 101149)

2)(北京科技大學(xué)國家材料服役安全科學(xué)中心,北京 100083)

1 引 言

復(fù)雜網(wǎng)絡(luò)理論興起于20世紀(jì)90年代,是對復(fù)雜系統(tǒng)的一種抽象和描述方式.復(fù)雜網(wǎng)絡(luò)由節(jié)點和邊組成,節(jié)點表示元素,邊表示元素之間的互相作用.復(fù)雜網(wǎng)絡(luò)普遍存在于現(xiàn)實世界,如生物分子網(wǎng)、互聯(lián)網(wǎng)、交通網(wǎng)、電力網(wǎng)等.

知識圖譜由Google公司于2012年提出后,就在搜索引擎與人工智能領(lǐng)域備受關(guān)注.知識圖譜旨在通過語義知識的結(jié)構(gòu)化儲備實現(xiàn)智能檢索、自動問答等應(yīng)用,相關(guān)研究主要圍繞著知識圖譜的知識提取、知識融合以及知識推理等進(jìn)行.知識圖譜描述知識之間的語義關(guān)聯(lián),同樣可以網(wǎng)絡(luò)化.網(wǎng)絡(luò)化的知識圖譜是否符合復(fù)雜網(wǎng)絡(luò)模型？知識間的關(guān)系是否可以通過復(fù)雜網(wǎng)絡(luò)理論進(jìn)行分析？目前尚沒有明確的結(jié)論.微軟概念圖譜(Microsoft concept graph)是微軟研究院于2016年發(fā)布的一個知識圖譜,其形式為概念(concept)、實例(instance)和關(guān)系(relation)的三元組,描述實例與概念之間的IsA關(guān)系,用于實現(xiàn)實例的概念化推理[1].例如三元組(sport,basketball,6423)表示basketball與sport之間存在IsA關(guān)系,即basketball是一種sport.其中basketball (籃球)是實例,sport (運動)是概念,6423是從微軟bing搜索日志中抽取到的basketball和sport之間的IsA關(guān)系的次數(shù),以下稱為共現(xiàn)次數(shù).概念和實例是對事物的描述,概念較抽象,通常描述事物的類別,例如fruit (水果);實例描述較為具體,一般為具體事物的名稱或標(biāo)識,例如orange (橙子).概念圖譜正是通過這些由用戶搜索記錄提取到的實例、概念以及它們之間的IsA關(guān)系反映人們對實物的認(rèn)知和理解.

本文以微軟概念圖譜為研究對象,構(gòu)建描述概念與實例之間概念化關(guān)系的概念圖譜網(wǎng)絡(luò),進(jìn)而研究概念詞與實例詞之間的關(guān)聯(lián)關(guān)系.選取該研究對象的優(yōu)勢在于：1)圖譜數(shù)據(jù)來源于bing搜索日志中數(shù)以億計的用戶搜索記錄,反映了用戶對事物的真實看法;2)圖譜中的共現(xiàn)次數(shù)反映了IsA關(guān)系的可信度,可據(jù)此調(diào)整網(wǎng)絡(luò)規(guī)模;3)微軟概念圖譜只有IsA一種關(guān)系,在構(gòu)造網(wǎng)絡(luò)時不需要對關(guān)系進(jìn)行區(qū)分,簡化了網(wǎng)絡(luò)模型的構(gòu)建.

首先采用NetworkX工具計算相關(guān)統(tǒng)計特征[2],但由于概念圖譜網(wǎng)絡(luò)的節(jié)點數(shù)量巨大,導(dǎo)致計算時間過長,因此本文提出一種適用于概念圖譜的子網(wǎng)提取算法,用來獲取最大連通子網(wǎng),在時間和空間效率上都有顯著提高,并對最大子網(wǎng)的復(fù)雜網(wǎng)絡(luò)特征進(jìn)行了分析.在計算網(wǎng)絡(luò)的最短平均路徑長度時,本文提出了一種計算概念圖譜網(wǎng)絡(luò)近似平均最短路徑的方法,并對算法準(zhǔn)確性進(jìn)行了驗證.對于聚類系數(shù)的計算,本文根據(jù)節(jié)點度值給出了不同的聚類系數(shù)求解方法,并采用Map/Reduce模式進(jìn)行了計算提速.

2 相關(guān)工作

復(fù)雜網(wǎng)絡(luò)理論起步于Erdos和Renyi的隨機圖論(ER圖),而后隨著Watts和Strogatz[3]提出的小世界網(wǎng)絡(luò)、Barabási和Albert[4]提出的無標(biāo)度網(wǎng)絡(luò)逐漸興起,復(fù)雜網(wǎng)絡(luò)理論為復(fù)雜系統(tǒng)的特征分析提供了重要的理論依據(jù),已被廣泛應(yīng)用于社會網(wǎng)絡(luò)分析[5]、城市建設(shè)用地布局[6]、國際貿(mào)易交流分析[7]、交通運輸分析[8]等.其中交通運輸領(lǐng)域的應(yīng)用又包括公路交通[9]、軌道交通[10]、鐵路[11]、航運[12]、航空[13]等.通過求解網(wǎng)絡(luò)特征,如網(wǎng)絡(luò)節(jié)點的度分布、平均路徑長度、聚集特性以及介數(shù)中心性等,分析復(fù)雜系統(tǒng)中各因子之間的關(guān)系和整體穩(wěn)定性[14].以上文獻(xiàn)中復(fù)雜網(wǎng)絡(luò)系統(tǒng)的節(jié)點以交通站點、城市、國家等為主,邊以交通線路、城市區(qū)域間道路、國家關(guān)系等為主,系統(tǒng)中節(jié)點和邊的數(shù)量較少,且多為連通網(wǎng)絡(luò),因此分析其統(tǒng)計特性時資源消耗不大.

在研究如萬維網(wǎng)[15,16]、電話呼叫網(wǎng)[17,18]這類超大規(guī)模網(wǎng)絡(luò)時,由于很難得到描述整個網(wǎng)絡(luò)結(jié)構(gòu)的全部信息,通常的方法是先分析局部實際數(shù)據(jù)的特性,根據(jù)這些特性建立實際網(wǎng)絡(luò)的數(shù)學(xué)模型,再由數(shù)學(xué)模型推算整個網(wǎng)絡(luò)的相關(guān)特性.Albert等[16]先從萬維網(wǎng)抓取了部分實際數(shù)據(jù),得到其局部結(jié)構(gòu),據(jù)此分析出節(jié)點的度分布符合冪律分布,并根據(jù)擬合結(jié)果對局部網(wǎng)絡(luò)進(jìn)行擴展得到較大規(guī)模的拓?fù)浣Y(jié)構(gòu);據(jù)此分析萬維網(wǎng)的拓?fù)浣Y(jié)構(gòu)和連接特性,得到網(wǎng)絡(luò)半徑與節(jié)點數(shù)量之間的函數(shù)關(guān)系;最后,將萬維網(wǎng)節(jié)點實際數(shù)量代入該函數(shù)推測出萬維網(wǎng)的網(wǎng)絡(luò)直徑.Aiello等[17,18]也通過類似的方法對電話呼叫網(wǎng)進(jìn)行了拓?fù)浣：脱莼芯?目前較快的串行最短路徑算法的時間復(fù)雜度也只能降低到O(n2.376)[19],n為網(wǎng)絡(luò)節(jié)點的數(shù)量.

隨著時間的發(fā)展,萬維網(wǎng)的節(jié)點數(shù)量早已超過數(shù)十億數(shù)量級,邊的數(shù)量更是不計其數(shù);電話呼叫網(wǎng)絡(luò)根據(jù)已存在的電話線路之間的關(guān)系進(jìn)行建立,包括約47000000個節(jié)點,80000000條邊.對于規(guī)模如此巨大的網(wǎng)絡(luò)直接計算其直徑(節(jié)點間最短路徑的平均值)和聚類系數(shù)幾乎是不可行的.這可能是相關(guān)文獻(xiàn)均未給出具體的網(wǎng)絡(luò)聚類系數(shù)值,對于網(wǎng)絡(luò)直徑也只給出由網(wǎng)絡(luò)模型計算得到的推測值的原因[15,17,18].

因此有學(xué)者開展了網(wǎng)絡(luò)精簡、評估方法改進(jìn)、網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化等研究.網(wǎng)絡(luò)精簡通過閾值網(wǎng)絡(luò)[20]、最小生成樹[21]、差分網(wǎng)絡(luò)[22]等方法減小網(wǎng)絡(luò)的規(guī)模.孫延風(fēng)和王朝勇[23]采用互信息表示金融網(wǎng)絡(luò)中節(jié)點間的關(guān)系,并用閾值網(wǎng)絡(luò)和最小生成樹對網(wǎng)絡(luò)進(jìn)行精簡,最后驗證了網(wǎng)絡(luò)模型的有效性.

評估方法改進(jìn)包括基于度中心性的評估方法[24]、k-shell分解[25]和基于PageRank的評估方法[26]等.Ruan等[27]將約束系數(shù)引入節(jié)點核心性的度量,提出了一種綜合節(jié)點鄰居節(jié)點的k-shell值和鄰居節(jié)點間拓?fù)浣Y(jié)構(gòu)的核心性度量方法,該方法能更準(zhǔn)確地評估節(jié)點的傳播能力.孔江濤等[28]利用復(fù)雜網(wǎng)絡(luò)動力學(xué)模型描述復(fù)雜網(wǎng)絡(luò)中節(jié)點間的相互影響活動,建立了基于偏離均值與偏離均值的方差的兩級節(jié)點重要性評估標(biāo)準(zhǔn),并通過擾動測試和破壞測試驗證了標(biāo)準(zhǔn)的有效性.

網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化主要以實際應(yīng)用為目的,如韓定定等[29]結(jié)合時變特征和網(wǎng)絡(luò)客流分布,對航空網(wǎng)進(jìn)行優(yōu)化,提出了一種快速推算航線網(wǎng)絡(luò)最優(yōu)拓?fù)浼跋鄳?yīng)航班頻率分布的方法.Niu和Pan[30]通過自組織優(yōu)化機制對運輸網(wǎng)絡(luò)進(jìn)行優(yōu)化,證明了無標(biāo)度網(wǎng)絡(luò)在gradient-driven運輸模式下可以有效地通過自組織優(yōu)化機制提高運輸能力.Jiang等[31]以中國航空運輸網(wǎng)(CNTA)為例研究多層網(wǎng)絡(luò)融合過程的本質(zhì),通過一系列拓?fù)鋵傩钥坍嫸鄬泳W(wǎng)絡(luò)的融合過程,發(fā)現(xiàn)CNTA在融合過程中發(fā)生了明顯的結(jié)構(gòu)轉(zhuǎn)換,為中國航空運輸系統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化和管理提供了啟示.

而知識圖譜作為智能化的語義知識儲備,其規(guī)模也會隨著時間而不斷積累擴大,節(jié)點數(shù)量往往突破千萬數(shù)量級,對這類大規(guī)模網(wǎng)絡(luò)的特征計算也必然十分復(fù)雜與耗時.NetworkX是一款用Python語言開發(fā)的復(fù)雜網(wǎng)絡(luò)構(gòu)建與分析軟件工具包,是復(fù)雜網(wǎng)絡(luò)建模與分析的有力工具[2].由于知識圖譜的規(guī)模巨大,使用NetworkX僅是構(gòu)建出整個網(wǎng)絡(luò)便需要消耗近40 GB的內(nèi)存.萬維網(wǎng)可以通過網(wǎng)絡(luò)中的路由設(shè)備找到通往各個網(wǎng)站節(jié)點需要跳轉(zhuǎn)的次數(shù),即平均最短路徑長度,而知識圖譜與萬維網(wǎng)不同,知識間的拓?fù)渚嚯x無法如此計算.為了解決大規(guī)模復(fù)雜網(wǎng)絡(luò)分析的問題,有學(xué)者設(shè)計了近似算法以計算復(fù)雜網(wǎng)絡(luò)的平均距離.Rattigan等[19]通過引入網(wǎng)絡(luò)結(jié)構(gòu)索引(network structure index,NSI)計算節(jié)點間路徑,從而降低計算網(wǎng)絡(luò)平均路徑長度這樣的基于節(jié)點間路徑應(yīng)用的搜索復(fù)雜度.NSI由各個節(jié)點的標(biāo)記和根據(jù)節(jié)點標(biāo)記估算節(jié)點對間距離的函數(shù)構(gòu)成.唐晉韜等[32]提出了基于區(qū)域中心點距離(centers distance of zone,CDZ)的復(fù)雜網(wǎng)絡(luò)最短路徑計算的近似方法,根據(jù)網(wǎng)絡(luò)特征將網(wǎng)絡(luò)分成多個區(qū)域,每個區(qū)域都設(shè)置一個中心點,將兩節(jié)點之間的距離轉(zhuǎn)換為節(jié)點到中心點以及中心點間的距離之和,實現(xiàn)近似計算.受CDZ思想的啟發(fā)本文提出了一種根據(jù)節(jié)點所在網(wǎng)絡(luò)層與中心節(jié)點的距離及不同網(wǎng)絡(luò)層之間的距離計算概念圖譜網(wǎng)絡(luò)近似平均最短路徑的方法.

3 概念圖譜網(wǎng)絡(luò)構(gòu)建及最大連通子網(wǎng)抽取

3.1 概念圖譜網(wǎng)絡(luò)構(gòu)建

微軟官方提供的概念圖譜的數(shù)據(jù)文件是一個純文本文件,構(gòu)成該文件的元數(shù)據(jù)是描述實例與概念之間IsA關(guān)系的三元組.通過對該數(shù)據(jù)文件的遍歷發(fā)現(xiàn),有些詞既作為概念(Concept)出現(xiàn),也作為實例(Instance)出現(xiàn),本文將這部分詞稱為子概念詞(subConcept).為了構(gòu)建描述實例與概念之間的實例關(guān)系的復(fù)雜網(wǎng)絡(luò),將概念、子概念和實例作為網(wǎng)絡(luò)的節(jié)點,在存在IsA關(guān)系的兩個節(jié)點之間添加一無向條邊,表示它們之間的實例關(guān)聯(lián),從而構(gòu)建出如圖1所示的描述概念、子概念、實例之間的實例關(guān)聯(lián)的概念圖譜網(wǎng)絡(luò).

圖1 概念圖譜網(wǎng)絡(luò)示意圖Fig.1.Network of concept graph.

建立的概念圖譜網(wǎng)絡(luò)是一種無向非加權(quán)網(wǎng),具有如下特征：1)網(wǎng)絡(luò)規(guī)模巨大,包括16936670個節(jié)點和33354328條邊,因此建立非加權(quán)網(wǎng)絡(luò)以減少計算復(fù)雜度,便于特征分析;2)只描述概念和實例間的IsA關(guān)聯(lián)及關(guān)聯(lián)間的跳轉(zhuǎn)層次,忽略關(guān)系的方向;3)共現(xiàn)次數(shù)描述節(jié)點間關(guān)系的可信度,旨在通過閾值設(shè)置得到不同較小規(guī)模的概念圖譜網(wǎng)絡(luò)以進(jìn)行深入的比較分析.

表1列出了在整體概念圖譜網(wǎng)絡(luò)中,概念詞、實例詞以及子概念詞的度值分布.在概念圖譜網(wǎng)絡(luò)中,概念節(jié)點的度表示有多少個實例或子概念與該概念存在IsA關(guān)系.實例節(jié)點的度表示該實例與多少個概念或子概念具有IsA關(guān)系.首先,因為概念圖譜的基本數(shù)據(jù)是由概念、實例和它們之間的IsA關(guān)聯(lián)構(gòu)成的三元組,因此,每個概念至少與一個實例相關(guān),一個實例也至少與一個概念相關(guān),因此所構(gòu)建的概念圖譜網(wǎng)絡(luò)中不應(yīng)有孤立節(jié)點,即不存在度為0的節(jié)點,這與表1的統(tǒng)計數(shù)據(jù)一致.其次,由于子概念既可以處在概念的位置,也可以處在實例的位置,所以子概念的度都應(yīng)大于等于2.但由表1可知概念圖譜網(wǎng)絡(luò)中有18個子概念節(jié)點的度為1.為探究該現(xiàn)象,在概念圖譜的數(shù)據(jù)文件中對度為1的子概念節(jié)點進(jìn)行了檢索和分析,發(fā)現(xiàn)存在類似于(small business issuer,company,4)和(company,small business issuer,1)這樣的兩個節(jié)點互為對方的概念與實例的情況.同時,因為這兩個節(jié)點都未出現(xiàn)在其他三元組中,所以它們的度都為1.這些度為1的子概念節(jié)點也揭示了所構(gòu)建的概念圖譜網(wǎng)絡(luò)并非一個連通網(wǎng)絡(luò).因此,為了真實描述其網(wǎng)絡(luò)特性,必須抽取該網(wǎng)絡(luò)的最大連通子網(wǎng),并將其作為后續(xù)研究對象分析概念圖譜網(wǎng)絡(luò)的復(fù)雜網(wǎng)絡(luò)特性.

表1 概念圖譜網(wǎng)絡(luò)的節(jié)點度分布Table 1.Degree distribution of the concept graph network.

3.2 子網(wǎng)抽取算法

由于概念圖譜網(wǎng)絡(luò)不是連通網(wǎng)絡(luò),無法計算節(jié)點間的平均距離,所以需要計算出概念圖譜網(wǎng)絡(luò)的最大連通子網(wǎng).我們按照廣度優(yōu)先思想,實現(xiàn)了基于廣度優(yōu)先的子網(wǎng)提取算法(SubNet Extraction based on Breadth-first,SNEBF).

算法1基于廣度優(yōu)先的子網(wǎng)提取算法(SNEBF)

輸入：概念圖譜數(shù)據(jù)文件Graph

輸出：最大連通子網(wǎng)節(jié)點集合MaxSubNet

1)從Graph中抽取一個三元組,該三元組包含的兩個節(jié)點的度之和最大,將該三元組中的概念和實例作為兩個初始節(jié)點,構(gòu)成初始節(jié)點集合InitialSet,并將這兩個節(jié)點加入MaxSubNet.

2)對InitialSet中的每一個節(jié)點node

{a.遍歷Graph中的三元組(概念(con),實例(ins),關(guān)系(rel))信息,如果其con或ins等于node,則將該三元組中相應(yīng)的ins或con加入節(jié)點node的鄰居節(jié)點集合NeighborSet.

b.判斷NeighborSet中是否還有未加入MaxSubNet的節(jié)點,如果有,將這些節(jié)點加入MaxSubNet,將NeighborSet集合與MaxSubNet的差集并入InitialSet.}.

3)返回MaxSubNet.

類似于廣度優(yōu)先的按層掃描,對于InitialSet中的每一節(jié)點node算法1總是找出其全部相鄰節(jié)點并據(jù)此對最大子網(wǎng)進(jìn)行擴展,對找出的相鄰節(jié)點重復(fù)相同的操作.但在實際運行時,由于網(wǎng)絡(luò)中的節(jié)點之間關(guān)系復(fù)雜,不同節(jié)點的鄰居節(jié)點集合可能相互包含了許多相同的節(jié)點.如在圖2所示的概念圖譜網(wǎng)絡(luò)中,Concept1的鄰居節(jié)點集合包括4個節(jié)點：Instance2,Instance3,Instance4和Instance5.Concept2也有4個鄰居節(jié)點：Instance1,Instance2,Instance3和Instance4.其中Instance2,Instance3和Instance4是Concept1的鄰居節(jié)點也是Concept2的鄰居節(jié)點.

圖2 導(dǎo)致節(jié)點的鄰居節(jié)點集合冗余的網(wǎng)絡(luò)結(jié)構(gòu)Fig.2.Network structure leading to the overlap of neighbor node sets.

這些相同的節(jié)點在處理Concept1的鄰居節(jié)點和Concept2的鄰居節(jié)點時會被重復(fù)進(jìn)行遞歸檢索處理.這不但會增加大量的冗余存儲空間而且需要多次重復(fù)檢索圖譜數(shù)據(jù).同時由于算法中循環(huán)嵌套了循環(huán),所以在進(jìn)行遍歷時十分耗時.因此我們引入集合運算,從而得到基于集合運算的子網(wǎng)抽取算法(SubNet Extraction based on Set Operation,SNESO).

算法2基于集合運算的子網(wǎng)抽取算法(SNESO)

輸入：概念圖譜數(shù)據(jù)文件Graph

輸出：最大連通子網(wǎng)節(jié)點集合MaxSubNet

1)從Graph中抽取一條包含度值最大節(jié)點的三元組信息,將該三元組中的概念和實例作為中心節(jié)點構(gòu)成最大連通子網(wǎng)的中心層SubNeti(此時i=1),并將其加入MaxSubNet.

2)尋找SubNeti集合的鄰居節(jié)點,即遍歷Graph中的(con,ins,rel)信息,判斷其con或ins是否屬于SubNeti集合,若存在,則表示對應(yīng)的ins或con是集合SubNeti的鄰居節(jié)點,將這些節(jié)點加入SubNeti的鄰居節(jié)點集合NeighborsSeti.

3)判斷NeighborsSeti中是否還有新的未在MaxSubNet中的節(jié)點,如果有,則將NeighborsSeti并入MaxSubNet,將SubNeti替換為NeighborsSeti與MaxSubNet的差集,i=i+1.然后跳轉(zhuǎn)至步驟2;若無,則繼續(xù)步驟4.

4)返回MaxSubNet.

算法1和算法2的關(guān)鍵操作是對Graph三元組信息的遍歷.由中心層出發(fā),每掃描一次Graph,算法1獲得一個節(jié)點的鄰接節(jié)點,算法2獲得一層節(jié)點的全部鄰接節(jié)點,因此算法2能顯著減少對Graph的掃描次數(shù).由于度值大的節(jié)點在最大連通子網(wǎng)的概率較高,為了保證可以找到最大子網(wǎng),我們從度值最大的節(jié)點以及與最大節(jié)點相連的度值較大的節(jié)點開始進(jìn)行搜索.在實際運行中,運算時間和空間復(fù)雜度確實有所降低,具體的復(fù)雜度分析見3.3節(jié).

先由算法2得到最大連通子網(wǎng)的節(jié)點集合MaxSubNet;再根據(jù)MaxSubNet從概念圖譜數(shù)據(jù)文件Graph中提取出最大子網(wǎng)的邊的集合,其中的每條邊依然采用Graph中的三元組形式并存儲在文本文件GraphLink中;最后由MaxSubNet和GraphLink生成如圖3所示結(jié)構(gòu)的最大連通子網(wǎng).其中,中心層(Central Layer)由兩個節(jié)點構(gòu)成,這兩個節(jié)點是各三元組對應(yīng)的節(jié)點對中度值和最大的節(jié)點對;第二層(Layer-2)為中心層各節(jié)點的鄰居節(jié)點的集合;第三層(Layer-3)為第二層的各節(jié)點的鄰居節(jié)點的集合.以此類推,直到網(wǎng)絡(luò)的最外層(Outermost Layer).

圖3 最大連通子網(wǎng)的分層邏輯結(jié)構(gòu)Fig.3.Hierarchical logical structure of the largest connected subnet.

3.3 算法復(fù)雜度分析

根據(jù)算法1我們實現(xiàn)了函數(shù)GetNeighbor(Node,Graph),該函數(shù)遍歷Graph中的邊(三元組)信息,判斷Node是否為當(dāng)前邊的端點.由于一條邊有兩個端點,完成一條邊的掃描需要兩次判斷操作.將1個端點的判斷操作定義為1次基本操作,Graph的邊數(shù)為n,則GetNeighbor(Node,Graph)的時間復(fù)雜度為2n.由算法1可知,每當(dāng)最大連通子網(wǎng)中有一個新的節(jié)點,就要調(diào)用一次GetNeighbor(Node,Graph).設(shè)最大連通子網(wǎng)的節(jié)點數(shù)為m,則算法1的時間復(fù)雜度為m×2n.由后面3.4節(jié)的實際計算結(jié)果可知,m近似為n/2,所以算法1的時間復(fù)雜度為O(n2).

算法2在算法1的基礎(chǔ)上引入了集合運算,兩者的區(qū)別在于：算法1每遍歷一次Graph可以找出一個節(jié)點的鄰居節(jié)點;算法2每遍歷一次Graph可以找出一層節(jié)點的全部鄰居節(jié)點,只要將函數(shù)GetNeighbor的參數(shù)由Node改為NodeSet即可.該函數(shù)遍歷Graph中的邊信息,判斷邊端點是否在集合NodeSet中.由于GetNeighbor(Node,Graph)的時間復(fù)雜度為2n,由3.4節(jié)的實驗可知GetNeighbor(NodeSet,Graph)的平均運算時間約為算法1中GetNeighbor(Node,Graph)運行時間的1.6倍,所以GetNeighbor(NodeSet,Graph)的時間復(fù)雜度為1.6×2n=3.2n.由算法2可知,對最大子網(wǎng)的每一子網(wǎng)層需調(diào)用一次GetNeighbor(NodeSet,Graph),設(shè)構(gòu)建最大連通子網(wǎng)過程中,子網(wǎng)層數(shù)為nl,則運行GetNeighbor(NodeSet,Graph)的次數(shù)為nl次,所以算法2的時間復(fù)雜度為nl×3.2n.通過3.4節(jié)的最大子網(wǎng)抽取實驗發(fā)現(xiàn),nl的實際值為12,由于nl遠(yuǎn)小于n(33377320),所以算法2的時間復(fù)雜度近似為O(n).

3.4 最大子網(wǎng)抽取實驗與對比

分別采用NetwrokX和算法1(SNEBF)、算法2(SNESO)對所構(gòu)建的概念圖譜網(wǎng)絡(luò)進(jìn)行了最大連通子網(wǎng)的抽取實驗,具體的實驗環(huán)境為64位Win7系統(tǒng),16 GB內(nèi)存,Anacodna集成Python開發(fā)環(huán)境,其時間復(fù)雜度和實際運算時間見表2.

表2 最大子網(wǎng)提取算法時間復(fù)雜度對比表Table 2.Time complexity of the subset extraction algorithms.

其中采用NetworkX以及SNEBF求解最大子網(wǎng)時程序并未運行出結(jié)果,在實際運行時間為15 d時終止了這兩個程序,由此可以得出NetworkX構(gòu)建最大子網(wǎng)時間大于15 d的結(jié)論.實驗過程中SNEBF中的GetNeighbor (Node,Graph)運算時間約為10.9 s,SNESO中的GetNeighbor (NodeSet,Graph)的平均運算時間為17.6 s,約為GetNeighbor(Node,Graph)的1.6倍.因為SNEBF的時間復(fù)雜度為(m×2n),而2n,即GetNeighbor(Node,Graph)的平均運行時間為10.9 s,所以可以推算出SNEBF的運行時間約為m×2n=15114834×10.9 s=5.22 a.由GetNeighbor(NodeSet,Graph)的平均計算時間和nl=12,得到SNESO的運行時間為3.49 min,而該算法的實際運行時間為3.80 min.所以,SNESO時間復(fù)雜度最小,計算速度最快,運算時間在可接受范圍內(nèi),遠(yuǎn)小于SNEBF的運行時間.

使用NetworkX抽取最大子網(wǎng),首先通過其內(nèi)部函數(shù)connected_component_subgraphs(Graph)求解所有子網(wǎng)[33],再從中找到節(jié)點數(shù)量最多的子網(wǎng),即為最大連通子網(wǎng).connected_component_subgraphs(Graph)的輸入是一個無向NetworkX圖G,輸出是G的所有連通子網(wǎng)的列表.該函數(shù)是一個由兩行代碼構(gòu)成的for循環(huán)：

forcin connected_components(G)：

yieldG.subgraph(c).copy()

其中connected_components(G)返回各個連通子網(wǎng)的全部節(jié)點c的列表,G.subgraph(c).copy()將節(jié)點列表c轉(zhuǎn)換成圖G的一個連通子圖.以下是connected_components(G)的定義：

① seen={};

② forvinG：/*對G中的每個節(jié)點v*/

③ ifvnot in seen：/*如果沒有遍歷過節(jié)點v*/

④c=sp_length(G,v);/*計算點v到所有可以連通節(jié)點的距離字典c*/

⑤ yield list(c);/*將獲得的c轉(zhuǎn)換為列表返回*/

表3 算法空間復(fù)雜度和實際內(nèi)存消耗對比表Table 3.Space complexity of the algorithms.

⑥ seen.update(c);/*更新seen的值以確保不會尋找重復(fù)節(jié)點*/

⑦ end if

⑧ end for;

NetworkX求解最大子網(wǎng)的關(guān)鍵操作是sp_length(G,v)函數(shù),具體的時間復(fù)雜度分析在第4節(jié)中采用事后統(tǒng)計法給出.

表3列出了NetworkX與算法2運行時的實際內(nèi)存消耗.實驗中NetworkX抽取概念圖譜最大連通子網(wǎng)至少需要40 GB內(nèi)存.采用SNESO求解最大子網(wǎng)時,占用內(nèi)存的變量為SubNeti,NeighborsSet,MaxSubNet,數(shù)值與最大子網(wǎng)的節(jié)點數(shù)、子網(wǎng)某層的節(jié)點數(shù)相關(guān),實際占用內(nèi)存為5.23 GB.

由算法2根據(jù)概念圖譜的數(shù)據(jù)文件生成的最大子網(wǎng)包含15114834個節(jié)點和32274081條邊,分別占整個概念圖譜網(wǎng)絡(luò)節(jié)點和邊的89.24%和96.69%.可知該子網(wǎng)覆蓋了概念圖譜網(wǎng)絡(luò)絕大部分的節(jié)點與邊,其網(wǎng)絡(luò)特性可以較好地反映出整個網(wǎng)絡(luò)的特征,后續(xù)對概念圖譜復(fù)雜網(wǎng)絡(luò)特性的分析都基于此最大連通子網(wǎng).

4 概念圖譜網(wǎng)絡(luò)的復(fù)雜網(wǎng)絡(luò)特性分析

復(fù)雜網(wǎng)絡(luò)的統(tǒng)計特征主要包括度分布、kshell核心性、平均路徑、聚類系數(shù)和度相關(guān)性等.

1)度分布p(k)：度分布可以用來表征網(wǎng)絡(luò)最基本的拓?fù)涮匦?圖4是最大連通子網(wǎng)的節(jié)點累積度分布,節(jié)點度呈冪律分布,符合無標(biāo)度網(wǎng)絡(luò)特性.

表4統(tǒng)計了三類節(jié)點中度值為1—13的節(jié)點數(shù)量與比例：82%的實例節(jié)點度值為1,即82%的實例只與一個概念相關(guān).度值為1的節(jié)點,實例占85.5%,概念占14.5%.由此判斷在自然語言處理過程中使用實例詞比使用概念詞更不易因一詞多義而引起文本描述的歧義.82%的概念度值在1—3之間,表明絕多數(shù)概念只有1—3個含義.在度值相同的節(jié)點中,子概念的比例隨度值的增大而增加,表明子概念通常作為連接多個節(jié)點的核心節(jié)點.

圖4 概念圖譜最大連通子網(wǎng)累積度分布Fig.4.Cumulative degree distribution of the largest connected subnet.

2)k-shell核心性：思想是處于網(wǎng)絡(luò)核心位置的節(jié)點,即使度很小,對網(wǎng)絡(luò)的影響力也可以很大.k-shell分解把網(wǎng)絡(luò)由邊緣至中心劃分成若干層,能夠有效識別網(wǎng)絡(luò)核心.

概念圖譜最大子網(wǎng)經(jīng)k-shell分解為185層,圖5是各層節(jié)點的度分布及平均度值,可見節(jié)點度越大其k-shell分層越高,越靠近中心層,說明大度值節(jié)點位于靠近概念圖譜網(wǎng)絡(luò)中心的位置,而不是邊緣位置.如圖5所示,度高于10000的節(jié)點大都劃分到了核心層,只有極少數(shù)k-shell值很低.我們發(fā)現(xiàn)這些節(jié)點的多數(shù)鄰居節(jié)點的度很低.如劃分到13-shell層的節(jié)點“common search term”和“connected tool”的度高達(dá)102033和31963,但這兩個節(jié)點的鄰居節(jié)點中度為1的分別多達(dá)101892個和31942個.

核心層(185-shell)包括786個節(jié)點,其中子概念782個,概念和實例各2個.核心層節(jié)點間有119162條邊,構(gòu)成了一個稠密圖,網(wǎng)絡(luò)密度0.386,遠(yuǎn)高于最大子網(wǎng)的2.825×10—7.表5是核心層中度值最高的20個節(jié)點及其度值.

雖然子概念只占最大子網(wǎng)節(jié)點的6.2%,卻占核心層的99.5%.說明子概念在概念圖譜中起著重要的連接作用.其根源在于子概念既可以作為比其描述能力抽象的詞的實例,也可以作為比其描述具體的詞的概念,如topic作為概念時包括cultural,political,physica等實例,這些實例都可以說是某一種具體的topic (話題),都與topic具有IsA關(guān)系.作為實例時,topic又是多個概念的實例,如concept,document,information等.

表4 概念圖譜最大子網(wǎng)度分布分析Table 4.Degree distribution analysis of the largest connected subnet.

圖5 節(jié)點度與k-shell分解中心性關(guān)系Fig.5.Relationship between degree andk-shell.

3)平均路徑：網(wǎng)絡(luò)的平均路徑avg(l)是所有節(jié)點對之間距離的平均值,它描述了網(wǎng)絡(luò)中節(jié)點間的分離程度.目前最快的串行最短路徑算法只能將計算的時間復(fù)雜度降到O(n2.376)[19].概念圖譜網(wǎng)絡(luò)的節(jié)點數(shù)為15114834,要精確計算平均最短路徑,需要計算114229095866361個節(jié)點對之間的最短路徑,計算量巨大;同時計算過程中每條路徑上需要存儲多個節(jié)點信息,存儲消耗也很大.

表5 核心層中度值最高的20個節(jié)點Table 5.Top 20 nodes with the highest degree in core.

首先嘗試用NetworkX計算最大子網(wǎng)的avg(l),運行了30 d沒有輸出結(jié)果.為了探究其時間復(fù)雜度,需要對較小規(guī)模的概念圖譜網(wǎng)絡(luò)進(jìn)行計算.為此將共現(xiàn)次數(shù)作為閾值限制邊的數(shù)量從而形成不同較小規(guī)模的網(wǎng)絡(luò),如表6所列.其中t為閾值,n為節(jié)點數(shù),e為邊數(shù).

圖6展示了NetworkX計算表6中各網(wǎng)絡(luò)平均路徑的實際運算時間time(s)與網(wǎng)絡(luò)規(guī)模(節(jié)點數(shù)n),經(jīng)過擬合可知存在函數(shù)關(guān)系：time(n)=5.121×10—7×n2.236.當(dāng)t=10時,NetworkX實際運行了1868428.416 s,約22 d.將最大子網(wǎng)節(jié)點數(shù)代入該函數(shù)可知NetworkX需要計算184 a,這也是計算30 d沒有輸出結(jié)果的原因.

表6 部分閾值網(wǎng)絡(luò)及節(jié)點數(shù)Table 6.Threshold networks and the number of nodes.

圖6 NetworkX計算平均路徑所需時間Fig.6.Time cost of NetworkX for avg(l).

隨后,嘗試用唐晉韜等[32]提出的CDZ方法進(jìn)行計算.該方法首先根據(jù)局部中心性尋找區(qū)域中心點并據(jù)此對網(wǎng)絡(luò)進(jìn)行區(qū)域劃分;之后用區(qū)域中心點的距離表示區(qū)域間節(jié)點的路徑長度,此時節(jié)點間路徑近似等于區(qū)域中心點的路徑與區(qū)域內(nèi)路徑的和.其時間復(fù)雜函數(shù)為O(nlogn+e+d3),n是節(jié)點數(shù),e是邊數(shù),d是中心點數(shù)量[32].相對于隨機網(wǎng)絡(luò),CDZ更適合具有無標(biāo)度特征的復(fù)雜網(wǎng)絡(luò).CDZ計算無標(biāo)度網(wǎng)絡(luò)Cora平均路徑的時間為20余秒.Cora的n=30751,e=134450,按照文獻(xiàn)所述方法計算得到的d為46,因此時間復(fù)雜度函數(shù)值為369792.對于概念圖譜最大子網(wǎng)而言,n=15114834,e=32274081,d=130109,因此時間復(fù)雜度函數(shù)值為2202531075674600,是Cora的5956132434倍.按照CDZ計算Cora平均路徑用時為20 s計算,CDZ計算概念圖譜的最大子網(wǎng)平均路徑需要3777 a.

為此我們提出了一種概念圖譜網(wǎng)絡(luò)最短路徑長度的近似計算方法,該算法區(qū)別于CDZ的是用網(wǎng)絡(luò)層代替區(qū)域,且忽略同層內(nèi)節(jié)點的具體距離.根據(jù)圖3所示的最大連通子網(wǎng)的層次結(jié)構(gòu),用層與層之間的距離近似代替點與點之間的距離,計算網(wǎng)絡(luò)的近似平均最短路徑長度：

其中AppAvg(l)表示網(wǎng)絡(luò)的近似平均最短路徑長度,minavg(l)表示可能存在的近似平均最短路徑長度的最小值,maxavg(l)表示可能存在的近似平均路徑長度的最大值.

其中l(wèi)min_ij表示節(jié)點i到節(jié)點j可能的最小路徑長度,lmax_ij表示節(jié)點i到節(jié)點j可能的最大路徑長度.

由于網(wǎng)絡(luò)的層級關(guān)系,節(jié)點i到節(jié)點j之間必定存在一條路徑為(節(jié)點i,中心節(jié)點,節(jié)點j),此路徑為可能存在的最大的近似路徑,其距離公式為

其中l(wèi)iCenter和lCenterj分別表示節(jié)點i到中心節(jié)點(Center)的距離和Center到節(jié)點j的路徑長度.根據(jù)對稱性,節(jié)點i到節(jié)點j與節(jié)點j到節(jié)點i的路徑長度相同.

其中floor(i)表示節(jié)點i所在的層數(shù).由于中心層包括兩個節(jié)點,所以在計算時統(tǒng)一為節(jié)點所在的層數(shù)減去1再加1.減1表示節(jié)點所在層數(shù)到中心層的路徑長度,加1表示中心層兩個節(jié)點之間的路徑長度.

表7為經(jīng)過算法2的運行結(jié)果后統(tǒng)計的網(wǎng)絡(luò)層數(shù)及各層包含的節(jié)點數(shù)量.根據(jù)(4),(5)式以及表7計算得到子網(wǎng)中各節(jié)點之間的最大距離的和為770350922065817,代入(3)式maxavg(l)=6.74.

表7 子網(wǎng)結(jié)構(gòu)與節(jié)點數(shù)量Table 7.Subnet structure and quantity of nodes.

假設(shè)每層節(jié)點到其他各層節(jié)點的最短距離為層數(shù)相減的絕對值,此時,節(jié)點對之間的路徑長度最短,有

根據(jù)(6)式及表7中的數(shù)據(jù)可以求得子網(wǎng)節(jié)點間最小距離的和為125617583016439,將其代入(2)式可知最小近似平均最短路徑長度minavg(l)為1.10.所以子網(wǎng)的實際平均最短路徑長度處于(1.10,6.74)的開區(qū)間內(nèi),根據(jù)(1)式可計算得到網(wǎng)絡(luò)的近似平均最短路徑長度為3.92,表明知識圖譜網(wǎng)絡(luò)中的實體平均經(jīng)過3.92個實體就可以到達(dá)任意實體的位置,概念圖譜網(wǎng)絡(luò)具有小世界的特性.相對于逐條匹配而言,以基于網(wǎng)狀拓?fù)浣Y(jié)構(gòu)進(jìn)行的知識搜索更為迅速.

圖7是由NetworkX和本文方法計算的不同規(guī)模網(wǎng)絡(luò)的實際平均路徑RealAvg(l)和近似平均路徑AppAvg(l),n為節(jié)點數(shù)量.AppAvg(l)與RealAvg(l)變化趨勢相同,且隨網(wǎng)絡(luò)規(guī)模增加而減小,并穩(wěn)定在一個4左右的定值.我們計算了各規(guī)模網(wǎng)絡(luò)平均路徑的真實值與近似值比值的平均值,有RealAvg(l)≈ 1.1×AppAvg(l).

圖7 平均路徑精確值、近似值與節(jié)點數(shù)的關(guān)系Fig.7.Relationships of RealAvg(l)and AppAvg(l)ton.

根據(jù)隨機網(wǎng)絡(luò)平均最短路徑長度的估算公式計算相同規(guī)模隨機網(wǎng)絡(luò)的平均最短路徑為Lrandom～ ln(N)/ln(k)=11.38,其中N是最大子網(wǎng)的節(jié)點數(shù),k=4.274是節(jié)點的平均度值,根據(jù)互聯(lián)網(wǎng)平均最短路徑長度[16]公式,可以計算得〈i〉～0.35 +2.06×lgN=15.14,可知概念圖譜網(wǎng)絡(luò)的節(jié)點間的聯(lián)系比同等規(guī)模的隨機網(wǎng)絡(luò)和萬維網(wǎng)節(jié)點間的聯(lián)系更緊密.此外,不同于互聯(lián)網(wǎng)平均最短路徑隨網(wǎng)絡(luò)規(guī)模的增大而增大,概念圖譜網(wǎng)絡(luò)的平均路徑隨網(wǎng)絡(luò)規(guī)模的增大反而減小,并最終趨近于一個4左右的定值.這一現(xiàn)象可能與概念圖譜的結(jié)構(gòu)有關(guān),為解釋此現(xiàn)象,對由算法2計算各閾值網(wǎng)絡(luò)最大子網(wǎng)時得到的網(wǎng)絡(luò)層次結(jié)構(gòu)進(jìn)行了統(tǒng)計.表8是各閾值網(wǎng)絡(luò)由中心層擴展時形成的層次結(jié)構(gòu)及各層包含的節(jié)點數(shù).

從表8可以看出,這些閾值網(wǎng)絡(luò)與概念圖譜最大子網(wǎng)在結(jié)構(gòu)上十分相似,都形成了類似“菱形”結(jié)構(gòu)：大量節(jié)點集中在中間靠前的網(wǎng)絡(luò)層,少量節(jié)點處于兩端的“邊緣”層.隨著網(wǎng)絡(luò)規(guī)模的增加,大量的節(jié)點更是集中在了前4層,表明大部分節(jié)點間經(jīng)由中心層節(jié)點經(jīng)過不超過4步就可到達(dá)彼此,可以一定程度地解釋概念圖譜網(wǎng)絡(luò)平均最短路徑隨著網(wǎng)絡(luò)規(guī)模增加而趨近于4左右這個定值的原因.概念圖譜反映的是知識間的聯(lián)系,可以將其看作人擁有的知識.通常一個人掌握的知識越多,其由一個知識推理或搜索到另外一個知識的速度也就越快.

4)聚類系數(shù)：聚類系數(shù)C是所有節(jié)點聚類系數(shù)的平均值,描述網(wǎng)絡(luò)中節(jié)點的聚集情況,即網(wǎng)絡(luò)緊密性.

對于度為1的節(jié)點,計算其聚類系數(shù)沒有實際意義,為此在計算網(wǎng)絡(luò)的聚類系數(shù)前首先要剔除度值為1的節(jié)點.在剔除度為1的節(jié)點后,最大子網(wǎng)還有5010477個節(jié)點.由于我們只有記錄最大子網(wǎng)邊信息的三元組的文本文件GraphLink,如果對每個節(jié)點直接計算其聚類系數(shù),首先需要遍歷最大子網(wǎng)邊集合GraphLink得到該節(jié)點的鄰居節(jié)點集合,為此需調(diào)用3.3節(jié)中的GetNeighbor(Node,Graph)函數(shù),并將參數(shù)Graph替換為GraphLink;之后再次遍歷GraphLink得到鄰居節(jié)點集合中存在的邊的數(shù)量,為此需再次調(diào)用GetNeighbor(Node,Graph),此處也應(yīng)將Graph替換為GraphLink.參照3.4節(jié)中時間復(fù)雜度的分析,可知計算一個節(jié)點聚類系數(shù)的時間復(fù)雜度為以上兩個函數(shù)的時間復(fù)雜度之和,即2n+ 3.2n=5.2n,此處的n為GraphLink包含的邊數(shù)(32274033).由于需要計算聚類系數(shù)的節(jié)點數(shù)量為5010477,約為邊數(shù)的1/6,所以計算網(wǎng)絡(luò)的聚類系數(shù)的時間復(fù)雜度為5.2n×n×1/6 ≈ 0.867n2,時間復(fù)雜度仍較高,所以我們采用分段式計算方法.

表8 不同閾值網(wǎng)絡(luò)的層次結(jié)構(gòu)及各層的節(jié)點數(shù)Table 8.Layer structure and node number in each layer.

Nodeki表示度值為ki的節(jié)點的集合.根據(jù)度分布可知,度值越小,對應(yīng)的節(jié)點數(shù)量越大,設(shè)定閾值θ=100.

對于度值大于θ的節(jié)點的集合Nodeki(ki=θ+1,θ+2,···,kmax,其中kmax表示節(jié)點的最大度值)：先根據(jù)最大連通子網(wǎng)的邊集合GraphLink尋找到每個節(jié)點Nodej∈Nodeki的鄰居節(jié)點的集合Neighborjki然后遍歷GraphLink中的每一條邊,對Nodeki中的每個Nodej,判斷該邊的兩個端點是否都屬于Neighborjki,若是,則表示該邊是連接Nodej的兩個鄰居節(jié)點的邊.度值為ki的各個節(jié)點的鄰居節(jié)點間的邊數(shù)構(gòu)成邊數(shù)集合Edgeki,其存儲形式為k-value形式,如Edgeki={{Node1：edge1},{Node2：edge2},···,{Nodej：edgej}},其 中edgej為節(jié)點Nodej的鄰居節(jié)點間的邊數(shù).節(jié)點Nodej的聚類系數(shù)計算公式如下：

其中Edgeki(Nodej)表示Edgeki中與Nodej對應(yīng)的edgej.

對于度值小于等于θ的節(jié)點集合Nodeki(ki=1,2,···,θ)：首先同上得到與度值ki對應(yīng)的Nodeki及Neighborjki(j=1,2,···,length(Nodeki)),其中l(wèi)ength(Nodeki)表示Nodeki中節(jié)點的數(shù)量;然后根據(jù)(Nodeki∪Neighborjki,j=1,2,···,length(Nodeki))從GraphLink中篩選與這些節(jié)點相關(guān)的邊,組成部分邊集合PartOfGraphki;再對PartOfGraphki中的每一條邊,對Nodeki的每個Nodej,判斷邊的兩個端點是否屬于Neighborjki,若是,則表示該邊是連接Nodej的兩個鄰居節(jié)點間的邊.得到度值ki對應(yīng)的Nodeki中各個節(jié)點Nodej的鄰居節(jié)點間的邊數(shù)構(gòu)成集合Edgeki,然后根據(jù)(7)式計算該集合中每個節(jié)點的聚類系數(shù).

由于度值越小,節(jié)點數(shù)量越多,聚類系數(shù)就越難計算.在實驗中,度值在2—10范圍內(nèi)的節(jié)點數(shù)占所有可計算聚類系數(shù)節(jié)點的89.66%,所以我們在度值小于閾值時引入Map/Reduce模式,將大型計算任務(wù)分解為多個小計算量任務(wù),然后同時進(jìn)行計算.對于度值相同的節(jié)點統(tǒng)一計算其聚類系數(shù),在計算時分別計算分子,分母只需要計算一次(分母是相同的).并且,此種計算模式在分析度-平均聚類系數(shù)時也十分方便.

最大連通子網(wǎng)中聚類系數(shù)不為0的節(jié)點為1837431個,占12.16%,由全部節(jié)點聚類系數(shù)計算得到的網(wǎng)絡(luò)聚類系數(shù)為0.0468;剔除度值為1的節(jié)點后計算得到的網(wǎng)絡(luò)聚類系數(shù)為0.1410.為了判斷網(wǎng)絡(luò)的小世界特性,計算了相同規(guī)模(節(jié)點數(shù)量和平均度相同)的隨機網(wǎng)絡(luò)的聚類系數(shù)Crandom～k/N=2.83×10—7,其中N=15114834為節(jié)點數(shù),k=4.274是網(wǎng)絡(luò)的平均度值[3].顯然概念圖譜網(wǎng)絡(luò)的聚類系數(shù)遠(yuǎn)大于Crandom,可知概念圖譜網(wǎng)絡(luò)中節(jié)點聚群現(xiàn)象比較明顯.圖8是度值與平均聚類系數(shù)的關(guān)系,可知低度值節(jié)點的聚類系數(shù)較大,高度值節(jié)點的聚類系數(shù)普遍較小.

5)度相關(guān)性：度相關(guān)性描述的是節(jié)點之間根據(jù)度值作為相互之間連接的選擇偏好性,如度值為k的節(jié)點的鄰點平均度knn(k)隨k增加,表示度大的節(jié)點偏好連接其他度大的節(jié)點,則網(wǎng)絡(luò)是正相關(guān)的;反之,如果knn(k)隨k而減小,表示度大的節(jié)點偏好連接度小的節(jié)點,則網(wǎng)絡(luò)是負(fù)相關(guān)的.

表9列出了部分度值和該度值對應(yīng)的所有節(jié)點的鄰點平均度,可知值最低的5個度其所有節(jié)點的鄰點平均度非常大,而值最高的5個度其所有節(jié)點的鄰點平均度相對而言卻非常小.

將度值k和與度為k的所有節(jié)點的鄰點平均度knn的關(guān)系繪制成圖9,可以看出,knn隨著k的增大而減小,呈現(xiàn)負(fù)相關(guān)性,表明概念圖譜網(wǎng)中與高度值節(jié)點相連接的節(jié)點的度值偏低,與低度值節(jié)點相連接的節(jié)點的度值偏高.

Newman[34]還給出了一種通過網(wǎng)絡(luò)節(jié)點度的Pearson相關(guān)系數(shù)r來判斷網(wǎng)絡(luò)相關(guān)性的量化方法,具體公式如下：

其中M表示網(wǎng)絡(luò)的邊數(shù),ji和ki分別是第i條邊(i=1,2,···,M)的兩個端點的度值,r(—1≤r≤1)表示網(wǎng)絡(luò)相關(guān)性.經(jīng)計算可知概念圖譜最大連通子網(wǎng)的相關(guān)性為—0.067,網(wǎng)絡(luò)是負(fù)相關(guān)的,與度值的鄰點平均度分析結(jié)論相同.同時,網(wǎng)絡(luò)的負(fù)相關(guān)性也保證了低度值節(jié)點可以與高度值節(jié)點相連,由于高度值節(jié)點可以連接到很多其他節(jié)點,所以在應(yīng)用中可以實現(xiàn)推理過程.

6)知識丟失對概念圖譜完整性的影響：用節(jié)點刪除模擬知識丟失,通過隨機刪除和定向刪除(度值由高到低)分別測試了不同閾值下較小規(guī)模概念圖譜網(wǎng)絡(luò)的完整性.圖10(a)是閾值為500的實驗結(jié)果,x軸是節(jié)點刪除比,y軸是最大子網(wǎng)節(jié)點比例S,能夠一定程度上描述概念圖譜的完整性.隨機刪除對S影響很小,刪除80%以上的節(jié)點時S才接近0;定向刪除對S影響顯著,僅減少0.5%左右的節(jié)點時S就減少到了0.定向刪除下S的下降規(guī)律與computer network十分相似,快于同是無尺度網(wǎng)的BA網(wǎng)和科學(xué)合作網(wǎng)[35].

表9 部分度的節(jié)點數(shù)與該度值的所有節(jié)點的鄰點平均度Table 9.Part ofNkandknn(k).

圖9 度-鄰點平均度相關(guān)性分析Fig.9.Analysis of degree and average degree of neighbor nodes.

圖10 知識丟失對概念圖譜完整性的影響Fig.10.Size of the giant component when nodes are removed.

還測試了概念、實例、子概念丟失對概念圖譜完整性的影響,圖10(b)是隨機刪除1—140個三類節(jié)點時S的變化,可見子概念的丟失對圖譜完整性影響最大,其次是概念,最后是實例.為了分析以上現(xiàn)象,由度分布計算了各類節(jié)點的度期望值：概念節(jié)點的度期望為2.911,實例為1.899,子概念為36.214.也就是說隨機刪除1個概念同時丟失約3條邊(知識之間的聯(lián)系);隨機刪除1個實例同時丟失不到2條邊,隨機刪除1個子概念,平均會減少約36條邊,因此子概念的丟失對網(wǎng)絡(luò)完整性影響最大.

概念圖譜來源于數(shù)億用戶的搜索記錄,是反映人類對事物認(rèn)知的知識庫.盡管每個人擁有的知識只是其中的一部分,但卻有類似的結(jié)構(gòu)特征.即最具體的實例對于掌握知識而言重要性最低,而抽象的概念或子概念更重要.現(xiàn)實世界中,若忘記了某個實例,比如忘記了3是prime number (素數(shù)),只要掌握了prime number的概念,就可以推斷出3是prime number.但如果忘記的是概念或者子概念,如prime number,由3推理出prime number或其他素數(shù)就非常困難.

5 結(jié) 論

本文運用復(fù)雜網(wǎng)絡(luò)理論對由微軟概念圖譜所構(gòu)建的概念圖譜網(wǎng)絡(luò)進(jìn)行了分析.由于概念圖譜網(wǎng)絡(luò)中包含多個子網(wǎng)結(jié)構(gòu),提出了一種適合概念圖譜的最大子網(wǎng)抽取算法,實驗表明對于節(jié)點數(shù)量龐大的概念圖譜網(wǎng)絡(luò),該算法在時間和空間上都優(yōu)于NetworkX.在進(jìn)行節(jié)點度分布分析時不但發(fā)現(xiàn)最大連通子網(wǎng)具有無標(biāo)度特性,還發(fā)現(xiàn)子概念在概念圖譜中扮演著連接其他節(jié)點的角色.82%的實例節(jié)點只與一個概念存在IsA關(guān)聯(lián),向我們揭示了實例詞在文本分析中通常不會因為一詞多義的原因?qū)е吕斫馍系钠缌x.為解決網(wǎng)絡(luò)規(guī)模巨大導(dǎo)致的計算困難,提出了一種近似網(wǎng)絡(luò)平均距離的計算方法,對比NetworkX和CDZ具有明顯優(yōu)勢.分析表明概念圖譜網(wǎng)絡(luò)具有小世界特性,平均路徑隨網(wǎng)絡(luò)規(guī)模增加而減小并趨于定值4;概念圖譜網(wǎng)絡(luò)的“菱形”結(jié)構(gòu)揭示了平均路徑趨于定值4的根源;平均路徑隨網(wǎng)絡(luò)規(guī)模增加而減小這一現(xiàn)象與人類認(rèn)知和推理能力隨知識增加而提升這一現(xiàn)象一致.網(wǎng)絡(luò)聚類系數(shù)較大,網(wǎng)絡(luò)中節(jié)點的群聚現(xiàn)象較為明顯.根據(jù)度相關(guān)性的分析,可知網(wǎng)絡(luò)中與高度值節(jié)點相連接的節(jié)點的度值偏低,與低度值節(jié)點相連接的節(jié)點的度值偏高,度-平均度呈現(xiàn)負(fù)相關(guān),有利于實現(xiàn)概念圖譜中的知識推理;概念圖譜完整性對知識的隨機缺失不敏感且子概念對概念圖譜完整性的影響明顯高于概念和實例.

考慮到概念圖譜的海量數(shù)據(jù),以上對全網(wǎng)特性的分析都沒有考慮關(guān)系的方向和關(guān)系的緊密程度(邊的長度),在以后的工作中可以將關(guān)系的方向和邊長引入概念圖譜網(wǎng)絡(luò)模型的構(gòu)建中,在此基礎(chǔ)上利用局部拓?fù)涮匦赃M(jìn)行概念圖譜的自動補全研究.