曲超　袁瑞芬　張國煉

(東莞理工學(xué)院　計(jì)算機(jī)學(xué)院，廣東東莞　523808)

?

網(wǎng)絡(luò)點(diǎn)邊對偶性變換及其性質(zhì)研究

曲超袁瑞芬張國煉

(東莞理工學(xué)院計(jì)算機(jī)學(xué)院，廣東東莞523808)

摘要：針對網(wǎng)絡(luò)拓?fù)渥儞Q提出了一種新的點(diǎn)邊對偶性變換方式，即將原始網(wǎng)絡(luò)中的邊映射為結(jié)點(diǎn)，結(jié)點(diǎn)映射為鄰接邊之間的多個二元關(guān)系。提出并證明了該變換的某些特性。通過實(shí)驗(yàn)對相應(yīng)性質(zhì)在不同結(jié)構(gòu)網(wǎng)絡(luò)中的表現(xiàn)加以驗(yàn)證。

關(guān)鍵詞：網(wǎng)絡(luò)拓?fù)?；點(diǎn)邊對偶變換；復(fù)雜網(wǎng)絡(luò)；網(wǎng)絡(luò)性質(zhì)

目前，互聯(lián)網(wǎng)規(guī)模越來越大，結(jié)點(diǎn)間相互作用復(fù)雜，其拓?fù)浣Y(jié)構(gòu)基本上未知或未曾探索[1]。人們對描述真實(shí)系統(tǒng)拓?fù)浣Y(jié)構(gòu)的研究經(jīng)歷了從歐幾里德格網(wǎng)到隨機(jī)圖，再到直到最近幾年發(fā)現(xiàn)的復(fù)雜網(wǎng)絡(luò)模型。小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)的發(fā)現(xiàn)，掀起了復(fù)雜網(wǎng)絡(luò)的研究熱潮，同時也帶動了各種網(wǎng)絡(luò)拓?fù)鋺?yīng)用的蓬勃發(fā)展。其中對于網(wǎng)絡(luò)拓?fù)淠Ｐ妥儞Q的研究主要應(yīng)用于交通網(wǎng)絡(luò)。其主要方法是將交通網(wǎng)絡(luò)抽象為復(fù)雜網(wǎng)絡(luò)的形式，這些復(fù)雜網(wǎng)絡(luò)是對交通網(wǎng)絡(luò)的映射，不同的抽象方法所獲得的復(fù)雜網(wǎng)絡(luò)圖，能夠從不同的角度反映出交通網(wǎng)絡(luò)的特點(diǎn)。其中主要包括：L-space、 C-space[2]、B-space[3]、P-space[4]、Primal Approach[5]以及Dual Approach[6]等。

上述的各類方法都是以邏輯概念做為變換依據(jù)，例如Dual Approach方法，將若干個連續(xù)的同名道路視為一個結(jié)點(diǎn)，將道路的交叉路口映射為結(jié)點(diǎn)間邊，雖然能夠?qū)煌ňW(wǎng)絡(luò)加以描述，但未能將網(wǎng)絡(luò)信息與道路實(shí)體相聯(lián)系，導(dǎo)致在實(shí)際應(yīng)用中產(chǎn)生各種問題。

1復(fù)雜網(wǎng)絡(luò)的基本概念

復(fù)雜網(wǎng)絡(luò)的復(fù)雜性體現(xiàn)在兩個方面：其一，復(fù)雜網(wǎng)絡(luò)常常包含海量的結(jié)點(diǎn)，即結(jié)點(diǎn)數(shù)量非常龐大；其二，復(fù)雜網(wǎng)絡(luò)之間的連接關(guān)系通常較為復(fù)雜。其主要度量參數(shù)及含義如下。

