上海交通大学自动化系研究生课程 Graduate Course at the Dept. of
Automation, SJTU (Spring 2006)
复杂网络与混沌控制Complex
Networks and Chaos Control
Time & Place: Monday
Instructor:
汪小帆(Xiaofan Wang) Email: xfwang@sjtu.edu.cn Tel.: 54744831 Office: SEIEE 2-423
******************************************************************************************************************
1. 课程介绍Course Description
如果说二十一世纪的科学有一个共同的主题的话，那么这个主题也许就是“探索复杂性”。本课程将介绍复杂性研究的两个主要工具：从广义上说是非线性科学和网络科学，从狭义上说是混沌和复杂网络理论。尽管世界在本质上是非线性的，有关非线性的课程却很少；尽管人类社会的生存和发展日益依赖于各种各样的大规模复杂网络，传统的课程却很少涉及人类对复杂网络的认识。二十世纪中叶以来，在探索各种复杂非线性现象之间的共性的基础上诞生的非线性科学取得了长足的进展；二十世纪末以来，在探索各种复杂网络之间的共性的基础上正在兴起一门新科学—网络科学。本课程将以鸟瞰的方式介绍非线性科学和网络科学的中心内容—混沌和复杂网络理论。对于混沌理论将着重介绍混沌、分形、分叉和混沌控制等基本概念；对于复杂网络理论则在介绍小世界和无标度等基本概念的基础上，让学生阅读最新文献以了解复杂网络研究的最新进展。
本课程主要针对工科研究生，先修课程为线性代数和线性系统基础。
If there is a common theme for
science in 21th century, then the theme might be “exploring complexity”. This
course will introduce two main tools for the study of complexity: nonlinear
science and network science in general; chaos theory and complex network theory
in particular. Even though the world is inherently nonlinear, students are mainly trained to focus on linear
phenomena, models, and analysis techniques that play a paramount role among the
tools commonly employed to solve many practical tasks; Although the survival
and developing of mankind are increasingly depending on a wide variety of
large-scale complex networks, traditional
curriculum has very little room for our understanding on complex networks. Since the middle of 20th
century, nonlinear science which was born from exploring the common features of
different kinds of complex nonlinear phenomena has made significant progress;
While since the end of 20th century, we have witnessed the emergence of a new
science-network science from exploring the common features of different kinds
of complex networks. This course will give the students a bird’s eye view of
the central topics in nonlinear science and network science-chaos and complex
netwotk theory. For the chaos theory, this course will focus on the basic
concepts such as chaos, fractal, bifurcation and chaos control. For the complex
network theory, the students will be required to read some newest papers so as
to have a feeling of the state-of-art of complex network research, based on a
understanding of the basic concepts such as small-world and scale-free in
complex network theory.
The course will be taught at a level accessible to
graduate students in fields of engineering. The prerequisites include
introductory-level background in linear algebra and linear system.
2. 课程大纲Course Outline
一、复杂网络理论 Complex Network
Theory
1. 引言 Introduction
1.1 What are complex networks
and complex network theory? 1.2
History of complex network study: from Euler to Erdos 1.3 Some basic definitions and notations
2. 复杂网络模型Complex Network
Models
2.1 Small-World Models 2.2 Scale-Free Models 2.3 Internet topology generators 2.4 Weighted Network Models
3. 复杂网络上的过程Processes on
Complex Networks
3.1 Spreading Dynamics 3.2 Cascading failures 3.3 Searching 3.4 Synchronization 3.5 Control
二、混沌及其控制Chaos and its
Control
1. 引言：从线性到非线性 Introduction:
From linear to nonlinear
2. 混沌简介 A brief
introduction to chaos
3. 分形简介 A brief
introduction to fractal
4. 分叉简介 A brief
introduction to bifurcation
5. 混沌控制与同步 Chaos control and
synchronization
3. 教材Textbooks
Ø 汪小帆、李翔、陈关荣，复杂网络理论及其应用，清华大学出版社，2006 （将给注册上课学生每人赠送一本）
Wang
X F, Li X, Chen G. Complex Network
Theory and Its Application, Qinghua Publisher, 2006
Ø Kapitaniak T. Chaos for Engineers: theory, application and control, Springer, 2000（可借阅）
Ø Strogatz S H. Nonlinear Dynamics and Chaos. Addison-Wesley, 1994（可借阅）
4. 考核要求
本课程要求学生就复杂网络中的某一课题在查阅文献的基础上提交书面报告并在课堂上用PPT做20分钟的口头报告。以下列出一些值得研究的课题（仅供参考）：
l 一些实际网络的建模需要考虑节点之间的地理上的距离，关于这方面的研究参见综述[8]的2.5节Spatio
networks
l 许多网络的拓扑其实是随时间演化的（如Internet、WWW），如何刻画时变拓扑网络的特征有可能是下一阶段网络拓扑性质分析与建模的一个重要课题。J. Leskovec, J. Kleinberg, C.
Faloutsos. Graphs
over Time: Densification Laws, Shrinking Diameters and Possible Explanations.
Proc. 11th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2005
(Best research paper)
l 关于复杂网络的鲁棒性和脆弱性，近年有很多的研究，请见综述[8]的3.1节和综述[5]，以及 J. Kleinberg, M. Sandler,
A. Slivkins. Network
Failure Detection and Graph Connectivity. Proc. 15th ACM-SIAM Symposium on
Discrete Algorithms, 2004 (In PDF)
l 一个大型软件可以看作一个复杂网络；而许多软件之间也是相互关联的，因此，把一个软件看作一个节点，则众多软件也构成了复杂网络。从复杂网络理论角度研究软件系统也许会带来软件工程的新发展。特别推荐Sergi Valverde的主页（包括他的博士论文）。另一篇文章可见C.
R. Myers. "Software
systems as complex networks: structure, function, and evolvability of software
collaboration graphs", Phys. Rev. E 68, 046116 (2003)
l 语言也可以看作一个复杂网络，可见综述：Sole, R. V.,
Corominas,
B., Valverde,
S. and Steels,
L. (2005). Language
Networks: their structure, function and evolution , Trends
in Cognitive Sciences,2006
l
如何运用复杂网络理论构建创新研究团队？请看Amaral’s Group的文章：Guimera, R, Uzzi, B, Spiro, J & Amaral, L. Team assembly mechanisms
determine collaboration network structure and team performance. Science 308,
697-702 (2005). [PDF
file]以及Barabasi对这篇文章的介绍 Network Theory—the Emergence
of the Creative Enterprise, Science
308, 639(2005).
l 关于复杂网络上的搜索算法可见综述[8]的7.2节，特别推荐访问这一研究的开拓者J.
Kleinberg的主页及其综述 Complex Networks
and Decentralized Search Algorithms. Proceedings of the International
Congress of Mathematicians (ICM), 2006
l Amaral’s Group关于复杂网络模块化的文章：Guimera, R, & Amaral, L. Cartography
of complex networks: modules and universal roles, J. Stat. Mech.-Theory
Exp. -1, art. no. P02001,
1-13 (2005). [PDF
file] Guimera, R, & Amaral, L.
Functional
cartography of complex metabolic networks, Nature 433,
895-900 (2005) [PDF
file]
l 关于复杂网络理论在生物学中的应用的研究非常活跃。无标度网络研究的先驱Barabasi和Albert现在都在从事该领域的研究。Barabasi在Center for Cancer Systems Biology, Dana-Farber
Cancer Institute, Harvard University访问，而Albert从Barabasi那里博士毕业后就到了Department
of Physics, Pennsylvania State University从事生物物理和网络建模研究。两人分别撰写了研究综述：A.-L. Barabási & Z. N. Oltvai. Network
Biology: Understanding the Cells's Functional Organization, Nature Reviews Genetics 5, 101-113
(2004); R.
Albert. Scale-free networks in
cell biology, Journal
of Cell Science 118, 4947-4957 (2005).
l 在分析网络性质时如何合理地评价得到的结论值得考虑，否则的话很可能会产生谬误：“great
care has to be taken to put the analysis on solid statistical grounds.
Otherwise, our analysis will only tell
us what we want to hear.” 这篇文章值得一读：Amaral,
L Guimera, R.
Lies, damned lies and bad statistics, Nature
Phys. 
。对应的文章为：Detecting
rich-club ordering in complex networks
5. 综述文章Survey Papers
[1] Strogatz S H. Exploring
complex networks. Nature, 2001, 410:
268-276
[2] Albert R, Barabási A-L. Statistical
mechanics of complex networks. Reviews of Modern Physics, 2002, 74: 47-97
[3] Dorogovtsev S N, Mendes J F F. Evolution of
networks. Advances in Physics, 2002, 51:
1079-1181
[4] Wang X F. Complex
networks: Topology, dynamics and synchronization. Int. J. Bifurcation and Chaos, 2002, 21(5): 885-916
[5] Newman M E J. The
structure and function of complex networks.
[6] Wang X F, Chen
G. Complex networks: Small world, scale free and
beyond. IEEE Circuits and System Magazine, 2003, 3(1):
6-21
[7]
[8] Boccaletti S, Latora V,
[9] L da F. Costa,
F. A. Rodrigues, G. Travieso and P. R. Villas Boas.
Characterization
of complex networks: A survey of measurements. cond-mat/0505185
6. 复杂网络相关书目Complex Network Related Books
专著和会议录 Monograph and Proceedings:
|
[1]
这本书是围绕着作者于1998年发表在Nature上的小世界模型而展开的，可以说是第一本从数学和物理角度阐述小世界现象及其对系统动力学影响的著作。 Everyone
knows the small-world phenomenon: soon after meeting a stranger, we are
surprised to discover that we have a mutual friend, or we are connected
through a short chain of acquaintances. In his book, Duncan Watts uses this
intriguing phenomenon--colloquially called "six degrees of
separation"--as a prelude to a more general exploration: under what
conditions can a small world arise in any kind of network? The networks of
this story are everywhere: the brain is a network of neurons; organizations
are people networks; the global economy is a network of national economies,
which are networks of markets, which are in turn networks of interacting
producers and consumers. Food webs, ecosystems, and the Internet can all be
represented as networks, as can strategies for solving a problem, topics in a
conversation, and even words in a language. Many of these networks, the
author claims, will turn out to be small worlds. How do such networks matter? Simply put, local actions can have
global consequences, and the relationship between local and global dynamics
depends critically on the network's structure. |
|
|
[2] Bornholdt S, Schuster
H G. (ed.) Handbook
of Graphs and Networks: From the Genome to the Internet. 本书是由复杂网络领域知名学者各自撰写的综述性质的文章合成的，有助于了解03年之前的主要研究进展并感受不同学者的研究风格。 This book defines
the field of complex interacting networks in its infancy and presents the
dynamics of networks and their structure as a key concept across disciplines.
The contributions present common underlying principles of network dynamics
and their theoretical description and are of interest to specialists as well
as to the non-specialized reader looking for an introduction to this new
exciting field. Theoretical concepts include modeling networks as dynamical
systems with numerical methods and new graph theoretical approaches, but also
focus on networks that change their topology as in morphogenesis and self-organization.
The authors offer concepts to model network structures and dynamics, focusing
on approaches applicable across disciplines. Authors of the book include: L. A. Adamic, Uri Alon, Daniel ben-Avraham,
A-L Barabasi, B. Bollobas, R. Cohen, S. N. Dorogovtsev, S. Bornholdt is Professor of Theoretical Physics and heads the
Statistical Physics Group of the |
|
|
[3] Dorogovtsev S
N, Mendes J F. Evolution of Networks: From
Biological Nets to the Internet and WWW. 这是两位作者在02年发表于Advances in Physics上的综述文章扩充而成的，因此只要看一下那篇综述就可以了。 Only recently did
mankind realize that it resides on a world of networks. The Internet and the
World Wide Web are changing our life. Our physical existence is based on
various biological networks. We have recently learned that the term
"network" turns out to be a central notion in our time, and the consequent explosion of interest in
networks is a social and cultural phenomenon. The principles of the complex
organization and evolution of networks, natural and artificial are the topic
of this book, which is written by physicists and is addressed to all involved
researchers and students. The aim of the text
is to understand networks and the basic principles of their structural organization
and evolution. The ideas are presented in a clear and pedagogical way, with
minimal mathematics, so even students without a deep knowledge of mathematics
and statistical physics will be able to rely on this as a reference. Special attention is given to real
networks, both natural and artificial. Collected empirical data and numerous
real applications of existing theories are discussed in detail, as well as
the topical problems of communication networks. |
|
|
[4] Pastor-Satorras
R, Rubi M, Diaz-Guilera A (Eds.). Statistical Mechanics of
Complex Networks. 与[2]类似，也是文章合集。 Networks can provide
a useful model and graphic image useful for the description
of a wide variety of web-like structures in the physical and
man-made realms, e.g. protein networks, food webs and the
Internet. The contributions gathered in the present volume provide both an
introduction to, and an overview of, the multifaceted phenomenology of
complex networks. Statistical Mechanics of Complex Networks also
provides a state-of-the-art picture of current theoretical methods and
approaches. |
|
|
[5] Pastor-Satorras R, Vespignani A. Evolution and Structure of the Internet: A
Statistical Physics Approach. Cambridge University
Press, 2004 这是一本介绍应用复杂网络理论研究Internet结构与演化的著作。 Viewed in this
analysis from a statistical physics perspective, the Internet is perceived as
a developing system that evolves through the addition and removal of nodes
and links. This perspective permits the authors to outline the dynamical
theory that can appropriately describe the Internet's macroscopic evolution.
The presence of such a theoretical framework will provide a revolutionary way
of enhancing the reader's understanding of the Internet's varied network
processes. |
|
|
[6] Ben-Naim E, Frauenfelder H, Toroczkai Z (Eds.). Complex Networks. Berlin: Springer-Verlag, 2004 与[2][4]类似，也是文章合集。 This volume is devoted to the applications of techniques from statistical physics to the characterization and modeling of complex networks. The first two parts of the book concern theory and modeling of networks, the last two parts survey applications to a wide variety of natural and artificial networks. The tutorial reviews tha |
