社區(qū)網(wǎng)的增長(zhǎng)趨向及其分形特征分析

沈陽理工大學(xué)信息科學(xué)與工程學(xué)院 苑 勛 徐 野

東北大學(xué)軟件學(xué)院 黃利萍

復(fù)雜網(wǎng)絡(luò)是指具有自組織、自相似、吸引子、小世界、無標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)出現(xiàn)在各個(gè)學(xué)科領(lǐng)域，如生物學(xué)、物理學(xué)，甚至社會(huì)科學(xué)中。在過去的若干年中，許多關(guān)于復(fù)雜網(wǎng)絡(luò)的規(guī)律被發(fā)現(xiàn)，如服從雙向冪律分布的萬維網(wǎng)，具有無尺度的特點(diǎn)藝人網(wǎng)絡(luò)，呈現(xiàn)指數(shù)級(jí)衰減的送電網(wǎng)則。

本文通過研究一個(gè)社區(qū)網(wǎng)實(shí)例，確定社區(qū)網(wǎng)的分形規(guī)律，分析它的維數(shù)，做出奇異吸引子混沌軌道運(yùn)動(dòng)形式的數(shù)學(xué)模型，揭示其網(wǎng)絡(luò)的復(fù)雜性及其在生長(zhǎng)變化中的分形或混沌特征，確定預(yù)測(cè)模型的數(shù)學(xué)形式。

1.幾個(gè)定義

定義1 社區(qū)網(wǎng)沈陽市某社區(qū)的全部業(yè)主，具有想建立聯(lián)系想法的業(yè)主之間相互連接，組成業(yè)主為節(jié)點(diǎn)、相互聯(lián)系為邊的網(wǎng)絡(luò)，稱為社區(qū)網(wǎng)。

定義2 新增節(jié)點(diǎn)，社區(qū)網(wǎng)中新注冊(cè)的用戶代表的節(jié)點(diǎn)稱為新增節(jié)點(diǎn)，一天內(nèi)新增節(jié)點(diǎn)數(shù)用Nb表示。

定義3 增聯(lián)節(jié)點(diǎn)，社區(qū)網(wǎng)中已注冊(cè)用戶若增加至少一個(gè)連接稱為增聯(lián)節(jié)點(diǎn)，一天內(nèi)的增聯(lián)節(jié)點(diǎn)數(shù)用Ns表示

定義4 眠聯(lián)節(jié)點(diǎn)，社區(qū)網(wǎng)中的已注冊(cè)用戶一天之內(nèi)連接保持不變稱為眠聯(lián)節(jié)點(diǎn)，一天內(nèi)的眠聯(lián)節(jié)點(diǎn)數(shù)用Nd表示。

定義5 覺聯(lián)節(jié)點(diǎn)，社區(qū)網(wǎng)中的眠聯(lián)結(jié)點(diǎn)如果一天之內(nèi)至少增加一條邊則稱為覺聯(lián)節(jié)點(diǎn)，一天內(nèi)的覺聯(lián)節(jié)點(diǎn)數(shù)用Na表示。

定義6 規(guī)模增速，設(shè)社區(qū)網(wǎng)中節(jié)點(diǎn)數(shù)為N，社區(qū)網(wǎng)規(guī)模增速r可用下式表示：

2.模型

2.1 讓模型體現(xiàn)社區(qū)網(wǎng)的震蕩性

由定義2～6及和 (1)，我們計(jì)算社區(qū)網(wǎng)的規(guī)模增速r，通過觀察計(jì)算得出的三周內(nèi)節(jié)點(diǎn)增長(zhǎng)速率圖可知：社區(qū)網(wǎng)規(guī)模增速在不斷地震蕩。從肉眼觀察可以看出震蕩曲線表現(xiàn)出一定的周期性特點(diǎn)。因?yàn)檎鹗幍那€可以用不同周期的正弦余弦函數(shù)及其組合表示，所以可以將r轉(zhuǎn)換為(2)來表示。

其中v為總體偏移量，p為振幅。h1、 h2為震蕩半周期，單位為天。u1、 u2為震蕩幅角。

把式(2)中r的表示代入Logistic模型，就是本文對(duì)Logistic模型的進(jìn)一步修改，使其能夠表示周期性的變化。

2.2 求解r表示式的系數(shù)

下面采用浮點(diǎn)型遺傳算法求解r表示式的系數(shù)。

首先定義遺傳基因，一個(gè)基因中包含了所有r表示式中的待定參數(shù)如(3)所示：

(2) 生成最初的基因群體，即若干組r表示式中的待定參數(shù)。本文中基因群的基因數(shù)為N=100，每個(gè)基因的編碼值由隨機(jī)算法生成。

(3) 匹配度估計(jì)函數(shù)

由基因編碼確定的參數(shù)值計(jì)算出的r(t)應(yīng)當(dāng)與采樣值r*(t)越接近越好。我們用社區(qū)網(wǎng)25天的采樣數(shù)據(jù)來計(jì)算r(t)與r*(t)的差，由此得到匹配度估計(jì)函數(shù)。

