基于空間活躍度網(wǎng)絡的搜索策略研究

韓定定，柳 康，陳 超，陳 趣

(華東師范大學上海市多維度信息處理重點實驗室,上海 200241)

基于空間活躍度網(wǎng)絡的搜索策略研究

韓定定，柳 康，陳 超，陳 趣

(華東師范大學上海市多維度信息處理重點實驗室,上海 200241)

基于具有時變特性與空間特性的空間活躍度網(wǎng)絡模型，研究了時變網(wǎng)絡中的搜索問題。結(jié)合空間活躍度網(wǎng)絡的特性，引入了搜索時間、搜索路徑長度和等待時間3種搜索策略的評價指標，提出了最大活躍度搜索策略、改進的貪婪搜索策略和最大活躍度最小距離搜索策略。利用這些策略在空間活躍度網(wǎng)絡中進行搜索，研究發(fā)現(xiàn)和其他的搜索策略相比，改進的貪婪搜索策略與最大活躍度最小距離搜索策略具有較好的搜索性能，能夠很好地適用于這種類型的時變網(wǎng)絡，從而優(yōu)化了目標搜索的過程。

時變網(wǎng)絡；活躍度驅(qū)動；空間性；搜索策略；最優(yōu)搜索

0 引言

在復雜網(wǎng)絡的研究中，研究對象通常是靜態(tài)網(wǎng)絡[1-3]，即網(wǎng)絡的拓撲是固定不變的。然而，現(xiàn)實網(wǎng)絡總是隨著時間不斷變化，網(wǎng)絡內(nèi)的節(jié)點與連邊會不斷產(chǎn)生或消失[4]。例如，因特網(wǎng)中的網(wǎng)頁鏈接每天都在不斷增加和減少；在通信網(wǎng)絡中，用戶間的連接會受通信狀態(tài)影響持續(xù)不同時間等。這些現(xiàn)象均體現(xiàn)了網(wǎng)絡的時變特征，我們把具有時變特征的網(wǎng)絡統(tǒng)稱為時變網(wǎng)絡。通過對時變網(wǎng)絡的拓撲變化情況與動力學過程進行探索，可以幫助人們更好地理解真實網(wǎng)絡的結(jié)構(gòu)與功能，從而解決現(xiàn)實生活中的諸多問題。

時變網(wǎng)絡的研究主要包括：時變數(shù)據(jù)的描述與處理[5-7]、時變拓撲統(tǒng)計特性的定義[8-10]、時變條件下的社團探測與演化規(guī)律研究[11]以及真實系統(tǒng)的時變特性建模等[12-14]。在時變網(wǎng)絡建模研究中，學者們建立了很多不同的時變網(wǎng)絡模型，其中較為著名的是Nicola Perra等人提出的活躍度驅(qū)動模型[15]。在一些受人類行為影響的網(wǎng)絡中，個體的行為存在著很大差異，NicolaPerra等人將這些行為差異定義為個體的活躍度，并從個體活躍度驅(qū)動的角度提出了一種時變網(wǎng)絡的建模方法，構(gòu)建了活躍度驅(qū)動模型，為人們理解時變網(wǎng)絡提供了新的視角。該模型指出，使網(wǎng)絡產(chǎn)生時變特性的內(nèi)在驅(qū)動力是節(jié)點的活躍度。然而在復雜的現(xiàn)實網(wǎng)絡中，除了活躍度外還存在很多其它的特性，比如空間性、聚集性等，它們也影響著網(wǎng)絡的結(jié)構(gòu)特征。

