復(fù)雜網(wǎng)絡(luò)全局拓?fù)湎嗨贫扔?jì)算方法實(shí)證研究

胡燕祝++權(quán)桁++艾新波

摘要：相似度研究對(duì)于復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測(cè)、演化機(jī)制以及社團(tuán)檢測(cè)等相關(guān)熱門(mén)研究領(lǐng)域都具有重要的作用，本文從網(wǎng)絡(luò)相似度及演化的角度出發(fā)，基于提取復(fù)雜網(wǎng)絡(luò)全局拓?fù)涮匦?，定義了一種新的復(fù)雜網(wǎng)絡(luò)相似度計(jì)算方法，仿真結(jié)果表明，該相似度計(jì)算方法可以準(zhǔn)確表征不同復(fù)雜網(wǎng)絡(luò)的相似程度，通過(guò)將該方法應(yīng)用于技術(shù)交易中進(jìn)行實(shí)證分析，發(fā)現(xiàn)可以將技術(shù)交易分為三個(gè)不同的階段，每一階段內(nèi)的復(fù)雜網(wǎng)絡(luò)之間相似度明顯高于該階段外的復(fù)雜網(wǎng)絡(luò)，證實(shí)了本文提出的相似度計(jì)算方法具有可行性與有效性。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；相似度；全局拓?fù)涮匦裕患夹g(shù)交易

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.3969/j.issn.1003-6970.2015.09.004

0 引言

復(fù)雜網(wǎng)絡(luò)即具有白組織、白相似、吸引子、小世界、無(wú)標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)。對(duì)于復(fù)雜網(wǎng)絡(luò)相似度研究的意義主要在于以相似度研究為基礎(chǔ)來(lái)準(zhǔn)確進(jìn)行鏈路預(yù)測(cè)、有效檢測(cè)社團(tuán)網(wǎng)絡(luò)以及探索復(fù)雜網(wǎng)絡(luò)的演化機(jī)制等，例如Chao S.根據(jù)節(jié)點(diǎn)之間的相似性來(lái)判斷兩節(jié)點(diǎn)之間建立連接的可能性，即鏈路的演化預(yù)測(cè)；社交網(wǎng)絡(luò)中也經(jīng)常使用復(fù)雜網(wǎng)絡(luò)技術(shù)進(jìn)行用戶挖掘；基于相似度的算法也經(jīng)常用來(lái)進(jìn)行社團(tuán)檢測(cè)，它基于全局或者局部網(wǎng)絡(luò)特性來(lái)計(jì)算節(jié)點(diǎn)之間的相似度，結(jié)合一般聚類算法來(lái)進(jìn)行社團(tuán)劃分，此外，Girvan和Newman也曾基于邊移除的算法來(lái)實(shí)現(xiàn)社團(tuán)檢測(cè)，即GN算法；趙偉艇等也基于節(jié)點(diǎn)相似度特性和三角結(jié)構(gòu)提出了一種復(fù)雜網(wǎng)絡(luò)演化算法，以上都是當(dāng)前對(duì)于復(fù)雜網(wǎng)絡(luò)研究比較熱門(mén)的領(lǐng)域。

目前，關(guān)于復(fù)雜網(wǎng)絡(luò)相似度的研究主要是自身局部相似度以及復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)間的相似度研究，例如王林等通過(guò)提出一種基于局部相似度的K-means譜聚類算法，計(jì)算節(jié)點(diǎn)間相似度，達(dá)到對(duì)網(wǎng)絡(luò)中社團(tuán)進(jìn)行檢測(cè)的目的；李佳佳提出一種自相似復(fù)雜網(wǎng)絡(luò)，其主要根據(jù)通過(guò)提出一種基于節(jié)點(diǎn)的共有鄰居數(shù)目的指數(shù)來(lái)描述節(jié)點(diǎn)相似度的局部相似度。

