隨機圖中正則Laplace矩陣的譜分析

張 玲,丁 雪

(1. 長春工程學(xué)院 理學(xué)院,長春 130012; 2. 吉林大學(xué) 數(shù)學(xué)學(xué)院,長春 130012)

隨機圖中正則Laplace矩陣的譜分析

張 玲1,丁 雪2

(1. 長春工程學(xué)院 理學(xué)院,長春 130012; 2. 吉林大學(xué) 數(shù)學(xué)學(xué)院,長春 130012)

用隨機矩陣中的矩方法研究給定期望度數(shù)隨機圖中正則Laplace矩陣經(jīng)驗譜分布的收斂性,結(jié)果表明,在期望度數(shù)滿足一定條件時,相應(yīng)正則Laplace矩陣的經(jīng)驗譜分布幾乎處處收斂到固定的概率分布,但在不同的期望度數(shù)下,此概率分布可能不同.

隨機圖； 隨機矩陣； 正則Laplace矩陣； 經(jīng)驗譜分布

0 引言及主要結(jié)果

隨機圖在物理和化學(xué)等領(lǐng)域應(yīng)用廣泛,目前已有許多研究成果[1-2]. 隨機圖的譜理論主要研究與其有關(guān)的相鄰矩陣和Laplace矩陣特征值和特征向量的性質(zhì)[3-4]. 給定期望度數(shù)隨機圖是隨機圖中一類較重要的隨機圖,文獻(xiàn)[5-12]研究了給定期望度數(shù)隨機圖的譜理論. 本文研究一類期望度數(shù)特殊的隨機圖所對應(yīng)正則Laplace矩陣的譜性質(zhì).

此時,G(w)稱為給定期望度數(shù)的隨機圖模型. 對于隨機圖G(w),與其相關(guān)的相鄰矩陣和正則Laplace矩陣定義如下:

1) 相鄰矩陣An=(aij)1≤i,j≤n是一個對稱矩陣,其中

1 預(yù)備知識

設(shè)k,n是兩個正整數(shù),i1,i2,…,ik是從{1,2,…,n}中取值的k個正整數(shù),定義路徑π={(i1,i2),(i2,i3),…,(ik-1,ik),(ik,i1)},稱該路徑為長度為k的循環(huán),稱(il,il+1)為循環(huán)π的一條邊,il,il+1是邊(il,il+1)的頂點. 對π的兩條邊(il,il+1),(is,is+1),如果il=is,il+1=is+1或者il=is+1,il+1=is,則稱這兩條邊是相同的,如果π的邊(il,il+1)與所有的邊都不同,則稱它是單獨的.

引理1[1]對任意的正整數(shù)k,n,所有長度為k正好擁有l(wèi)個不同邊的循環(huán)個數(shù)不多于θlknl+1,這里θlk是一個只依賴于l,k的常數(shù).

引理2[2]所有長度為2k正好有l(wèi)個不同邊,且沒有單獨邊的循環(huán)個數(shù)不多于

令π1,π2,π3,π4是4個長度為k的在{1,2,…,n}中取值的循環(huán),如果π1,π2,π3,π4的所有邊中沒有單獨的邊,則稱它們是匹配的; 如果πi的所有邊與πj(j≠i)中的任何邊都不同,則稱πi為自匹配的.

引理3[1]假設(shè)k,n是兩個正整數(shù),用S表示所有長度為k匹配的,沒有自匹配的,并且不同的邊個數(shù)正好是l的循環(huán)π1,π2,π3,π4,則S中元素的個數(shù)最多為ηlknl+2,這里ηlk是不依賴n的常數(shù).

2 主要結(jié)果的證明

下面證明定理1. 正則Laplace矩陣有如下表述:

其中: Vol(G)=∑d(vi);Kn是所有值都為1的n×n矩陣. 定義

注意到

計算可得

對任意的M≥2成立.

這里:π是取遍所有長度為2k每條邊至少重復(fù)兩次的循環(huán);S1是所有長度為2k每條邊正好重復(fù)兩次且正好有k+1個不同頂點的循環(huán)組成的集合;S2是所有長度為2k每條邊重復(fù)至少兩次,并且至少有一條邊重復(fù)三次以上的循環(huán)組成的集合;S3是所有長度為2k在{1,2,…,n}中取值的每條邊正好重復(fù)兩次且不同頂點個數(shù)不超過k的循環(huán)組成的集合. 對S2中的任何循環(huán)π,π中不同邊的個數(shù)至多為k-1,則有

由式(3)知E(Cij)2=ρ(1-ωiωjρ),由假設(shè)(H1)可找到一個正數(shù)列δn→0,使得

這里τ=maxφts. 綜上有

至此證明了斷言1)的第一部分和斷言2)都成立.

考慮

