多重分形序列的可見圖分析

唐 鎮(zhèn), 王建勇, 楊會杰

(1.上海理工大學(xué)管理學(xué)院,上海 200093;2.邢臺學(xué)院物理系,邢臺 054001)

多重分形序列的可見圖分析

唐 鎮(zhèn)1, 王建勇2, 楊會杰1

(1.上海理工大學(xué)管理學(xué)院,上海 200093;2.邢臺學(xué)院物理系,邢臺 054001)

可見圖方法將多重分形時間序列映射為相應(yīng)的網(wǎng)絡(luò),研究并對比了由不同機制產(chǎn)生的多重分形序列的非平凡特征,發(fā)現(xiàn)單分形時間序列的簡單疊加得到的混合序列有多分形性質(zhì),對應(yīng)的可見圖是無尺度網(wǎng)絡(luò);而通過模型產(chǎn)生的多分形序列對應(yīng)的可見圖一般不具有無標(biāo)度性質(zhì).為了辨別不同機制生成的多分形時間序列,小波分析和可見圖必須聯(lián)合運用才能識別這兩種不同的分形結(jié)構(gòu),可見圖算法作為傳統(tǒng)時間序列分析方法的補充在揭示序列產(chǎn)生機制時具有重要的用途.

可見圖;多重分形時間序列;度分布

近年來一個長盛不衰的研究課題是將時間序列映射到復(fù)雜網(wǎng)絡(luò),從復(fù)雜網(wǎng)絡(luò)這一全新的視角出發(fā)對時間序列進(jìn)行分析,期望能夠提取到新的序列結(jié)構(gòu)特征,深入認(rèn)識復(fù)雜系統(tǒng)的結(jié)構(gòu)和動力學(xué)機制[1-9].其中,有廣泛影響的是可見圖方法[10].將時間序列的每個數(shù)據(jù)點映射為節(jié)點,從任意節(jié)點出發(fā),將該節(jié)點“視野”內(nèi)的其他節(jié)點與之相連,得到時間序列對應(yīng)的可見圖.這種網(wǎng)絡(luò)能反映原時間序列的大部分性質(zhì),如周期、隨機、分形序列分別轉(zhuǎn)化為規(guī)則、隨機和無標(biāo)度網(wǎng)絡(luò).并且,可見圖可以用于估算分?jǐn)?shù)布朗運動的休斯特指數(shù)(Hurst exponent).可以證明,分?jǐn)?shù)布朗運動的可見圖的度分布滿足冪律函數(shù),冪律指數(shù)α與休斯特指數(shù)H滿足線性函數(shù)關(guān)系[11],α=3-2H.可見圖也被成功地應(yīng)用于匯率序列[12]、心跳信號[13-14]等實證數(shù)據(jù)分析.

但是,現(xiàn)有文獻(xiàn)的研究工作主要是基于理論模型產(chǎn)生的數(shù)據(jù)的分析.這些數(shù)據(jù)具有定態(tài)、單純成分等良好的特性,這是實際數(shù)據(jù)不具備的.現(xiàn)實中大量的時間序列具有多分形的特征.很多序列是多個時間序列的混合,如股票綜合指數(shù)、居民消費價格指數(shù)、信息流量紀(jì)錄等.只有文獻(xiàn)[15]考察了多重分形隨機游走序列的可見圖,發(fā)現(xiàn)這種機制生成的多分形的可見圖也具有無尺度性質(zhì).本文考察和比較了采用不同形成機制產(chǎn)生的多分形的可見圖的性質(zhì),發(fā)現(xiàn)單分形布朗運動疊加得到的混合序列同時具有多分形特征和無尺度性質(zhì),而多分形理論模型產(chǎn)生的序列一般不具有無尺度性質(zhì).因此,必須聯(lián)合運用小波分析和可見圖方法,才能發(fā)現(xiàn)不同種類的多分形序列背后產(chǎn)生機制的差異.一般情況下,需要通過分析復(fù)雜系統(tǒng)的輸出序列來探測系統(tǒng)的動力學(xué)機制,因此,本文的結(jié)論具有重要的理論參考價值和潛在的應(yīng)用價值.