1)度分布。結(jié)點(diǎn)vi的度ki被定義為與該結(jié)點(diǎn)連接的相鄰結(jié)點(diǎn)的數(shù)目，所有結(jié)點(diǎn)的度的平均值稱為網(wǎng)絡(luò)的平均度，記為。網(wǎng)絡(luò)中結(jié)點(diǎn)的度分布用度分布函數(shù)P(k)來表示，含義是任意一個結(jié)點(diǎn)有k條邊的概率，也等于網(wǎng)絡(luò)中度為k的結(jié)點(diǎn)的數(shù)目占結(jié)點(diǎn)總數(shù)的比例。復(fù)雜網(wǎng)絡(luò)研究的另外一個重大發(fā)現(xiàn)是大部分大規(guī)模真實(shí)網(wǎng)絡(luò)在中，兩種度分布較為常見：一是指數(shù)度分布,即P(k)隨著k的增大以指數(shù)形式衰減；另一種分布是冪律分布，即P(k)~k(-γ)，其中γ稱為度指數(shù)，不同的網(wǎng)絡(luò)，其動力學(xué)性質(zhì)也不同。另外,度分布還有其它形式，如星型網(wǎng)絡(luò)的度分布是兩點(diǎn)分布，規(guī)則網(wǎng)絡(luò)的度分布為單點(diǎn)分布。

4)介數(shù)。介數(shù)通常分為邊介數(shù)和結(jié)點(diǎn)介數(shù)兩種。結(jié)點(diǎn)介數(shù)定義為網(wǎng)絡(luò)中所有最短路徑中經(jīng)過該結(jié)點(diǎn)的路徑的數(shù)目占最短路徑總數(shù)的比例。邊介數(shù)定義為網(wǎng)絡(luò)中所有最短路徑中經(jīng)過該邊的路徑的數(shù)目占最短路徑總數(shù)的比例。介數(shù)反映了相應(yīng)的結(jié)點(diǎn)或者邊在整個網(wǎng)絡(luò)中的作用和影響力，是一個重要的全局幾何量，具有很強(qiáng)的現(xiàn)實(shí)意義。根據(jù)結(jié)點(diǎn)和邊得介數(shù),能夠分析網(wǎng)絡(luò)系統(tǒng)中任意一個結(jié)點(diǎn)和另外結(jié)點(diǎn)之間的關(guān)聯(lián)，這種關(guān)聯(lián)被刪除或是失效時對整個系統(tǒng)的影響。

5)度和簇系數(shù)之間的相關(guān)性。網(wǎng)絡(luò)中度和簇系數(shù)之間的相關(guān)性被用來描述不同網(wǎng)絡(luò)結(jié)構(gòu)之間的差異，包括連接度不同的結(jié)點(diǎn)的相關(guān)性和結(jié)點(diǎn)的度與其簇系數(shù)之間的相關(guān)性。在網(wǎng)絡(luò)系統(tǒng)中，度和簇系數(shù)之間的相關(guān)性有助于分析系統(tǒng)的層次性和模塊程度。

用上述參數(shù)可以很方便地衡量現(xiàn)實(shí)網(wǎng)絡(luò)的特性。根據(jù)Newman的觀點(diǎn)[8]，現(xiàn)實(shí)網(wǎng)絡(luò)大致分為四種：社會網(wǎng)絡(luò)、信息網(wǎng)絡(luò)、技術(shù)網(wǎng)絡(luò)和生物網(wǎng)絡(luò)。這四種網(wǎng)絡(luò)雖然各自具有不同的物理形式、彼此描述的系統(tǒng)各異、其結(jié)點(diǎn)和邊的定義差別也很大，但它們卻具有一些相同的特征：網(wǎng)絡(luò)結(jié)點(diǎn)間的作用很復(fù)雜，而且高度不規(guī)則；結(jié)點(diǎn)之間在度、簇系數(shù)、集中性等網(wǎng)絡(luò)特征度量方面表現(xiàn)出不對稱性，不同結(jié)點(diǎn)差異很大；盡管這些網(wǎng)絡(luò)大而復(fù)雜，結(jié)點(diǎn)間的平均距離卻很小，呈現(xiàn)出小世界特性。大量的實(shí)證研究表明：現(xiàn)實(shí)世界中的許多網(wǎng)絡(luò)具有下面三個共同特性:結(jié)點(diǎn)度服從度指數(shù)介于[2,3]的冪律分布；集聚程度高；結(jié)點(diǎn)間平均距離小。

2網(wǎng)絡(luò)點(diǎn)邊對偶變換

