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

唐 鎮, 王建勇, 楊會杰

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

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

唐 鎮1, 王建勇2, 楊會杰1

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

可見圖方法將多重分形時間序列映射為相應的網絡,研究并對比了由不同機制產生的多重分形序列的非平凡特征,發現單分形時間序列的簡單疊加得到的混合序列有多分形性質,對應的可見圖是無尺度網絡;而通過模型產生的多分形序列對應的可見圖一般不具有無標度性質.為了辨別不同機制生成的多分形時間序列,小波分析和可見圖必須聯合運用才能識別這兩種不同的分形結構,可見圖算法作為傳統時間序列分析方法的補充在揭示序列產生機制時具有重要的用途.

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

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

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

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

1 方 法

1.1 可見圖

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

圖1 可見圖構造算法示意圖Fig.1 Illustration for the algorithm of visibility graph

1.2 多分形譜

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

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

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

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

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

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

式中,χ1和χ2為統計參數,決定分形譜的特征.

2 模 型

2.1 混合分數布朗運動(FBM)

式中,參數f為調節序列中兩個指數序列成分相對強度的參數,取值范圍0≤f≤1.

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

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

構建長度為N的時間序列

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

文獻[19]證明了該序列具有多分形性質,并給出了多分形譜的解析結果.該時間序列具有長程相關性.

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

多分形序列通過隨機方式產生,即序列值的生成服從某一概率密度函數,此類序列沒有長程關聯特性[19].

3 結 果

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

圖2 混合分數布朗運動多分形和無尺度性質Fig.2 Multi-fractal and scale-free characteristics for mixture series of fractal Brownian motions

二進制多分形模型序列,為了得到其全部的可見圖性質,調節參數w以0.05為間隔,從0.55～0.95,所有可見圖的度分布結果如圖3所示.

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

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

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

4 結 論

鑒于實際問題中普遍存在的時間序列具有多分形特征,本文考察了不同的形成機制導致的多分形序列的可見圖的拓撲結構屬性,發現分數布朗運動的疊加導致的時間序列具有多分形特征,對應的可見圖具有無標度特征,并且分形行為由休斯特指數小的成分決定,而二進制多分形和數值分布多分形模型產生的時間序列沒有無標度特征.綜上,可以得出的結論是傳統的小波分析提取多分形特征的方法并不能分辨不同產生機制得到的多分形,而單獨使用可見圖方法也不能分辨單分形與多個單分形疊加導致的混合序列,必須聯合運用這兩種方法才能提取到關于序列形成機制的更多的信息.

[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] 王建波.基于復雜網絡理論的時間序列分析[D].上海:上海理工大學,2010.

[18] 趙麗麗,唐鎮,王建勇,等.基于復雜網絡理論的時間序列分析[J].上海理工大學學報,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

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

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