本文首先介紹了可見圖的概念,對單分形布朗運動的疊加進(jìn)行小波和可見圖分析,并與理論模型產(chǎn)生的多分形序列的可見圖進(jìn)行了比較,發(fā)現(xiàn)必須聯(lián)合使用小波分析和可見圖方法才能識別多分形序列的產(chǎn)生機制之間的差異.

1 方 法

1.1 可見圖

可見圖方法是由西班牙馬德里理工大學(xué)Lacasa與Luque等人提出的關(guān)于將時間序列映射為相應(yīng)網(wǎng)絡(luò)的數(shù)學(xué)算法[10],該方法的優(yōu)點不但保留了原有序列的大部分性質(zhì),而且通過研究網(wǎng)絡(luò)參數(shù)可以提供更多關(guān)于有關(guān)序列的信息.先假設(shè)一標(biāo)量序列為{y i|i=1,2,…,N},其中,N為記錄序列的最大值.若對于兩節(jié)點A(a,y a),B(b,y b)之間的任意節(jié)點C(c,y c)滿足條件那么,節(jié)點A,B相連,或稱其可見.如圖1所示,因序列為標(biāo)量序列,圖中縱坐標(biāo)為相應(yīng)標(biāo)量值.一般情況下,周期序列、隨機序列、分形序列最終分別轉(zhuǎn)化為規(guī)則網(wǎng)絡(luò)、隨機網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò).

圖1 可見圖構(gòu)造算法示意圖Fig.1 Illustration for the algorithm of visibility graph

1.2 多分形譜

采用小波變換探測序列的標(biāo)度性質(zhì)[16].時間序列{y i|i=1,2,…,N}的小波變換可以寫為

式中,g(·)為小波函數(shù);a為小波變換窗口尺度;s為序列中的元素編號.

時間序列的多分形指該序列能夠分解為具有不同局域休斯特指數(shù)的子集,也就是具有不同的局域奇異性特征.找出上述小波變換T(s,a)序列的極大值集合T(s,a),s=s1,s2,…,s M,其中,s是序列的極大值對應(yīng)的元素編號,相應(yīng)的配分函數(shù)定義為

式中,q為配分函數(shù)的階數(shù),取值范圍為不等于零的整數(shù).

當(dāng)配分函數(shù)滿足冪律關(guān)系,Z(a,q)～aτ(q)表明時間序列有標(biāo)度不變性,τ(q)為冪指數(shù),如果τ(q)是一條直線,時間序列是單分形;否則,就是多分形.多分形性質(zhì)可用分形維數(shù)D(h),即多重分形譜來表示,可以由勒讓德變換得到

由于勒讓德變換在計算中涉及到求導(dǎo)數(shù),這在實際計算中會導(dǎo)致不可接受的誤差,因此,往往先對離散的τ(q)進(jìn)行擬合,再進(jìn)行式(4)的變換

式中,χ1和χ2為統(tǒng)計參數(shù),決定分形譜的特征.

2 模 型

2.1 混合分?jǐn)?shù)布朗運動(FBM)

式中,參數(shù)f為調(diào)節(jié)序列中兩個指數(shù)序列成分相對強度的參數(shù),取值范圍0≤f≤1.

序列z就是序列y1和序列y2疊加后的混合序列.

2.2 二進(jìn)制多分形模型(BMF)

構(gòu)建長度為N的時間序列

式中,參數(shù)w的取值范圍為0＜w＜0.5;φ(k)為轉(zhuǎn)換函數(shù),其作用是將任意十進(jìn)制數(shù)k轉(zhuǎn)換成其相應(yīng)二進(jìn)制數(shù),然后數(shù)其中數(shù)值位是1的個數(shù),例如,φ(13)=3,因為,13的二進(jìn)制表示為1101,其共有3個1.

文獻(xiàn)[19]證明了該序列具有多分形性質(zhì),并給出了多分形譜的解析結(jié)果.該時間序列具有長程相關(guān)性.

2.3 數(shù)值分布引起的多分形模型(DMF)

多分形序列通過隨機方式產(chǎn)生,即序列值的生成服從某一概率密度函數(shù),此類序列沒有長程關(guān)聯(lián)特性[19].

3 結(jié) 果

