一種動(dòng)態(tài)的移動(dòng)社交網(wǎng)絡(luò)拓?fù)淠Ｐ?/h1>
2014-06-06 10:46:47田雪穎劉衍珩王亞洲林佳佳
計(jì)算機(jī)工程 2014年9期 關(guān)鍵詞：模型
田雪穎,劉衍珩,孫 鑫,王亞洲,林佳佳
(1.吉林大學(xué)a.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;b.符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室,長(zhǎng)春130012; 2.中國(guó)海洋大學(xué)信息科學(xué)與工程學(xué)院,山東青島266100)
一種動(dòng)態(tài)的移動(dòng)社交網(wǎng)絡(luò)拓?fù)淠Ｐ?/p>
田雪穎1a,1b,劉衍珩1a,1b,孫 鑫2,王亞洲1a,林佳佳1a
(1.吉林大學(xué)a.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;b.符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室,長(zhǎng)春130012; 2.中國(guó)海洋大學(xué)信息科學(xué)與工程學(xué)院,山東青島266100)
針對(duì)移動(dòng)社交網(wǎng)絡(luò)的動(dòng)態(tài)性、用戶(hù)不同重要性和信息交互有向性,基于4種初始網(wǎng)絡(luò)提出能準(zhǔn)確描述移動(dòng)社交網(wǎng)絡(luò)結(jié)構(gòu)的拓?fù)淠Ｐ?。采用隨機(jī)游走理論和改進(jìn)的PageRank算法,引入過(guò)渡概率使每?jī)蓵r(shí)步之間的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相互聯(lián)系。通過(guò)PageRank算法得到節(jié)點(diǎn)的勢(shì),進(jìn)而求出概率過(guò)渡矩陣,利用隨機(jī)游走理論由上一時(shí)步邊存在概率矩陣和概率過(guò)渡矩陣得到當(dāng)前時(shí)步邊存在概率矩陣,每一時(shí)步動(dòng)態(tài)地增加一個(gè)節(jié)點(diǎn)并檢驗(yàn)是否有離開(kāi)的節(jié)點(diǎn)。仿真結(jié)果顯示,該模型在4種初始網(wǎng)絡(luò)下得到的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),入度、出度、勢(shì)分布以及度-勢(shì)相關(guān)性均具有明顯冪律特性,表明隨機(jī)游走理論和改進(jìn)的PageRank算法能較準(zhǔn)確描述移動(dòng)社交網(wǎng)絡(luò),具有一定的實(shí)踐意義。
社交網(wǎng)絡(luò);網(wǎng)絡(luò)拓?fù)?隨機(jī)游走;PageRank算法;過(guò)渡概率;仿真模型
1 概述
近年來(lái),隨著無(wú)線(xiàn)通信技術(shù)的飛速發(fā)展,無(wú)線(xiàn)網(wǎng)絡(luò)已經(jīng)廣泛應(yīng)用于我國(guó)的廣大地區(qū),尤其是在經(jīng)濟(jì)較為發(fā)達(dá)的城市。Wifi是無(wú)線(xiàn)局域網(wǎng)的重要部分,它可以最大限度地滿(mǎn)足個(gè)人、家庭和小型辦公系統(tǒng)對(duì)于移動(dòng)網(wǎng)絡(luò)連接的需求。手機(jī)、電腦、iPad無(wú)疑成了人們?cè)谝苿?dòng)網(wǎng)絡(luò)中進(jìn)行信息交互的主要工具。人們上班、購(gòu)物、出游等社交行為賦予了移動(dòng)自組網(wǎng)絡(luò)動(dòng)態(tài)性的特征,使其具有社會(huì)流動(dòng)性。因此,掌握移動(dòng)社交網(wǎng)絡(luò)的行為特征,分析移動(dòng)社交網(wǎng)絡(luò)的動(dòng)態(tài)性和規(guī)律性,具有重要的理論價(jià)值和現(xiàn)實(shí)意義。
由于移動(dòng)網(wǎng)絡(luò)具有規(guī)模大、增長(zhǎng)快的特點(diǎn),因此很難把它作為實(shí)驗(yàn)對(duì)象來(lái)進(jìn)行研究和分析[1]。對(duì)移動(dòng)網(wǎng)絡(luò)所引發(fā)的一系列網(wǎng)絡(luò)問(wèn)題的研究往往只能基于拓?fù)淠Ｐ瓦M(jìn)行。網(wǎng)絡(luò)拓?fù)淠Ｐ褪菍?duì)真實(shí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的模擬,利用拓?fù)淠Ｐ偷姆绞窖芯恳苿?dòng)網(wǎng)絡(luò)中用戶(hù)行為的方法由來(lái)已久。文獻(xiàn)[2]根據(jù)現(xiàn)實(shí)網(wǎng)絡(luò)中用戶(hù)行為的隨機(jī)性提出了經(jīng)典的Waxman隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ?文獻(xiàn)[3]基于邊概率隨節(jié)點(diǎn)距離增加而呈指數(shù)減少的思想提出了另外2種隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ?指數(shù)模型和位置模型;文獻(xiàn)[4]提出了“小世界網(wǎng)絡(luò)”模型,即WS模型,該模型的主要貢獻(xiàn)是提出了介于規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)之間的小世界網(wǎng)絡(luò),并能通過(guò)重連概率p進(jìn)行調(diào)節(jié),從而可使網(wǎng)絡(luò)結(jié)構(gòu)在規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)之間轉(zhuǎn)化;文獻(xiàn)[5]在研究域間系統(tǒng)時(shí)發(fā)現(xiàn)節(jié)點(diǎn)度的冪律法則,無(wú)標(biāo)度網(wǎng)絡(luò)由此成為了研究者關(guān)注的主要對(duì)象;文獻(xiàn)[6]通過(guò)向一個(gè)簡(jiǎn)單的模型中動(dòng)態(tài)地添加新節(jié)點(diǎn)和新連接模擬Internet網(wǎng)絡(luò)發(fā)展過(guò)程來(lái)生成符合冪法則的模型,稱(chēng)之為BA模型,BA模型解釋了域間系統(tǒng)的節(jié)點(diǎn)度符合冪法則分布的現(xiàn)象。
以上模型大多未考慮現(xiàn)實(shí)網(wǎng)絡(luò)中信息交互的有向性、節(jié)點(diǎn)的動(dòng)態(tài)加入和離開(kāi),以及節(jié)點(diǎn)的重要程度和節(jié)點(diǎn)間的聯(lián)系強(qiáng)度,存在一定的缺陷。同時(shí),移動(dòng)網(wǎng)絡(luò)的結(jié)構(gòu)變化很快,限制了對(duì)移動(dòng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的確定。雖然可以知道其大致特征,但無(wú)法構(gòu)造詳盡拓?fù)鋱D。因此,本文在隨機(jī)游走理論的基礎(chǔ)上,結(jié)合PageRank算法和移動(dòng)網(wǎng)絡(luò)所具有的現(xiàn)實(shí)特點(diǎn)對(duì)移動(dòng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行模型抽象,從而更真實(shí)地反映用戶(hù)在移動(dòng)社交網(wǎng)絡(luò)中的行為規(guī)律。
2 隨機(jī)游走理論和PageRank算法
2.1 隨機(jī)游走理論
隨機(jī)游走[7]是一種數(shù)學(xué)統(tǒng)計(jì)模型,它由一連串的軌跡所組成,其中每一次都是隨機(jī)的。在給定當(dāng)前知識(shí)或信息的情況下,只有當(dāng)前的狀態(tài)用來(lái)預(yù)測(cè)將來(lái),過(guò)去(即當(dāng)前以前的歷史狀態(tài))對(duì)于預(yù)測(cè)將來(lái)(即當(dāng)前以后的未來(lái)狀態(tài))是無(wú)關(guān)的。
在隨機(jī)游走理論中,單個(gè)的隨機(jī)事件不可預(yù)測(cè),但隨機(jī)大量的群體行為卻是精確可知的。隨機(jī)性造成了低尺度下的差異性,但在高尺度下又表現(xiàn)為相似性。利用隨機(jī)游走理論的這一特性,可以較準(zhǔn)確地預(yù)測(cè)移動(dòng)社交網(wǎng)絡(luò)中用戶(hù)行為在當(dāng)前狀態(tài)下的下一時(shí)刻狀態(tài)。
2.2 PageRank算法
PageRank算法[8-9]可以看作是隨機(jī)游走模型的一個(gè)實(shí)例,基本思想主要來(lái)自傳統(tǒng)文獻(xiàn)計(jì)量學(xué)中的文獻(xiàn)引文分析,即一篇文獻(xiàn)的質(zhì)量和重要性可以通過(guò)其他文獻(xiàn)對(duì)其引用的數(shù)量和引文質(zhì)量來(lái)衡量。也就是說(shuō),一篇文獻(xiàn)被其他文獻(xiàn)引用越多,并且引用它的文獻(xiàn)的質(zhì)量越高,則該文獻(xiàn)本身就很重要。
PageRank算法的簡(jiǎn)單描述如下:
其中,每個(gè)網(wǎng)頁(yè)的pr值等于所有指向該網(wǎng)頁(yè)的pr值貢獻(xiàn)度之和;ε是阻尼常數(shù)因子,一般取0.85;N為網(wǎng)頁(yè)總數(shù);IN(i)為所有指向i網(wǎng)頁(yè)的集合;OUT(r)為網(wǎng)頁(yè)r出鏈的集合。每個(gè)網(wǎng)頁(yè)的初始值為1/N,每一輪為每個(gè)網(wǎng)頁(yè)計(jì)算出pr值以后,下一輪用上一輪的值。
3 拓?fù)淠Ｐ?/h2>
3.1 模型簡(jiǎn)介
為使本文構(gòu)建的模型更加完善,貼近現(xiàn)實(shí)網(wǎng)絡(luò),在現(xiàn)實(shí)移動(dòng)社交網(wǎng)絡(luò)具有有向性和節(jié)點(diǎn)不同的重要程度特點(diǎn)的基礎(chǔ)上重點(diǎn)突出網(wǎng)絡(luò)的動(dòng)態(tài)性特征。移動(dòng)社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在每一時(shí)步都可能發(fā)生變化,將每?jī)蓵r(shí)步之間的拓?fù)浣Y(jié)構(gòu)用一個(gè)概率過(guò)渡矩陣聯(lián)系起來(lái),當(dāng)前時(shí)步的邊存在概率矩陣由上一時(shí)步邊存在概率矩陣和過(guò)渡矩陣得到,同時(shí)每一時(shí)步增加一個(gè)節(jié)點(diǎn)并驗(yàn)證是否有離開(kāi)的節(jié)點(diǎn)直至網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為1 000。為此,本文構(gòu)造了4種初始網(wǎng)絡(luò)觀(guān)察對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)生長(zhǎng)演化產(chǎn)生的影響。在所構(gòu)建的拓?fù)淠Ｐ椭?每個(gè)節(jié)點(diǎn)代表移動(dòng)網(wǎng)絡(luò)中的一個(gè)用戶(hù),節(jié)點(diǎn)間的有向邊表示這兩個(gè)節(jié)點(diǎn)所代表的用戶(hù)之間存在信息傳遞。節(jié)點(diǎn)間有向邊的邊存在概率越大,表明2個(gè)節(jié)點(diǎn)間信息傳遞的可能性就越大。模型中的節(jié)點(diǎn)可能是信息的接收者,也可能是信息的傳遞者,或者兼具這2種角色。
3.2 模型構(gòu)建過(guò)程
模型構(gòu)建過(guò)程如下:
(1)初始化
假設(shè)初始網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為n0,本文將初始網(wǎng)絡(luò)分為4種情況[10]:隨機(jī)網(wǎng)絡(luò),環(huán)形網(wǎng)絡(luò),星形網(wǎng)絡(luò),全耦合網(wǎng)絡(luò)。
根據(jù)初始網(wǎng)絡(luò)產(chǎn)生邊存在矩陣G0如下:
(2)模型生長(zhǎng)演化
Step 1 求概率過(guò)渡矩陣。PageRank公式中的阻尼因子ε來(lái)于隨機(jī)沖浪模型,然而在節(jié)點(diǎn)的拓?fù)溥B接中并不適宜,因此,改進(jìn)的PageRank算法[11]如式(3)所示,使其更符合于求各節(jié)點(diǎn)的勢(shì):
將任意2個(gè)節(jié)點(diǎn)i,j的過(guò)渡概率表示如下:
得到概率過(guò)渡矩陣:
Step 2 求下一時(shí)步邊存在概率矩陣。因?yàn)殡S機(jī)游走理論具有當(dāng)前狀態(tài)的變化僅與它前一個(gè)時(shí)刻的狀態(tài)有關(guān),而與前面其他時(shí)刻的狀態(tài)無(wú)關(guān)這一特性,所以可以用上一時(shí)步的邊存在概率矩陣和概率過(guò)渡矩陣得到邊存在概率矩陣:
Step 3 求增加一個(gè)節(jié)點(diǎn)后邊存在概率矩陣。每一時(shí)步增加一個(gè)新的節(jié)點(diǎn),直到網(wǎng)絡(luò)規(guī)模為1 000。加入的新節(jié)點(diǎn)的s值、加入的新節(jié)點(diǎn)與任一舊節(jié)點(diǎn)之間進(jìn)行互相連接的概率均為 1/Nt,在式(6)的基礎(chǔ)上得到當(dāng)前狀態(tài)邊存在概率矩陣:
Step 4 得到當(dāng)前邊存在矩陣如下:
Step 5 刪除節(jié)點(diǎn)。由于現(xiàn)實(shí)移動(dòng)網(wǎng)絡(luò)中人類(lèi)的移動(dòng)具有隨機(jī)性,在不斷有新節(jié)點(diǎn)加入的同時(shí)也會(huì)有舊節(jié)點(diǎn)隨機(jī)離開(kāi),因此在求得的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中,將沒(méi)有與任何節(jié)點(diǎn)相連同時(shí)也沒(méi)有任何節(jié)點(diǎn)與其相連的節(jié)點(diǎn)看作是已離開(kāi)的節(jié)點(diǎn),并將其刪除,即在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中滿(mǎn)足下列條件的節(jié)點(diǎn)刪除:
Step 6 返回Step 1。
3.3 模型分析
提出的模型借鑒PageRank算法,將拓?fù)淠Ｐ椭袆?shì)小于α的節(jié)點(diǎn)稱(chēng)為普通節(jié)點(diǎn),勢(shì)大于α的節(jié)點(diǎn)稱(chēng)為關(guān)鍵節(jié)點(diǎn)[12]。當(dāng)一個(gè)節(jié)點(diǎn)連接到另一節(jié)點(diǎn)時(shí),它會(huì)向這個(gè)被相連的節(jié)點(diǎn)進(jìn)行一次“投票”,節(jié)點(diǎn)得到的“票數(shù)”越多,其越重要,同時(shí)它投出的票也越重要。換句話(huà)說(shuō),一個(gè)與很多節(jié)點(diǎn)相連的節(jié)點(diǎn)被視為重要節(jié)點(diǎn),一個(gè)被很多重要節(jié)點(diǎn)連接的節(jié)點(diǎn)是一個(gè)核心節(jié)點(diǎn)。聯(lián)系實(shí)際移動(dòng)社交網(wǎng)絡(luò)可以很容易想到,核心節(jié)點(diǎn)往往是這個(gè)移動(dòng)社交網(wǎng)絡(luò)中的領(lǐng)導(dǎo)人物,核心節(jié)點(diǎn)之間的聯(lián)系狀態(tài)在下一時(shí)步發(fā)生變化的可能性很小,而普通節(jié)點(diǎn)之間的聯(lián)系狀態(tài)在下一時(shí)步很容易發(fā)生變化,核心節(jié)點(diǎn)與普通節(jié)點(diǎn)之間的聯(lián)系狀態(tài)在下一時(shí)步發(fā)生變化的概率介于前2種情況之間。即核心節(jié)點(diǎn)間連接強(qiáng)度最強(qiáng),普通節(jié)點(diǎn)間連接強(qiáng)度最弱。另一方面,同時(shí)連接兩個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)個(gè)數(shù)越多,表明這兩個(gè)節(jié)點(diǎn)之間的關(guān)系越緊密。這些節(jié)點(diǎn)相當(dāng)于真實(shí)網(wǎng)絡(luò)中的中間人,可以把與之有聯(lián)系的一個(gè)用戶(hù)介紹給與之有聯(lián)系的另一個(gè)用戶(hù)使之產(chǎn)生信息傳遞。由于在一個(gè)隨機(jī)過(guò)程中,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化僅與它的前一個(gè)狀態(tài)有關(guān),而與它前面時(shí)刻的狀態(tài)無(wú)關(guān),因此在當(dāng)前狀態(tài)同時(shí)連接2個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)越多,在下一時(shí)刻這2個(gè)節(jié)點(diǎn)間失去聯(lián)系的可能性越小?；谝陨嫌^(guān)點(diǎn),模型在Step 1中利用改進(jìn)的PageRank算法求得當(dāng)前狀態(tài)到下一狀態(tài)的過(guò)渡概率,較真實(shí)地模擬了移動(dòng)社交網(wǎng)絡(luò)環(huán)境的拓?fù)渥兓?/p>
由模型構(gòu)建過(guò)程可以看出,本文在構(gòu)建模型時(shí)綜合考慮了節(jié)點(diǎn)的動(dòng)態(tài)性、信息傳遞的有向性和現(xiàn)實(shí)生活中普遍存在的朋友介紹現(xiàn)象對(duì)移動(dòng)社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響,并且通過(guò)引入外部參數(shù)d來(lái)調(diào)節(jié)節(jié)點(diǎn)的勢(shì)對(duì)拓?fù)浣Y(jié)構(gòu)的影響。由式(3)可以看出,通過(guò)調(diào)節(jié)參數(shù)d的值,直接影響節(jié)點(diǎn)勢(shì)的大小。節(jié)點(diǎn)勢(shì)的大小直接影響2個(gè)節(jié)點(diǎn)間過(guò)渡概率的大小。過(guò)渡概率的改變又將改變下一時(shí)步的邊存在概率,從而影響下一時(shí)步的邊存在矩陣。邊存在矩陣的變化使整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)的連接狀態(tài)發(fā)生改變,即節(jié)點(diǎn)的入度和出度發(fā)生變化,移動(dòng)拓?fù)浣Y(jié)構(gòu)的生長(zhǎng)演變隨之改變。
4 仿真實(shí)驗(yàn)
為了驗(yàn)證所構(gòu)建的網(wǎng)絡(luò)模型的有效性,本文分析了所生成網(wǎng)絡(luò)的入度、出度、勢(shì)和度-勢(shì)相關(guān)性等拓?fù)鋮?shù)。在仿真實(shí)驗(yàn)中,設(shè)定初始網(wǎng)絡(luò)規(guī)模n0= 5,最后生成的網(wǎng)絡(luò)規(guī)模為N=1 000。仿真實(shí)驗(yàn)得到的圖形均為無(wú)量綱的比率圖。
實(shí)驗(yàn)中,隨機(jī)網(wǎng)絡(luò)的初始邊存在概率矩陣是一個(gè)隨機(jī)生成的邊存在概率在0～1之間的矩陣;因?yàn)榄h(huán)形、星形、全耦合網(wǎng)絡(luò)的初始邊存在矩陣是已知的,所以實(shí)驗(yàn)假設(shè)與存在的邊相對(duì)應(yīng)的邊存在概率是通過(guò)隨機(jī)數(shù)產(chǎn)生法得到的0.5～1之間的隨機(jī)數(shù),其他節(jié)點(diǎn)之間的邊存在概率是0～0.5之間的隨機(jī)數(shù),當(dāng)然,與自身相連的邊的邊存在概率為0。
4.1 節(jié)點(diǎn)度分布
仿真實(shí)驗(yàn)對(duì)比了4種初始網(wǎng)絡(luò)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)入度、出度分布的影響,以及控制參數(shù)d對(duì)節(jié)點(diǎn)入度、出度分布的影響。從圖1和圖2中可以看出,對(duì)應(yīng)于不同的d值,同一初始網(wǎng)絡(luò)的節(jié)點(diǎn)入度、出度分布具有較大差異,但均符合冪律分布[13];在相同的d值下,不同初始網(wǎng)絡(luò)的節(jié)點(diǎn)入度、出度分布也不相同。然而,對(duì)同一初始網(wǎng)絡(luò)而言,隨著d值的變化,隨機(jī)初始網(wǎng)絡(luò)的度分布變化程度最大,環(huán)形初始網(wǎng)絡(luò)的變化程度最小;對(duì)不同的初始網(wǎng)絡(luò)而言,d=2.0時(shí)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的生長(zhǎng)演化影響最小,d=3.0時(shí)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)生長(zhǎng)演化影響最大。由此可知,不同的初始網(wǎng)絡(luò)及控制參數(shù)d對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的生長(zhǎng)有一定的影響。
通過(guò)對(duì)比每個(gè)初始網(wǎng)絡(luò)的節(jié)點(diǎn)入度圖和出度圖可以發(fā)現(xiàn),在不同的d值影響下,拓?fù)渚W(wǎng)絡(luò)節(jié)點(diǎn)入度和出度的變化幾乎是同步的,入度大出度大,入度小出度小。隨機(jī)初始網(wǎng)絡(luò)、環(huán)形初始網(wǎng)絡(luò)和全耦合初始網(wǎng)絡(luò)中均是d=2.5時(shí),節(jié)點(diǎn)的入度和出度值最大,拓?fù)渚W(wǎng)絡(luò)間的聯(lián)系最緊密;對(duì)于星形初始網(wǎng)絡(luò), d=2.5和d=3.0時(shí),節(jié)點(diǎn)的入度、出度值相差不明顯。由此可以看出,不同的初始網(wǎng)絡(luò)在相同d值下的聯(lián)系緊密程度不同。
圖1 4種初始網(wǎng)絡(luò)下的節(jié)點(diǎn)入度分布情況
圖2 4種初始網(wǎng)絡(luò)下的節(jié)點(diǎn)出度分布情況
4.2 節(jié)點(diǎn)勢(shì)分布
由圖3可以看出,對(duì)同一初始網(wǎng)絡(luò),控制參數(shù)d對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的勢(shì)也具有較明顯影響。具體而言, d值對(duì)全耦合初始網(wǎng)絡(luò)節(jié)點(diǎn)勢(shì)的影響最明顯,對(duì)環(huán)形和星形初始網(wǎng)絡(luò)的影響不是很大。隨機(jī)初始網(wǎng)絡(luò)和全耦合初始網(wǎng)絡(luò)中,d=3.0時(shí)節(jié)點(diǎn)的勢(shì)最大,但是全耦合初始網(wǎng)絡(luò)中節(jié)點(diǎn)勢(shì)的值波動(dòng)較大;環(huán)形和星形初始網(wǎng)絡(luò)d分別為2.5和2.0時(shí)節(jié)點(diǎn)的勢(shì)最大。
圖3 4種初始網(wǎng)絡(luò)下的節(jié)點(diǎn)勢(shì)分布情況
4.3 度-勢(shì)相關(guān)性
本文以d=2.5為例,對(duì)4種初始網(wǎng)絡(luò)度-勢(shì)相關(guān)性進(jìn)行分析。文獻(xiàn)[14]在研究了大量實(shí)際網(wǎng)絡(luò)數(shù)據(jù)集的基礎(chǔ)上,發(fā)現(xiàn)加權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)的度值與勢(shì)值是存在冪律關(guān)系的,若用s表示節(jié)點(diǎn)的勢(shì),k表示節(jié)點(diǎn)的度,則節(jié)點(diǎn)度值與勢(shì)值的冪律相關(guān)性可以表示為:
通過(guò)仿真實(shí)驗(yàn)得到4種初始網(wǎng)絡(luò)的有關(guān)節(jié)點(diǎn)的入度值、出度值與勢(shì)值,并對(duì)其進(jìn)行線(xiàn)性擬合后發(fā)現(xiàn),節(jié)點(diǎn)入度值、出度值與勢(shì)值之間存在冪律關(guān)系,如圖4所示。本文選取具有代表性的星形和全耦合初始網(wǎng)絡(luò),圖4(a)、圖4(b)分別是星形初始網(wǎng)絡(luò)節(jié)點(diǎn)入度、出度與勢(shì)的相關(guān)性,其斜率分別為0.75和0.78;圖4(c)、圖4(d)分別是全耦合初始網(wǎng)絡(luò)節(jié)點(diǎn)入度、出度與勢(shì)的相關(guān)性,其斜率分別為0.90和0.90。另外,隨機(jī)初始網(wǎng)絡(luò)節(jié)點(diǎn)入度、出度值與勢(shì)值擬合后得到的直線(xiàn)斜率分別為0.72和0.73;環(huán)形初始網(wǎng)絡(luò)節(jié)點(diǎn)入度、出度值與勢(shì)值擬合后得到的直線(xiàn)斜率分別為0.76和0.74。
圖4 星形和全耦合網(wǎng)絡(luò)的度-勢(shì)相關(guān)性
5 結(jié)束語(yǔ)
本文結(jié)合現(xiàn)實(shí)生活中信息傳播所遵循的規(guī)律,提出通過(guò)加權(quán)有向拓?fù)淠Ｐ湍M社會(huì)交往的動(dòng)態(tài)性。使用PageRank公式求節(jié)點(diǎn)的勢(shì)將節(jié)點(diǎn)分為關(guān)鍵節(jié)點(diǎn)和普通節(jié)點(diǎn),引入概率過(guò)渡矩陣,利用隨機(jī)游走理論中的當(dāng)前狀態(tài)只與其上一時(shí)刻的狀態(tài)有關(guān)而與其他時(shí)刻狀態(tài)無(wú)關(guān)的特性,得到社交網(wǎng)絡(luò)在每時(shí)步的生長(zhǎng)演化拓?fù)浣Y(jié)構(gòu)直至網(wǎng)絡(luò)規(guī)模N=1 000。仿真結(jié)果表明,在不同的初始網(wǎng)絡(luò)條件下,該模型所生成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的入度、出度、勢(shì)分布以及度-勢(shì)相關(guān)性有較明顯差異,但又具有一定的相似性。下一步將對(duì)網(wǎng)絡(luò)拓?fù)涞木垲?lèi)系數(shù)、核數(shù)和基尼系數(shù)等進(jìn)行仿真研究,檢驗(yàn)?zāi)Ｐ褪欠衲軌蝮w現(xiàn)移動(dòng)社交網(wǎng)絡(luò)的聚集特性、層次性和異質(zhì)性等特點(diǎn)。
[1] 劉衍珩,李飛鵬,孫 鑫,等.基于信息傳播的社交網(wǎng)絡(luò)拓?fù)淠Ｐ蚚J].通信學(xué)報(bào),2013,34(4):5-13.
[2] Waxman B M.Routing of Multiple Connections[J]. IEEE Journal on Selected Areas in Communication, 1998,6(9):1617-1622.
[3] Zegura E W,Calvert K L,Bhattacharjee S.How to Model an Internetwork[C]//Proceedings of the 15th Annual Joint Conference of the IEEE Computer Societies.San Fransisco,USA:IEEE Press,1996:594-602.
[4] Watts D J,Strogatz S H.Collective Dynamicsof‘Small-world' Networks[J].Nature,1998,393 (6684):440-442.
[5] Faloutsos M,Faloutsos P,Faloutsos C.On Power-law Relationships of the Internet Topology[C]//Proceedings of SIGCOMM'99.[S.l.]:ACM Press,1999:251-262.
[6] Barabasi A,Albert R.Emergence of Scaling in Random Networks[J].Science,1999,286(5439):509-512.
[7] 徐曉華.圖上的隨機(jī)游走學(xué)習(xí)[D].南京:南京航空航天大學(xué),2008.
[8] 趙 國(guó),宋建成.Google搜索引擎的數(shù)學(xué)模型及其應(yīng)用[J].西南民族大學(xué)學(xué)報(bào),2010,36(3):160-166.
[9] 黃德才,戚華春.PageRank算法研究[J].計(jì)算機(jī)工程, 2006,32(4):151-152,168.
[10] 楊 莉.網(wǎng)絡(luò)拓?fù)淠Ｐ偷难芯縖J].湖北第二師范學(xué)院學(xué)報(bào),2008,25(8):5-9.
[11] 王德廣,周志剛,梁 旭.PageRank算法的分析及改進(jìn)[J].計(jì)算機(jī)工程,2010,36(22):297-299.
[12] 劉衍珩,孫 鑫,王 健,等.基于用戶(hù)行為和網(wǎng)絡(luò)拓?fù)涞?Email蠕蟲(chóng)傳播[J].吉林大學(xué)學(xué)報(bào),2010,40 (6):196-203.
[13] 周 苗,楊家海,劉洪波.Internet網(wǎng)絡(luò)拓?fù)浣J].軟件學(xué)報(bào),2009,20(1):113-127.
[14] Barrat A,Barthelemy M,Pastor-Satorras R.The Architecture ofComplexWeighted Networks[J]. Proceedings of the National Academy of Sciences of the United States of America,2004,101(11):3747-3752.
編輯 金胡考
A Dynamic Mobile Social Network Topology Model
TIAN Xue-ying1a,1b,LIU Yan-heng1a,1b,SUN Xin2,WANG Ya-zhou1a,LIN Jia-jia1a
(1a.College of Computer Science and Technology;1b.Key Laboratory of Symbolic Computation and Knowledge Engineering,Ministry of Education,Jilin University,Changchun 130012,China;
2.College of Information Science and Engineering,Ocean University of China,Qingdao 266100,China)
A topological model that can describe the mobile social network accurately is proposed based on four initial networks considering the dynamic of social network,the different importance of users and the direction of information interaction.Random walking theory and improved PageRank algorithm are adopted,and transition probability is introduced to associate the network topological structure between two time-steps.Firstly,PageRank algorithm is used to obtain the strength of the nodes in order to get the probability transition matrix.Then random walking theory is used to get the current time-step edge existence probability matrix based on the last time-step edge existence probability matrix and the probability transition matrix.During each time-step,a node is added and it is checked if there is any departure node.Finally,simulation model is used to simulate the four initial networks in in-degree,out-degree,strength distribution and the correlation between degree and strength.The results indicate that the four initial networks'in-degree,out-degree,strength distribution and the correlation between degree and strength show obvious power-law character.It shows that the random walking theory and improved PageRank algorithm can describe the mobile social network better,which is of certain practical significance.
socialnetwork;network topology;random walking;PageRank algorithm;transition probability; simulation model
1000-3428(2014)09-0124-06
A
TP393
10.3969/j.issn.1000-3428.2014.09.025
國(guó)家自然科學(xué)基金資助項(xiàng)目(60973136,61073164);吉林省科技發(fā)展計(jì)劃青年科研基金資助項(xiàng)目(201101033);吉林大學(xué)國(guó)家級(jí)創(chuàng)新基金資助項(xiàng)目(2012A53143)。
田雪穎(1990-),女,碩士研究生,主研方向:網(wǎng)絡(luò)拓?fù)浣?網(wǎng)絡(luò)安全;劉衍珩,教授、博士、博士生導(dǎo)師;孫 鑫,博士;王亞洲,學(xué)士;林佳佳,碩士研究生。
2013-05-17
2013-08-26E-mail:txy_0902@126.com
猜你喜歡
一半模型童話(huà)王國(guó)·奇妙邏輯推理(2024年5期)2024-06-19 16:03:38 一種去中心化的域名服務(wù)本地化模型網(wǎng)絡(luò)安全與數(shù)據(jù)管理(2022年1期)2022-08-29 03:15:20 適用于BDS-3 PPP的隨機(jī)模型導(dǎo)航定位學(xué)報(bào)(2022年4期)2022-08-15 08:27:00 提煉模型 突破難點(diǎn)中學(xué)生數(shù)理化·中考版(2022年8期)2022-06-14 06:55:24 函數(shù)模型及應(yīng)用新世紀(jì)智能(數(shù)學(xué)備考)(2021年9期)2021-11-24 01:14:36 p150Glued在帕金森病模型中的表達(dá)及分布成都醫(yī)學(xué)院學(xué)報(bào)(2021年2期)2021-07-19 08:35:14 函數(shù)模型及應(yīng)用新世紀(jì)智能(數(shù)學(xué)備考)(2020年9期)2021-01-04 00:25:14 重要模型『一線(xiàn)三等角』中學(xué)生數(shù)理化·七年級(jí)數(shù)學(xué)人教版(2020年10期)2020-11-26 08:24:50 重尾非線(xiàn)性自回歸模型自加權(quán)M-估計(jì)的漸近分布數(shù)學(xué)物理學(xué)報(bào)(2020年2期)2020-06-02 11:29:24 3D打印中的模型分割與打包光學(xué)精密工程(2016年6期)2016-11-07 09:07:19
田雪穎,劉衍珩,孫 鑫,王亞洲,林佳佳
(1.吉林大學(xué)a.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;b.符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室,長(zhǎng)春130012; 2.中國(guó)海洋大學(xué)信息科學(xué)與工程學(xué)院,山東青島266100)
一種動(dòng)態(tài)的移動(dòng)社交網(wǎng)絡(luò)拓?fù)淠Ｐ?/p>
田雪穎1a,1b,劉衍珩1a,1b,孫 鑫2,王亞洲1a,林佳佳1a
(1.吉林大學(xué)a.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;b.符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室,長(zhǎng)春130012; 2.中國(guó)海洋大學(xué)信息科學(xué)與工程學(xué)院,山東青島266100)
針對(duì)移動(dòng)社交網(wǎng)絡(luò)的動(dòng)態(tài)性、用戶(hù)不同重要性和信息交互有向性,基于4種初始網(wǎng)絡(luò)提出能準(zhǔn)確描述移動(dòng)社交網(wǎng)絡(luò)結(jié)構(gòu)的拓?fù)淠Ｐ?。采用隨機(jī)游走理論和改進(jìn)的PageRank算法,引入過(guò)渡概率使每?jī)蓵r(shí)步之間的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相互聯(lián)系。通過(guò)PageRank算法得到節(jié)點(diǎn)的勢(shì),進(jìn)而求出概率過(guò)渡矩陣,利用隨機(jī)游走理論由上一時(shí)步邊存在概率矩陣和概率過(guò)渡矩陣得到當(dāng)前時(shí)步邊存在概率矩陣,每一時(shí)步動(dòng)態(tài)地增加一個(gè)節(jié)點(diǎn)并檢驗(yàn)是否有離開(kāi)的節(jié)點(diǎn)。仿真結(jié)果顯示,該模型在4種初始網(wǎng)絡(luò)下得到的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),入度、出度、勢(shì)分布以及度-勢(shì)相關(guān)性均具有明顯冪律特性,表明隨機(jī)游走理論和改進(jìn)的PageRank算法能較準(zhǔn)確描述移動(dòng)社交網(wǎng)絡(luò),具有一定的實(shí)踐意義。
社交網(wǎng)絡(luò);網(wǎng)絡(luò)拓?fù)?隨機(jī)游走;PageRank算法;過(guò)渡概率;仿真模型
1 概述
近年來(lái),隨著無(wú)線(xiàn)通信技術(shù)的飛速發(fā)展,無(wú)線(xiàn)網(wǎng)絡(luò)已經(jīng)廣泛應(yīng)用于我國(guó)的廣大地區(qū),尤其是在經(jīng)濟(jì)較為發(fā)達(dá)的城市。Wifi是無(wú)線(xiàn)局域網(wǎng)的重要部分,它可以最大限度地滿(mǎn)足個(gè)人、家庭和小型辦公系統(tǒng)對(duì)于移動(dòng)網(wǎng)絡(luò)連接的需求。手機(jī)、電腦、iPad無(wú)疑成了人們?cè)谝苿?dòng)網(wǎng)絡(luò)中進(jìn)行信息交互的主要工具。人們上班、購(gòu)物、出游等社交行為賦予了移動(dòng)自組網(wǎng)絡(luò)動(dòng)態(tài)性的特征,使其具有社會(huì)流動(dòng)性。因此,掌握移動(dòng)社交網(wǎng)絡(luò)的行為特征,分析移動(dòng)社交網(wǎng)絡(luò)的動(dòng)態(tài)性和規(guī)律性,具有重要的理論價(jià)值和現(xiàn)實(shí)意義。
由于移動(dòng)網(wǎng)絡(luò)具有規(guī)模大、增長(zhǎng)快的特點(diǎn),因此很難把它作為實(shí)驗(yàn)對(duì)象來(lái)進(jìn)行研究和分析[1]。對(duì)移動(dòng)網(wǎng)絡(luò)所引發(fā)的一系列網(wǎng)絡(luò)問(wèn)題的研究往往只能基于拓?fù)淠Ｐ瓦M(jìn)行。網(wǎng)絡(luò)拓?fù)淠Ｐ褪菍?duì)真實(shí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的模擬,利用拓?fù)淠Ｐ偷姆绞窖芯恳苿?dòng)網(wǎng)絡(luò)中用戶(hù)行為的方法由來(lái)已久。文獻(xiàn)[2]根據(jù)現(xiàn)實(shí)網(wǎng)絡(luò)中用戶(hù)行為的隨機(jī)性提出了經(jīng)典的Waxman隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ?文獻(xiàn)[3]基于邊概率隨節(jié)點(diǎn)距離增加而呈指數(shù)減少的思想提出了另外2種隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ?指數(shù)模型和位置模型;文獻(xiàn)[4]提出了“小世界網(wǎng)絡(luò)”模型,即WS模型,該模型的主要貢獻(xiàn)是提出了介于規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)之間的小世界網(wǎng)絡(luò),并能通過(guò)重連概率p進(jìn)行調(diào)節(jié),從而可使網(wǎng)絡(luò)結(jié)構(gòu)在規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)之間轉(zhuǎn)化;文獻(xiàn)[5]在研究域間系統(tǒng)時(shí)發(fā)現(xiàn)節(jié)點(diǎn)度的冪律法則,無(wú)標(biāo)度網(wǎng)絡(luò)由此成為了研究者關(guān)注的主要對(duì)象;文獻(xiàn)[6]通過(guò)向一個(gè)簡(jiǎn)單的模型中動(dòng)態(tài)地添加新節(jié)點(diǎn)和新連接模擬Internet網(wǎng)絡(luò)發(fā)展過(guò)程來(lái)生成符合冪法則的模型,稱(chēng)之為BA模型,BA模型解釋了域間系統(tǒng)的節(jié)點(diǎn)度符合冪法則分布的現(xiàn)象。
以上模型大多未考慮現(xiàn)實(shí)網(wǎng)絡(luò)中信息交互的有向性、節(jié)點(diǎn)的動(dòng)態(tài)加入和離開(kāi),以及節(jié)點(diǎn)的重要程度和節(jié)點(diǎn)間的聯(lián)系強(qiáng)度,存在一定的缺陷。同時(shí),移動(dòng)網(wǎng)絡(luò)的結(jié)構(gòu)變化很快,限制了對(duì)移動(dòng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的確定。雖然可以知道其大致特征,但無(wú)法構(gòu)造詳盡拓?fù)鋱D。因此,本文在隨機(jī)游走理論的基礎(chǔ)上,結(jié)合PageRank算法和移動(dòng)網(wǎng)絡(luò)所具有的現(xiàn)實(shí)特點(diǎn)對(duì)移動(dòng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行模型抽象,從而更真實(shí)地反映用戶(hù)在移動(dòng)社交網(wǎng)絡(luò)中的行為規(guī)律。
2 隨機(jī)游走理論和PageRank算法
2.1 隨機(jī)游走理論
隨機(jī)游走[7]是一種數(shù)學(xué)統(tǒng)計(jì)模型,它由一連串的軌跡所組成,其中每一次都是隨機(jī)的。在給定當(dāng)前知識(shí)或信息的情況下,只有當(dāng)前的狀態(tài)用來(lái)預(yù)測(cè)將來(lái),過(guò)去(即當(dāng)前以前的歷史狀態(tài))對(duì)于預(yù)測(cè)將來(lái)(即當(dāng)前以后的未來(lái)狀態(tài))是無(wú)關(guān)的。
在隨機(jī)游走理論中,單個(gè)的隨機(jī)事件不可預(yù)測(cè),但隨機(jī)大量的群體行為卻是精確可知的。隨機(jī)性造成了低尺度下的差異性,但在高尺度下又表現(xiàn)為相似性。利用隨機(jī)游走理論的這一特性,可以較準(zhǔn)確地預(yù)測(cè)移動(dòng)社交網(wǎng)絡(luò)中用戶(hù)行為在當(dāng)前狀態(tài)下的下一時(shí)刻狀態(tài)。
2.2 PageRank算法
PageRank算法[8-9]可以看作是隨機(jī)游走模型的一個(gè)實(shí)例,基本思想主要來(lái)自傳統(tǒng)文獻(xiàn)計(jì)量學(xué)中的文獻(xiàn)引文分析,即一篇文獻(xiàn)的質(zhì)量和重要性可以通過(guò)其他文獻(xiàn)對(duì)其引用的數(shù)量和引文質(zhì)量來(lái)衡量。也就是說(shuō),一篇文獻(xiàn)被其他文獻(xiàn)引用越多,并且引用它的文獻(xiàn)的質(zhì)量越高,則該文獻(xiàn)本身就很重要。
PageRank算法的簡(jiǎn)單描述如下:
其中,每個(gè)網(wǎng)頁(yè)的pr值等于所有指向該網(wǎng)頁(yè)的pr值貢獻(xiàn)度之和;ε是阻尼常數(shù)因子,一般取0.85;N為網(wǎng)頁(yè)總數(shù);IN(i)為所有指向i網(wǎng)頁(yè)的集合;OUT(r)為網(wǎng)頁(yè)r出鏈的集合。每個(gè)網(wǎng)頁(yè)的初始值為1/N,每一輪為每個(gè)網(wǎng)頁(yè)計(jì)算出pr值以后,下一輪用上一輪的值。
3 拓?fù)淠Ｐ?/h2>
3.1 模型簡(jiǎn)介
為使本文構(gòu)建的模型更加完善,貼近現(xiàn)實(shí)網(wǎng)絡(luò),在現(xiàn)實(shí)移動(dòng)社交網(wǎng)絡(luò)具有有向性和節(jié)點(diǎn)不同的重要程度特點(diǎn)的基礎(chǔ)上重點(diǎn)突出網(wǎng)絡(luò)的動(dòng)態(tài)性特征。移動(dòng)社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在每一時(shí)步都可能發(fā)生變化,將每?jī)蓵r(shí)步之間的拓?fù)浣Y(jié)構(gòu)用一個(gè)概率過(guò)渡矩陣聯(lián)系起來(lái),當(dāng)前時(shí)步的邊存在概率矩陣由上一時(shí)步邊存在概率矩陣和過(guò)渡矩陣得到,同時(shí)每一時(shí)步增加一個(gè)節(jié)點(diǎn)并驗(yàn)證是否有離開(kāi)的節(jié)點(diǎn)直至網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為1 000。為此,本文構(gòu)造了4種初始網(wǎng)絡(luò)觀(guān)察對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)生長(zhǎng)演化產(chǎn)生的影響。在所構(gòu)建的拓?fù)淠Ｐ椭?每個(gè)節(jié)點(diǎn)代表移動(dòng)網(wǎng)絡(luò)中的一個(gè)用戶(hù),節(jié)點(diǎn)間的有向邊表示這兩個(gè)節(jié)點(diǎn)所代表的用戶(hù)之間存在信息傳遞。節(jié)點(diǎn)間有向邊的邊存在概率越大,表明2個(gè)節(jié)點(diǎn)間信息傳遞的可能性就越大。模型中的節(jié)點(diǎn)可能是信息的接收者,也可能是信息的傳遞者,或者兼具這2種角色。
3.2 模型構(gòu)建過(guò)程
模型構(gòu)建過(guò)程如下:
(1)初始化
假設(shè)初始網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為n0,本文將初始網(wǎng)絡(luò)分為4種情況[10]:隨機(jī)網(wǎng)絡(luò),環(huán)形網(wǎng)絡(luò),星形網(wǎng)絡(luò),全耦合網(wǎng)絡(luò)。
根據(jù)初始網(wǎng)絡(luò)產(chǎn)生邊存在矩陣G0如下:
(2)模型生長(zhǎng)演化
Step 1 求概率過(guò)渡矩陣。PageRank公式中的阻尼因子ε來(lái)于隨機(jī)沖浪模型,然而在節(jié)點(diǎn)的拓?fù)溥B接中并不適宜,因此,改進(jìn)的PageRank算法[11]如式(3)所示,使其更符合于求各節(jié)點(diǎn)的勢(shì):
將任意2個(gè)節(jié)點(diǎn)i,j的過(guò)渡概率表示如下:
得到概率過(guò)渡矩陣:
Step 2 求下一時(shí)步邊存在概率矩陣。因?yàn)殡S機(jī)游走理論具有當(dāng)前狀態(tài)的變化僅與它前一個(gè)時(shí)刻的狀態(tài)有關(guān),而與前面其他時(shí)刻的狀態(tài)無(wú)關(guān)這一特性,所以可以用上一時(shí)步的邊存在概率矩陣和概率過(guò)渡矩陣得到邊存在概率矩陣:
Step 3 求增加一個(gè)節(jié)點(diǎn)后邊存在概率矩陣。每一時(shí)步增加一個(gè)新的節(jié)點(diǎn),直到網(wǎng)絡(luò)規(guī)模為1 000。加入的新節(jié)點(diǎn)的s值、加入的新節(jié)點(diǎn)與任一舊節(jié)點(diǎn)之間進(jìn)行互相連接的概率均為 1/Nt,在式(6)的基礎(chǔ)上得到當(dāng)前狀態(tài)邊存在概率矩陣:
Step 4 得到當(dāng)前邊存在矩陣如下:
Step 5 刪除節(jié)點(diǎn)。由于現(xiàn)實(shí)移動(dòng)網(wǎng)絡(luò)中人類(lèi)的移動(dòng)具有隨機(jī)性,在不斷有新節(jié)點(diǎn)加入的同時(shí)也會(huì)有舊節(jié)點(diǎn)隨機(jī)離開(kāi),因此在求得的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中,將沒(méi)有與任何節(jié)點(diǎn)相連同時(shí)也沒(méi)有任何節(jié)點(diǎn)與其相連的節(jié)點(diǎn)看作是已離開(kāi)的節(jié)點(diǎn),并將其刪除,即在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中滿(mǎn)足下列條件的節(jié)點(diǎn)刪除:
Step 6 返回Step 1。
3.3 模型分析
提出的模型借鑒PageRank算法,將拓?fù)淠Ｐ椭袆?shì)小于α的節(jié)點(diǎn)稱(chēng)為普通節(jié)點(diǎn),勢(shì)大于α的節(jié)點(diǎn)稱(chēng)為關(guān)鍵節(jié)點(diǎn)[12]。當(dāng)一個(gè)節(jié)點(diǎn)連接到另一節(jié)點(diǎn)時(shí),它會(huì)向這個(gè)被相連的節(jié)點(diǎn)進(jìn)行一次“投票”,節(jié)點(diǎn)得到的“票數(shù)”越多,其越重要,同時(shí)它投出的票也越重要。換句話(huà)說(shuō),一個(gè)與很多節(jié)點(diǎn)相連的節(jié)點(diǎn)被視為重要節(jié)點(diǎn),一個(gè)被很多重要節(jié)點(diǎn)連接的節(jié)點(diǎn)是一個(gè)核心節(jié)點(diǎn)。聯(lián)系實(shí)際移動(dòng)社交網(wǎng)絡(luò)可以很容易想到,核心節(jié)點(diǎn)往往是這個(gè)移動(dòng)社交網(wǎng)絡(luò)中的領(lǐng)導(dǎo)人物,核心節(jié)點(diǎn)之間的聯(lián)系狀態(tài)在下一時(shí)步發(fā)生變化的可能性很小,而普通節(jié)點(diǎn)之間的聯(lián)系狀態(tài)在下一時(shí)步很容易發(fā)生變化,核心節(jié)點(diǎn)與普通節(jié)點(diǎn)之間的聯(lián)系狀態(tài)在下一時(shí)步發(fā)生變化的概率介于前2種情況之間。即核心節(jié)點(diǎn)間連接強(qiáng)度最強(qiáng),普通節(jié)點(diǎn)間連接強(qiáng)度最弱。另一方面,同時(shí)連接兩個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)個(gè)數(shù)越多,表明這兩個(gè)節(jié)點(diǎn)之間的關(guān)系越緊密。這些節(jié)點(diǎn)相當(dāng)于真實(shí)網(wǎng)絡(luò)中的中間人,可以把與之有聯(lián)系的一個(gè)用戶(hù)介紹給與之有聯(lián)系的另一個(gè)用戶(hù)使之產(chǎn)生信息傳遞。由于在一個(gè)隨機(jī)過(guò)程中,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化僅與它的前一個(gè)狀態(tài)有關(guān),而與它前面時(shí)刻的狀態(tài)無(wú)關(guān),因此在當(dāng)前狀態(tài)同時(shí)連接2個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)越多,在下一時(shí)刻這2個(gè)節(jié)點(diǎn)間失去聯(lián)系的可能性越小?；谝陨嫌^(guān)點(diǎn),模型在Step 1中利用改進(jìn)的PageRank算法求得當(dāng)前狀態(tài)到下一狀態(tài)的過(guò)渡概率,較真實(shí)地模擬了移動(dòng)社交網(wǎng)絡(luò)環(huán)境的拓?fù)渥兓?/p>
由模型構(gòu)建過(guò)程可以看出,本文在構(gòu)建模型時(shí)綜合考慮了節(jié)點(diǎn)的動(dòng)態(tài)性、信息傳遞的有向性和現(xiàn)實(shí)生活中普遍存在的朋友介紹現(xiàn)象對(duì)移動(dòng)社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響,并且通過(guò)引入外部參數(shù)d來(lái)調(diào)節(jié)節(jié)點(diǎn)的勢(shì)對(duì)拓?fù)浣Y(jié)構(gòu)的影響。由式(3)可以看出,通過(guò)調(diào)節(jié)參數(shù)d的值,直接影響節(jié)點(diǎn)勢(shì)的大小。節(jié)點(diǎn)勢(shì)的大小直接影響2個(gè)節(jié)點(diǎn)間過(guò)渡概率的大小。過(guò)渡概率的改變又將改變下一時(shí)步的邊存在概率,從而影響下一時(shí)步的邊存在矩陣。邊存在矩陣的變化使整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)的連接狀態(tài)發(fā)生改變,即節(jié)點(diǎn)的入度和出度發(fā)生變化,移動(dòng)拓?fù)浣Y(jié)構(gòu)的生長(zhǎng)演變隨之改變。
4 仿真實(shí)驗(yàn)
為了驗(yàn)證所構(gòu)建的網(wǎng)絡(luò)模型的有效性,本文分析了所生成網(wǎng)絡(luò)的入度、出度、勢(shì)和度-勢(shì)相關(guān)性等拓?fù)鋮?shù)。在仿真實(shí)驗(yàn)中,設(shè)定初始網(wǎng)絡(luò)規(guī)模n0= 5,最后生成的網(wǎng)絡(luò)規(guī)模為N=1 000。仿真實(shí)驗(yàn)得到的圖形均為無(wú)量綱的比率圖。
實(shí)驗(yàn)中,隨機(jī)網(wǎng)絡(luò)的初始邊存在概率矩陣是一個(gè)隨機(jī)生成的邊存在概率在0～1之間的矩陣;因?yàn)榄h(huán)形、星形、全耦合網(wǎng)絡(luò)的初始邊存在矩陣是已知的,所以實(shí)驗(yàn)假設(shè)與存在的邊相對(duì)應(yīng)的邊存在概率是通過(guò)隨機(jī)數(shù)產(chǎn)生法得到的0.5～1之間的隨機(jī)數(shù),其他節(jié)點(diǎn)之間的邊存在概率是0～0.5之間的隨機(jī)數(shù),當(dāng)然,與自身相連的邊的邊存在概率為0。
4.1 節(jié)點(diǎn)度分布
仿真實(shí)驗(yàn)對(duì)比了4種初始網(wǎng)絡(luò)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)入度、出度分布的影響,以及控制參數(shù)d對(duì)節(jié)點(diǎn)入度、出度分布的影響。從圖1和圖2中可以看出,對(duì)應(yīng)于不同的d值,同一初始網(wǎng)絡(luò)的節(jié)點(diǎn)入度、出度分布具有較大差異,但均符合冪律分布[13];在相同的d值下,不同初始網(wǎng)絡(luò)的節(jié)點(diǎn)入度、出度分布也不相同。然而,對(duì)同一初始網(wǎng)絡(luò)而言,隨著d值的變化,隨機(jī)初始網(wǎng)絡(luò)的度分布變化程度最大,環(huán)形初始網(wǎng)絡(luò)的變化程度最小;對(duì)不同的初始網(wǎng)絡(luò)而言,d=2.0時(shí)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的生長(zhǎng)演化影響最小,d=3.0時(shí)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)生長(zhǎng)演化影響最大。由此可知,不同的初始網(wǎng)絡(luò)及控制參數(shù)d對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的生長(zhǎng)有一定的影響。
通過(guò)對(duì)比每個(gè)初始網(wǎng)絡(luò)的節(jié)點(diǎn)入度圖和出度圖可以發(fā)現(xiàn),在不同的d值影響下,拓?fù)渚W(wǎng)絡(luò)節(jié)點(diǎn)入度和出度的變化幾乎是同步的,入度大出度大,入度小出度小。隨機(jī)初始網(wǎng)絡(luò)、環(huán)形初始網(wǎng)絡(luò)和全耦合初始網(wǎng)絡(luò)中均是d=2.5時(shí),節(jié)點(diǎn)的入度和出度值最大,拓?fù)渚W(wǎng)絡(luò)間的聯(lián)系最緊密;對(duì)于星形初始網(wǎng)絡(luò), d=2.5和d=3.0時(shí),節(jié)點(diǎn)的入度、出度值相差不明顯。由此可以看出,不同的初始網(wǎng)絡(luò)在相同d值下的聯(lián)系緊密程度不同。
圖1 4種初始網(wǎng)絡(luò)下的節(jié)點(diǎn)入度分布情況
圖2 4種初始網(wǎng)絡(luò)下的節(jié)點(diǎn)出度分布情況
4.2 節(jié)點(diǎn)勢(shì)分布
由圖3可以看出,對(duì)同一初始網(wǎng)絡(luò),控制參數(shù)d對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的勢(shì)也具有較明顯影響。具體而言, d值對(duì)全耦合初始網(wǎng)絡(luò)節(jié)點(diǎn)勢(shì)的影響最明顯,對(duì)環(huán)形和星形初始網(wǎng)絡(luò)的影響不是很大。隨機(jī)初始網(wǎng)絡(luò)和全耦合初始網(wǎng)絡(luò)中,d=3.0時(shí)節(jié)點(diǎn)的勢(shì)最大,但是全耦合初始網(wǎng)絡(luò)中節(jié)點(diǎn)勢(shì)的值波動(dòng)較大;環(huán)形和星形初始網(wǎng)絡(luò)d分別為2.5和2.0時(shí)節(jié)點(diǎn)的勢(shì)最大。
圖3 4種初始網(wǎng)絡(luò)下的節(jié)點(diǎn)勢(shì)分布情況
4.3 度-勢(shì)相關(guān)性
本文以d=2.5為例,對(duì)4種初始網(wǎng)絡(luò)度-勢(shì)相關(guān)性進(jìn)行分析。文獻(xiàn)[14]在研究了大量實(shí)際網(wǎng)絡(luò)數(shù)據(jù)集的基礎(chǔ)上,發(fā)現(xiàn)加權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)的度值與勢(shì)值是存在冪律關(guān)系的,若用s表示節(jié)點(diǎn)的勢(shì),k表示節(jié)點(diǎn)的度,則節(jié)點(diǎn)度值與勢(shì)值的冪律相關(guān)性可以表示為:
通過(guò)仿真實(shí)驗(yàn)得到4種初始網(wǎng)絡(luò)的有關(guān)節(jié)點(diǎn)的入度值、出度值與勢(shì)值,并對(duì)其進(jìn)行線(xiàn)性擬合后發(fā)現(xiàn),節(jié)點(diǎn)入度值、出度值與勢(shì)值之間存在冪律關(guān)系,如圖4所示。本文選取具有代表性的星形和全耦合初始網(wǎng)絡(luò),圖4(a)、圖4(b)分別是星形初始網(wǎng)絡(luò)節(jié)點(diǎn)入度、出度與勢(shì)的相關(guān)性,其斜率分別為0.75和0.78;圖4(c)、圖4(d)分別是全耦合初始網(wǎng)絡(luò)節(jié)點(diǎn)入度、出度與勢(shì)的相關(guān)性,其斜率分別為0.90和0.90。另外,隨機(jī)初始網(wǎng)絡(luò)節(jié)點(diǎn)入度、出度值與勢(shì)值擬合后得到的直線(xiàn)斜率分別為0.72和0.73;環(huán)形初始網(wǎng)絡(luò)節(jié)點(diǎn)入度、出度值與勢(shì)值擬合后得到的直線(xiàn)斜率分別為0.76和0.74。
圖4 星形和全耦合網(wǎng)絡(luò)的度-勢(shì)相關(guān)性
5 結(jié)束語(yǔ)
本文結(jié)合現(xiàn)實(shí)生活中信息傳播所遵循的規(guī)律,提出通過(guò)加權(quán)有向拓?fù)淠Ｐ湍M社會(huì)交往的動(dòng)態(tài)性。使用PageRank公式求節(jié)點(diǎn)的勢(shì)將節(jié)點(diǎn)分為關(guān)鍵節(jié)點(diǎn)和普通節(jié)點(diǎn),引入概率過(guò)渡矩陣,利用隨機(jī)游走理論中的當(dāng)前狀態(tài)只與其上一時(shí)刻的狀態(tài)有關(guān)而與其他時(shí)刻狀態(tài)無(wú)關(guān)的特性,得到社交網(wǎng)絡(luò)在每時(shí)步的生長(zhǎng)演化拓?fù)浣Y(jié)構(gòu)直至網(wǎng)絡(luò)規(guī)模N=1 000。仿真結(jié)果表明,在不同的初始網(wǎng)絡(luò)條件下,該模型所生成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的入度、出度、勢(shì)分布以及度-勢(shì)相關(guān)性有較明顯差異,但又具有一定的相似性。下一步將對(duì)網(wǎng)絡(luò)拓?fù)涞木垲?lèi)系數(shù)、核數(shù)和基尼系數(shù)等進(jìn)行仿真研究,檢驗(yàn)?zāi)Ｐ褪欠衲軌蝮w現(xiàn)移動(dòng)社交網(wǎng)絡(luò)的聚集特性、層次性和異質(zhì)性等特點(diǎn)。
[1] 劉衍珩,李飛鵬,孫 鑫,等.基于信息傳播的社交網(wǎng)絡(luò)拓?fù)淠Ｐ蚚J].通信學(xué)報(bào),2013,34(4):5-13.
[2] Waxman B M.Routing of Multiple Connections[J]. IEEE Journal on Selected Areas in Communication, 1998,6(9):1617-1622.
[3] Zegura E W,Calvert K L,Bhattacharjee S.How to Model an Internetwork[C]//Proceedings of the 15th Annual Joint Conference of the IEEE Computer Societies.San Fransisco,USA:IEEE Press,1996:594-602.
[4] Watts D J,Strogatz S H.Collective Dynamicsof‘Small-world' Networks[J].Nature,1998,393 (6684):440-442.
[5] Faloutsos M,Faloutsos P,Faloutsos C.On Power-law Relationships of the Internet Topology[C]//Proceedings of SIGCOMM'99.[S.l.]:ACM Press,1999:251-262.
[6] Barabasi A,Albert R.Emergence of Scaling in Random Networks[J].Science,1999,286(5439):509-512.
[7] 徐曉華.圖上的隨機(jī)游走學(xué)習(xí)[D].南京:南京航空航天大學(xué),2008.
[8] 趙 國(guó),宋建成.Google搜索引擎的數(shù)學(xué)模型及其應(yīng)用[J].西南民族大學(xué)學(xué)報(bào),2010,36(3):160-166.
[9] 黃德才,戚華春.PageRank算法研究[J].計(jì)算機(jī)工程, 2006,32(4):151-152,168.
[10] 楊 莉.網(wǎng)絡(luò)拓?fù)淠Ｐ偷难芯縖J].湖北第二師范學(xué)院學(xué)報(bào),2008,25(8):5-9.
[11] 王德廣,周志剛,梁 旭.PageRank算法的分析及改進(jìn)[J].計(jì)算機(jī)工程,2010,36(22):297-299.
[12] 劉衍珩,孫 鑫,王 健,等.基于用戶(hù)行為和網(wǎng)絡(luò)拓?fù)涞?Email蠕蟲(chóng)傳播[J].吉林大學(xué)學(xué)報(bào),2010,40 (6):196-203.
[13] 周 苗,楊家海,劉洪波.Internet網(wǎng)絡(luò)拓?fù)浣J].軟件學(xué)報(bào),2009,20(1):113-127.
[14] Barrat A,Barthelemy M,Pastor-Satorras R.The Architecture ofComplexWeighted Networks[J]. Proceedings of the National Academy of Sciences of the United States of America,2004,101(11):3747-3752.
編輯 金胡考
A Dynamic Mobile Social Network Topology Model
TIAN Xue-ying1a,1b,LIU Yan-heng1a,1b,SUN Xin2,WANG Ya-zhou1a,LIN Jia-jia1a
(1a.College of Computer Science and Technology;1b.Key Laboratory of Symbolic Computation and Knowledge Engineering,Ministry of Education,Jilin University,Changchun 130012,China;
2.College of Information Science and Engineering,Ocean University of China,Qingdao 266100,China)
A topological model that can describe the mobile social network accurately is proposed based on four initial networks considering the dynamic of social network,the different importance of users and the direction of information interaction.Random walking theory and improved PageRank algorithm are adopted,and transition probability is introduced to associate the network topological structure between two time-steps.Firstly,PageRank algorithm is used to obtain the strength of the nodes in order to get the probability transition matrix.Then random walking theory is used to get the current time-step edge existence probability matrix based on the last time-step edge existence probability matrix and the probability transition matrix.During each time-step,a node is added and it is checked if there is any departure node.Finally,simulation model is used to simulate the four initial networks in in-degree,out-degree,strength distribution and the correlation between degree and strength.The results indicate that the four initial networks'in-degree,out-degree,strength distribution and the correlation between degree and strength show obvious power-law character.It shows that the random walking theory and improved PageRank algorithm can describe the mobile social network better,which is of certain practical significance.
socialnetwork;network topology;random walking;PageRank algorithm;transition probability; simulation model
1000-3428(2014)09-0124-06
A
TP393
10.3969/j.issn.1000-3428.2014.09.025
國(guó)家自然科學(xué)基金資助項(xiàng)目(60973136,61073164);吉林省科技發(fā)展計(jì)劃青年科研基金資助項(xiàng)目(201101033);吉林大學(xué)國(guó)家級(jí)創(chuàng)新基金資助項(xiàng)目(2012A53143)。
田雪穎(1990-),女,碩士研究生,主研方向:網(wǎng)絡(luò)拓?fù)浣?網(wǎng)絡(luò)安全;劉衍珩,教授、博士、博士生導(dǎo)師;孫 鑫,博士;王亞洲,學(xué)士;林佳佳,碩士研究生。
2013-05-17
2013-08-26E-mail:txy_0902@126.com
猜你喜歡
童話(huà)王國(guó)·奇妙邏輯推理(2024年5期)2024-06-19 16:03:38
網(wǎng)絡(luò)安全與數(shù)據(jù)管理(2022年1期)2022-08-29 03:15:20
導(dǎo)航定位學(xué)報(bào)(2022年4期)2022-08-15 08:27:00
中學(xué)生數(shù)理化·中考版(2022年8期)2022-06-14 06:55:24
新世紀(jì)智能(數(shù)學(xué)備考)(2021年9期)2021-11-24 01:14:36
成都醫(yī)學(xué)院學(xué)報(bào)(2021年2期)2021-07-19 08:35:14
新世紀(jì)智能(數(shù)學(xué)備考)(2020年9期)2021-01-04 00:25:14
中學(xué)生數(shù)理化·七年級(jí)數(shù)學(xué)人教版(2020年10期)2020-11-26 08:24:50
數(shù)學(xué)物理學(xué)報(bào)(2020年2期)2020-06-02 11:29:24
光學(xué)精密工程(2016年6期)2016-11-07 09:07:19