搜索是復雜網(wǎng)絡中基礎的動力學過程之一。搜索問題起源于20世紀60年代Milgram做的信件傳遞實驗，他利用該實驗來估計社會網(wǎng)絡中兩個人之間的實際距離，通過實驗結(jié)果提出了著名的“六度分離”推斷[16]。Milgram的實驗揭示了社會網(wǎng)絡的兩個性質(zhì)，一是網(wǎng)絡的小世界特性，二是網(wǎng)絡的可搜索特性。網(wǎng)絡的可搜索特性其實與網(wǎng)絡本身的結(jié)構(gòu)性質(zhì)密切相關。除了網(wǎng)絡結(jié)構(gòu)對搜索過程的影響，搜索策略也是影響網(wǎng)絡搜索能力的重要因素?，F(xiàn)有的復雜網(wǎng)絡搜索策略的研究多是基于網(wǎng)絡拓撲不變的條件，研究的載體網(wǎng)絡主要是一系列靜態(tài)網(wǎng)絡，缺乏針對時變網(wǎng)絡的研究。網(wǎng)絡的時變特征使得網(wǎng)絡結(jié)構(gòu)隨著時間動態(tài)變化，而不同的拓撲結(jié)構(gòu)亦會對網(wǎng)絡上的動力學過程產(chǎn)生重大影響。

以疾病或病毒在網(wǎng)絡上的傳播為例，當網(wǎng)絡的拓撲結(jié)構(gòu)發(fā)生變化時，病毒在網(wǎng)絡上的傳播路徑會受到影響，從而使疾病傳染強度的閾值也相應發(fā)生變化，呈現(xiàn)或上升或下降的趨勢，進而影響疾病的傳播速度與傳播范圍。對于具有時變特征的實際網(wǎng)絡，之前的一些搜索策略可能無法使搜索效率達到最優(yōu)，策略的有效性也沒有得到驗證。比如在搜索到某個點時所有與該點的連邊都消失了，該點成為了孤立的節(jié)點，無法將該點上的信息傳遞出去，這就會使得搜索失敗。因此研究時變網(wǎng)絡上提高搜索效率的策略，探索時變拓撲的特殊網(wǎng)絡特性，挖掘時變網(wǎng)絡動力學特征具有必然性。

本文基于具有時變性和空間性的空間活躍度網(wǎng)絡模型對時變網(wǎng)絡進行搜索研究，旨在驗證靜態(tài)網(wǎng)絡搜索策略的有效性，并設計符合該時變網(wǎng)絡特性的搜索策略，系統(tǒng)地研究時變網(wǎng)絡中的搜索問題。

1 空間活躍度網(wǎng)絡模型構(gòu)建

本文提出一種空間活躍度網(wǎng)絡模型，主要考慮了兩方面的內(nèi)容：一是節(jié)點的活躍度，二是節(jié)點的地理位置?；钴S度特性使得網(wǎng)絡具有時變的特征，地理位置特性使得生成的連邊具有地理趨近性。模型設定N個節(jié)點分布在L×L的二維網(wǎng)格上，使得每個節(jié)點都具有坐標信息，其中N=L×L。每個節(jié)點i賦予活躍度，ai代表了在單位時間內(nèi)給定的節(jié)點能自發(fā)與其他節(jié)點生成連邊的概率。ai滿足冪律分布F(a)，即F(a)∝a-γ，γ為活躍度冪指數(shù)，網(wǎng)絡的生成機制如下：

1)在每個時間步長t內(nèi)，二維網(wǎng)格內(nèi)節(jié)點之間均無連邊；

2)節(jié)點i根據(jù)概率aiΔt變成活躍節(jié)點，與其他m個節(jié)點產(chǎn)生m條連邊，其中與節(jié)點j連接的概率滿足：

(1)

其中，rij為節(jié)點i與節(jié)點j之間的曼哈頓距離。α為偏好連接冪指數(shù)，當指數(shù)α取值為0時，節(jié)點在選擇連邊時不具地理偏好性，能與任意的其他節(jié)點都產(chǎn)生連邊。隨著冪指數(shù)α值的增加，兩個曼哈頓距離較遠的節(jié)點之間有連邊的概率會越來越小；

3)在t+Δt時刻，網(wǎng)絡中所有生成的連邊同時消失，然后重復第2)步的過程形成下一個時刻的拓撲結(jié)構(gòu)。

