【作者】 刘群；

【导师】 陈夏；

【作者基本信息】 吉林大学 ， 概率论与数理统计， 2018， 博士

【摘要】 近些年来,复杂网络分析在越来越多的学科中发挥着重要的作用,例如物理学,生物学,医学,化学,计算科学,统计学等等.然而,随着研究的深入和伴随的网络环境的愈发复杂,传统的随机图模型和复杂网络分析方法已经不能很好的服务于研究的需要.为了解决这一问题,一些学者提出了更加复杂的广义随机图模型和学科高度交叉的复杂网络分析方法.本文主要研究的广义随机图模型是由Britton提出的带有顶点权重的广义随机图模型:在广义随机图GRG(ω)中,顶点集为{1,…,n},点i与j(这里默认?≠ j)存在一条边的概率为Pij=ωiωj/ln+ωiωj,这里ω=(ωi)i∈[n]是对应的顶点权重,ln表示所有权重的和ln=(?).该广义随机图的顶点权重有俩种配置方式:满足一定正则化条件的固定顶点权重和随机顶点权重.当用固定顶点权重配置广义随机图时,相应的正则化条件为(a)顶点权重的弱收敛.wn(?)w,这里Wn是分布服从顶点权重经验分布的的随机变量,W 和w的分布函数分别为Fn和F.等价的,对于任意的x使得x→F(x)连续,(?)(b)平均顶点权重收敛.(?)这里0<E[W]<∞.(c)顶点权重的二阶矩收敛.(?)在本文中的3.2.1节,我们利用传统大偏差理论计算了当顶点权重满足正则化条件(a)-(c)时,广义随机图边的数量的大偏差:定理1在广义随机图GRGn(ω)中,如果顶点权重满足正则化条件(a)-(c),上表示边的数目,Pn表示由En/n诱导的概率分布,则En/n满足如下的大偏差原则.·对任意的闭集F(?)R-,(?)对任意的开集U(?)R,(?)这里I(λ)=λlog2λ/EW-λ+EW/2当顶点权重是独立同分布的随机变量时,在3.2.2节中我们利用混合大偏差理论计算了广义随机图边的数量的大偏差:定理2在广义随机图GRGn(ω)中,如果顶点权重都独立同分布的在一个给定的集合∑ = {c1;C2,…,Cfκ}中取值.,对应的离散抽取分布为S = {S1,s2,…,sk},这里对任意的1 ≤ i ≤ k,ci>0,st ≥ 0.Pn表示En/n的分布,△表示Σ上所有概率测度的集合,则En/n满足如下的大偏差原则:对于任意的闭集F(?)R+,(?)对于任意的开集U(?)R+,(?)这里I(λ)= inf{Λx*;(λ)+ φ(x):x∈Δ},并且(?)稀疏随机图的极限理论研究是随机图论研究的一个难点,在本文的3.3节,通过把稀疏Erdos-Renyi随机图G(n,p)映射到图因子空间W(这里p=λ/n1-α,λ>0是一个固定的常数),我们给出对应的图因子所诱导的概率测度Pn,p的大偏差结果:定理3在弱拓扑意义下,图因子空间W上的概率测度Pn,p满足如下大偏差原则.对于任意的弱闭集F(?)W,(?)对于任意的弱开集U(?)W,(?)这里Ip(f)= 1/2∫∫[0,1]2(f(x,y)logf(x,y)/λ-f(x,y)+λ)dxdy.复杂网络谱分析在很多领域内都有着重要的应用,例如复杂网络上的传染病过程和同步化过程等.在4.2节中,利用代数图论的方法,我们给出了随机顶点权重下广义随机图的邻接矩阵的前四阶谱矩:定理4在广义随机图GRGn(u)中,顶点权重ω = {ω1,…,ωn}为独立同分布的随机变量序列..顶点权重之间互相独立,与随机变量W同分布,且存在一个一致上界M,使得W ≤ M<∞.则当顶点数n → ∞时对应的邻接矩阵的前四阶期望谱矩为E[m1+(A)=0,E[m2(A)]→E[W],E[m3(A)]→0,E[m4(A)]→2E[W2]+E[W].利用类似的方法,我们给出了随机顶点权重下广义随机图的Laplacian矩阵的前四阶谱矩:定理5在广义随机图GRGn(ω)中,顶点权重ω = {ω1,..ωn}为独立同分布的随机变量序列..顶点权重之间互相独立,与随机变量W同分布,且存在一个一致上界M,使得W ≤ M<∞.则当顶点数n → ∞时,对应的Laplacian矩阵的前四阶渐进期望谱矩为E[m1+(L)→E[W],E[m2(L)]→E[W2]+2E[W],E[m3(L)]→E[W3]+6E[W2]+4E[W]E[m4(L)]→E[W4]+10E[W3]+21E[W2]+6E[W]+2(E[W]+E[W2])/E[W]利用所得的谱分析结果,我们设计并分析了广义随机图上的病毒感染过程.实验结果证明我们的谱分析结果可以很好的用来预测广义随机图上的病毒感染过程,也可以用来构建能够有效抵抗病毒感染的网络环境.复杂网络的社团侦查是复杂网络聚类分析中的一项核心任务,在本文的4.3节中我们提出一种新颖的谱假设检验算法:首先把Erdos-Renyi随机图的邻接矩阵经过适当的尺度变换转化成标准的Wigner矩阵,然后利用Wigner矩阵的谱性质设计一个统计量,最后利用该统计量的极限分布设计假设检验.我们首先给出如下定理:定理6 A表示一个Erdos-Renyi图G(n,p)的邻接矩阵,矩阵P定义为P = pJn-pln,这里Jn是一个n × n的矩阵元全为1的矩阵,In是一个n × n的单位阵.定义(?)这里C是一个对角矩阵,相应的元Cii为独立同分布的随机变量满足P(Cn =-(?))= P(Cii =(?))= 1/2,(?)i,这时,我们有(?)tracx(A3)(?)N(0,1),这里N(0,1)表示标准正态分布.在该定理的基础上,考虑到在一些情形时Erdos-Renyi图的连接概率p是未知的,我们通过图内边的数量来估计p,我们把这个估计量表示为p:p=(?)我们用Λ表示把概率P替换成p的矩阵:(?)这里p = pJn-pIn.我们证明了如果把P替换成统计量p,定理6的结论依然成立:定理7统计量θ:=(?)lracc([Λ]3),则有θ(?)N(0,1).通过统计量θ的分布性质,我们提出了一种高效的谱假设检验算法,之后我们设计了大量的实验检验我们算法的效率和准确率.实验证实我们的算法可以出色的完成不同类型网络的社团侦查任务.复杂网络的图比较问题是复杂网络聚类分析的另一项核心任务,据我们所知,已有的图比较算法大多没有严格的数学理论背景支撑.在本文中的第五章,我们结合机器学习技术提出了一种新的基于切割距离的图比较算法,首次将理论数学中的切割距离概念应用到复杂网络的聚类分析问题.我们设计了一系列实验来验证我们算法的有效性,实验结果表明,我们的算法可以近乎完美的比较一些传统的随机图模型,并可以出色的完成不同的真实网络的聚类分析任务;另外,为了检验我们算法的准确率,我们设计了模型选择实验,结果表明我们的算法在分类准确率上要明显优于其他传统分类算法.更多还原

【Abstract】 In recent years,complex network analysis has played a central role in a wide range of disciplines,such as physics,biology,medical science,chemistry,computer science and statistics,etc.As the research going further,it turns out that the associated network environment become more and more complicated,some traditional random graph models and old-fashioned complex network analysis methods no longer work well on finishing different network analysis tasks.To address this issue,some researchers put forward some generalized random graph models with more complex structure and some novel network analysis methods with a high level intersection of different disciplines.In this thesis,we focus ourselves on investigating the generalized random graph model proposed by Britton:In a generalized random graph GRG(ω)with node set{1,...,n},the probability of a link between node i and j is(?)here i ≠ j,ω ＝(ωi)i∈[n]represents the associated node weight sequence,ln =(?)denotes the total of all node weights.Usually,there are two ways to assign weights to each node:fixed node weights with some regularity conditions,or random node weights.When constructing generalized random graphs via using fixed node weights,the corresponding regularity conditions are as follows:(a)Weak convergence of node weight.As n → ∞,(?)here Wn is a random variable whose law is the same as the empirical distribution of the node weights,and W,and W have distribution functions Fn and F,respectively.Equivalently,for any for which x→ F(x)is continuous,(?)(b)Convergence of average node weight.(?)Further,we assume that E[W]>0.(c)Convergence of second moment node weight.(?)In section 3.2.1,when the node weights satisfying the above regularity conditions(a)-(c),we obtain the large deviation principle for the number of edges in a generalized random graph by using some classic large deviations results:Theorem 1 Let the node weights in a generalized random graph with n nodes satisfy the regularity conditions(a),(b)and(c),let En denotes the number of edges,Pn denotes the distribution of En/n,then En/n satisfies an LDP as follows:For every closed set F(?)R+,(?)and for every open set U(?)R+,(?)here(?)When the node weights are i.i.d random variables,in section 3.2.2,we obtain the corresponding large deviation principle for the number of edges in a generalized random graph via utilizing the large deviation for mixture:Theorem 2 In a generalized random graph,each node weight is chosen inde-pendently from a finite set ∑=｛c1,…,ck},Ci>0,1≤i ≤ k,and the corresponding probability distribution is s = ｛s1,…,sk}.Let Pn defnotes the distribution of En/n,Δbe the set of probability distribution on ∑,then En/n satisfies an LDP as follows:For every closed set F(?)R+,(?)and for every open set U(?)R-,(?)whereL(λ)=inf{Λx*(λ)+φ(x):x∈Δ},(?)and(?)The research on the limit theory of sparse random graphs is a difficulty in random graph theory,in section 3.3,by mapping sparse Erdos-Renyi graphs into the graphon space W,here p λ/n1α,λ>0 is a constant,we obtain the large deviation principle for the induced probability measure Pn,p on the graphon space W:Theorem 3 The sequence Pn,p on W satisfies a large deviation principle in the weak topology.That is,for every weakly closed set F(?)C W(?)and for any weakly open sel U(?)W(?)hereIp(f)= 1/2∫∫(f(x,y))logf(x,y)/λ-f(x,y)+λ)dxdyComplex network analysis has played a central role in many realms,such as an?alyzing the virus spreading process or the synchronization of oscillators in various complex networks.In section 4.2,by using a algebraic graph theory method,we obtain the corresponding first four spectral moments of the adjacency matrix of a generalized random graph with random node weights:Theorem 4 In a generalized random graph GRG(ω),the node weights ω ={ω1,…,ωn}are i.i.d copies of an upper-bounded random variable W,the first four asymptotic spectral moments of the adjacency matrix are thenE[m1(A)]= 0,E[m2(A]→E[W],E[m3(A)]→0,E[m4(Λ)]→ 2E[W2]+ E[W].By using similar method,we obtain the first four spectral moments of the Lapla-ciau matrix of a generalized ranCdom graph with random node weights:Theorem 5 In a generalized rafndom graph GRG(ω),the node weights ω={ω1,…,ωn｝ are i.i.d copies of an upper-bounded random variable the first four asymptotic spectral moments of the Laplacian matrix are the nE[m1+(L)→E[W],E[m2(L)]→E[W2]+2E[W],E[m3(L)]→E[W3]+6E[W2]+5E[W]E[m4(L)]→E[W4]+10E[W3]+21E[W2]+6E[W]+2E[W]+E[W2])/E[W]These expressions are applied to study the behavior of a viral infection in a gener-alized random graph.On the basis of our results,we can forecast the virus spreading process in a generalized random graph,as well as design a generalized random graph with good antivirus ability when facing an initial virus infection.Numerical simulations agree with our analytical predictions.Community detection in a complex network is a central task in complex network clustering analysis.In section 4.3,we develop a novel spectral hypothesis testing algorithm:First,after some appropriate scaling,we transform the adjacency matrix of a Erdos-Renyi random graph into a standard Wigner matrix,then we put forward a test statistic by using some Wigner matrix’s characters;finally,we design the hypothesis test via using the limit distribution of this test statistic.Let us give the following important theorem:Theorem 6 Let A denotes the adjacency matrix of an Erdos-Renyi graph.Under an Erdos-Renyi graph G(n,p),denote P asP = pJn-pIn,where Jn is the n×n matrix of ones,and In is the n×n identify matrix.The fnofrmalized matrix then defined as follows:(?)here C is diagonal matrix where Cii are i.i.d rafndom variables such thatP(Cii =-(?))= P(Cii =(?))= 1/2,(?)i.Then,we have(?)trace(A3)(?)(0,1),here N(0,1)represents a stafndard normal distribution.On the basis of above theorem,by considering sometimes the true connection probability p of an Erdos-Rnyi graph G(n,p)is unknown,we estimate it via computing the proportion of pairs of nodes that forms an edge.Let us denote this estimate by p,that is p =(?).Let Λ denote the normalized matrix where p is replaced by p:(?)where P isP=pJn-pInIn our work,we show that the result of Theorem 6 remains true by replacing p with the estimation p:Theorem 7 Defnote our test statistic by θ=(?)trace([A’]3),thenθ(?)N(0,1).Through the property of the test statistic θ,we put forward a high-efficiency hypothesis testing algorithm;after that,we design a lot of experiments to test our algorithm’s efficiency,as well as accuracy;The results demonstrate that our hypothesis testing algorithm is capable of finishing different community detection tasks in various complex networks with outstanding performance.The graph comparison problem is another central task in the complex network clustering analysis domain,to the best of our knowledge,most of the existing network comparison methods are suffering the drawback of lacking enough rigorous mathemat-ical backgrounds.In chapter 5,by combining machine learning technique,we develop a novel network comparison algorithm on the basis of cut distance.To the best of our knowledge,it is the first time one can utilize the theoretical cut distance on solving complex network comparison problems.To test the effectiveness of our algorithm,we design a series of experiments.The results show that our algorithm can perfectly clus-ter different classic random graphs,and have an excellent performance on comparing different real world networks.To test our method’s accuracy,we also design a model selection process,the associated results demonstrate that our approach outperforms other sate of the art methods with respect to accuracy.更多还原