其中π1,π2,π3,π4取遍所有長度為r在{1,2,…,n}中取值的循環(huán). 如果π1,π2,π3,π4有單獨邊或有自匹配,則可斷定其期望為零. 因此在式(13)中,只需考慮沒有單獨邊且沒有自匹配的π1,π2,π3,π4. 由于沒有單獨邊,則π1,π2,π3,π4中至多有2r條邊,如果正好有1≤l≤2r條邊,則由式(3)知

（14）

（15）

（16）

將式(13)中的求和項展開,有

其中第一個求和

于是

又由式(13)可知存在只依賴于r的常數(shù)κr,使得當(dāng)n充分大時,有

證畢.

證明: 由于

其中:Cn由式(1)定義;Bn,Rn,Sn是對稱的隨機矩陣,分別有元素

aij是相鄰矩陣An的元素,di是頂點vi的實際度數(shù)d(vi). 易見

因此有

這里:

故有

其中:

易見

下面證明定理1.

[1]Gugelmann L,Sp?hel R. On Balanced Coloring Games in Random Graphs [J]. European J Combin,2014,35: 297-312.

[2]Fountoulakis N F,Kang R J,McDiarmid C. Largest Sparse Subgraphs of Random Graphs [J]. European J Combin,2014,35: 232-244.

[3]Fan C,Radcliffe M. On the Spectra of General Random Graphs [J]. Electron J Combin,2011,18(1): Paper 215.

[4]Fan C,Lu L Y. Complex Graphs and Networks [M]. Vol.107. Boston: AMS,2004.

[5]Fan C,Lu L Y,Vu V. Spectra of Random Graphs with Given Expected Degrees [J]. PNAS,2003,100(11): 6313-6318.

[6]Fan C,Lu L Y,Vu V. Eigenvalues of Random Power Law Graphs [J]. Ann Comb,2003,7(1): 21-33.

[7]Fan C,Lu L Y. The Average Distances in Random Graphs with Given Expected Degrees [J]. Proc Natl Acad Sci USA,2002,99(25): 15879-15882.

[8]Anand K,Bianconi G,Severini S. Shannon and Von Neumann Entropy of Random Networks with Heterogeneous Expected Degree [J]. Phys Rev E,2011,83(3): 036109.

[9]Coja-Oghlan A,Lanka A. The Spectral Gap of Random Graphs with Given Expected Degrees [M]. Lecture Notes in Comput Sci. Vol.4051. New York: Springer,2006.

[10]Fan C,Graham R. Quasi-random Graphs with Given Degree Sequences [J]. Random Structures Algorithms,2008,32(1): 1-19.

[11]SHANG Yilun. A Remark on the Spectra of Random Graphs with Given Expected Degrees [J]. J Discrete Math Sci Cryptogr,2012,15(6): 317-321.

[12]Miller J C,Hagberg A. Efficient Generation of Networks with Given Eexpected Degrees [C]//Proceeding of the 8th International Conference on Algorithms and Models for the Web Graph. Berlin: Springer-Verlag,2011: 115-126.

[13]BAI Zhidong,Silverstein J W. Spectral Analysis of Large Dimensinal Random Matrices [M]. 2nd ed. Beijing: Science Press,2010.

[14]汪嘉岡. 現(xiàn)代概率論基礎(chǔ) [M]. 2版. 上海: 復(fù)旦大學(xué)出版社,2006. (WANG Jiagang. Foundations of Modern Probability [M]. 2nd ed. Shanghai: Fudan University Press,2006.)

(責(zé)任編輯： 趙立芹)

SpectralAnalysisofNormalizedLaplacianMatrixinRandomGraphs

ZHANG Ling1,DING Xue2
(1.SchoolofScience,ChangchunInstituteofTechnology,Changchun130012,China;
2.CollegeofMathematics,JilinUniversity,Changchun130012,China)

We investigated the convergence of the empirical spectral distribution (ESD) of normalized Laplacian matrix from random graph with given expected degree. It was shown that the ESD of normalized Laplacian matrix converges to a fixed probability distribution when the expected degree satisfys some assumptions,but the fixed probability distribution may be different at different places.

random graph; random matrix; normalized Laplacian matrix; empirical spectral distribution

2013-10-21.

張 玲(1981—),女,漢族,碩士,講師,從事概率論與數(shù)理統(tǒng)計的研究,E-mail: allenyz@163.com. 通信作者: 丁 雪(1983—),女,漢族,博士,講師,從事概率論與數(shù)理統(tǒng)計的研究,E-mail: dingxue83@jlu.edu.cn.

國家自然科學(xué)基金(批準(zhǔn)號: 11201175)和教育部博士學(xué)科點新教師基金(批準(zhǔn)號: 20120061120003).

O211.4

A

1671-5489(2014)05-0954-07