為了直觀地說明偏好連接指數(shù)α對網(wǎng)絡特性的影響，畫出了α取不同值時整個網(wǎng)絡聚合拓撲的對比，如圖1所示。設定節(jié)點數(shù)N=L×L=625，聚合時間窗t=5。拓撲圖通過復雜網(wǎng)絡可視化軟件工具Gephi畫出，為了清晰地顯示網(wǎng)絡的拓撲結(jié)構(gòu)，省略了網(wǎng)絡中孤立的節(jié)點。在圖1a中，設置α=0，此時連邊分布隨機，可以看出圖中的長邊數(shù)與短邊數(shù)基本差不多。在圖1b中，設置α=3，節(jié)點在連邊時具有空間上的偏好連接特性，更易與距離自己近的節(jié)點產(chǎn)生連邊，而與距離遠的節(jié)點產(chǎn)生連邊的概率很小，因此在圖中表現(xiàn)為短邊數(shù)比長邊數(shù)多，體現(xiàn)了局部的聚集現(xiàn)象。

2 空間活躍度網(wǎng)絡搜索策略研究

在構(gòu)建了空間活躍度網(wǎng)絡模型，對網(wǎng)絡結(jié)構(gòu)特性有了一定認識后，希望研究該網(wǎng)絡模型上的搜索過程從而能夠應用到實際生活中。對于搜索而言，如何在給定的網(wǎng)絡結(jié)構(gòu)中快速搜索到目標是人們希望解決的問題，這就涉及到搜索策略的研究。通過選取和設計合適的搜索策略，以較小的搜索代價快速準確地搜索到目標并進行反饋，這具有重要的現(xiàn)實意義。而搜索策略的制定需要通過網(wǎng)絡的局部信息，諸如節(jié)點的度或者介數(shù)等一系列刻畫網(wǎng)絡特征的參數(shù)。那么，根據(jù)上一章節(jié)中我們構(gòu)建的空間活躍度網(wǎng)絡模型特性，我們是否可以利用節(jié)點的活躍度和地理空間信息來設計出合理的搜索策略以適應該時變網(wǎng)絡的特點？

圖1 不同偏好連接指數(shù)下網(wǎng)絡的拓撲結(jié)構(gòu)Fig.1 The topology of the network under different preferences link index

2.1 搜索效率的衡量指標

搜索策略需要具體的測量參數(shù)作為評價指標，用來比較各種搜索策略的優(yōu)劣。這一部分主要介紹了3種衡量搜索策略性能的參數(shù)，它們分別是搜索步數(shù)、搜索路徑長度以及等待時間，分別從不同的角度表示了搜索策略在實際網(wǎng)絡搜索中的效率與開銷。

2.1.1 搜索時間

搜索時間是指，從源節(jié)點開始至查找到目標節(jié)點結(jié)束這個過程中所經(jīng)歷的時間間隔，即在網(wǎng)絡搜索過程中找到明確目標節(jié)點的搜索步數(shù)。對復雜網(wǎng)絡的搜索來說，搜索時間是重要的衡量參數(shù)，它最直接反映了搜索策略的速度。通常來說，搜索時間越短，相應的搜索策略的效率就越高，搜索速度就越快。因此好的搜索策略的搜索時間一般都很短。而在一般的大規(guī)模網(wǎng)絡中，光靠幾條搜索出來的路徑對應的搜索時間是不夠有說服力的，所以一般采取平均搜索時間這個統(tǒng)計性質(zhì)來衡量搜索速度，在文章中用T表示。為了便于計算，在接下來搜索策略的研究中設定時變網(wǎng)絡中拓撲變化的時間間隔與每一步搜索的時間間隔在相同的時間尺度內(nèi)。也就是說，每進行一步搜索，網(wǎng)絡的拓撲就會發(fā)生一次變化。因此，搜索時間也指從源節(jié)點開始至搜索到目標節(jié)點期間網(wǎng)絡拓撲的演化時間。

2.1.2 搜索路徑長度

