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

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

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

中圖分類號：TP319

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

DOI：10.3969/j.issn.1003-6970.2015.09.004

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

2.2 距離計算方法的選取

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

2.3 可視化展示

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

3 算法仿真分析

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

仿真所使用的工具仍為R語言的igraph包，其中barabasi.game函數(shù)可用來生成無標(biāo)度網(wǎng)絡(luò)，對無標(biāo)度網(wǎng)絡(luò)生成控制采用兩種屬性參數(shù)：每時步網(wǎng)絡(luò)新增連接數(shù)m和無標(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個無標(biāo)度網(wǎng)絡(luò)，序號為l到12。根據(jù)事先定制的無標(biāo)度網(wǎng)絡(luò)生成模式，我們預(yù)期根據(jù)本文的相似度計算方法可以將這12個無標(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)，使用本文所使用的相似度計算方法，可以將具有相似生成模式的無標(biāo)度網(wǎng)絡(luò)聚到同一類中，證明了根據(jù)本文提取的復(fù)雜網(wǎng)絡(luò)拓?fù)渲笜?biāo)建立特征向量可以比較準(zhǔn)確的表征復(fù)雜網(wǎng)絡(luò)的全局特征，此方法具有可行性。下面采用該相似度研究方法對實際的技術(shù)交易復(fù)雜網(wǎng)絡(luò)進(jìn)行實證分析。

4 相似度算法實證分析

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

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

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

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

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

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

5 結(jié)論

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

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

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

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

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

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