以上文獻(xiàn)所研究的相似度均為節(jié)點(diǎn)或局部的相似度，并沒(méi)有對(duì)全局拓?fù)涮匦缘南嗨贫冗M(jìn)行研究，所以，為探索復(fù)雜網(wǎng)絡(luò)整體拓?fù)浣Y(jié)構(gòu)的相似度算法，本文主要基于提取全局的復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征來(lái)計(jì)算不同復(fù)雜網(wǎng)絡(luò)的相似度并進(jìn)行研究與實(shí)證。

本文主要研究方法為算法研究結(jié)合實(shí)證分析驗(yàn)證，通過(guò)對(duì)技術(shù)交易復(fù)雜網(wǎng)絡(luò)全局拓?fù)涮卣鞯倪x取以及計(jì)算提取，構(gòu)建表征復(fù)雜網(wǎng)絡(luò)全局特征的特征向量，對(duì)比常見(jiàn)的距離計(jì)算方法，得出對(duì)本文相似度計(jì)算最為有效的距離度量方法，最后通過(guò)對(duì)網(wǎng)絡(luò)進(jìn)行層次聚類可視化地展示相似度計(jì)算效果，并根據(jù)數(shù)據(jù)的實(shí)際意義來(lái)分析不同類別的復(fù)雜網(wǎng)絡(luò)具有何種特征以及網(wǎng)絡(luò)的演化發(fā)展趨勢(shì)。

本文接下來(lái)安排如下，第1節(jié)是數(shù)據(jù)的描述；第2節(jié)為復(fù)雜技術(shù)交易網(wǎng)絡(luò)拓?fù)涮卣鞯倪x取以及相似度方法的闡述；第3節(jié)是算法的仿真分析；第4節(jié)是相似度算法的實(shí)證研究及結(jié)果論證；最后第5節(jié)為本文工作的總結(jié)與展望。

1 數(shù)據(jù)描述及研究背景

本文實(shí)證采用的數(shù)據(jù)為技術(shù)交易數(shù)據(jù)，技術(shù)交易即技術(shù)從賣(mài)方到買(mǎi)方的流通過(guò)程，由于這一過(guò)程涉及的企業(yè)數(shù)量巨大，企業(yè)之間的交易情況復(fù)雜，所以適合于用復(fù)雜網(wǎng)絡(luò)來(lái)進(jìn)行表征，技術(shù)交易可相當(dāng)于復(fù)雜網(wǎng)絡(luò)中兩節(jié)點(diǎn)之間的連接行為。本文使用統(tǒng)計(jì)分析工具R語(yǔ)言中的igraph包對(duì)2006年到2014年共9年的技術(shù)交易數(shù)據(jù)進(jìn)行網(wǎng)絡(luò)構(gòu)建，數(shù)據(jù)的主要字段包括：項(xiàng)目名稱和領(lǐng)域，合同時(shí)間，買(mǎi)賣(mài)雙方信息等字段，本文利用賣(mài)方名稱、買(mǎi)方名稱以及合同時(shí)間來(lái)進(jìn)行技術(shù)交易復(fù)雜網(wǎng)絡(luò)的構(gòu)建，得到的網(wǎng)絡(luò)模型（以2008年復(fù)雜技術(shù)交易網(wǎng)絡(luò)為例）如圖1所示。其中復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)代表技術(shù)交易主體，包括技術(shù)賣(mài)方、技術(shù)買(mǎi)方以及技術(shù)中介等；復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)之間的連線代表著買(mǎi)方和賣(mài)方之間的交易。技術(shù)交易網(wǎng)絡(luò)的節(jié)點(diǎn)和邊描述了技術(shù)交易活動(dòng)最主要的部分，除了邊和點(diǎn)之外，復(fù)雜技術(shù)交易網(wǎng)絡(luò)的某些拓?fù)涮匦砸部梢苑从硨?shí)際技術(shù)交易行為的特點(diǎn)。

2 網(wǎng)絡(luò)相似度計(jì)算方法