在空間活躍度網(wǎng)絡中，所有的節(jié)點都分布在二維網(wǎng)格上，具有各自的地理空間信息，節(jié)點間的距離又稱為曼哈頓距離，可通過節(jié)點坐標計算得到。假設節(jié)點u的坐標為(i,j)，節(jié)點v的坐標為(k,l)，則兩點間的曼哈頓距離d(u,v)為

d(u,v)=d((i,j),(k,l))=|k-i|+|l-j|

(2)

搜索路徑長度定義為從源節(jié)點開始搜索到目標節(jié)點時所走過的曼哈頓距離之和。對于起點為x0，終點為xn，搜索時依次經(jīng)過節(jié)點x1，x2，…，xn-1的搜索路徑長度用公式表示為

(3)

在現(xiàn)實網(wǎng)絡中，搜索路徑長度一般映射為搜索的成本大小。比如在航空網(wǎng)絡中，從一個城市飛到另一個城市所需要花費的成本可考慮成這一趟航班的票價，而票價主要受航程距離的影響，長距離的航班票價往往比短距離的航班票價貴。因此，搜索成本可以用搜索路徑長度來表示。和搜索時間一樣，計算幾次搜索結(jié)果的搜索路徑長度是不夠的，所以我們一般在多次搜索后計算平均搜索路徑長度這一統(tǒng)計特性，在文章中用S表示，它也是衡量搜索策略好壞的重要指標。

2.1.3 等待時間

由于空間活躍度網(wǎng)絡的拓撲具有時變特性，所以在進行搜索時，會遇到信息在上一時刻傳遞到當前節(jié)點，而當前節(jié)點在當前時刻沒有與任何其他節(jié)點發(fā)生連邊的情況。這時該節(jié)點成了孤立的節(jié)點，沒有鄰居節(jié)點使其能將信息傳遞出去。為了避免搜索的失敗，引入等待時間這一指標，用W表示，在搜索過程中遇到上述狀況時對等待時間進行累加，直到在某一時刻拓撲的變化使得該節(jié)點重新有了鄰居節(jié)點，從而能夠重新將信息傳遞出去，保證搜索過程的順利進行。因此，在搜索開始時將等待時間初始化為0，在搜索過程中每次遇到上述狀況時，將其值加1，直到搜索過程的完成。由搜索時間的定義可知，在搜索時間中包含了等待時間，通過計算搜索時間與等待時間可以知道在搜索過程中真正發(fā)生信息傳遞的步數(shù)。

2.2 搜索策略的設計

網(wǎng)絡搜索過程開始時，首先選定源節(jié)點和目標節(jié)點，然后從源節(jié)點開始，在搜索到當前節(jié)點時，利用不同的搜索策略所制定的規(guī)則，選擇出符合條件的節(jié)點作為下一步傳遞信息的節(jié)點，并計算相應的搜索效率指標。以此循環(huán)，直至搜索到目標節(jié)點，完成整個搜索過程，通過搜索指標比較各搜索策略的性能差異。

常用的搜索策略有隨機游走搜索策略[17]、最大度搜索策略[18-19]和貪婪搜索策略[20]等。在選擇下一步的信息傳遞節(jié)點時，隨機游走策略選取的是一個隨機的鄰居節(jié)點，最大度策略選取的是度最大的鄰居節(jié)點，貪婪策略選取的是距目標節(jié)點最近的鄰居節(jié)點。這些搜索策略適用于靜態(tài)網(wǎng)絡，在時變網(wǎng)絡中的有效性還有待驗證。

2.2.1 最大活躍度搜索策略

在空間活躍度網(wǎng)絡中，影響網(wǎng)絡拓撲的主要因素是節(jié)點的活躍度屬性與地理空間偏好連接屬性。一方面，活躍度越大的節(jié)點在每個時間間隔內(nèi)具有越大的概率成為活躍節(jié)點，從而擁有較多的鄰居節(jié)點。另一方面，活躍節(jié)點越容易與距離近的節(jié)點產(chǎn)生連邊。因此，在進行網(wǎng)絡搜索時，理論上通過這些活躍度大的節(jié)點搜索到目標節(jié)點的概率也會越大。因此，我們提出一種與最大度搜索策略類似的最大活躍度搜索策略，該搜索策略在搜索的每一步把信息傳遞給活躍度最大的鄰居節(jié)點，這些節(jié)點產(chǎn)生連邊的能力較強，從而使得找到目標節(jié)點的概率增大。最大活躍度搜索策略的具體搜索過程如下：