利用匹配度估計(jì)函數(shù)計(jì)算每個(gè)基因編碼（即每組參數(shù)取值）的分?jǐn)?shù)，該分?jǐn)?shù)為匹配度估計(jì)函數(shù)的倒數(shù)，即：

(4) 挑選優(yōu)秀基因

設(shè)有隨機(jī)數(shù)m(0＜m＜1)，挑選分?jǐn)?shù)比m高的前w個(gè)基因作為進(jìn)一步繁殖的種群。為簡(jiǎn)化計(jì)算，復(fù)制選出的w個(gè)個(gè)體，刪除按分?jǐn)?shù)排序的后w個(gè)個(gè)體，保持種群個(gè)體數(shù)不變，進(jìn)行下一步的繁殖。

(5) 雜交

繁殖種群個(gè)體數(shù)設(shè)為N，設(shè)MP=(x1…xi…xj…xn) 為雜交池中，用隨機(jī)方法從中選擇xi、xj兩個(gè)基因進(jìn)行雜交[10]，基因中每個(gè)參數(shù)的雜交方式類同，如在參數(shù)v上進(jìn)行雜交，公式為

按照上述雜交操作，對(duì)每個(gè)基因中的每個(gè)參數(shù)進(jìn)行修正。修正的同時(shí)要防止參數(shù)衰減到0，當(dāng)其值小于0.01時(shí)，設(shè)置為0.01。

(6) 變異

對(duì)雜交的到的N個(gè)基因中的每個(gè)參數(shù)進(jìn)行變異，變異概率為0.3。參數(shù)v 的變異算法公式如下：

(7) 結(jié)束判斷

本文采用雙重結(jié)束判斷算法，一個(gè)結(jié)束判斷條件是(為結(jié)束時(shí)達(dá)到的分?jǐn)?shù)下限，在本文中采用0.1作為下限)；另一個(gè)結(jié)束判斷條件是遺傳算法的循環(huán)次數(shù)，如果循環(huán)次數(shù)達(dá)到上限，結(jié)束計(jì)算，不管此時(shí)score是否越過下限s。本文中設(shè)定的循環(huán)次數(shù)上限為1000，實(shí)驗(yàn)表明循環(huán)次數(shù)達(dá)到這一數(shù)值可以保證產(chǎn)生優(yōu)良的后代。

2.3 擬合結(jié)果與評(píng)價(jià)

2.3.1 收斂分析

經(jīng)過1000次遺傳算法的循環(huán)，得到的最優(yōu)基因（參數(shù)組），代入社區(qū)增長(zhǎng)模型的結(jié)果如式(8)：

由此可以從圖上看到100次循環(huán)以后，遺傳基因達(dá)到最優(yōu)，其后900次循環(huán)中，基因的分?jǐn)?shù)變化不大，所以可以認(rèn)為該遺傳算法收斂，得到的結(jié)果較好。

2.3.2 擬合精確度分析

本文定義相對(duì)擬合誤差ε，據(jù)此分析模型的擬合程度。定義7 設(shè)社區(qū)網(wǎng)規(guī)模采樣數(shù)據(jù)原始值為y*(ti)，用擬合模型計(jì)算出的值為y(ti)(i31，i?N)，則相對(duì)擬合誤差ε定義為誤差和的均值占原始數(shù)據(jù)均值的比重，公式如下：

其中，i， n(n=25)表示采樣天數(shù)為25天，每天采集一個(gè)數(shù)據(jù)。采用平均誤差占平均原始值的比重表示相對(duì)的誤差程度。

由式(9)，可以計(jì)算出25天內(nèi)社區(qū)網(wǎng)規(guī)模的相對(duì)擬合誤差，故社區(qū)網(wǎng)規(guī)模增長(zhǎng)模型的擬合精確度為1-0.1311=86.89%，結(jié)果較好，可以接受。

3.社區(qū)網(wǎng)規(guī)模增長(zhǎng)的混沌分析

3.1 社區(qū)網(wǎng)規(guī)模增長(zhǎng)曲線

由前面所述的社區(qū)規(guī)模增長(zhǎng)的數(shù)學(xué)模型可以做出如圖1的增長(zhǎng)曲線。

圖1 增長(zhǎng)趨向圖（x軸-增長(zhǎng)時(shí)間/天，y軸-網(wǎng)絡(luò)節(jié)點(diǎn)值）

圖2 增長(zhǎng)趨向圖（x軸-增長(zhǎng)時(shí)間/0.1天，y軸-網(wǎng)絡(luò)節(jié)點(diǎn)值）

從圖1可以看出，社區(qū)網(wǎng)規(guī)模震蕩向上走高，曲線呈現(xiàn)鋸齒狀，不光滑。為了表明曲線的特點(diǎn)，便于觀察，我們將圖中時(shí)間單位由1天變?yōu)?.1天，再次繪圖得到如圖2的曲線。

我們得到圖2的曲線顯示社區(qū)網(wǎng)規(guī)模曲線是一條連續(xù)向上增長(zhǎng)的波動(dòng)曲線，曲線仍然呈現(xiàn)鋸齒狀，在每個(gè)取值點(diǎn)都不可導(dǎo)，表現(xiàn)出混沌分形的特點(diǎn)。下文我們計(jì)算這一曲線的維數(shù)。