本文所使用的網(wǎng)絡(luò)相似度計(jì)算方法如下：首先對(duì)復(fù)雜網(wǎng)絡(luò)的全局拓?fù)涮卣鬟M(jìn)行提取，所選特征需可以表征復(fù)雜網(wǎng)絡(luò)的全局特性；然后根據(jù)拓?fù)涮卣鹘?fù)雜網(wǎng)絡(luò)的特征向量，通過(guò)選取合適的距離計(jì)算方式計(jì)算特征向量之間的距離，即可映射為復(fù)雜網(wǎng)絡(luò)之間的相似度大小。

2.1 拓?fù)涮卣鞯奶崛?/p>

在如上一節(jié)所描述構(gòu)建復(fù)雜技術(shù)交易網(wǎng)絡(luò)后，需要對(duì)網(wǎng)絡(luò)的全局拓?fù)涮卣鬟M(jìn)行提取，本文結(jié)合技術(shù)交易的實(shí)際行為特點(diǎn)主要提取了七種拓?fù)涮匦灾笜?biāo)，如表1所示。

對(duì)每年的技術(shù)交易復(fù)雜網(wǎng)絡(luò)提取以上七種拓?fù)涮卣骱螅⒂蛇@七種特征取值組成的網(wǎng)絡(luò)特征向量，進(jìn)而建立不同年份復(fù)雜技術(shù)交易網(wǎng)絡(luò)的特征矩陣。

2.2 距離計(jì)算方法的選取

本文所用相似度計(jì)算方法的另一個(gè)重點(diǎn)是不同復(fù)雜網(wǎng)絡(luò)的特征向量的距離計(jì)算方法，計(jì)算距離的方式有多種，主要有歐氏距離、曼哈頓距離以及余弦距離等，本文通過(guò)計(jì)算方式及實(shí)際意義對(duì)比來(lái)進(jìn)行選取。

2.3 可視化展示

通過(guò)對(duì)不同復(fù)雜網(wǎng)絡(luò)的特征向量進(jìn)行距離計(jì)算，得到不同年份復(fù)雜技術(shù)交易網(wǎng)絡(luò)的距離矩陣，根據(jù)該矩陣進(jìn)行自底向上的層次聚類方法得到復(fù)雜網(wǎng)絡(luò)的相似度結(jié)果，類標(biāo)號(hào)一致的復(fù)雜網(wǎng)絡(luò)相似度高，若同一類的復(fù)雜網(wǎng)絡(luò)確有相似的生成模式，那么證明本文的相似度計(jì)算方法是可行的。

3 算法仿真分析

為了證實(shí)本文對(duì)于復(fù)雜網(wǎng)絡(luò)相似度研究的可行性，筆者采用對(duì)無(wú)標(biāo)度網(wǎng)絡(luò)生成模型進(jìn)行仿真的方式來(lái)驗(yàn)證。無(wú)標(biāo)度網(wǎng)絡(luò)是一種度分布呈冪律分布的復(fù)雜網(wǎng)絡(luò)，其明顯特征即具有擇優(yōu)連接特性，即度大的節(jié)點(diǎn)被連接的概率較大。因現(xiàn)實(shí)中大部分網(wǎng)絡(luò)都具有或多或少的無(wú)標(biāo)度特性，所以本文選取無(wú)標(biāo)度網(wǎng)絡(luò)進(jìn)行仿真實(shí)驗(yàn)。

仿真所使用的工具仍為R語(yǔ)言的igraph包，其中barabasi.game函數(shù)可用來(lái)生成無(wú)標(biāo)度網(wǎng)絡(luò)，對(duì)無(wú)標(biāo)度網(wǎng)絡(luò)生成控制采用兩種屬性參數(shù)：每時(shí)步網(wǎng)絡(luò)新增連接數(shù)m和無(wú)標(biāo)度網(wǎng)絡(luò)擇優(yōu)連接的強(qiáng)度power，其中power的數(shù)值越大，表示網(wǎng)絡(luò)的擇優(yōu)連接特性越明顯。

所選參數(shù)具體數(shù)值如表3所示：

