络中所包含的内在科学规律，学者们结合空间数据挖掘等方法展开了相应的研究。

空间网络的特征空间网络是节点位于具有度量的空间上的网络，一般来说是二维空间，通常的度量方式是欧式距离[2]。

在这些网络中，节点包含了位置信息，连接边包含了距离或者是空间关系信息。

例如在社交网络中，节点包含了该个体的位置信息，连接边长包含了朋友间的地理距离信息；又如在城市路网中，如果将路段看作节点，若路段与路段之间有交叉口，则两点相连，这时连接边就包含了空间相邻关系。

空间网络的连接不一定是嵌入空间的，例如社交网络、航空网络，因此它不等同于平面网络，但是很多空间网络却具有平面性，例如公路网、铁路网、电力网等。

学者们从图论的角度对空间网络进行研究，发现许多空间网络具有复杂网络的特征。

例如对印度铁路和航空网络的分析均发现了网络的小世界属性[3,4]；对城市路网和城市交通流的研究发现了城市交通的幂律分布，交通最繁忙的20%街道承载了80%的交通流[5,6]。

由于这些空间现象中存在着复杂网络的特征，人们开始用复杂网络的方法解决空间网络的问题。

克鲁奇蒂(Cru-citti)等人研究了不同城市路网的四种中心性指标，发现用这四种中心性指标能够反映城市的结构，而且可以通过中心性指标的分级聚类判断城市的规划和组织模式——自组织的城市具有复杂网络的无标度特征，而有规划的城市没有这样的特征[7]。

对中国航空网络中心性以及客流量的研究发现，航空网络中城市的中心性和吸引力与城市的人口、社会经济指标高度相关[8,9]。

与一般的复杂网络相比，空间网络还具有独特的空间上的特征。

在这些网络中节点之间的距离与它们的连接强度有关，因而对网络的拓扑属性有重要的影响。

2011年手机照片社交网络软件Color提出了“弹性社交网络”这一新概念（参见Mobile 2.0网引言在我们生存的空间，事物之间密不可分的联系好似千丝万缕将其连接起来，形成各种巨大的网络。

长久以来，大量探索自然的研究都是将整个世界不断地拆分，去分析理解各个部件，却不知道如何再把它们组装起来[1]。

我们似乎往往是知道了方方面面的知识，却依然对整个系统一无所知。

究其原因是我们忽视了对事物间连接关系的研究。

专门研究连接关系的理论——复杂网络，恰好为从表面看来杂乱无章的复杂系统提供了有力有效的分析方法。

很多复杂网络都是构建在地理空间之中的。

最典型的是交通网络，如城市路网、航线网络、铁路网络，还有社交网络、手机通讯网络等。

基于托普勒地理学第一定律(Tobler’s First Law of Geography)：越接近的事物越相关。

涉及到地理现象和人类活动时，复杂网络表现出空间上的相关性或随距离变化的特征。

为了能够清晰地诠释这类空间复杂网许　珺　陈　娱　徐敏政中国科学院地理科学与资源研究所空间网络的数据挖掘和应用关键词：空间网络　数据挖掘　异构信息网站，2011）。

所谓“弹性”是指每当Color 监测到你与其他用户地理位置接近时，就会调整你们原本的关系强度，将关注同一事件并在附近的人通过群组的方式划分，进而构建社区。

弹性社交网络从侧面反映出人们关系的强度与人们地理位置的接近程度是有关系的，人与人之间的关系随着地理位置的远近是“可松可紧”的，而越接近的人成为一个群组的可能性越大。

借助互联网，在虚拟社交网络中人们的“距离”被拉近了。

这种距离突破了地理的限制，相隔千里仍然可以即时交流或者一起参加线上活动。

表面上看，托普勒地理学第一定律在社交网络中失效了。

然而，在社交网络中，用户的地理位置潜移默化地影响着社交网络的构成、动态演变与信息传播。

从多个虚拟社交网站的数据中发现人们会更倾向于与周围的人相识，这与现实世界的现象一致。

多个研究表明在社交网络中，地理距离d 与两人互为朋友的概率P (d )相关，符合距离衰减函数：P (d )~d -α。

即两人越近越有可能是好友，而随着距离的增加，两人互为好友的概率降低（图1）。

只是在不同的数据中衰减系数α值不同。

在Liben-Nowell(立本-诺埃尔)等人对超过100万节点的社交网络数据（美国LiveJour-nal 网站数据）的研究中，得到的α值约为1[10]；朗姆比奥特(Lambiotte)等人对比利时地区的手机通讯数据展开了研究，其α值约为2[11]；而在翁尼拉(Onnela)等人对比利时手机通讯数据的研究中，α值约为1.5[12]。

由于连接概率随距离的衰减，网络中三角形的数量也会呈现随距离衰减的趋势。

塞拉托(Scellato)等人采用改进的加权聚类系数对几个著名的社交网站数据进行了分析对比，发现考虑地理距离之后，网络的聚类系数变小[13]。

空间网络数据挖掘复杂网络都具有社区结构的性质，即整个网络是由若干个“群”或者“团”构成的，社区内部节点连接相对紧密而社区之间的连接相对比较稀疏（如图2所示）。

对网络的社区发现有助于发现具有共性的群体，是网络数据挖掘的重要方法。

对于具有复杂网络特征的空间网络，节点之间的紧密度除了需要衡量连接关系上的紧密性，还需要考虑到它们地理距离上的远近。

复杂网络的社区发现复杂网络的社区发现，也叫图的聚类(graph cluster)或者图的分割，是根据网络结构和节点属性的相似性，将网络中的节点进行分组的方法。

将任意特征空间的点集表示为一个加权的无方向图形G =(V , E )，其中特征空间的点为图形的节点，而图形的边的权重就代表任意两点之间的相似性，用w (i , j ) 来表示。