1)隨機選擇網(wǎng)絡中的源節(jié)點s與目標節(jié)點t，并將s賦值給s0，s0為當前節(jié)點。

2)搜索節(jié)點s0的鄰居節(jié)點，判斷其中是否存在目標節(jié)點t，如果存在，則搜索結(jié)束，否則執(zhí)行第3)步。

3)找到s0的鄰居中活躍度最大的節(jié)點sn，將搜索信息傳遞給sn，并將sn賦值給節(jié)點s0。

4)重復執(zhí)行第2)和第3)步，直至搜索到目標節(jié)點t為止。

2.2.2 改進的貪婪搜索策略

我們對貪婪搜索策略進行改進，除了計算當前節(jié)點的鄰居節(jié)點到目標節(jié)點的距離di外，另外也將當前節(jié)點到目標節(jié)點的距離d0計算在內(nèi)，選擇其中最小的值對應的節(jié)點作為下一跳的地址，若d0比任何的di都小，則在當前時刻不進行信息的傳遞，而是停留在當前節(jié)點上等待下一時刻拓撲的變化。這樣做可以保證每次信息傳遞到的節(jié)點都會離目標節(jié)點的距離更近，從而避免傳遞時方向的偏離產(chǎn)生更多的搜索成本，但是這樣做可能會使在每一時刻發(fā)生信息傳遞的概率變小，進而使得等待時間增加。搜索過程如下：

1)隨機選擇網(wǎng)絡中的源節(jié)點s與目標節(jié)點t，并將s賦值給s0，s0為當前節(jié)點。

2)搜索節(jié)點s0的鄰居節(jié)點，判斷其中是否存在目標節(jié)點t，如果存在，則搜索結(jié)束，否則執(zhí)行第3)步。

3)計算s0到目標節(jié)點的距離d0以及它的鄰居節(jié)點各自到目標節(jié)點的距離di，若d0比任何di都小，則不進行信息的傳遞，停留一個時間間隔；若di中有比d0小的鄰居節(jié)點存在，則找到其中di最小的鄰居節(jié)點i，將搜索信息傳遞給i，并將i賦值給節(jié)點s0。

4)重復執(zhí)行第2)步和第3)步，直至搜索到目標節(jié)點t為止。

2.2.3 最大活躍度最小距離搜索策略

在搜索的過程中，當前節(jié)點在選擇下一跳節(jié)點時，使用貪婪搜索策略，可以做到不使傳遞信息的方向偏離我們所要搜索的目標節(jié)點；使用最大活躍度搜索策略，將搜索信息傳遞給具有較大活躍度的節(jié)點，而這些節(jié)點往往擁有較多的長程連邊，使得搜索到目標節(jié)點的可能性增大。因此，可以結(jié)合最大活躍度搜索策略和貪婪搜索策略的優(yōu)點，每次在傳遞時將信息傳遞給活躍度較大且離目標節(jié)點較近的鄰居節(jié)點，從而快速準確地找到目標節(jié)點。利用交通意識路由協(xié)議(Traffic Awareness Protocol, TAP)的設計思想[21]，引入耦合函數(shù)

J(i)=c/ai+(1-c)di

(4)

該搜索策略在傳遞信息的每一步將信息傳遞給J(i)最小的鄰居節(jié)點，其中ai為節(jié)點i的活躍度，di為節(jié)點i到目標節(jié)點的距離，c為耦合系數(shù)，0≤c≤1。當c=0時，此策略為貪婪搜索策略；當c=1時，此策略為最大活躍度搜索策略；當c取其它值時，在選擇最佳路徑時會同時考慮活躍度的因素和路徑長度的因素。搜索過程如下：

