Journal of Geo-information Science >
A Distance-based Method of Community Detection in Complex Networks
Received date: 2013-02-27
Revised date: 2013-03-04
Online published: 2013-06-17
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
CHEN Yu, HU Jun- . A Distance-based Method of Community Detection in Complex Networks[J]. Journal of Geo-information Science, 2013 , 15(3) : 338 -344 . DOI: 10.3724/SP.J.1047.2013.00338
[1] 李树彬,吴建军,高自友,等.基于复杂网络的交通拥堵与传播力学分析[J].物理学报,2011,60(5):050701(1-9).
[2] Bagler G. Analysis of the airport network of India as acomplex weighted network[J]. Elsevier, 2008,387(12):2972-2980.
[3] LiW, Cai X. Statistical analysis of airport network of China[J]. Physical Review E, 2004,69(2):046106(1-6).
[4] Guo D. Flow mapping and multivariate visualization oflarge spatial interaction data[J]. IEEE, 2009,15(6):1041-1048.
[5] 汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006.
[6] Pothen A, Simon H, Liou K P. Partioning sparse matriceswith eigenvectors of graphs[J]. SIAM. J. Matrix Anal. &Appl., 1990,11(3):430-452.
[7] Kernighan B W, Lin S. A efficient heuristic procedure forpartition graphs[J]. Bell System Technical Journal, 1970(49):291-307.
[8] Girvan M, Newman M E J. Community structure in socialand biological networks[J]. Proceedings of the NationalAcademy of Science, 2001(99):7821-7826.
[9] Newman M E J. Fast algorithm for detecting communitystructure in networks[J]. Physical Review, 2004,69(6):066133(1-5).
[10] Expert P, Evans T S, Blondel V D, et al. Uncoveringspace-independent communities in spatial networks[J].PNAS, 2011,108(19):7663-7668.
[11] Clauset A, Newman M E J, Moore C. Finding communitystructure in very large networks[J]. Physical Review E,2004,70(6):066111(1-6).
[12] Newman M E J, Girvan M. Finding and evaluating communitystructure in networks[J]. Physical Review E, 2004,69(2):026113(1-15).
[13] Guimerà R, Mossa S, Turtschl A, et al. The worldwide airtransportation network: Anomalous centrality, communitystructure, and cities' global roles[J]. PNAS, 2005,102(22):7794-7799.
[14] Guimerà R, Amaral L A N. Modeling the world-wide airportnetwork[J]. The European Physical Journal. B, 2004(38):381-385.
[15] Guida M, Maria F. Topology of the Italian airport network:A scale-free small-world network with a fractalstructure?[J] Chaos, Solitons and Fractals, 2007,31(3):527-536.
[16] Wang J E, Mo H H, Wang F H, et al. Exploring the networkstructure and nodal centrality of China's air transportnetwork: A complex network approach[J]. Journal ofTransport Geography, 2011(19):712-721.
[17] 明朝辉,韩松臣,张明.基于复杂网络理论的中国民航机场航线网络静态特征挖掘和应用[J].江苏教育学院学报(自然科学),2011,27(3):22-27.
[18] Watts D J, Strogatz S H. Collective dynamics of'small-world' networks[J]. Nature, 1998,393(6684):440-442.
[19] 宋岭,魏秀丽.中国经济区域划分综述[J].新疆财经,2000(2):48-49.
/
| 〈 |
|
〉 |