网络这一阵很热. 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条线的图的几率就是
.
图也可以 用矩阵来表示, 如果给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度分离的一个例证。
在复杂网络研究中经常用到随机图论, 通俗地说, 就是让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条线的图的几率就是
.图也可以 用矩阵来表示, 如果给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度分离的一个例证。