The Combinatorics of Complex Networks

复杂网络的组合学

• 批准号: 36501-2012
• 负责人: Reed, Bruce
• 金额: $ 4.52万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=568739
• 关键词: Combinatorics; Complex; Networks

Transportation Networks, Communications Networks, and Social Networks have all played a crucial role in humanity's progress. While quite different, these various networks are all sets of objects connected by links. Extracting this common feature leads to an abstract model which allows us to study the properties these and other networks share. A graph consists of a set of objects called vertices joined by a set of links called edges (formally, each edge is an unordered pair of vertices). If the links have an associated directions (e.g. a web hyperlink leading from one web page to another), we obtain a directed graph . The simplicity of this model of connectivity makes it widely applicable. When modeling transportation networks, the nodes may be cities and the edges roads, railway lines, or airline routes. Molecular chemists consider graphs whose nodes are atoms and whose edges are molecular bonds. Self organizing biological networks are also modeled using graphs. Statisitical physicists use graphs to model crystal formation. In fact the connections of any physical or conceptual network can be modelled using a graph. The size of the networks modelled by graphs has grown exponentially. The first problem in graph theory, concerned seven bridges and the four land masses they linked, Graph theorists now study the graph formed by the billions of devices linked by the web and help sequence the billions of base pairs which occur in the human genome. The study of such large and complex networks is intimately linked to advances in computer science in two ways. Firstly, this area gives rise to many of the networks studied: the web, fibreoptic networks, the connections burned into a computer chip. More importantly, sophisticated computers are necessary to model, design, and solve problems with respect to the large and complex networks of the modern era. I develop and apply mathematical machinery which can handle such large and complex networks. My principal focus is on using local analysis to obtain information about the global properties of the network.

交通网络、通信网络和社交网络都在人类进步中发挥了至关重要的作用。虽然有很大的不同，但这些不同的网络都是通过链路连接的对象集。提取这一共同特征将产生一个抽象模型，该模型允许我们研究这些网络和其他网络共享的属性。图由一组称为顶点的对象组成，这些对象由一组称为边的链接连接(形式上，每条边是一对无序的顶点)。如果链接具有关联的方向(例如，从一个网页到另一个网页的网页超链接)，则我们获得有向图。 这种连接模式的简单性使其具有广泛的适用性。在对交通网络进行建模时，节点可以是城市和边缘道路、铁路线或航线。分子化学家认为，图的节点是原子，边是分子键。自组织生物网络也是用图来建模的。统计物理学家使用图表来模拟晶体的形成。事实上，任何物理或概念网络的连接都可以用图来建模。 以图表为模型的网络规模呈指数级增长。图论中的第一个问题是关于七座桥和它们连接的四块陆地，图论家们现在研究通过网络连接的数十亿个设备形成的图形，并帮助对出现在人类基因组中的数十亿个碱基对进行排序。 对这种庞大而复杂的网络的研究在两个方面与计算机科学的进步密切相关。首先，这一领域产生了许多被研究的网络：网络、光纤网络、烧毁在计算机芯片上的连接。更重要的是，复杂的计算机对于模拟、设计和解决与现代大型复杂网络有关的问题是必要的。 我开发和应用数学机器，可以处理如此庞大和复杂的网络。我的主要关注点是使用局部分析来获取有关网络的全局属性的信息。