Tuesday, March 16, 2010
Thursday, July 9, 2009
随机图论相关信息
什么是随机图论？
在研究复杂网络中，研究者使用的主要工具就是随机图理论。该理论创始于上个世纪40年代。由Erdos等人创立。最早提出的经典随机图模型就是ER模型。在随机图中，边的出现成为概率事件。随机图和经典图之间最大的区别在于引入了随机的方法，使得图的空间变得更大，其数学性质也发生了巨大的变化，在随机图的经典数学模型中，随机图上的结点度数分布服从泊松分布。
经过长达60多年的研究，最近由圣塔非的M.E.J Newman等人将随机图中的度数分布扩展到任意度数分布，我们称之为"广义随机图"，这使得对复杂网络的研究有了进一步的深入。虽然我觉得广义随机图理论在解决power-law问题上仍然存在这一定的缺陷。但是至少它在仿真上已经被证实了。
随机图论研究
随机图近十年已成为离散数学的主流之一。目前，2002年排名美国第一大学的普林斯顿大学助理教授、博士导师、图论专家Sudakov正做得不错（1999年才获博士学位，但已是权威的SCI杂志《SIAM Discrete Math》编委和《图论》编委) 。
此领域前辈级的有剑桥大学、微软研究院以大师Lovász(他是世界数学联合会1987-1994年两届包括主席共八个执行委员之一，他的博士学位论文搞Factors图，相交的Factors就是哈密尔顿图)为首的八、九个研究人员。还有一些在这里做博士后的在搞此领域和耶鲁大学、加拿大滑铁卢大学、以色列的特拉维夫大学以及卡内基-梅隆大学（Alan Frieze，他在随机图的哈密尔顿性方面贡献极大）、加利福尼亚大学SD（原美国数学会主席Graham和夫人Chung）、伦敦大学（Colin Cooper，他在随机图的哈密尔顿性领域的贡献也很值得尊敬）、纽约大学（Joel Spencer）、贝尔实验室（Peter Winkler）、瑞典Uppsala大学（Janson Svante）、波兰Adam Mick.大学（Tomasz Luczak）等，而且这些专家都因此成为此领域世界顶尖大师。
一些以随机图为主兼有其它学科还有牛津大学(Colin McDiarmid，也做很密切的Probab.)、加利福尼亚大学-伯克莱(Aldous和Peres，也做密切相关的Probab.)及加利福尼亚州立大学的一些城市的分校、伊利诺斯大学、俄亥俄州立大学、澳大利亚国立大学（Mckay，算最先搞的之一）、匈牙利数学院等。
国内做得最好的有国家重点学科带头人博士导师孟吉翔院长及在Bollobás现任职的大学获得博士学位得其真传的李雨生博士，随机图是有做为的，已有编辑部设于波兰和美国孟菲斯的两个期刊主要发表此学科的论文。
虽随机图历史已较长，现各种限制随机图的哈密尔顿图性问题等也还有很多空白，总体还只处于萌芽阶段。若用PDF可从Sudakov网页的On-line available papers的论文中获得足够的随机图知识。我们这里在致力于一般图及互连网络图的哈密尔顿性和容错哈密尔顿性问题的同时，也正涉及此领域一些哈密尔顿性的工作。
贝洛博洛巴斯教授（ Bela Bollobas ），英国剑桥大学三一学院（Trinity College Cambridge）的数学研究主任，美国孟菲斯大学特聘教授，国际知名组合学和图论专家，国际数学家大会45分钟报告人，匈牙利国家科学院院士。由他所著的《Modern Graph Theory》、《Extremal Graph Theory》及《Random Graph》均为经典图论著作。他参加了首 三届（ 1959 年到 1961 年 ）的国际数学奥林匹克 ，取得2 金 1 铜 ， 是当时唯一取得金牌的学生。Bela Bollobas也是数学大师Paul Erdos最得意的学生之一，他的研究领域广泛涉及有限几何、数论、组合论及图论等，是当今世界最有影响的
数学家之一。
随机图学习资源
1. http://www.math.cmu.edu/~af1p/MAA2005/MAA.html
Random Graphs（这是由Frieze组织的包括卡耐基－梅隆大学、普林斯顿、微软、滑铁卢、多伦多及波兰专家主讲的随机图讲座。这八个专家都是现居随机图前沿的。这八讲虽独立，但基本上循序渐进。国外有许多随机图教材，但我国专家在国内发表的随机图论文不超过3篇，在国外也不超过11篇，我国图论界现也只有张福基、孟吉翔和李雨生教授等各搞一点。就因搞的人少，现还没有一本随机图中文教材，也没有人愿意把英文版翻译过来。特此把Frieze组织的这个最新系列讲座列在这里，期望我国能更大地发展此领域。因随机图的重要性参看与下面的复杂网络的关系）。
随机图应用
近年来人们发现真实世界的复杂网络有所不同于经典随机图，即复杂网络可以从数学上被描述为有大量结点的动态的发展的随机图。不同领域的复杂网络主要有如下：
1) 信息网络：WWW，Internet，计算机共享，Email网，专利使用网
2) 技术网络：电力网，电话线路网，无线通讯网
3) 交通运输网：航线网，铁路网，公路网，自然河流网
4) 社会网：企事业关系网，金融关系网，论文引用，人际关系网，科研合作网
5) 生物网：食物链网，生物神经网，新陈代谢网，蛋白质网，基因网络，细胞网
在研究复杂网络中，研究者使用的主要工具就是随机图理论。该理论创始于上个世纪40年代。由Erdos等人创立。最早提出的经典随机图模型就是ER模型。在随机图中，边的出现成为概率事件。随机图和经典图之间最大的区别在于引入了随机的方法，使得图的空间变得更大，其数学性质也发生了巨大的变化，在随机图的经典数学模型中，随机图上的结点度数分布服从泊松分布。
经过长达60多年的研究，最近由圣塔非的M.E.J Newman等人将随机图中的度数分布扩展到任意度数分布，我们称之为"广义随机图"，这使得对复杂网络的研究有了进一步的深入。虽然我觉得广义随机图理论在解决power-law问题上仍然存在这一定的缺陷。但是至少它在仿真上已经被证实了。
随机图论研究
随机图近十年已成为离散数学的主流之一。目前，2002年排名美国第一大学的普林斯顿大学助理教授、博士导师、图论专家Sudakov正做得不错（1999年才获博士学位，但已是权威的SCI杂志《SIAM Discrete Math》编委和《图论》编委) 。
此领域前辈级的有剑桥大学、微软研究院以大师Lovász(他是世界数学联合会1987-1994年两届包括主席共八个执行委员之一，他的博士学位论文搞Factors图，相交的Factors就是哈密尔顿图)为首的八、九个研究人员。还有一些在这里做博士后的在搞此领域和耶鲁大学、加拿大滑铁卢大学、以色列的特拉维夫大学以及卡内基-梅隆大学（Alan Frieze，他在随机图的哈密尔顿性方面贡献极大）、加利福尼亚大学SD（原美国数学会主席Graham和夫人Chung）、伦敦大学（Colin Cooper，他在随机图的哈密尔顿性领域的贡献也很值得尊敬）、纽约大学（Joel Spencer）、贝尔实验室（Peter Winkler）、瑞典Uppsala大学（Janson Svante）、波兰Adam Mick.大学（Tomasz Luczak）等，而且这些专家都因此成为此领域世界顶尖大师。
一些以随机图为主兼有其它学科还有牛津大学(Colin McDiarmid，也做很密切的Probab.)、加利福尼亚大学-伯克莱(Aldous和Peres，也做密切相关的Probab.)及加利福尼亚州立大学的一些城市的分校、伊利诺斯大学、俄亥俄州立大学、澳大利亚国立大学（Mckay，算最先搞的之一）、匈牙利数学院等。
国内做得最好的有国家重点学科带头人博士导师孟吉翔院长及在Bollobás现任职的大学获得博士学位得其真传的李雨生博士，随机图是有做为的，已有编辑部设于波兰和美国孟菲斯的两个期刊主要发表此学科的论文。
虽随机图历史已较长，现各种限制随机图的哈密尔顿图性问题等也还有很多空白，总体还只处于萌芽阶段。若用PDF可从Sudakov网页的On-line available papers的论文中获得足够的随机图知识。我们这里在致力于一般图及互连网络图的哈密尔顿性和容错哈密尔顿性问题的同时，也正涉及此领域一些哈密尔顿性的工作。
贝洛博洛巴斯教授（ Bela Bollobas ），英国剑桥大学三一学院（Trinity College Cambridge）的数学研究主任，美国孟菲斯大学特聘教授，国际知名组合学和图论专家，国际数学家大会45分钟报告人，匈牙利国家科学院院士。由他所著的《Modern Graph Theory》、《Extremal Graph Theory》及《Random Graph》均为经典图论著作。他参加了首 三届（ 1959 年到 1961 年 ）的国际数学奥林匹克 ，取得2 金 1 铜 ， 是当时唯一取得金牌的学生。Bela Bollobas也是数学大师Paul Erdos最得意的学生之一，他的研究领域广泛涉及有限几何、数论、组合论及图论等，是当今世界最有影响的
数学家之一。
随机图学习资源
1. http://www.math.cmu.edu/~af1p/MAA2005/MAA.html
Random Graphs（这是由Frieze组织的包括卡耐基－梅隆大学、普林斯顿、微软、滑铁卢、多伦多及波兰专家主讲的随机图讲座。这八个专家都是现居随机图前沿的。这八讲虽独立，但基本上循序渐进。国外有许多随机图教材，但我国专家在国内发表的随机图论文不超过3篇，在国外也不超过11篇，我国图论界现也只有张福基、孟吉翔和李雨生教授等各搞一点。就因搞的人少，现还没有一本随机图中文教材，也没有人愿意把英文版翻译过来。特此把Frieze组织的这个最新系列讲座列在这里，期望我国能更大地发展此领域。因随机图的重要性参看与下面的复杂网络的关系）。
随机图应用
近年来人们发现真实世界的复杂网络有所不同于经典随机图，即复杂网络可以从数学上被描述为有大量结点的动态的发展的随机图。不同领域的复杂网络主要有如下：
1) 信息网络：WWW，Internet，计算机共享，Email网，专利使用网
2) 技术网络：电力网，电话线路网，无线通讯网
3) 交通运输网：航线网，铁路网，公路网，自然河流网
4) 社会网：企事业关系网，金融关系网，论文引用，人际关系网，科研合作网
5) 生物网：食物链网，生物神经网，新陈代谢网，蛋白质网，基因网络，细胞网
Wednesday, January 7, 2009
Information Theory (信息论主题)
Study Note:
Theorem 2.7.4 (P31) The mutual information I(X;Y) is a convex function of p(y|x) for fixed p(x).
Hint: the key here is to consider I(X;Y) as function of p(x) and p(y|x) on one hand, and to use the relationship I(X;Y)=D(p(x,y)||p(x)p(y)) on the other hand.
To prove the convexity of I(X;Y)=I(p(x),p(y|x)) about p(y|x) is to demonstrate
I(p(x),up1(y|x)+(1-u)p2(y|x))<=uI(p(x),p1(y|x))+(1-u)I(p(x),p2(y|x)).
it is true because
I(p(x),up1(y|x)+(1-u)p2(y|x))
=D(u*p1(x,y)+(1-u)*p2(y|x)||p(x)(u*p1(y)+(1-u)*p2(y)))
<=uD(p1(x,y)||p(x)p1(y))+(1-u)D(p2(x,y)||p(x)p2(y))
=u*I(p(x),p1(y|x))+(1-u)I(p(x),p2(y|x))
[note that the expression of D(p||q) according to I(X;Y) is decided by the corresponding combine distribution of p(x,y) and marginals p(x) and p(y), so here basiclly is the change of form. Also note hat p1(x)=p2(x)=p(x)]
Theorem 2.7.4 (P31) The mutual information I(X;Y) is a convex function of p(y|x) for fixed p(x).
Hint: the key here is to consider I(X;Y) as function of p(x) and p(y|x) on one hand, and to use the relationship I(X;Y)=D(p(x,y)||p(x)p(y)) on the other hand.
To prove the convexity of I(X;Y)=I(p(x),p(y|x)) about p(y|x) is to demonstrate
I(p(x),up1(y|x)+(1-u)p2(y|x))<=uI(p(x),p1(y|x))+(1-u)I(p(x),p2(y|x)).
it is true because
I(p(x),up1(y|x)+(1-u)p2(y|x))
=D(u*p1(x,y)+(1-u)*p2(y|x)||p(x)(u*p1(y)+(1-u)*p2(y)))
<=uD(p1(x,y)||p(x)p1(y))+(1-u)D(p2(x,y)||p(x)p2(y))
=u*I(p(x),p1(y|x))+(1-u)I(p(x),p2(y|x))
[note that the expression of D(p||q) according to I(X;Y) is decided by the corresponding combine distribution of p(x,y) and marginals p(x) and p(y), so here basiclly is the change of form. Also note hat p1(x)=p2(x)=p(x)]
Friday, January 2, 2009
Matlab主题
1. Useful Links
Mathworks - 公司主页
http://www.mathworks.com/access/helpdesk/help/techdoc/matlab.shtml
MATLAB Central - an open exchange for Matlab and Simulink community
其中fileexchange目录下有世界各地的MATLAB编程爱好者提供的各种MATLAB函数，有很强的使用价值http://www.mathworks.com/matlabcentral/index.html
MAThTools站点 有很多好的工具箱或者小的辅助函数：http://www.mathtools.net/MATLAB/index.html
国内中文站点
1，我爱matlab：http://www.ilovematlab.cn/
2,MATLAB大观园：http://matlab.myrice.com/
3,MATLAB中国论坛|实验室爱好者之家 针对学生，科研工作者 http://www.labfans.com/
2.Study Note
Mathworks - 公司主页
http://www.mathworks.com/access/helpdesk/help/techdoc/matlab.shtml
MATLAB Central - an open exchange for Matlab and Simulink community
其中fileexchange目录下有世界各地的MATLAB编程爱好者提供的各种MATLAB函数，有很强的使用价值http://www.mathworks.com/matlabcentral/index.html
MAThTools站点 有很多好的工具箱或者小的辅助函数：http://www.mathtools.net/MATLAB/index.html
国内中文站点
1，我爱matlab：http://www.ilovematlab.cn/
2,MATLAB大观园：http://matlab.myrice.com/
3,MATLAB中国论坛|实验室爱好者之家 针对学生，科研工作者 http://www.labfans.com/
2.Study Note
数学网络资源
1.General
mainly Advanced Algebra, Topology and Math Physics
http://www.sclsoft.com/Library/豆丁图书馆.aspx
2.Analysis
The first 4 chapters of Terence Tao's(陶轩哲) analysis book
http://www.math.unm.edu/~crisp/courses/math401/tao.pdf
3.Algebra
Element of Abstrct and Linear Algebra
http://www.math.miami.edu/~ec/book/book.pdf
Abstract Algebra (first Grad year) and some other Algebra materials
http://www.math.uiuc.edu/~r-ash/
4.Probability, Statistics & Stochastic Processes
mainly Advanced Algebra, Topology and Math Physics
http://www.sclsoft.com/Library/豆丁图书馆.aspx
2.Analysis
The first 4 chapters of Terence Tao's(陶轩哲) analysis book
http://www.math.unm.edu/~crisp/courses/math401/tao.pdf
3.Algebra
Element of Abstrct and Linear Algebra
http://www.math.miami.edu/~ec/book/book.pdf
Abstract Algebra (first Grad year) and some other Algebra materials
http://www.math.uiuc.edu/~r-ash/
4.Probability, Statistics & Stochastic Processes
Subscribe to:
Posts (Atom)