1)隨機選擇網(wǎng)絡中的源節(jié)點s與目標節(jié)點t，并將s賦值給s0，s0為當前節(jié)點。

2)搜索節(jié)點s0的鄰居節(jié)點，判斷其中是否存在目標節(jié)點t，如果存在，則搜索結(jié)束，否則執(zhí)行第3)步。

3)計算各鄰居節(jié)點的J(i)值，找到其中最小的值對應的鄰居節(jié)點i，將搜索信息傳遞給i，并將i賦值給節(jié)點s0。

4)重復執(zhí)行第2)步和第3)步，直至搜索到目標節(jié)點t為止。

3 搜索策略的比較

建立一組不同規(guī)模的空間活躍度網(wǎng)絡，設定偏好連接冪指數(shù)α=2，連邊數(shù)m=6，活躍度冪指數(shù)γ=2.8，耦合系數(shù)c=0.01，隨機地選取5 000對節(jié)點作為源節(jié)點和目標節(jié)點，分別利用隨機游走搜索策略(RW)、最大活躍度搜索策略(MA)、貪婪搜索策略(GY)、改進的貪婪搜索策略(IMGY)和最大活躍度最小距離搜索策略(MAMD)進行網(wǎng)絡搜索。為了衡量不同搜索策略的搜索效率，我們分別計算各搜索策略的平均搜索時間、平局搜索路徑長度和平均等待時間。3種指標越小，那么表示對應的搜索策略的效率就越高。

圖2為不同搜索策略下網(wǎng)絡規(guī)模與平均搜索時間的關系。由圖中曲線關系可得，隨著網(wǎng)絡規(guī)模的增大，所有搜索策略的平均搜索時間都變長了。和其他的幾種搜索策略相比，改進的貪婪搜索和最大活躍度最小距離搜索策略都具有明顯的優(yōu)勢，能夠大大縮短平均搜索時間，且最大活躍度最小距離搜索策略的平均搜索時間比改進的貪婪搜索策略的平均搜索時間還短。這是因為雖然在搜索過程的每一步都使信息的傳遞方向更靠近目標節(jié)點，但是選擇一個活躍度較大的鄰居節(jié)點，即使該鄰居離目標節(jié)點很遠，但是該鄰居節(jié)點在下一時刻活躍并且產(chǎn)生長程連邊的概率很大，那么在下一次傳遞信息時，可以把信息沿著該長程連邊傳遞，從而使接受信息的節(jié)點有可能離目標節(jié)點更近。最大活躍度最小距離搜索策略在搜索的過程中同時考慮了節(jié)點的活躍度與節(jié)點離目標節(jié)點的距離這兩個因素，仿真結(jié)果也證明了該策略的平均搜索時間比其他搜索策略的平均搜索時間更短。

在平均搜索路徑長度方面，改進的貪婪搜索策略和最大活躍度最小距離搜索策略也表現(xiàn)了較好的性能，且改進的貪婪搜索策略的平均搜索路徑比最大活躍度最小距離搜索策略更短，如圖3所示。這是由于改進的貪婪搜索策略保證了在進行每一步的信息傳遞時都會離目標節(jié)點更近，在出現(xiàn)鄰居節(jié)點到目標節(jié)點的距離均比當前節(jié)點到目標節(jié)點的距離長這種情況時，不進行信息的傳遞而是等待一個時間間隔，從而避免了傳遞時方向的偏移，減少了多余的搜索路徑，獲得較短的平均搜索路徑長度。

圖2 網(wǎng)絡規(guī)模L與平均搜索時間T的關系Fig.2 The relationship of network size L and the average search time T

圖3 網(wǎng)絡規(guī)模L與平均搜索路徑長度S的關系Fig.3 The relationship of network size L and average search path length S

