分形网络结构性质、建模与动力学.ppt

Fractal Networks: Structures, Modeling, and Dynamics,章 忠 志 复旦大学计算机科学技术学院 Email: Homepage: /zhangzz/ Blog: /home.php?mod=space&uid=311410,网络结构分析和拓扑识别学术研讨会,Main Contents,Small-world Effect,Remarkable properties of networks,Scale-free Property,OR,Fractal Behavior,Small world seemingly contradicts fractality!,Many real networks are fractal,-dB,log(lB),log(NB),fractal,Non-fractal,Protein interaction network,Hollywood film actor network,Metabolic network,World Wide Web,Box-covering method,Song, Havlin, and Makse, Nature (2005),Fractal biological networks,Metabolic,Protein interaction,Song, Havlin, Makse, Nature (2005),Three domains of life: archaea, bacteria, eukaria,E. coli, H. sapiens, yeast,43 organisms - all scale,Fractal information and social networks,World Wide Web, domain,Hollywood film actors,212,000 actors,300,000 web-pages,Other bio networks: Khang and Bremen groups Internet is not fractal!,Most efficient box-covering method,4 boxes,5 boxes,Mapping to graph colouring problem Greedy algorithm to find minimum boxes,J. Stat. Mech. (2007) P03006,Invariant of scaling under renormalization,k=2,renormalization,s=1/4,k=8,Gallos et al. PNAS (2007),and,follow the same distribution.,: exponent of the boxes,Renormalization of WWW with,Degree distribution of WWW,2019/5/1,Scaling relations,Numboer of boxes,Box size,Degree of box,Structural properties of fractal networks,Fractal networks are disassortative Betweennees distribution The number of spanning trees in fractal networks is larger than that in non-fractal networks,2019/5/1,2019/5/1,Brief introduction to spanning trees,Number of spanning trees:,EPL (Europhysics Letters), 2010, 90:68002.,Entropy of spanning trees:,The larger the entropy, the larger the number of spanning trees.,2019/5/1,Spanning trees in a non-fractal scale-free web,The entropy for spanning trees in square lattice is 1.16624,A counterintuitive conclusion that a network with more spanning trees may be relatively unreliable.,EPL, 2010, 90:68002,2019/5/1,Spanning trees in a fractal scale-free network,Physical Review E, 2011, 83:016116,Fractality can significantly increase the number of spanning trees in fractal scale-free networks.,A model of fractal scale-free network,2019/5/1,European Physical Journal B, 2007, 56:259-27.,large-world,disassortative,2019/5/1,Model: from fractal to non-fractal SF trees,EPJ B, 2008, 64:277-283,2019/5/1,A model for fractal and nonfractal scale-free networks with identical degree sequences,Physical Review E, 2009, 79: 031110.,Advantages： without crossing edges always connected,As q drops from 1 to 0, it undergoes transitions from large to small world and from fractal to non-fractal.,Impact of fractality on dynamics,2019/5/1,Robustness (Reliability) Percolation Disease spreading Random walks Synchronization Game ,Fractal networks are more robust under intentional attack,2019/5/1,Nature Physics, 2002, 2:275-281. European Physical Journal B, 2007, 56:259-27.,Relative size of the largest cluster, S, and the average size of the remaining isolated clusters, as a function of the removal fraction f of the largest hubs.,Bond percolation: nonzero thresholds,2019/5/1,It is in contrast to the conventional wisdom that null percolation threshold is an intrinsic nature of scale-free networks.,PRE, 2009, 79: 031110,Fractality can resist disease spread,2019/5/1,SI model:,J. Phys. A, 2010, 43:065001,SIR model: nonzero epidemic thresholds,J. Stat. Mech. (2008) P09008,2019/5/1,Trapping problem: Random walks on graphs with an immobile trap,Trapping time (TT) for node i denoted by Average trapping time (ATT),Research goal: obtain the dependence of average trapping time on the system size N.,2019/5/1,Previous work: ATT on Sierpinski gasket and complete graph,PRE, 2002, 65: 021105.,New J. Phys. 7, 26 (2005),2019/5/1,Walks on nonfractal scale-free nets,PRE, 2009, 79: 021127.,New finding: ATT scales sublinearly with network size.,EPL, 2009, 86: 10006.,2019/5/1,Walks on a fractal scale-free tree,EPL, 2009, 88: 10001.,Conclusion: fractality can induce a general slowing down of diffusion.,2019/5/1,Trapping time in fractal and non-fractal scale-free networks with identical degree sequences,Physical Review E, 2009, 80: 061111,27/43,2019/5/1,Significant impact of trap position on ATT in non-fractal scale-free trees,Journal of Mathematical Physics, 2009, 50: 033514.,Journal of Physics A, 2011, 44: 075102,2019/5/1,No essential impact of trap position on MTT in fractal scale-free trees,Journal of Physics A, 2011, 44: 075102.,The networks seem homogeneous in this sense.,Fractality plays a dominant role in determining the ATT in fractal scale-free networks.,2019/5/1,No qualitative effect of trap location on MFPT in extended T-graphs,Physical Review E, 2010, 82: 031140. New Journal of Physics, 2009, 11: 103043.,Impact of fractality on synchronization and game,2019/5/1,Fractality suppresses the synchoronizability in sc