网络社区发现与搜索

第1章绪论 1.1引言 网络的研究始于1736年欧拉的哥尼斯堡七桥问题，那时人们对网络及其数学性质开始感兴趣并开展了各种研究。20世纪60年代，两位匈牙利数学家Erdos和Renyi提出的随机图理论被公认为是数学上复杂网络理论的首创性的系统研究。近年来，计算机技术的不断发展为学者们提供了丰富的计算资源来处理和分析网络数据，人们能处理的真实网络规模也有了相当大的增长，达到了数百万甚至数十亿个节点的规模。正因如此，大规模网络的处理方式发生了巨大变化。此外，关于网络的科学研究融合了数学、物理学、生物学、计算机科学、社会科学和许多其他领域的思想，其发展也得益于不同学科研究人员的贡献。本节用一致的语言和符号整合网络知识，使其串联为一个整体。 1.网络概述 网络中包含若干节点和连接这些节点的边，表示诸多对象及其之间的相互联系[1]。进入21世纪之前，一般认为网络的结构是随机的。Barabasi等[2]和Watts等[3]在1999年和1998年分别发现了网络的无标度和小世界特性，并分别在世界著名期刊《科学》和《自然》上发表了研究成果之后，人们才认识到网络所具有的复杂性。图1.1为一个由6个节点和9条边组成的小网络示例。 数学上，网络是一种图，不失一般性地又专指加权图。除了数学上的定义外，网络还有其具体的物理含义，即网络是从某种相同类型的实际问题中抽象出来的模型。在计算机领域中，网络是信息传输、接收、共享的虚拟平台，能够把各个点、面、体的信息联系到一起，实现资源共享的目标。网络是人类发展史上*重要的发明之一，促进了科技的进步和人类社会的发展。作为一种简化表示，网络将一个系统简化为一个抽象结构，只捕获连接模式的基本信息，而很少涉及其他方面。网络中的节点和边可以用附加信息标记，以获取系统的更多细节。 许多领域的科学家已经提出了用于分析、建模和理解网络的数学计算和统计工具，这些工具中大多数是从一个简单的网络表示开始的，即一组节点和边，如图1.1所示。经过计算，可以获取关于网络的一些有用信息，如从一个节点到另一个节点的路径长度。其他工具采用网络模型的形式，这些模型可以对网络上发生的过程进行数学预测，如互联网上的流量流动方式或疾病在社区中的传播方式。 因为这些工具以抽象的形式处理网络，所以理论上它们几乎可以应用于任何以网络表示的系统。因此，如果对某个系统感兴趣，并且它可以被有效地表示为一个网络，那么就有上百种不同的工具，可以立即应用到系统分析中。当然，并不是所有的测量或计算都能得到有意义的结果。因此，网络是表示系统各部分之间连接或交互模式通用且强大的手段。 2.真实网络概述 网络*简单的形式就是由节点和边组成的集合。在网络中，点称为“节点”或“顶点”，线称为“边”。在许多学科分支中，网络被定义为表示复杂系统各组成部分之间连接模式的一种数据结构。自然界中存在着大量的复杂系统，都可以通过各种形式的网络进行描述。一个典型的网络包含许多节点与连接两个节点之间的边。节点表示不同的个体，边表示不同个体间的关系，其存在于具有某种特定关系的两个节点之间。如果网络中两个节点之间存在边，则这两个节点存在相邻关系。例如，社交网络中的节点表示人，边表示各种不同类型的社会交互，包括友谊、协作、业务关系或其他。 为了更直观地了解真实网络，下面介绍两个真实网络案例。 Internet网络：又称互联网络，指的是网络与网络串连成的庞大网络，这些网络以一组通用的协议相连，形成逻辑上的单一巨大国际网络，如图1.2所示。在Internet网络中，节点代表计算机，边代表数据连接，如光缆之间的信号传输。通常internet泛指互联网，而Internet则特指因特网。一般将计算机网络互相关联在一起的方法称为“网络互联”，而在此基础上发展出的覆盖全世界的全球性互联网络则称为互联网，即互相连接在一起的网络结构。互联网与万维网并不等同，万维网是基于超文本而相互连接的全球性系统，且是互联网所能提供的服务之一。 在线社交网络：在互联网的推动下，Facebook、Google+、Twitter新浪微博、知乎和豆瓣等大型在线社交网站的出现，刺激了对在线社交网络上社区发现的不断研究，见图1.3。随着大规模社交网络数据的大幅增长，带动社区发现领域发展出许多令人兴奋的应用，如社交圈发现和有影响力的社区搜索。此外，随着智能手机设备的兴起，在线社交网络带动了地理社交网络（也称为“基于位置的社交网络”）的快速增长，如Foursquare、Yelp、Google+和FacebookPlaces。在地理社交网络中，用户与位置信息（如家乡和办理登机手续的地点）相关联，而社区由在社交层中紧密联系的用户以及在空间层上距离较近的用户组成。 1.2基本术语 1.网络分类 本部分描述并定义一些社区发现与搜索中的常用网络，分为四类，即技术网络[4]、社交网络[5]、信息网络[6]和生物网络[7]，列出每类网络中常见的示例，并介绍用于检测这些网络结构的基本技术。 1）技术网络 技术网络是指在20世纪成长起来并构成现代技术社会支柱的物理基础设施网络。技术网络中*具代表性的是因特网，因特网是计算机和相关设备之间物理数据连接的世界性网络。因特网是一个分组交换的数据网络，这意味着通过它发送的信息被分解成分组、小块数据，分别通过网络发送，并在另一端重新组合成完整的信息。数据包的格式遵循因特网协议(internet　protocol，IP)的标准，并且需要在每个数据包中指定数据包目的地的IP地址，以便可以在网络中正确地路由。因特网*简单的网络表示法是用网络中的节点表示计算机和其他设备，而边表示其内部的物理连接，如光纤线路。事实上，普通的计算机大多只占据网络“外部”的节点，即数据往来的节点，并不充当其他计算机之间数据流动的中间点（实际上，大多数计算机只有一个网络连接，所以它们不可能位于其他计算机之间的路径上）。因特网的“内部”节点主要是路由器，它是功能强大的专用计算机，位于数据线之间的连接处，接收数据包并将其朝一个方向或另一个方向转发到预定目的地。 2）社交网络 社交网络中的节点是一个人或一群人，节点间的边代表了他们之间某种形式的社交互动。社交网络中十分重要的一点是网络中的边可能有许多不同的定义，如个人之间的友谊，但也可能代表职业关系、商品或金钱交换、沟通模式，或许多其他类型的联系。例如，如果用户对财富五百强公司董事会之间的专业互动感兴趣，那么由Facebook页面组成的网络相对于用户可能就没有多大用处。此外，人们用来探索不同类型社交互动的技术也可能有很大不同，因此通常需要不同类型的社交网络研究来解决不同类型的问题。 3）信息网络 信息网络是通过某种方式连接在一起的数据项所形成的网络。据目前研究可知，信息网络是人为设计的，而其中*著名的就是万维网。万维网中的节点是由文本、图片或其他信息组成的Web页面，而边是允许从一个页面导航到另一个页面的超链接。由于超链接只在一个方向上运行，因此Web是一个有向网络。此外还有许多其他网络值得研究，如各种引文网络。通常在论文末尾的参考文献中，如果论文A在其参考文献中引用B，则可以构造一个节点为论文的网络，存在从A指向B的有向边。 4）生物网络 网络在生物学的许多分支中被广泛应用，作为适当生物元素之间相互作用模式的方便表示。例如，分子生物学家用网络来表示细胞内化学物质之间的化学反应模式，神经科学家用网络来表示脑细胞之间的联系模式，生态学家则研究生态系统中物种之间的相互作用网络，如捕食或合作。近年来*受关注的生物网络中，有生物化学网络以及代表生物细胞内分子水平相互作用模式和控制机制的网络。 该领域研究的主要网络类型是代谢网络、蛋白质–蛋白质相互作用网络和遗传调控网络。 2.网络描述形式 本部分介绍用于描述和分析网络的基本理论工具，其中大部分来自图论。图论是一个包含许多研究内容的大领域，在这里只描述了其中的部分内容，重点关注与现实网络研究*相关的内容。网络是由边和节点构成的集合。节点和边在计算机科学中也称为节点和链接，在物理学中称为站点和纽带。表1.1为特定网络中节点和边的一些示例。 在本书中，通常用n表示网络中的节点数，用m表示边数。本书中介绍的大多数网络在任何一对节点之间*多只有一条边。在极少数情况下，节点对之间可能有多条边，将这些边统称为多边。在将要讨论的大多数网络中，没有将节点连接到自身的边，尽管在少数情况下会出现这样的边，这种边称为自边或自循环。 一个既没有自边又没有多边的网络称为简单网络或简单图，具有多边的网络称为多图。图1.4和图1.5分别为简单图示例以及具有多边和自边的非简单图示例。 1）邻接矩阵 网络的一个*基础的表示是邻接矩阵，其中简单图的邻接矩阵A由式(1.1)计算： (1.1) 图1.4的邻接矩阵如式(1.2)所示： (1.2) 需要注意的是，对于没有自环的网络，如简单网络，其邻接矩阵对角元素都为零。另外，邻接矩阵是对称的，即节点vi和vj的边关系是对等的，同时邻接矩阵也可以用来表示多边和自边。通过将对应的矩阵元素设置为边的多重性来表示多边，如节点vi和vj之间的双边由表示。 图1.5的邻接矩阵如式(1.3)所示： (1.3) 2）加权网络 在某些情况下，将边表示为具有强度或权重（通常为实数）是有意义的[8]。例如，在因特网中，边表示沿其流动的数据量的权重；在食物网络中，捕食者和被捕食者之间的相互作用可能是衡量被捕食者和捕食者之间总能量流的权重；在社交网络中，连接可能具有表示参与者之间接触频率的权重。这种加权网络可以通过给出邻接矩阵值的元素等于相应连接的权重来表示。式(1.4)的邻接矩阵表示一个加权网络，其中节点1和2之间的连接强度是节点1和3之间的两倍，而