| 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. |