作為一個典型的實例,圖2給出了休斯特指數(shù)為0.3和0.7的兩個分?jǐn)?shù)布朗運動混合序列的度分布,其中,混合相對強度f為1.p(k)表示序列可見圖的度分布,一般情況下,無標(biāo)度網(wǎng)絡(luò)對應(yīng)的度分布服從冪率分布,即p(k)～k-α,冪指數(shù)α被稱為無標(biāo)度指數(shù).由p(k)圖可以發(fā)現(xiàn)原始序列和混合序列的可見圖均為無標(biāo)度網(wǎng)絡(luò),并且混合序列的無標(biāo)度指數(shù)與H=0.3(休斯特值較小)的原始成分序列的無標(biāo)度指數(shù)相近.再通過對混合序列的小波分析,發(fā)現(xiàn)混合序列具有多分形特征,在多重分形譜D(h)圖中,可以明顯看到所分析的混合序列具有分形強度Δh=0.33,即表明該序列為多重分形序列.同時,從質(zhì)量指數(shù)τ(q)擬合圖中H=0.31進(jìn)一步印證了在多成分序列的競爭問題中,采用不同的休斯特指數(shù)和混合強度進(jìn)行的大量的計算表明,分?jǐn)?shù)布朗運動的混合序列具有多分形性質(zhì),同時,對應(yīng)的可見圖具有無尺度特征,并且度分布的斜率由休斯特指數(shù)小的成分決定.

圖2 混合分?jǐn)?shù)布朗運動多分形和無尺度性質(zhì)Fig.2 Multi-fractal and scale-free characteristics for mixture series of fractal Brownian motions

二進(jìn)制多分形模型序列,為了得到其全部的可見圖性質(zhì),調(diào)節(jié)參數(shù)w以0.05為間隔,從0.55～0.95,所有可見圖的度分布結(jié)果如圖3所示.

圖3給出了BMF模型產(chǎn)生的時間序列的可見圖的度分布,可以明顯看到這些度分布不具有無尺度特征,只有在w接近于0.5,也就是時間序列接近于單分形的時候,度分布逐步過渡到近似的冪律分布. 圖4給出了DMF模型產(chǎn)生的時間序列可見圖的度分布.一般來講,這些度分布也不具有無尺度特征,只有在β較大,度分布才過渡到冪律分布.當(dāng)β較大時,概率密度函數(shù)具有漸進(jìn)形式P(y)～y-3,對于這一分布指數(shù)為3的概率分布,在很大程度上與泊松分布是難以區(qū)分的,因此,這種模型產(chǎn)生的多分形時間序列的可見圖不具有無尺度特征.

圖3 二項式模型產(chǎn)生多分形的可見圖度分布Fig.3 Degree distributions for visibility graphs of BMF model generated series

圖4 數(shù)值分布多分形模型產(chǎn)生序列可見圖的度分布Fig.4 Degree distributions for visibility graphs of DMF model generated series

4 結(jié) 論

鑒于實際問題中普遍存在的時間序列具有多分形特征,本文考察了不同的形成機制導(dǎo)致的多分形序列的可見圖的拓?fù)浣Y(jié)構(gòu)屬性,發(fā)現(xiàn)分?jǐn)?shù)布朗運動的疊加導(dǎo)致的時間序列具有多分形特征,對應(yīng)的可見圖具有無標(biāo)度特征,并且分形行為由休斯特指數(shù)小的成分決定,而二進(jìn)制多分形和數(shù)值分布多分形模型產(chǎn)生的時間序列沒有無標(biāo)度特征.綜上,可以得出的結(jié)論是傳統(tǒng)的小波分析提取多分形特征的方法并不能分辨不同產(chǎn)生機制得到的多分形,而單獨使用可見圖方法也不能分辨單分形與多個單分形疊加導(dǎo)致的混合序列,必須聯(lián)合運用這兩種方法才能提取到關(guān)于序列形成機制的更多的信息.

[1] ZHANG J,SMALL M.Complex network from pseudoperiodic time series:Topology versus dynamics[J].Phys Rev Lett,2006,96:238701.

[2] ZHANG J,LUO X,NAKAMURA T,et al.Detecting temporal and spatial correlations in pseudo-periodic time series[J].Phys Rev E,2007,75:016218.

[3] XU X,ZHANG J,SMALL M.Super-family phenomena and motif of networks induced from time series[J].Proc Natl Acad Sci,2008,105:19601-19605.