由表3可得12種m和power的組合，即仿真生成12個(gè)無(wú)標(biāo)度網(wǎng)絡(luò)，序號(hào)為l到12。根據(jù)事先定制的無(wú)標(biāo)度網(wǎng)絡(luò)生成模式，我們預(yù)期根據(jù)本文的相似度計(jì)算方法可以將這12個(gè)無(wú)標(biāo)度網(wǎng)絡(luò)分成4類：{l，2，3}，{4，5，6}，{7，8，9}，{10，11，12}，即生成模式相近的網(wǎng)絡(luò)之間相似度較大。仿真結(jié)果如圖2所示：

由圖2可以發(fā)現(xiàn)，使用本文所使用的相似度計(jì)算方法，可以將具有相似生成模式的無(wú)標(biāo)度網(wǎng)絡(luò)聚到同一類中，證明了根據(jù)本文提取的復(fù)雜網(wǎng)絡(luò)拓?fù)渲笜?biāo)建立特征向量可以比較準(zhǔn)確的表征復(fù)雜網(wǎng)絡(luò)的全局特征，此方法具有可行性。下面采用該相似度研究方法對(duì)實(shí)際的技術(shù)交易復(fù)雜網(wǎng)絡(luò)進(jìn)行實(shí)證分析。

4 相似度算法實(shí)證分析

上一章算法仿真分析是以無(wú)標(biāo)度網(wǎng)絡(luò)為實(shí)驗(yàn)網(wǎng)絡(luò)的，為了證明算法可以應(yīng)用于復(fù)雜技術(shù)交易網(wǎng)絡(luò)，我們先證明復(fù)雜技術(shù)交易網(wǎng)絡(luò)具有無(wú)標(biāo)度特性即可。而這一點(diǎn)可以通過(guò)網(wǎng)絡(luò)的度分布來(lái)反映，復(fù)雜技術(shù)交易網(wǎng)絡(luò)的度分布如圖3所示，可以看出，左圖為度的長(zhǎng)尾分布，右圖對(duì)橫縱軸取對(duì)數(shù)結(jié)果近似一條直線，可知復(fù)雜技術(shù)交易網(wǎng)絡(luò)的度分布呈現(xiàn)冪律特性，證明其具有無(wú)標(biāo)度特性。

由于技術(shù)交易的合同通常為若干年，所以數(shù)據(jù)預(yù)處理時(shí)先將每條交易記錄的合同年份跨度標(biāo)出，然后遍歷數(shù)據(jù)，選取合同年份跨度中包含當(dāng)前時(shí)間的交易加入到該天的復(fù)雜技術(shù)交易網(wǎng)絡(luò)中，這樣可以很好的保持網(wǎng)絡(luò)中節(jié)點(diǎn)和邊的生存周期。實(shí)證分析所取數(shù)據(jù)以月份為單位構(gòu)建復(fù)雜網(wǎng)絡(luò)，對(duì)每月內(nèi)的特征數(shù)據(jù)進(jìn)行取平均值的操作。

復(fù)雜網(wǎng)絡(luò)拓?fù)涮匦缘奶崛∈褂玫氖荝語(yǔ)言igraph中的封裝好的函數(shù)，包括度計(jì)算（degree）、平均路徑長(zhǎng)度（average.path.length）、直徑（get.diameter）、聚集系數(shù)（transitivity）以及介數(shù)（betweenness）。將得到的特征向量組成特征矩陣，對(duì)特征矩陣每一種特征分別進(jìn)行歸一化處理，之后計(jì)算向量之間的距離，得到不同年份復(fù)雜技術(shù)交易網(wǎng)絡(luò)的距離矩陣，根據(jù)距離矩陣使用hclust函數(shù)進(jìn)行層次聚類，類與類之間的距離使用“complete”距離參數(shù)。

由于聚類結(jié)果中月份較多，使用層次聚類圖展示不方便觀察，所以筆者將每個(gè)復(fù)雜網(wǎng)絡(luò)所屬的類標(biāo)號(hào)及日期繪制成圖如下所示：

