地球信息科学学报

地球信息科学学报 ›› 2013, Vol. 15 ›› Issue (3): 338-344.doi: 10.3724/SP.J.1047.2013.00338

• 地球信息科学理论与方法 • 上一篇    下一篇

考虑地理距离的复杂网络社区挖掘算法

陈娱1,2, 许珺1   

  1. 1. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京100101;
    2. 中国科学院大学,北京100049
  • 收稿日期:2013-02-27 修回日期:2013-03-04 出版日期:2013-06-25 发布日期:2013-06-17
  • 作者简介:陈娱(1989-),女,江苏镇江人,硕士生,主要从事地理信息系统和复杂网络的研究。E-mail:chenyu@lreis.ac.cn
  • 基金资助:

    国家自然科学基金项目(41171296);国家“863”计划课题(2012AA12A211)。

A Distance-based Method of Community Detection in Complex Networks

CHEN Yu1,2, XU Jun1   

  1. 1. Institute of Geographic Sciences and Natural Resources Research, CAS, Beijing 100101, China;
    2. University of Chinese Academy of Sciences, Beijing 100049,China
  • Received:2013-02-27 Revised:2013-03-04 Online:2013-06-25 Published:2013-06-17

PDF (PC)

赞

被引次数

8 | 3

摘要：

复杂网络具有社区结构的性质,即社区内节点的连接比社区间的连接更为紧密。目前,具有复杂网络拓扑结构的社区挖掘算法已有很多,但在很多地理空间的复杂网络中节点间的紧密度,不仅与其连接关系有关,同时与它们之间的距离有关。因此,本文提出将节点间的地理距离考虑到社区挖掘的过程中,修改基于模块度增量矩阵的Newman快速算法(简称CNM算法),将1/dijn(d为节点i与节点j之间的距离)作为边权,对加权网络进行社区挖掘,从而发现既相互联系紧密又在地理空间上相互接近的社区。最后,本文用国内航线网络作为实例,将算法用于挖掘航线网络中城市的社区结构,得到10个在航线网络中联系紧密且在空间分布上具有一定地域性的城市社区,与我国的主要经济区域分布比较一致。本算法考虑地理相关性和连接紧密性,较好地识别出空间网络的社区结构。

关键词: 空间距离, 复杂网络, 航线网络, 模块度, 位置信息

Abstract:

One feature discovered in the study of complex networks is community structure, it means that vertices are gathered into several groups that the edges within groups are more than those between them. Detecting the community structure hidden in the networks has extensive application prospects. Recently, many approaches have been developed for finding communities, such as Gievan-Newman algorithm, Newman fast algorithm and so on. Also, there are some approaches consider both the network topology and the attributes of vertices, such as SA-cluster algorithm. However, a few studies focused on considering geographic distance between vertices. Tobler's first low says that near things are more related than distant things. Based on this proposition, we think that the strength of interaction between vertices is concerned with geographic distance. By defining the weights of the edges in the network as the function of distance between two directly connected nodes, we modified the fast modularity maximization algorithm (CNM algorithm). The weight is defined in such a way that the closer the distance, the greater the weight. The algorithm is tested on the flight network of China. We consider the strength of interaction between two cities is related with both the connection of flights and distance. We find 10 communities in the air transport network, and the distribution of communities displays regionally.

Key words: flight network, modularity, complex network, spatial distance, community structure