网络的谱性质与应用.ppt

《网络的谱性质与应用.ppt》由会员分享，可在线阅读，更多相关《网络的谱性质与应用.ppt（31页珍藏版）》请在三一办公上搜索。

1、Properties and applications of spectra for networks,章 忠 志复旦大学计算机科学技术学院Email:Homepage:http:/http:/,第七届全国复杂网络学术会议,Collaborators,2023/11/16,Prof.Chen Guanrong(陈关荣),CityU of Hongkong Prof.Comellas Francesc,Universitat Politecnica de Catalunya,Barcelona,SpainQi Yi(齐轶),Master student(graduated)Wu Shunqi(伍

2、顺琪),Master student Wu Bin(吴斌),Master studentLin Yuan(林苑),Undergraduate student,2023/11/16,Main contents,3/43,Spectral properties of various matrixes and their relevance to structure and dynamics,Computation of spectra for different matrixes and their applications to network structure and random walk

3、s,Definitions,4/45,2023/11/16,Adjacency matrix A Diagonal degree matrix D Laplacian matrix L=D-A Probability transition matrix Normalized Laplacian matrix Fundamental matrix Modular matrix,Adjacency matrix,5/45,2023/11/16,From the greatest eigenvalue(often called spectrum radius),one can provide a l

4、ower bound for diameter of a network.,J.Combin.Theory Ser.B 91(1)(2004)143146.,The diameter of a connected graph G is less than the number of distinct eigenvalues of the adjacency matrix of G.,Electronic Journal of Linear Algebra,2005,14:12-31,Adjacency matrix,6/45,2023/11/16,SIS model:the largest e

5、igenvalue defines an epidemic threshold,SI model:the eigenvector corresponding to the largest eigenvalue is related to the spreading power of nodes in a network.,Complexus 3,131-146(2006),ACM Trans.Inf.Syst.Secur.10,13(2008),Spectrum radius plays a central role in determining critical couplings for

6、the onset of coherent behavior.,Phys.Rev.E 71,036151 2005.,7/45,2023/11/16,If the probability of removing node i is,the network disintegrates if is such that the largest eigenvalue of the matrix with entries is less than 1,where A is the adjacency matrix of the network.,PRL 100,058701(2008),Weighted

7、 percolation on directed networks:,Adjacency matrix,Laplacian matrix,8/45,2023/11/16,Algebraic connectivityprovides a upper bound for diameter of a network.,SIAM Journal of discrete mathematics,1994,7(3):443-457.,Spanning trees,2023/11/16,9/43,Effective resistance,Laplacian matrix,2023/11/16,is degr

8、ee of node z,m is the number of edges.,10/43,Random walks,Laplacian matrix,2023/11/16,Quantum walks Synchronization Generalized Gaussian structures Ultimatum game,11/43,Laplacian matrix,Relevance to other dynamics,Transition probability matrix,12/45,2023/11/16,for non-bipartite graphs,are the corres

9、ponding mutually orthogonal eigenvectors of unit length.,Q is often called normalized adjacency matrix,Stationary distribution,13/45,2023/11/16,Transition probability matrix,Commute time,First passage time,Eigentime identity,14/45,2023/11/16,Mixing rate,Transition probability matrix,Mixing time,Retu

10、rn-to-origin probability,Normalized Laplacian matrix,15/45,2023/11/16,are the corresponding mutually orthogonal eigenvectors of unit length.,16/45,2023/11/16,Normalized Laplacian matrix,Our work,2023/11/16,Calculating spectra of adjacent and Laplacian matrices for particular networks Applying Laplac

11、ian spectra to enumerate spanning trees Using Laplacian spectra to determine mean first-passage timeSpectra of transition matrix for some networks and their applications,2023/11/16,Spectra of adjacency matrix for a family of deterministic recursive trees,Journal of Physics A,2009,42:165103.,2023/11/

12、16,Laplacian eigenvalues and eigenvectors of deterministic recursive trees,Physical Review E,2009,80:016104,2023/11/16,Spectra of adjacent matrix and Laplacian matrix of small-world networks,Completed,2023/11/16,Using Laplacian spectra to determine the number of spanning trees in Farey graph,Farey s

13、equence of order n denoted by,2023/11/16,Spanning trees in Farey graph,Two nodes and are linked to each other if they satisfy,Physica A(in revision),Theoretical Computer Science,2011,412:865875,2023/11/16,Spanning trees in scale-free networks,EPL,2010,90:68002.,A counterintuitive conclusion that a n

14、etwork with more spanning trees may be relatively unreliable.,Physical Review E,2011,83:016116.,Fractality can significantly increase the number of spanning trees in fractal scale-free networks.,Journal of Mathematical Physics(in press),2023/11/16,Application of spectra to random walks,Physical Revi

15、ew E,2010,81:031118.,24/43,Vicsek fractals,2023/11/16,Random walks on T fractals,Physical Review E,2010,82:031140,25/43,is obtained from the relationship between characteristic polynomials at different generations.Our method can void the computation of eigenvalues.,2023/11/16,Random Walks on dual Si

16、erpinski gasket,26/43,European Physical Journal B,2011,82:91-96.,Relation to the Hanoi Towers Game,What is the minimum number of moves?,2023/11/16,27/43,The Hanoi Towers Graphs,2023/11/16,28/43,2023/11/16,Spectra of transition matrix:T-fractal,EPL,2011,in press,29/43,We obtain all the eigenvalues and their multiplicities.The reciprocal of the smallest eigenvalue is approximately equal to the mean trapping time,2023/11/16,Spectra of transition matrix:fractal scale-free networks,Completed,30/43,Thank You!,