由圖4圓點(diǎn)代表第一類網(wǎng)絡(luò)，三角表示第二類網(wǎng)絡(luò)，方塊代表第三類網(wǎng)絡(luò)，可見(jiàn)，根據(jù)本文的相似度計(jì)算方法將不同年份的復(fù)雜技術(shù)交易網(wǎng)絡(luò)按照拓?fù)浣Y(jié)構(gòu)相似度聚類到一起，總體來(lái)看效果較好，沒(méi)有出現(xiàn)異常的單獨(dú)月份，從拓?fù)浣Y(jié)構(gòu)來(lái)看，月份相近的網(wǎng)絡(luò)確實(shí)在結(jié)構(gòu)上相似度較高，使用本文的相似度計(jì)算方法將技術(shù)交易的發(fā)展大致分為了三個(gè)階段，在不同階段交界處存在著模糊階段可忽略：其中2006到2008為第一階段，2009年到2013年為第二階段，之后為第三階段。每個(gè)階段的關(guān)鍵指標(biāo)歸一化平均值計(jì)算結(jié)果如下表所示：

由表中數(shù)據(jù)可見(jiàn)，復(fù)雜技術(shù)交易網(wǎng)絡(luò)發(fā)展的三個(gè)階段過(guò)程中，平均路徑長(zhǎng)度以及直徑都在減小，而度、介數(shù)和聚集系數(shù)這三個(gè)指標(biāo)都在增加，很清晰地說(shuō)明了技術(shù)交易成果轉(zhuǎn)化效率逐步提高，技術(shù)交易整體具有技術(shù)集中化、合作多元化的趨勢(shì)。

5 結(jié)論

本文提出了一種基于復(fù)雜網(wǎng)絡(luò)全局拓?fù)涮匦缘男拖嗨贫扔?jì)算方法，即提取復(fù)雜網(wǎng)絡(luò)的全局拓?fù)涮卣鹘?fù)雜網(wǎng)絡(luò)的特征向量，通過(guò)計(jì)算特征向量的距離來(lái)對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行聚類。方法的驗(yàn)證是通過(guò)使用無(wú)標(biāo)度網(wǎng)絡(luò)進(jìn)行仿真分析以及基于技術(shù)交易數(shù)據(jù)的實(shí)證分析，驗(yàn)證結(jié)果對(duì)該相似度計(jì)算方法給予了充分的證明，該方法在計(jì)算復(fù)雜網(wǎng)絡(luò)之間的相似度中具有可行性與可信性，根據(jù)該相似度計(jì)算方法將技術(shù)交易大致分為了三個(gè)階段，闡述了技術(shù)交易市場(chǎng)的發(fā)展趨勢(shì)，主要工作包含以下4點(diǎn)：

1、對(duì)技術(shù)交易數(shù)據(jù)進(jìn)行預(yù)處理

2、構(gòu)建復(fù)雜技術(shù)交易網(wǎng)絡(luò)并提取拓?fù)涮卣?/p>

3、對(duì)復(fù)雜網(wǎng)絡(luò)特征向量進(jìn)行距離計(jì)算

4、對(duì)聚類結(jié)果進(jìn)行解釋并探索原因

本文使用的相似度計(jì)算方法在于拓?fù)涮卣鳛榛谌志W(wǎng)絡(luò)提取的，構(gòu)建的特征向量可以比較全面得代表復(fù)雜網(wǎng)絡(luò)的整體特征，對(duì)復(fù)雜網(wǎng)絡(luò)的相似程度計(jì)算較為準(zhǔn)確。但是該方法扔存在可優(yōu)化的空間，比如拓?fù)涮卣鲾?shù)量比較少，可以尋找更多具有代表性的拓?fù)涮卣?。另外，拓?fù)涮卣髦g可能存在著一定的線性關(guān)系，對(duì)多維度的拓?fù)涮卣魅绾芜M(jìn)行降維（如主成分分析等）也是筆者下一步準(zhǔn)備研究的內(nèi)容之一。