對于交通網(wǎng)絡(luò)模型，Dual方法將句法空間里同名的多條邊看做一個結(jié)點(diǎn)，不能全面地反映出的城市道路網(wǎng)絡(luò)的深層特性。為此提出一種更具普遍意義的點(diǎn)邊網(wǎng)絡(luò)對偶變換。

不同于對偶圖，對偶變換圖是將原圖G中的邊轉(zhuǎn)換為結(jié)點(diǎn)，G中的結(jié)點(diǎn)轉(zhuǎn)換為新圖中的邊集。同樣，不同于Dual Approach方法，點(diǎn)邊對偶變換圖將任意一條邊看作新圖中的一個點(diǎn)，而不是在句法空間里將同名的多條邊作為新圖中的一個點(diǎn)，該定義更具普遍性。由定義可知對偶變換圖具有如下性質(zhì)：

定理1|V′|=|E|，即對偶變換圖G′的結(jié)點(diǎn)數(shù)等于原圖G中邊的條數(shù)。

證明 由定義可知該定理成立。

定理2G中的每一個結(jié)點(diǎn)在G′中轉(zhuǎn)化為一個團(tuán)(clique)，且任意兩個團(tuán)之間沒有公共邊。

圖1　k3，k4，k5及其點(diǎn)邊對偶變換圖

推論1G中度為n的結(jié)點(diǎn)在G′中轉(zhuǎn)化為Kn。

推論2G′中由G中結(jié)點(diǎn)轉(zhuǎn)化的團(tuán)兩兩之間最多只有一個公共點(diǎn)。

推論3G′中由G中度大于2的結(jié)點(diǎn)轉(zhuǎn)化的團(tuán)都是極大團(tuán)。

證明由定理2可知，G中度為di的結(jié)點(diǎn)vi在G′中轉(zhuǎn)化為團(tuán)kdi，其度數(shù)為di*(di-1)，又任意兩個團(tuán)之間沒有公共邊，因此圖G′的度數(shù)和為所有團(tuán)的度數(shù)和。

定理5表明在對偶變換后結(jié)點(diǎn)的簇系數(shù)不再依賴于對與目標(biāo)結(jié)點(diǎn)相鄰的結(jié)點(diǎn)之間邊數(shù)的計(jì)數(shù)，而是可以根據(jù)原始網(wǎng)絡(luò)結(jié)點(diǎn)的度來唯一確定。該性質(zhì)將對交通網(wǎng)絡(luò)的研究起到較為重要的作用。

3點(diǎn)邊對偶性變換的復(fù)雜網(wǎng)絡(luò)特性測試

對1 000個結(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)[9]、小世界網(wǎng)絡(luò)[10]以及無標(biāo)度網(wǎng)絡(luò)[11]進(jìn)行點(diǎn)邊對偶性變換，并考察其度量參數(shù)。

圖2　隨機(jī)網(wǎng)絡(luò)及其變換圖的度分布

圖3(a)、(b)分別顯示了平均度為4、6、8的小世界網(wǎng)絡(luò)及其點(diǎn)邊轉(zhuǎn)換后的網(wǎng)絡(luò)的度分布情況。與隨機(jī)網(wǎng)絡(luò)相似，小世界網(wǎng)絡(luò)的度分布呈現(xiàn)正態(tài)分布的特性，因而其點(diǎn)邊轉(zhuǎn)換圖的度分布也表現(xiàn)為正態(tài)分布。

圖3　小世界網(wǎng)絡(luò)及其變換圖的度分

圖4　無標(biāo)度網(wǎng)絡(luò)及其變換圖的度分布

圖4(a)、(b)分別顯示了平均度為4、6、8的無標(biāo)度網(wǎng)絡(luò)及其點(diǎn)邊轉(zhuǎn)換后的網(wǎng)絡(luò)的度分布情況。由于無標(biāo)度網(wǎng)絡(luò)度分布服從冪率分布，而冪率分布不具備線性可加性，因而點(diǎn)邊轉(zhuǎn)換后的網(wǎng)絡(luò)度分布并不符合馬太效應(yīng)。雖然如此，但從圖像中可以看出其度分布近似于冪率分布，導(dǎo)致該現(xiàn)象的原因有待進(jìn)一步研究和探索。