对图形的分组就是要将V 划分为点集V 1, V 2, ⋯ , V m ，使得V i 中节点的相似性最大，而V i , V j （i ≠j ）之间节点的相似性最小。

根据算法的基本思想，主要可分为图形分割算法（例如拉普拉斯谱平分算法、柯林汉-林(Kernighan-Lin)算法等）和分级聚类算法（例如GN算法、纽曼快速算法等）两图1　某社交网站数据中用户距离和连接概率的关系图2 社区结构示意图（不同的颜色代表不同社区）大类（如图3所示）。

图形分割算法　最早的柯林汉-林算法首先将网络划分为两个社区，然后不断调整社区内节点，判断它属于哪个社区更优，判断条件为增益函数（两个社区内部边数减去连接两个社区之间的边数）的大小[14]。

由于该算法需要提前知道社区的大小，因此现在使用不多。

由于复杂网络理论是基于数学图论的，因此图论中的经典分割理论，如最小割定理(minimum cut)、拉普拉斯图谱理论(Lapla-cian graph spectrum)等，是很多社区挖掘算法的理论基础。

珀森(Pothen)等人基于拉普拉斯图谱理论提出了谱平分算法[15]。

该算法复杂度较低，但是最大的缺陷是每次只能将网络平分，需要不断地重复该算法才能得到多个社区结构。

吴(Wu,音译)和赖希(Leahy)利用经典的最小割定理，提出了一种基于网络流理论的图形分割方法[16]，主要是通过不断移除网络中权重最小的边使得分组后被消去的所有边的权重和最小。

这种算法的缺陷是倾向于从网络中划分出一些孤立的小点集。

为了避免这一问题，施(Shi,音译)和马利克(Malik)提出了归一化割(normalized cut)算法，将归一化割作为被消去的边的权重和与图形中所有边的权重和的比值，从而得到了优于最小割算法的聚类结果[17]。

分级聚类算法　纽曼(New-man)等人在复杂网络社区挖掘算法领域有着系统的、成熟的研究理论，其研究起着举足轻重的作用。

早在2001年，格文(Girvan)和纽曼就提出了GN算法[18]，它的基本思想是不断地从网络中移除介数(Betweenness)最大的边，直到将整个网络分解为各个节点。

但是GN算法存在两个缺陷，第一是复杂度很高，处理大数量级网络时就会力不从心；第二是在不知道社区数目的情况下，GN算法不知道要分解到哪一步才能获得最优的社区结构。

针对这些问题，他们引入了模块度(modularity)的概念[19]。

假设将相同网络的边随机重新分布，模块度值就是组群中的边的数量减去随机分布后落入组群中边的数量，其物理意义就是网络中社区内部边所占的比例与同样连接数量下社区内部边所占比例的期望值之差。

如果社区内部边的比例不大于期望值，模块度值为零；模块度值为正意味着可能存在组群结构；模块度越接近1，就说明社区结构越明显。

因此寻找模块度值大的网络结构就可以发现节点的群组。

在分组过程中，每一次分解都计算一次网络的模块度值，模块度的最大值就对应着最佳的社区结构。

基于模块度的概念，纽曼等人实现了基于模块度增量的快速算法[20]，随后又提出了复杂度较低的基于模块度增量矩阵及堆结构的贪婪算法（CNM算法）[21]。

其他方法　无论是图形分割思想还是分集聚类思想，都基于网络的拓扑结构。

后来出现了一些考虑节点属性的社区挖掘算法，例如SCAN算法[22]。

偏重于网络拓扑结构一致性的算法会造成分类群组中节点的属性差别大，而偏重于图形中的节点属性的相似性的算法会造成群组内部网络结构的松散。

理想的图形聚类方法应该产生群组内部结构紧凑并且节点属性相似的结果。

据此，周（Zhou，音译）等人提出了既考虑网络的结构，又考虑节点属性的SA-Cluster算法[23]。

考虑空间的网络社区发现模块度是至今仍在广为应用的一种方法，特别是对空间网络的社区检测，基本都是基于模块度算法的改进[2]。

关于空间网络的社区挖掘的研究，目前主要有三大方向：第一，在大多数研究中，研究者们对地理距离因素未加考虑，用现有的经典算法对网络的拓扑结构进行社区挖掘。

由于很多网络中距离与连接之间存在图3 常见的复杂网络社区挖掘方法分类着关系：相距越近的节点之间连接的概率越大，而相距较远的节点间连接概率较小，因此其拓扑关系中隐藏着距离要素，所呈现出的社区结构在空间上有一定的地域性特征[24,25]。

例如吉梅拉(Guimerà)等人对全球范围的航线网络进行了社区挖掘，发现从全球尺度来看，社区的分布呈现地域性特点（如图4所示）。

第二，社区划分中考虑区域的约束作用。

郭（Guo ，音译）在对美国县级人口流动网络的社区划分时，考虑到区域邻接关系。

他用节点表示区域，节点间的连接边表示从某一区域到另一区域的总人口迁移数，提出了一个基于空间连续性的图形分割方法ALK 方法，并结合模块度指标，构建了流动人口数据的空间连续树，实现了在多级区域上人口流动的合并，从而将繁多的大数据集可视化（如图5所示）。

其中，区域化方法并不是根据行政边界，而是考虑空间邻近将人口流合并，实际上就是一种考虑空间相邻关系的社区挖掘方法[26,27]。

第三，社区划分中考虑空间距离的影响，这方面有两种不同的做法。

一种是排除空间距离的影响。

由于很多网络中用已有的社区挖掘算法得到的社区结构在其空间上具有地域性，因此有的学者希望剔除掉潜藏的距离对连接概率的影响，挖掘出与距离无关却又紧密相连的节点群。