隨機(jī)圖中正則Laplace矩陣的譜分析

張 玲,丁 雪

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

隨機(jī)圖中正則Laplace矩陣的譜分析

張 玲1,丁 雪2

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

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

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

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

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

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

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

1 預(yù)備知識(shí)

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

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

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

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

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

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

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

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

注意到

計(jì)算可得

對(duì)任意的M≥2成立.

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

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

這里τ=maxφts. 綜上有

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

考慮

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

（14）

（15）

（16）

將式(13)中的求和項(xiàng)展開(kāi),有

其中第一個(gè)求和

于是

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

證畢.

證明: 由于

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

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

因此有

這里:

故有

其中:

易見(jiàn)

下面證明定理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)計(jì)的研究,E-mail: allenyz@163.com. 通信作者: 丁 雪(1983—),女,漢族,博士,講師,從事概率論與數(shù)理統(tǒng)計(jì)的研究,E-mail: dingxue83@jlu.edu.cn.

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

O211.4

A

1671-5489(2014)05-0954-07