以上網(wǎng)絡(luò)的簇系數(shù)及平均最短路徑長度如表1所示。

表1　簇系數(shù)及平均最短路徑長度

從表1可以看出，隨機(jī)網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)經(jīng)過轉(zhuǎn)換后簇系數(shù)有所增大，其原因在于根據(jù)推論1，原始網(wǎng)絡(luò)的結(jié)點(diǎn)在轉(zhuǎn)換后的網(wǎng)絡(luò)中被轉(zhuǎn)換為若干團(tuán)，因而導(dǎo)致簇系數(shù)有所增大。根據(jù)定理6可知平均最短路徑長度應(yīng)隨轉(zhuǎn)換有所增大，但其幅度并不會很大，表1也驗(yàn)證了這一點(diǎn)。

4結(jié)論

網(wǎng)絡(luò)點(diǎn)邊對偶變換提供了一種新的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)研究方法。對于隨機(jī)網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)該變換基本保持了原圖的度分布規(guī)律、簇系數(shù)和平均最短路徑長度；對于無標(biāo)度網(wǎng)絡(luò)，其簇系數(shù)和平均最短路徑長度仍能與原圖保持基本一致。所證明的性質(zhì)及實(shí)驗(yàn)所的結(jié)論可應(yīng)用于交通網(wǎng)絡(luò)系統(tǒng)、生物學(xué)研究以及政治、經(jīng)濟(jì)、管理等領(lǐng)域。該變換的更多性質(zhì)有待進(jìn)一步研究和探索，在信息網(wǎng)絡(luò)模型中具有重要的研究價值。

參 考 文 獻(xiàn)

[1]Albert R, Barabasi A-L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002, 74(1): 47-97.

[2]Ferber C V, Holovatch T, Holovatch Y, et al. Public transport networks: empirical analysis and modeling [J]. Eur Phys J: B, 2009,68(2): 261-275.

[3]Zhang P P, Chen K, He Y. Model and empirical study on some collaboration networks [J]. Phys: A, 2006,360(2): 599-616.

[4]Ferber C V, Holovatch T, Holovatch Y, et al. Network harness: metropolis public transport [J]. Phys: A, 2007, 380(1):585-591.

[5]Porta S, Crucitti P, Latora V. The network analysis of urban streets: a primal approach [J]. Envir Planning: B, 2006,33: 705-725.

[6]Porta S, Crucitti P, Latora V. The network analysis of urban street: a dual approach [J]. Phys: A, 2006, 369(2): 853-866.

[7]Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393:440-442.

[8]Newman M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2):167-256.

[9]Vanhoucke M, Demeulemeester E, Herroelen W. A New Random Network Generator for Activity-on-the-Node Networks[J]. Journal of Scheduling, 2000, 6(1):1-23.

[10]Porter M A. Small-world network[J]. Scholarpedia, 2012, 7(2):1739.

[11]Cesar A H R, Barabási A L. Scale-free networks[J]. Encyclopedia of Genetics Genomics Proteomics & Informatics, 2008, 3(5):1716.

Vertex-Edge Duality Transformation for Network and Its Properties

QU ChaoYUAN RuifenZHANG Guodong

(Computer College, Dongguan University of Technology, Dongguan 523808, China)

AbstractThe paper proposes a new vertex-edge duality transformation method, that is, the edge mapping as a node, and the node mapping as a two element relationship between the adjacent edges, proving some properties about the duality transformation, and verifying the performance of the corresponding properties in different structures by experiments.

Key wordsnetwork topology; vertex-edge duality transformation; complex network; network properties

文章編號：1009-0312(2016)01-0001-06

中圖分類號：TP301

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

作者簡介：曲超(1979—)，男，山東煙臺人，講師，主要從事數(shù)據(jù)挖掘、語義網(wǎng)和物聯(lián)網(wǎng)等方面研究。

基金項(xiàng)目：東莞理工學(xué)院2014年大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201411819023)。

收稿日期：2015-07-08