知識(shí)圖譜復(fù)雜網(wǎng)絡(luò)特性的實(shí)證研究與分析*

丁連紅 孫斌 時(shí)鵬

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

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

1 引 言

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由于概念圖譜網(wǎng)絡(luò)不是連通網(wǎng)絡(luò),無(wú)法計(jì)算節(jié)點(diǎn)間的平均距離,所以需要計(jì)算出概念圖譜網(wǎng)絡(luò)的最大連通子網(wǎng).我們按照廣度優(yōu)先思想,實(shí)現(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é)點(diǎn)集合MaxSubNet

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

2)對(duì)InitialSet中的每一個(gè)節(jié)點(diǎn)node

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

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

3)返回MaxSubNet.

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

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

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

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

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

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

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

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

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

4)返回MaxSubNet.

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

先由算法2得到最大連通子網(wǎng)的節(jié)點(diǎn)集合MaxSubNet;再根據(jù)MaxSubNet從概念圖譜數(shù)據(jù)文件Graph中提取出最大子網(wǎng)的邊的集合,其中的每條邊依然采用Graph中的三元組形式并存儲(chǔ)在文本文件GraphLink中;最后由MaxSubNet和GraphLink生成如圖3所示結(jié)構(gòu)的最大連通子網(wǎng).其中,中心層(Central Layer)由兩個(gè)節(jié)點(diǎn)構(gòu)成,這兩個(gè)節(jié)點(diǎn)是各三元組對(duì)應(yīng)的節(jié)點(diǎn)對(duì)中度值和最大的節(jié)點(diǎn)對(duì);第二層(Layer-2)為中心層各節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的集合;第三層(Layer-3)為第二層的各節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的集合.以此類推,直到網(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我們實(shí)現(xiàn)了函數(shù)GetNeighbor(Node,Graph),該函數(shù)遍歷Graph中的邊(三元組)信息,判斷Node是否為當(dāng)前邊的端點(diǎn).由于一條邊有兩個(gè)端點(diǎn),完成一條邊的掃描需要兩次判斷操作.將1個(gè)端點(diǎn)的判斷操作定義為1次基本操作,Graph的邊數(shù)為n,則GetNeighbor(Node,Graph)的時(shí)間復(fù)雜度為2n.由算法1可知,每當(dāng)最大連通子網(wǎng)中有一個(gè)新的節(jié)點(diǎn),就要調(diào)用一次GetNeighbor(Node,Graph).設(shè)最大連通子網(wǎng)的節(jié)點(diǎn)數(shù)為m,則算法1的時(shí)間復(fù)雜度為m×2n.由后面3.4節(jié)的實(shí)際計(jì)算結(jié)果可知,m近似為n/2,所以算法1的時(shí)間復(fù)雜度為O(n2).

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

3.4 最大子網(wǎng)抽取實(shí)驗(yàn)與對(duì)比

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

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

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

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

forcin connected_components(G)：

yieldG.subgraph(c).copy()

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

① seen={};

② forvinG：/*對(duì)G中的每個(gè)節(jié)點(diǎn)v*/

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

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

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

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

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

⑦ end if

⑧ end for;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

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