[哲学]第六届全国网络科学论坛与第二届全国混沌应用研讨会.ppt

Random walks in complex networks 章 忠 志 复旦大学计算科学技术学院 Email: zhangzz@ Homepage: /~zhangzz/ 2010年7月26-31日 Contents Brief introduction to our group Research directions: structure and dynamics in networks Modeling networks and Structural analysis Spectrum analysis and its application Enumeration problems: spanning trees, perfect matching, Hamilton paths Dynamics: Random walks, percolation Random Walks on Graphs Random Walks on Graphs At any node, go to one of the neighbors of the node with equal probability. Random Walks on Graphs At any node, go to one of the neighbors of the node with equal probability. Random Walks on Graphs At any node, go to one of the neighbors of the node with equal probability. Random Walks on Graphs At any node, go to one of the neighbors of the node with equal probability. Random Walks on Graphs At any node, go to one of the neighbors of the node with equal probability. Important parameters of random walks Applications of random walks PageRank algorithm Community detection Recommendation systems Electrical circuits (resistances) Information Retrieval Natural Language Processing Machine Learning Graph partitioning In economics: random walk hypothesis Application to Community detection World Wide Web Citation networks Social networks Biological networks Food Webs Application to recommendation systems Connections with electrical networks Every edge – a resistor of 1 ohm. Voltage difference of 1 volt between u and v. R(u,v) – inverse of electrical current from u to v. Random walks and other topologies Communtity structure Spanning trees Average distance Our work Random walks on scale-free networks A pseudofractal scale-free web Apollonian networks Modular scale-free networks Koch networks A fractal scale-free network Scale-free networks with the same degree sequences Random walks on exponential networks Random walks on fractals Main contributions Methods for finding Mean first-passage time (MFPT) Backward equations G