在平均等待時間方面，由圖4中曲線可知改進的貪婪搜索與最大活躍度最小距離搜索策略所用的平均等待時間依然比其他的搜索策略短很多。例如在網(wǎng)絡規(guī)模N=L×L=400時，改進的貪婪搜索與最大活躍度最小距離搜索策略的平均等待時間分別只有23和20，而貪婪搜索策略的則為42，其他的搜索策略更高。盡管網(wǎng)絡的拓撲隨著時間在不斷發(fā)生變化，這兩種搜索策略還是能夠較快地將搜索信息傳遞出去。

圖5為各搜索策略的平均等待時間與平均搜索時間的比值。可以發(fā)現(xiàn)，改進的貪婪搜索策略與最大活躍度最小距離搜索策略的等待時間占據(jù)了平均搜索時間的很大一部分。比如在網(wǎng)絡規(guī)模N=L×L=400時，改進的貪婪搜索策略為82%，最大活躍度最小距離搜索策略為91%，而其他搜索策略均在41%以下。這說明在搜索過程中，運用這兩種搜索策略時真正用于信息傳遞的搜索步數(shù)并不多。既便如此，這兩種策略的搜索效率比其它的搜索策略效率還是高很多。這是因為改進的貪婪搜索策略保證了網(wǎng)絡搜索時方向不會偏離目標節(jié)點，最大活躍度最小距離搜索策略則同時考慮了節(jié)點的最大活躍度和距目標節(jié)點的最小距離，從而大大提高了搜索效率。而其他的幾種搜索策略雖然也能搜索到目標節(jié)點，但是由于搜索方向的偏移性產(chǎn)生了很多曲折迂回的搜索路線，以及低活躍性的節(jié)點在很長的時間間隔內(nèi)無法產(chǎn)生連邊將信息傳遞出去，這都導致了平均搜索時間和平均搜索路徑長度的增加。

圖4 網(wǎng)絡規(guī)模L與平均等待時間W的關系Fig.4 The relationship of network size L and the average waiting time W

圖5 不同網(wǎng)絡規(guī)模L下等待時間與搜索時間比值W/TFig.5 The waiting time and the search time ratio W/Tunder different network size L

綜上所述，在空間活躍度網(wǎng)絡上進行搜索工作時，結(jié)合網(wǎng)絡的時變性與空間性特點，利用最大活躍度最小距離搜索策略和改進的貪婪搜索策略均能較快搜索到目標，在很大程度上提高了搜索的性能。將本文提出的搜索策略應用于現(xiàn)實社交網(wǎng)絡中，用戶在每次搜索時將信息傳遞給與自己距離近且在社交活動中表現(xiàn)活躍的用戶，則會加快搜尋的速度，從而大大提升目標搜索的效率。因此，這些搜索策略的研究工作也為現(xiàn)實網(wǎng)絡中的搜索問題提供了重要的理論指導。

4 結(jié)語

本文構(gòu)建了一種具有時變特性與地理空間特性的空間活躍度網(wǎng)絡模型，在該網(wǎng)絡上進行搜索策略的研究。首先引入了搜索時間、搜索路徑長度和等待時間3個衡量搜索效率的指標；其次結(jié)合空間活躍度網(wǎng)絡的特性依次提出了最大活躍度搜索策略、改進的貪婪搜索策略和最大活躍度最小距離搜索策略；最后利用這些策略進行網(wǎng)絡搜索，通過比較發(fā)現(xiàn)改進的貪婪搜索策略與最大活躍度最小距離搜索策略能較好地適應空間活躍度網(wǎng)絡的特點，表現(xiàn)出較好的搜索性能。本文的研究工作為現(xiàn)實網(wǎng)絡中一些搜索問題的解決提供了思路與方法。

[1]Watts D J, Strogatz S H. Collective dynamics of “small-world” networks[J]. Nature, 1998, 393(6684):440-442.

[2]Liljeros F, Edling C R, Lan A. The web of human sexual contacts[J]. Nature, 2001, 411(6840):907-908.

