理想的光亮-张林分享 http://blog.sciencenet.cn/u/Zhanglincn 理想是一种明知不能得到但却必须要有的东西。

博文

图论和网络杂谈—贺复杂网络圈成立

已有 4282 次阅读 2009-11-26 22:51 |个人分类:学术园地|系统分类:科普集锦| 复杂网络

由于复杂网络圈现已成立,作为其中一员,想必应该写文为该圈子增些内容,也同时作为祝贺以期提升圈内的活跃气氛,顺便刺激大家的讨论欲望,所以写文如下,唯恐班门弄斧,但也无所谓,我不在乎。当然我所写的内容并非表明我就是此方面的专家,只是有些热情和兴趣,况且这方面的文章很多,每篇都比我更专业,再比如网圈发起者周涛在本科的时候就写了这方面的东西,他是这方面的专家,而我呢只想抛个砖头出去,都是些常识,目的是引来更多的玉来深化我们这个新圈子的气氛。

我们所处的物质世界在不同层次上都表现为网络的形式,是由可以分辨的个体和个体间的联系组成的网络,个体称为节点(node或顶点vertex),联系称为边(edge 或线line),这就是一个由点和线构成的图。所以所谓图就是由若干顶点及其连线所构成的几何图形,顶点的多少可以代表图的规模,边的多少可以代表图的相关度。图论(graph theory)是以图为研究对象的数学分支,和拓扑学有直接的联系,所以图也可以用拓扑的语言来定义。在图中顶点可以代表可分辨的事物或个体,边可代表联系或相互作用,这种图像可以从各种系统中抽象出来。例如晶体可以看成规则网络,准晶体可看成有随机性质的规则网络,生物圈整体可以看作网络,交通可以抽象为网络,社会关系是网,互联网也是网,还有电力网,通讯网,销售网,神经网,数据网,科学索引网等等,以及我们这个复杂网络圈,在这些不同网络上可以定义很多概念用以研究具体系统的诸多问题,在这些研究中都会涉及到图论的一些定理,作为研究物理的人来说,数学上的问题和结论有时会发挥重要作用。

图论的发展起源于著名的柯尼斯堡七桥问题,是一个与路径有关的问题,而后来的哈密顿城市网络问题和这个桥的问题类似,是一个用路径(图的一个子集合)连接顶点的问题,从图中某个顶点出发利用图中的边单次经过所有顶点最后回到出发点的路径是一个特殊的回路,称为哈密顿回路(当然还有哈密顿路径)。这个哈密顿回路问题可不是个简单的问题,由于数据结构和编码问题都可以转化为此问题,所以对这样的图的研究具有重要意义。

在图论发展历史中,还有一个最著名的问题:四色问题。这个问题起初是和地图上国家涂色加以区分的问题有关。如果把国家看成顶点,相邻看成边,如果两个国家相邻则用边连接,这样这个问题就抽象为一个图。现在在这个图上的着色问题就是顶点着色,当然还可以有边和面(由最小回路构成的广义面)等的着色,当然结合起来可以研究很多问题。四色问题也是一个表面简单但数学上要严格证明却是很难的问题,围绕该问题的研究对拓扑学的发展以及对图论在大众中的推广起到重要作用。

图根据不同约束可以分化为不同的图,如树图,路线图,环行图,联通图,完全图,子图,无边图等等,这些图在某些实际的系统中都会存在。

图所代表的网络可以用矩阵来表示,这个矩阵可以用来研究网络的结构。对于一个网络,对其顶点进行编号(随意),然后就可以用一个简单的矩阵来表示这样的网络,行和列是顶点的编号,矩阵元即为联系,有联系为1无联系则为0。如果排除自己和自己的联系,这是个矩阵是一个迹为0的方阵。如果是无向网络,此矩阵为对称矩阵。如果考虑联系的权重,则矩阵元可以取0和1之间的数表示联系的权重。很明显,这个矩阵在行和列的移动操作下是等价的(编号的随意性)。把网络抽象为矩阵对研究网络提供了方便的计算方法。但是很不幸的是图上的很多问题从计算角度讲都是NP-complete,更别说在其结构上谈论其他问题。

由于网络的抽象性,关于网络的研究所涉及的问题也非常广泛,现在主要的研究方向有:网络的基本拓扑结构研究(如普适度,标度率,维度,统计率,关联度,稳定性,联通性),网络的生成、演化和优化(模型),基于特定网络结构上的流及控制,网络上的自适应、合作、同步及相变行为,网络的信号处理等等问题,当然其他的问题还需要大家的讨论来加以完善。

好了砖抛完了,有点乱,大家凑合着看吧!



http://blog.sciencenet.cn/blog-318012-274236.html

上一篇:做为老师我不想上课
下一篇:我的悲哀

0

该博文允许注册用户评论 请点击登录 评论 (2 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-10-26 06:53

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部