博文
乱谈网络和图论
||
大约是在2002年前后，我们组一位曾经做过广义相对论和粒子物理的年轻教师开始对复杂网络感兴趣，我的一个博士生在硕士期间做过一些生物方面的事，希望接着做下去。于是，我就请这位青年教师带着这位博士生一起做点网络和生物联系起来的工作。 在他们的工作过程中，经常会告诉我一点复杂网络的ABC，听多了，似乎也知道了一点皮毛，于是就写下了几行字的介绍，主要是想把这点皮毛知识告诉别的学生。2006年，从要报废的计算机中翻出了这个介绍，稍整理了一下，发在一个论坛上。现在为祝贺圈的成立，再拿来发表一次。这应该是我写过的唯一一篇关于网络的文字，肤浅而又欠准确。对于复杂网络及其相关的研究，我认为非常重要，也很有前途，无奈精力所限，未能参与，希望通过“复杂网络圈”，能知道更多。
网络这一阵很热. www网在很大程度上改变了人们的生活方式. 细胞可以描述为由化学反应连接的网. 电话网, 文章的引用等等, 都可以用网络描述. 对于网络背后的基础, 知道的人并不多. 网络的基础之一就是图论, 大数学家欧勒很久以前就研究过. 图论好像是计算机科学的必修课, 但学习计算机技术的是否修这门课就不得而知了. 现在很多地方对于掌握计算机技术的定义好像是会用Windows就行, 哪自然是用不着学习图论的.
其实, 经典的图就是一对集合的集合, G=(V, E), V是一些顶点的集合, E是连接某些顶点对的边(线)的集合. 图在理论物理中很有用, 费曼当年做量子电动力学的微扰论, 就靠画图, 结果往往一个晚上就能算出别人花半年才能算出的结果. 后来搞清楚了, 按照某种规则画的费曼图和微扰论级数完全对应, 证明这一点的是戴森, 一个英国的数学家, 当时在普林斯顿高等研究所, 此后, 戴森就成为理论物理学家了. 由于戴森的证明, 画图的费曼, 利用泛函的薛温格和一个使用正统工具的日本人合得了炸药奖. 戴森则一直没有机会去斯德哥尔摩去过把得奖的瘾. 后来, 戴森就改行写畅销书了. 其实, 薛温格的泛函就是费曼的图的生成泛函. 在统计物理中, 非理想气体的微扰论也是图论, 配分函数就是买厄图的生成函数, 自由能是连接图的生成函数, 而热力势是不可约图的生成函数. 李政道先生的《统计力学》把这一部分讲的非常精彩, 可惜现在的大学, 研究生的统计物理都不学这些, 只算算第二位力系数就糊弄过去了.
在复杂网络研究中经常用到随机图论, 通俗地说, 就是让E中的线随机地和V中的点对连接. 这方面开创性地工作是Erdos和Renyi两位匈牙利的数学家做的, 时间大约是上世纪的50年代末60年代初.他们最早考虑的是N个顶点, n条线, 每对点被连接的几率相同. 所以图的总数就是N(N-1)/2 个顶点对中取出n个对的方式, C(n, N(N-1)/2), 每个图出现的几率都相同.
另一种随机图的定义是说每一对点被连接的可能性(几率)是p, 这样, 如果给定了N个点, 连线则是一个随机变量, 它的平均值(数学上好像叫做期望值)是p(N(N-1)/2). 显然, 得到一个n条线的图的几率就是 p^n(1-p)^{N(N-1)/2-n}.
图也可以用矩阵来表示, 如果给N个点编号, 例如从1到N, 我们就可以对每一个特定的图写出一个矩阵, 如果点i和j相连, 则对应的矩阵元取1, 否则取0. 这样, 就可以建立图和矩阵的一一对应关系. 代替研究图, 我们也可以研究这类矩阵.
描述图需要几个特征量, 一个是它的度(degree). 如果与某个顶点连接的线有k条, 就说这个顶点的度是k. 对于由有向线连接的图, 还要区分入度(in-degree)和出度(out-degree). k 的分布则给定了随机图的局域连接的状态. 第二个重要的量是图的直径. 如果我们取每一条线的长度是单位长度, 图中的任意二个点可能直接连接, 我们说这两个点相距为1; 也可能通过别的点间接连接, 其距离是从其中一点到另一点的最短的路径上的连线数; 当然, 也可能不连接, 那它们之间的距离就是无限大. 互相直接或间接连接的点构成集团, 一个集团中任何两个点之间的最大距离定义为集团的直径, 而一个图的所有集团的直径中最大的那个则定义为图的直径. 随机图的直径一般都很小. 第三个特征量是成团系数, 如果图的一个顶点有z个最近邻顶点, 这些最近邻顶点可以构成z(z-1)/2个可能的对, 这些对中平均来说有y个被连接, 则y与可能的对的数目之比为成团系数.
SCI这几年在我国的科学界炒的很热, 其实, 论文的引用就是一个简单的网络. 在某个给定的集合中每一篇论文是一个顶点, 而引用构成连线. 这个引用的网络是有向的. Redner研究了ISI的783339篇论文和Physical Review D 1975—1994年间的24296篇论文的引用网络, 发现一篇文章被引用k次(in-degree)的几率符合幂次规律, 并发现这个指数大约等于3.
一种非常有趣的网络是所谓的小世界网络，在最近几年，这是研究的热点之一。其中特别著名的一个早期的关于小世界网的例子是所谓的6度分离。在世界上随便找两个人，通过这两个人的熟人建立联系，平均说来，中间需要6个人。6是个很小的数字，这个结果有点出乎预料之外。但是，如果你在坐火车的时候喜欢闲聊的话，你会经常发现你的邻座竟然认识一个你的朋友，这其实就是6度分离的一个例证。
http://blog.sciencenet.cn/blog-2402-273916.html
上一篇：关于老院士和老非院士
下一篇：还可以这样炒作
网络这一阵很热. www网在很大程度上改变了人们的生活方式. 细胞可以描述为由化学反应连接的网. 电话网, 文章的引用等等, 都可以用网络描述. 对于网络背后的基础, 知道的人并不多. 网络的基础之一就是图论, 大数学家欧勒很久以前就研究过. 图论好像是计算机科学的必修课, 但学习计算机技术的是否修这门课就不得而知了. 现在很多地方对于掌握计算机技术的定义好像是会用Windows就行, 哪自然是用不着学习图论的.
其实, 经典的图就是一对集合的集合, G=(V, E), V是一些顶点的集合, E是连接某些顶点对的边(线)的集合. 图在理论物理中很有用, 费曼当年做量子电动力学的微扰论, 就靠画图, 结果往往一个晚上就能算出别人花半年才能算出的结果. 后来搞清楚了, 按照某种规则画的费曼图和微扰论级数完全对应, 证明这一点的是戴森, 一个英国的数学家, 当时在普林斯顿高等研究所, 此后, 戴森就成为理论物理学家了. 由于戴森的证明, 画图的费曼, 利用泛函的薛温格和一个使用正统工具的日本人合得了炸药奖. 戴森则一直没有机会去斯德哥尔摩去过把得奖的瘾. 后来, 戴森就改行写畅销书了. 其实, 薛温格的泛函就是费曼的图的生成泛函. 在统计物理中, 非理想气体的微扰论也是图论, 配分函数就是买厄图的生成函数, 自由能是连接图的生成函数, 而热力势是不可约图的生成函数. 李政道先生的《统计力学》把这一部分讲的非常精彩, 可惜现在的大学, 研究生的统计物理都不学这些, 只算算第二位力系数就糊弄过去了.
在复杂网络研究中经常用到随机图论, 通俗地说, 就是让E中的线随机地和V中的点对连接. 这方面开创性地工作是Erdos和Renyi两位匈牙利的数学家做的, 时间大约是上世纪的50年代末60年代初.他们最早考虑的是N个顶点, n条线, 每对点被连接的几率相同. 所以图的总数就是N(N-1)/2 个顶点对中取出n个对的方式, C(n, N(N-1)/2), 每个图出现的几率都相同.
另一种随机图的定义是说每一对点被连接的可能性(几率)是p, 这样, 如果给定了N个点, 连线则是一个随机变量, 它的平均值(数学上好像叫做期望值)是p(N(N-1)/2). 显然, 得到一个n条线的图的几率就是 p^n(1-p)^{N(N-1)/2-n}.
图也可以用矩阵来表示, 如果给N个点编号, 例如从1到N, 我们就可以对每一个特定的图写出一个矩阵, 如果点i和j相连, 则对应的矩阵元取1, 否则取0. 这样, 就可以建立图和矩阵的一一对应关系. 代替研究图, 我们也可以研究这类矩阵.
描述图需要几个特征量, 一个是它的度(degree). 如果与某个顶点连接的线有k条, 就说这个顶点的度是k. 对于由有向线连接的图, 还要区分入度(in-degree)和出度(out-degree). k 的分布则给定了随机图的局域连接的状态. 第二个重要的量是图的直径. 如果我们取每一条线的长度是单位长度, 图中的任意二个点可能直接连接, 我们说这两个点相距为1; 也可能通过别的点间接连接, 其距离是从其中一点到另一点的最短的路径上的连线数; 当然, 也可能不连接, 那它们之间的距离就是无限大. 互相直接或间接连接的点构成集团, 一个集团中任何两个点之间的最大距离定义为集团的直径, 而一个图的所有集团的直径中最大的那个则定义为图的直径. 随机图的直径一般都很小. 第三个特征量是成团系数, 如果图的一个顶点有z个最近邻顶点, 这些最近邻顶点可以构成z(z-1)/2个可能的对, 这些对中平均来说有y个被连接, 则y与可能的对的数目之比为成团系数.
SCI这几年在我国的科学界炒的很热, 其实, 论文的引用就是一个简单的网络. 在某个给定的集合中每一篇论文是一个顶点, 而引用构成连线. 这个引用的网络是有向的. Redner研究了ISI的783339篇论文和Physical Review D 1975—1994年间的24296篇论文的引用网络, 发现一篇文章被引用k次(in-degree)的几率符合幂次规律, 并发现这个指数大约等于3.
一种非常有趣的网络是所谓的小世界网络，在最近几年，这是研究的热点之一。其中特别著名的一个早期的关于小世界网的例子是所谓的6度分离。在世界上随便找两个人，通过这两个人的熟人建立联系，平均说来，中间需要6个人。6是个很小的数字，这个结果有点出乎预料之外。但是，如果你在坐火车的时候喜欢闲聊的话，你会经常发现你的邻座竟然认识一个你的朋友，这其实就是6度分离的一个例证。
http://blog.sciencenet.cn/blog-2402-273916.html
上一篇：关于老院士和老非院士
下一篇：还可以这样炒作
No comments:
Post a Comment