3.2 維數(shù)的計(jì)算方法

計(jì)算社區(qū)網(wǎng)規(guī)模增長(zhǎng)的維數(shù)，首先取得采樣時(shí)間序列，將一維的數(shù)據(jù)轉(zhuǎn)換成m維數(shù)據(jù)，m依次取值為2，4，8，10，15，18等等。然后根據(jù)表2的計(jì)算方法，對(duì)每個(gè)m值計(jì)算相應(yīng)的D2值，D2就是m的關(guān)聯(lián)維數(shù)。如果隨著m的增大，D2收斂于某一飽和值，說明社區(qū)網(wǎng)規(guī)模增長(zhǎng)系統(tǒng)具有混沌分形的特點(diǎn)。反之如果D2不隨m增大而收斂，而是趨向于無窮，則系統(tǒng)不具有混沌性。表2說明了與m相關(guān)聯(lián)的維數(shù)D2的計(jì)算方法。

表2 計(jì)算時(shí)間序列的關(guān)聯(lián)維數(shù)算法

3.3 社區(qū)網(wǎng)規(guī)模增長(zhǎng)系統(tǒng)的維數(shù)

采用表2的算法，對(duì)m=2,4,8,10,12,15,18,20 計(jì)算r和cr，繪出ln(r)-ln(cr)曲線，從圖中可以看出，m=12,15,18,20時(shí)曲線的直線部分具有平行性，它們的斜率基本相同，其斜率就是D2（關(guān)聯(lián)維數(shù)），該值收斂。計(jì)算可得：

由以上計(jì)算可知社區(qū)網(wǎng)規(guī)模增長(zhǎng)系統(tǒng)具有混沌分形特性，其關(guān)聯(lián)維數(shù)是在2和3之間的分?jǐn)?shù)維。

3.4 社區(qū)網(wǎng)規(guī)模增長(zhǎng)系統(tǒng)的長(zhǎng)期預(yù)測(cè)

根據(jù)文獻(xiàn)，維數(shù)為D2的分形混沌系統(tǒng)，設(shè)D2向上取整的值為D，則至少需要D個(gè)方程描述系統(tǒng)中D個(gè)重要的物理規(guī)律，才能實(shí)現(xiàn)長(zhǎng)期較準(zhǔn)確的預(yù)測(cè)。

由式(12)，社區(qū)網(wǎng)規(guī)模增長(zhǎng)系統(tǒng)的關(guān)聯(lián)維數(shù)為2、3之間的分?jǐn)?shù)維，為了對(duì)該系統(tǒng)進(jìn)行長(zhǎng)期預(yù)測(cè)，至少需要3個(gè)方程為其系統(tǒng)建模，公式如下：

式中x,y,z為表達(dá)社區(qū)網(wǎng)系統(tǒng)重要物理規(guī)律的物理量，x(n)為x的n階導(dǎo)數(shù)，y(n)為y的n階導(dǎo)數(shù)，z(n)為z的n階導(dǎo)數(shù)，n=1，2，3…。

式(13)表達(dá)了社區(qū)網(wǎng)混沌系統(tǒng)內(nèi)在的運(yùn)動(dòng)規(guī)律，由于本文中采樣數(shù)據(jù)較少，不能夠確定f1～f3中的具體參數(shù)，因而將這部分計(jì)算作為我們下一步的工作。

4.小結(jié)與展望

因?yàn)長(zhǎng)ogistic模型有效反映了有限資源條件下生物種群增長(zhǎng)的規(guī)律，和社區(qū)網(wǎng)絡(luò)具有內(nèi)在相似性，本文采用Logistic模型為社區(qū)網(wǎng)落規(guī)模增長(zhǎng)趨像建立了數(shù)學(xué)模型。因?yàn)樯鐓^(qū)網(wǎng)規(guī)模在震蕩中增長(zhǎng)，本文增加了模型中的三角函數(shù)因子，改進(jìn)了原模型，是其能夠反映震蕩特性，模型參數(shù)用遺傳算法進(jìn)行搜索，得到較為優(yōu)異的擬合值。

模型曲線連續(xù)但不可微，呈現(xiàn)鋸齒狀，表現(xiàn)出混沌分形特性，本文利用維數(shù)計(jì)算方法計(jì)算得到了社區(qū)網(wǎng)規(guī)模增長(zhǎng)系統(tǒng)的維數(shù)為2.062。維數(shù)計(jì)算收斂，表明社區(qū)網(wǎng)規(guī)模增長(zhǎng)系統(tǒng)中混沌分形性是真實(shí)存在的。

最后本文指出要對(duì)社區(qū)網(wǎng)規(guī)模增長(zhǎng)系統(tǒng)進(jìn)行長(zhǎng)期較為準(zhǔn)確的預(yù)測(cè)，必須至少采用三個(gè)以上的物理量及其多階導(dǎo)數(shù)的三個(gè)以上的方程式描述內(nèi)在的重要物理規(guī)律。本文給出了上述數(shù)學(xué)模型，我們下一步的工作便是求解模型中的參數(shù)。