[3]Ebel H, Mielsch L I, Bornholdt S. Scale-free topology of e-mail networks[J]. Physical Review E, 2002, 66(3):035103.

[4]Holme P, Saram?ki J. Temporal networks[J]. Physics Reports, 2012, 519(3):97-125.

[5]Bearman P S, Moody J, Stovel K. Chains of affection: the structure of adolescent romantic and sexual networks[J]. American journal of sociology, 2004, 110(1): 44-91.

[6]Cheng E, Grossman J W, Lipman M J. Time-stamped graphs and their associated influence digraphs[J]. Discrete Applied Mathematics, 2003, 128(2): 317-335.

[7]Riolo C S, Koopman J S, Chick S E. Methods and measures for the description of epidemiologic contact networks[J]. Journal of Urban Health, 2001, 78(3): 446-457.

[8]Pan R K, Saram?ki J. Path lengths, correlations, and centrality in temporal networks[J]. Physical Review E, 2011, 84(1): 016105.

[9]Tang J, Musolesi M, Mascolo C, et al. Temporal distance metrics for social network analysis[C]. Proceedings of the 2nd ACM Workshop on Online Social Networks. ACM, 2009: 31-36.

[10] Xuan B B, Ferreira A, Jarry A. Computing shortest, fastest, and foremost journeys in dynamic networks[J]. International Journal of Foundations of Computer Science, 2003, 14(2): 267-285.

[11] Holme P, Edling C R, Liljeros F. Structure and time evolution of an Internet dating community[J]. Social Networks, 2004, 26(2):155-174.

[12] Medo M, Cimini G, Gualdi S. Temporal effects in the growth of networks[J]. Physical review letters, 2011, 107(23): 238701.

[13] Chen Q, Han D D, Qian J H, et al. Optimal temporal path on spatial decaying networks[J]. Journal of Applied Analysis and Computation, 2016, 6(1):30-37.

[14] Chen Q, Qian J H, Zhu L, et al. Optimal transport in time-varying small-world networks[J]. Physical Review E, 2016, 93(3): 032321.

[15] Perra N, Gon?alves B, Pastor-Satorras R, et al. Activity driven modeling of time varying networks[J]. Scientific Reports, 2012, 2(6):1717-1720.

[16] Milgram S. The small world problem[J]. Psychology Today, 1967, 2(1):185-195.

[17] Pandit S A, Amritkar R E. Random spread on the family of small-world networks[J]. Physical Review E, 2001, 63(4): 041104.

[18] Adamic L A, Lukose R M, Huberman B A. Local search in unstructured networks[J]. Handbook of Graphs & Networks, 2002:295-317.

[19] Adamic L A, Lukose R M, Puniyani A R, et al. Search in power-law networks[J]. Physical review E, 2001, 64(4): 046135.

[20] Kleinberg J M. Navigation in a small world[J]. Nature, 2000, 41(10):2496-2515.

(責任編輯 耿金花)

Search Strategies Based on Spatial Activity Network

HAN Dingding, LIU Kang, CHEN Chao, CHEN Qu

(Shanghai Key Laboratory of Multidimensional Information Processing, East China Normal University, Shanghai 200241, China)

Based on spatial activity network with the characteristics oftime varying and spatial property, searching on time varying network was studied in this paper. Combined with the characteristics of spatial activity network, search time, search path length and waiting time were introduced as evaluation indexes for search strategy. And maximum activity searching strategy, improved greedy searching strategy and maximum activity minimum distance searching strategy were proposed. It was found that using improved greedy searching strategy and maximum activity minimum distance searching strategy to search on the spatial activity network would get higher efficiency than any of other strategies. They were suitable for this type of time varying network and able to optimize the searching process.

time varying network; activity driven; spatial property; searching strategies; optimal searching

1672-3813(2017)02-0103-07；

10.13306/j.1672-3813.2017.02.015

2016-11-01；

2016-12-28

韓定定(1968-)，女，上海人，博士，教授，主要研究方向為復雜網(wǎng)絡與智能信息處理。

TP393.2

A