复杂网络社团发现理论与应用

第1章 复杂网络基础知识　　网络规模的扩大增加了大型复杂网络的研究难度。为了在可接受的计算成本下发现并研究网络中蕴含的规律，有必要简化研究对象，因而社团发现算法越来越受人们的关注。在复杂网络中发现社团结构，并以这些社团结构为单位形成的网络作为研究对象，能够大幅减少研究的复杂度。　　本章介绍复杂网络及其在科学领域和现实世界中的应用，主要介绍与社团发现有关的复杂网络基础知识，包括复杂网络概述、图论基础、无标度网络、小世界网络、度相关性和现实世界中的复杂网络等内容。　　1.1 复杂网络概述　　物理学家霍金认为：21世纪是复杂性的世纪。作为研究复杂性科学和复杂系统的有力工具，复杂网络已成为学术界研究的一个热点，在工程技术、社会、政治、医药、经济和管理领域都有着潜在和广泛的应用。复杂网络借助图论和统计物理的方法，可捕捉并描述系统的演化机制和规律，同时也能很好地分析系统的整体行为。复杂网络的复杂性主要体现在以下几个方面。　　(1) 结构复杂性：网络结构纵横交错、复杂混乱，且连接结构可能随时发生改变。例如，万维网(world wide web， WWW)每天都会产生和删除许多网页和链接。另外，节点之间的连接可能具有不同的权重和方向。例如，交通网络中每条公路上都有不同数量和方向的汽车在行驶。　　(2) 节点复杂性：网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统。例如，基因网络中每个节点都具有复杂的时间演化行为。一个网络中还可能存在多种不同类型的节点。例如，控制哺乳动物细胞分裂的生化网络包含各种各样的蛋白质和酶。　　(3) 各种复杂性因素的相互影响：现实中的复杂网络每时每刻都会受到各种因素的影响。例如，如果耦合神经元同时被重复激活，它们之间的连接就会加强，这也是记忆和学习的基础。另外，各种不同类型的网络之间也存在密切的联系，从而相互影响，如电力网络的故障可能会导致网络流量变慢、金融机构关闭、运输系统失去控制等一系列连锁反应。　　由于真实网络的规模庞大、结构复杂，其拓扑结构在21世纪初才得到广泛的研究。人们对真实网络拓扑结构的研究大致经历了以下过程：最初，研究者们认为真实网络各要素之间的关系可以用一些规则的结构表示，如二维平面上的网格；20世纪50～90年代末，人们主要用随机网络描述没有明确设计原则的大规模网络；近年来，研究者们发现大量的真实网络既不是随机网络，也不是规则网络，而是统计特性与前两者都不同的网络，其中最有影响的复杂网络模型是小世界网络和无标度网络。下文将介绍复杂网络中需要用到的基本概念。　　网络可以抽象为一个由节点集V和边集E组成的图，节点数记为，边数记为。网络中节点和边与具体研究对象紧密相关。例如，在生命系统的巨型遗传网络中，节点表示蛋白质，边表示蛋白质之间的相互作用；在WWW中，节点表示各个不同的页面，边表示页面之间的链接。节点数和边数均有限的图称为有限图，否则称为无限图。由于研究的网络都是真实网络的模型，一般为有限图。如果网络中任意一个节点对与对应同一条边，则称该网络为无向网络，否则称为有向网络。两个端点相同的边称为环(loop)，有公共起点并且同时具有公共终点的两条边称为平行边或重边。无环并且没有重边的图称为简单图，任何两个节点之间都有边相连的简单无向图称为完全图。现实世界中的网络往往需要根据某种度量标准，为网络上的每个点和每条边都赋予相应的权值，这种网络称为加权网络[1，2]。例如，在交通网中，每两个站点之间的距离不同，而且每条线路上的车流量往往也不同，即每条边具有不同的权值。没有赋予权重的网络称为无权网络，无权网络也可以看作是每条边的权值都是1的网络。点和边的权值通常用和表示。无向网络中，一个点的权值是与之相连的所有边的权值总和，即。　　介数分为节点介数和边介数。节点介数为网络中所有最短路径中经过该节点的数目比例，边介数的含义和节点介数相似。介数反映了节点和边在整个网络中的地位和作用，有很具体的现实意义。在社会关系网络或技术网络中，介数的分布特征反映了不同人员、资源、技术等因素在生产关系中的地位，对在网络中发现和保护关键资源和技术具有非常重要的意义。　　1.2 图论基础　　图论最早起源于1736年欧拉(Euler)所解决的哥尼斯堡(Konigsberg)七桥问题，现已广泛应用于计算机科学、商业、心理学等领域。本节介绍图的矩阵表示和度分布。　　1.2.1 图的矩阵表示　　任何复杂的网络都可以表示为图，借助矩阵对图进行研究，可以大大简化和促进对图的分析。