[4] YANG Y,YANGH.Complex network-based time series analysis[J].Physica A,2008,387:1381-1386.

[5] WANGJ,YANG H.Complex network-based analysis of air temperature data in China[J].Mod Phys Lett B,2009,23:1781-1789.

[6] DONNER R V,ZOU Y.Recurrence networks-a novel paradigm for nonlinear time series analysis[J].New J Phys,2010,12:033025.

[7] GAOZ,JIN N.Flow-pattern identification and nonlinear dynamics of gas-liquid two-phase flow in complex networks[J].Phys Rev E,2009,79:066303.

[8] GAO Z,JIN N.Community structure detection in complex networks with applications to gas-liquid twophase flow[J].LNICST,2009,5:1917-1928.

[9] LUO F.Constructing gene co-expression networks and predicting functions of unknown genes by random matrix theory[J].BMC Bioinformatics,2007,8:299.

[10] LACASA L,LUQUE B,LUQUE J,et al.From time series to complex networks:The visibility graph[J].Proc Natl Acad Sci,2008,105:4972-4975.

[11] LACASA L,LUQUE B,LUQUE J,et al.The visibility graph:A new method for estimating the Hurst exponent of fractional Brownian motion[J].Europhys Lett,2009,86:30001.

[12] YANG Y,WANGJ,YANG H,et al.Visibility graph approach to exchange rate series[J].Physica A,2009,388:4431-4437.

[13] SHAO Z.Network analysis of human heartbeat dynamics[J].Appl Phys Lett,2010,96:073703.

[14] ZHAO D,LI X.Comment on“Network analysis of human heartbeat dynamics”[J].Appl Phys Lett,2010,96:266101.

[15] NI X,JIANG Z,ZHOU W.Degree distributions of the visibility graphs mapped from fractional Brownian motions and multi-fractal random walks[J].Phys Lett A,2009,373:3822-3826.

[16] YANG H,YIN C,ZHU G,LI B.Self-affinefractals embedded in spectra of complex networks[J].Phys Rev E,2008,77:045101.

[17] 王建波.基于復(fù)雜網(wǎng)絡(luò)理論的時間序列分析[D].上海:上海理工大學(xué),2010.

[18] 趙麗麗,唐鎮(zhèn),王建勇,等.基于復(fù)雜網(wǎng)絡(luò)理論的時間序列分析[J].上海理工大學(xué)學(xué)報,2011,33(1):38-44.

[19] KANTELHARDT J W.Multifractal detrended fluctuation analysis of nonstationary time series[J].Physica A,2002,316:87-114.

Visibility graph approach for multi-fractal series analysis

TANGZhen1, WANGJian-yong2, YANGHui-jie1
(1.Business School,University of Shanghai for Science and Technology,Shanghai 200093,China;2.Department of Physics,Xingtai College,Xingtai 054001,China)

Visibility graph method is used to map multi-fractal series to complex networks.Intrinsic traits of multi-fractal series generated by different dynamical mechanisms were compared.It is found that mixture series constructed by superposition of several mono-fractal Brownian motions behave generally with multi-fractal character and the corresponding networks are scale-free.While for the multi-fractal series generated by theoretical models,the corresponding visibility graphs display complicated behaviors rather than scale-free.In order to distinguish between these different generators,joint use of wavelet analysis and visibility graph is required to make clear the dynamical mechanisms embedded in multi-fractal time series.Visibility graph method is a necessary complement to traditional time series analysis approaches,which has potential use in detecting dynamical mechanisms of complex systems from output series.

visibility graph;multi-fractal time series;degree distribution

N 941

A

1007-6735(2011)04-0357-05

2011-04-08

國家自然科學(xué)基金資助項目(10975099,10635040);上海市重點學(xué)科建設(shè)資助項目(S30501);上海市高等學(xué)校特聘教授(東方學(xué)者)崗位計劃資助項目

唐 鎮(zhèn)(1984-),男,碩士研究生.研究方向:非線性時間序列.E-mail:ad_min09@126.com楊會杰(聯(lián)系人),男,教授.研究方向:復(fù)雜系統(tǒng)理論與系統(tǒng)生物學(xué).E-mail:hjyang@ustc.edu.cn