留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于地理加权中心节点距离的网络社区发现算法

万幼 刘耀林

万幼, 刘耀林. 基于地理加权中心节点距离的网络社区发现算法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(10): 1545-1552. doi: 10.13203/j.whugis20180025
引用本文: 万幼, 刘耀林. 基于地理加权中心节点距离的网络社区发现算法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(10): 1545-1552. doi: 10.13203/j.whugis20180025
WAN You, LIU Yaolin. Community Detection Algorithm Based on Geographical Weighted Central Node Distance[J]. Geomatics and Information Science of Wuhan University, 2019, 44(10): 1545-1552. doi: 10.13203/j.whugis20180025
Citation: WAN You, LIU Yaolin. Community Detection Algorithm Based on Geographical Weighted Central Node Distance[J]. Geomatics and Information Science of Wuhan University, 2019, 44(10): 1545-1552. doi: 10.13203/j.whugis20180025

基于地理加权中心节点距离的网络社区发现算法

doi: 10.13203/j.whugis20180025
基金项目: 

国家重点研发计划 2017YFB0503601

国家自然科学基金 41471327

详细信息
    作者简介:

    万幼, 博士, 讲师, 从事地理大数据和空间数据挖掘理论与方法研究。wanyou@whu.edu.cn

    通讯作者: 刘耀林, 博士, 教授。yaolin610@163.com
  • 中图分类号: P208

Community Detection Algorithm Based on Geographical Weighted Central Node Distance

Funds: 

The National Key Research and Development Program of China 2017YFB0503601

the National Natural Science Foundation of China 41471327

More Information
    Author Bio:

    WAN You, PhD, lecturer, specializes in the theories and methods of geo-big data and spatial data mining. E-mail:wanyou@whu.edu.cn

    Corresponding author: LIU Yaolin, PhD, professor. E-mail: yaolin610@163.com
  • 摘要: 提出一种基于地理加权中心节点距离的网络社区发现算法(geographical weighted central node distance based Louvain method,GND-Louvain)。该算法扩展了传统复杂网络领域的经典社区发现方法Louvain,利用地理加权中心节点来度量社区发现过程中的空间距离关系,并将此距离衰减效应加入到距离模块度模型中,以此来计算和评估空间网络社区划分结果的质量,并探究了空间社区发现结果不稳定的原因。通过定义节点计算顺序,保证了社区发现结果的质量和稳定性。利用中国铁路网线路数据,设计了5种不同空间约束的空间社区发现对比性实验。结果证明,GND-Louvain算法的准确性最高,并且算法结果最稳定。
  • 图  1  两个网络子社区之间的距离度量方式

    Figure  1.  Different Distance Measures Between Two Meta-Communities

    图  2  铁路网络的L空间模型和P空间模型

    Figure  2.  The Space L Model and Space P Model for Train Nets

    图  3  两种不同模块度的社区发现结果比较

    Figure  3.  Community Detection Result of Two Modwlarities on a Sample Network

    图  4  6个空间网络社区发现结果的模块度大小比较

    Figure  4.  Modularities Comparison of Six Train Nets

    图  5  3个距离模块度算法的模块度波动范围与网络平均边长度之间的线性回归分析

    Figure  5.  Linear Regression Analysis Between Range of Modularity and Average Distance of Connections

    图  6  两类节点度排序情况下GND-Louvain算法的距离模块度

    Figure  6.  Modularities of Two Degree Ordered GND-Louvain

    图  7  两类节点度排序下GND-Louvain算法模块度标准化值

    Figure  7.  Normalized Modularities of Two Degree Ordered GND-Louvain

    图  8  城铁和高铁网络数据及GND-Louvain社区分割结果

    Figure  8.  High-Speed Train Net and It's Community Detection Results by Using GND-Louvain

    表  1  6个不同类型空间网络的节点和边个数

    Table  1.   The Number of Nodes and Edges of Six Networks

    空间网络 铁路类型 城市数 连接数 所有连边的平均长度/km 所有节点间平均距离(σ值)/km
    CG-net 高铁 167 5 044 740 997
    D-net 动车 175 1 824 501 1 174
    K-net 普快 294 13 920 895 1 326
    T-net 特快 212 3 812 913 1 291
    X-net 临客 203 1 370 449 1 379
    Z-net 卧铺 177 3 337 1 004 1 203
    下载: 导出CSV

    表  2  两个社区发现算法结果的模块度数值对比

    Table  2.   Modularities of Two Partition Results

    社区分割结果 传统模块度 距离模块度
    NG-Louvain社区分割结果 0.190 0.079
    GND-Louvain社区分割结果 0.181 0.118
    下载: 导出CSV
  • [1] Barthélemy M. Spatial Networks[J]. Physics Reports, 2011, 499(1-3):1-101 doi:  10.1016/j.physrep.2010.11.002
    [2] Fortunato S. Community Detection in Graphs[J]. Physics Reports, 2010, 486(3):75-174 http://d.old.wanfangdata.com.cn/OAPaper/oai_arXiv.org_0911.5239
    [3] 唐磊, 刘欢.社会计算: 社区发现和社会媒体挖掘[M].刘益民, 闭应洲.北京: 机械工业出版社, 2013

    Tang Lei, Liu Huan. Community Detection and Mining in Social Media[M]. Wen Yimin, Bi Yingzhou. Beijing: Morgan & Claypool 2013
    [4] Gao S, Liu Y, Wang Y L, et al. Discovering Spatial Interaction Communities from Mobile Phone Data[J]. Transactions in GIS, 2013, 17(3):463-481 http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0230166666/
    [5] 杨静, 程昌秀, 李晓岚, 等.网络结构空间格局相似度分析——以1938-2014年北京市骨干交通网络为例[J].武汉大学学报·信息科学版, 2016, 41(12):1593-1598 http://ch.whu.edu.cn/CN/abstract/abstract5610.shtml

    Yang Jing, Cheng Changxiu, Li Xiaolan, et al. A Similarity Evaluation Method on Spatial Patterns of Network Structures:A Case Study About Beiing Traffic-Network Backbones from 1938 to 2014[J]. Geomatics and Information Science of Wuhan University, 2016, 41(12):1593-1598 http://ch.whu.edu.cn/CN/abstract/abstract5610.shtml
    [6] Liu X, Gong L, Gong Y X, et al. Revealing Travel Patterns and City Structure with Taxi Trip Data[J]. Journal of Transport Geography, 2015, 43:78-90 doi:  10.1016/j.jtrangeo.2015.01.016
    [7] 刘瑜, 龚俐, 童庆禧.空间交互作用中的距离影响及定量分析[J].北京大学学报(自然科学版), 2014, 50(3):526-534 http://d.old.wanfangdata.com.cn/Periodical/bjdxxb201403015

    Liu Yu, Gong Li, Tong Qingxi. Quantifying the Distance Effect in Spatial Interactions[J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2014, 50(3):526-534 http://d.old.wanfangdata.com.cn/Periodical/bjdxxb201403015
    [8] Chen Y G. The Distance-Decay Function of Geographi-cal Gravity Model:Power Law or Exponential Law[J]. Chaos, Solitons & Fractals, 2015, 77:174-189
    [9] 许珺, 陈娱, 徐敏政.空间网络的数据挖掘和应用[J].中国计算机学会通讯, 2015, 11(11):40-49 http://d.old.wanfangdata.com.cn/Periodical/dianzsw201604037

    Xu Jun, Chen Yu, Xu Minzheng. Data Mining and Applications in Spatial Networks[J]. Communications of the CCF, 2015, 11(11):40-49 http://d.old.wanfangdata.com.cn/Periodical/dianzsw201604037
    [10] Guimera R, Mossa S, Turtschi A, et al. The Worldwide Air Transportation Network:Anomalous Centrality, Community Structure, and Cities' Global Roles[J]. Proceedings of the National Academy of Sciences of the United States of America, 2005, 102(22):7794-7799 doi:  10.1073/pnas.0407994102
    [11] Guo D S. Flow Mapping and Multivariate Visualization of Large Spatial Interaction Data[J]. IEEE Transactions on Visualization and Computer Graphics, 2009, 15(6):1041-1048 doi:  10.1109/TVCG.2009.143
    [12] Chen Y, Xu J, Xu M Z. Finding Community Structure in Spatially Constrained Complex Networks[J]. International Journal of Geographical Information Science, 2015, 29(6):889-911 doi:  10.1080/13658816.2014.999244
    [13] Expert P, Evans T S, Blondel V D, et al. Uncovering Space-Independent Communities in Spatial Networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2011, 108(19):7663-7668 doi:  10.1073/pnas.1018962108
    [14] Liu X, Murata T, Wakita K. Detecting Network Communities Beyond Assortativity-Related Attributes[J]. Physical Review E, 2014, 90(1):012806 doi:  10.1103/PhysRevE.90.012806
    [15] Guo D S. Regionalization with Dynamically Constrained Agglomerative Clustering and Partitioning (REDCAP)[J]. International Journal of Geographical Information Science, 2008, 22(7):801-823 http://d.old.wanfangdata.com.cn/Periodical/zgdl-e201904001
    [16] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast Unfolding of Communities in Large Networks[J]. Journal of Statistical Mechanics:Theory and Experiment, 2008(10):10008 doi:  10.1088-1742-5468-2008-10-P10008/
    [17] Sobolevsky S, Campari R, Belyi A, et al. General Optimization Technique for High-quality Community Detection in Complex Networks[J]. Physical Review E, 2014, 90(1):012811 doi:  10.1103/PhysRevE.90.012811
    [18] 刘军.整体网分析——UCINET软件使用指南[M]. 2版.上海:格致出版社, 2014

    Liu Jun. Lectures on Whole Network Application-A Practical Guide to UCINET[M]. 2nd ed. Shanghai:Gezhi Press, 2014
    [19] Burt J E, Barber G M, Rigby D L. Elementary Statistics for Geographers[M]. 3rd ed. New York:Guilford Press, 2009
    [20] Lee J, Wong D W. Statistical Analysis with ArcView GIS[M]. New York:John Wiley & Sons, 2001
    [21] Newman M E. Modularity and Community Structure in Networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(23):8577-8582 doi:  10.1073/pnas.0601602103
    [22] Seaton K A, Hackett L M. Stations, Trains and Small-World Networks[J]. Physica A:Statistical Mechanics and Its Applications, 2004, 339(3):635-644 http://d.old.wanfangdata.com.cn/OAPaper/oai_arXiv.org_cond-mat%2f0311254
    [23] 钟柯, 肖昱, 许珺, 等.基于列车运行网络的中国城市中心性分析[J].地球信息科学学报, 2012, 14(1):85-93 http://d.old.wanfangdata.com.cn/Periodical/dqxxkx201201013

    Zhong Ke, Xiao Yu, Xu Jun, et al. Measuring City Centralities Based on the Train Network of China[J]. Journal of Geo-Information Science, 2012, 14(1):85-93 http://d.old.wanfangdata.com.cn/Periodical/dqxxkx201201013
  • [1] 郭艺文, 蔡建南, 陈袁芳, 邓敏, 赵斌.  网络约束下局部空间同位模式的扫描统计方法 . 武汉大学学报 ● 信息科学版, 2022, 47(9): 1383-1389. doi: 10.13203/j.whugis20200177
    [2] 刘涛, 张晓辉, 杜萍, 杜清运, 李爱勤, 龚丽芳.  文本大数据中地震应急的知识发现方法 . 武汉大学学报 ● 信息科学版, 2020, 45(8): 1205-1213. doi: 10.13203/j.whugis20200106
    [3] 马超, 孙群, 陈换新, 徐青, 温伯威.  加权网页排序算法在道路网自动选取中的应用 . 武汉大学学报 ● 信息科学版, 2018, 43(8): 1159-1165. doi: 10.13203/j.whugis20160127
    [4] 王增利, 刘学军, 陆娟, 吴伟, 张宏.  犯罪网络构建及其时空分析——以入室盗窃为例 . 武汉大学学报 ● 信息科学版, 2018, 43(5): 759-765. doi: 10.13203/j.whugis20150666
    [5] 杨静, 程昌秀, 李晓岚, 陈驰.  网络结构空间格局相似度分析——以1938~2014年北京市骨干交通网络为例 . 武汉大学学报 ● 信息科学版, 2016, 41(12): 1593-1598. doi: 10.13203/j.whugis20140569
    [6] 李德仁, 沈欣, 龚健雅, 张军, 陆建华.  论我国空间信息网络的构建 . 武汉大学学报 ● 信息科学版, 2015, 40(6): 711-715. doi: 10.13203/j.whugis20150021
    [7] 田晶, 王一恒, 颜芬, 熊富全.  一种网络空间现象同位模式挖掘的新方法 . 武汉大学学报 ● 信息科学版, 2015, 40(5): 652-660. doi: 10.13203/j.whugis20130448
    [8] 王赛, 邓福兴, 程子敬, 王兆俊, 张安安, 吴静.  面向空间延迟可容忍网络的路由协议仿真研究 . 武汉大学学报 ● 信息科学版, 2015, 40(10): 1312-1316. doi: 10.13203/j.whugis20130408
    [9] 田晶, 何遒, 周梦杰.  运用Q统计分析网络空间现象关联模式 . 武汉大学学报 ● 信息科学版, 2014, 39(4): 486-491. doi: 10.13203/j.whugis20120562
    [10] 陆锋, 张恒才.  大数据与广义GIS . 武汉大学学报 ● 信息科学版, 2014, 39(6): 645-654. doi: 10.13203/j.whugis20140148
    [11] 孟令奎, 娄书荣, 黄长青.  利用空间格网划分的P2P Delaunay网络路由方法 . 武汉大学学报 ● 信息科学版, 2012, 37(2): 205-209.
    [12] 栾学晨, 杨必胜, 张云菲.  城市道路复杂网络结构化等级分析 . 武汉大学学报 ● 信息科学版, 2012, 37(6): 728-732.
    [13] 邱国利, 蒋国平, 宋玉蓉.  一种带节点移动的手机蓝牙病毒传播模型 . 武汉大学学报 ● 信息科学版, 2010, 35(5): 610-613.
    [14] 马江林, 赵忠明, 汪承义, 钟建强.  一种新的基于Gabor小波的非监督纹理分割方法 . 武汉大学学报 ● 信息科学版, 2009, 34(1): 11-14.
    [15] 焦利民, 刘耀林, 任周桥.  基于自组织神经网络的空间点群聚类及其应用分析 . 武汉大学学报 ● 信息科学版, 2008, 33(2): 168-171.
    [16] 安杨, 边馥苓, 关佶红.  基于Ontology的网络地理服务描述与发现 . 武汉大学学报 ● 信息科学版, 2004, 29(12): 1063-1066.
    [17] 朱欣焰, 陈能成, 王密, 刘琳.  面向网络的海量影像空间数据在线分发技术 . 武汉大学学报 ● 信息科学版, 2003, 28(3): 288-293.
    [18] 齐华, 李德仁, 朱庆.  确定射线空间相邻关系的两个非角度算法的时间复杂度分析 . 武汉大学学报 ● 信息科学版, 2003, 28(5): 611-614.
    [19] 陆锋, 周成虎, 万庆.  基于层次空间推理的交通网络行车最优路径算法 . 武汉大学学报 ● 信息科学版, 2000, 25(3): 226-232.
    [20] 张力, 沈未名, 张祖勋, 张剑清.  基于空间约束的神经网络影像匹配 . 武汉大学学报 ● 信息科学版, 2000, 25(1): 55-59.
  • 加载中
图(8) / 表(2)
计量
  • 文章访问数:  932
  • HTML全文浏览量:  165
  • PDF下载量:  207
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-08-07
  • 刊出日期:  2019-10-05

基于地理加权中心节点距离的网络社区发现算法

doi: 10.13203/j.whugis20180025
    基金项目:

    国家重点研发计划 2017YFB0503601

    国家自然科学基金 41471327

    作者简介:

    万幼, 博士, 讲师, 从事地理大数据和空间数据挖掘理论与方法研究。wanyou@whu.edu.cn

    通讯作者: 刘耀林, 博士, 教授。yaolin610@163.com
  • 中图分类号: P208

摘要: 提出一种基于地理加权中心节点距离的网络社区发现算法(geographical weighted central node distance based Louvain method,GND-Louvain)。该算法扩展了传统复杂网络领域的经典社区发现方法Louvain,利用地理加权中心节点来度量社区发现过程中的空间距离关系,并将此距离衰减效应加入到距离模块度模型中,以此来计算和评估空间网络社区划分结果的质量,并探究了空间社区发现结果不稳定的原因。通过定义节点计算顺序,保证了社区发现结果的质量和稳定性。利用中国铁路网线路数据,设计了5种不同空间约束的空间社区发现对比性实验。结果证明,GND-Louvain算法的准确性最高,并且算法结果最稳定。

English Abstract

万幼, 刘耀林. 基于地理加权中心节点距离的网络社区发现算法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(10): 1545-1552. doi: 10.13203/j.whugis20180025
引用本文: 万幼, 刘耀林. 基于地理加权中心节点距离的网络社区发现算法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(10): 1545-1552. doi: 10.13203/j.whugis20180025
WAN You, LIU Yaolin. Community Detection Algorithm Based on Geographical Weighted Central Node Distance[J]. Geomatics and Information Science of Wuhan University, 2019, 44(10): 1545-1552. doi: 10.13203/j.whugis20180025
Citation: WAN You, LIU Yaolin. Community Detection Algorithm Based on Geographical Weighted Central Node Distance[J]. Geomatics and Information Science of Wuhan University, 2019, 44(10): 1545-1552. doi: 10.13203/j.whugis20180025
  • 空间网络是节点位于一个可物理度量空间中的网络[1]。通常是在一个二维空间,采用欧氏距离度量。社区结构是复杂网络的一个基本属性[2]。复杂网络的社区发现是识别一个节点的集合,使得集合内节点之间的相互作用比它们与集合外节点的相互作用更强[3]。而空间网络的社区发现能获得分布在地理空间中的非随机连接所产生的、具有高内聚低耦合的子网络社区结构,从而揭示城市内部和城市之间的空间交互模式[4]、道路交通网络的空间分布格局[5]、人群活动行为模式[6]等,因此具有很好的研究意义。

    与传统复杂网络的结构构成不同,空间网络中节点间的连接概率不仅与其自身的度有关,还与空间距离有关。其连接概率呈现随距离衰减的效应[7-8]。当涉及到由地理现象和人类活动所构成的空间网络社区发现时,除网络拓扑关系外,常需要考虑其他空间约束的影响。针对空间网络社区发现的研究方法可分为4种[9]:①忽略空间距离关系,直接采用传统的社区发现方法对网络拓扑结构进行社区挖掘[10];②在传统社区发现方法中加入空间邻近约束条件,获得区域内部空间连通的社区结果[11];③在网络连接的属性中加入空间距离的反作用影响,重构空间网络,再利用传统社区发现方法挖掘社区结构[12];④改进网络模块度计算的概率模型,建立距离与拓扑关联关系相结合的节点间联系的联合概率函数,作为距离模块度计算的期望值部分,从而挖掘出剔除距离因素之后仍然紧密联系的空间社区[13-14]。此类方法识别出的社区结果可以分析除了空间距离影响之外,其他构成社区空间结构的因素,因此可以获得更多有价值的知识[13-14]。如Expert等[13]采用剔除距离影响的模块度模型,从比利时手机通话数据中识别出在空间上存在重叠的两大社区,而两大社区的空间分布揭示了比利时的两大语言体系的所在区域。

    现有空间网络社区发现方法存在如下的两个问题:①对社区空间距离的度量方式有多种形式,但缺乏由此造成的社区发现结果的差异性分析研究。如图 1所示,在度量两个子社区1和2之间的距离时,可使用所有连接边/存在空间邻近区域的连接边之间的最短/平均/最大距离[15], 或子社区的地理几何中心节点距离,或子社区的度中心节点距离。不同的距离度量方式得到的距离值差异很大,这个差异直接影响到它们之间距离衰减效应的计算,进而影响空间社区发现的结果。到目前为止,还未有针对此影响探究何种度量方式更加准确和有效的研究。②缺乏对空间网络社区发现方法稳定性的分析研究。在空间网络社区发现中最普遍采用的是基于快速展开策略的模块度最大化方法Louvain[16]。此方法的效率和准确性很高,适合于大型网络[1, 17],但其社区发现结果存在不稳定性。当网络节点输入顺序改变时,会导致计算结果的显著不同。

    图  1  两个网络子社区之间的距离度量方式

    Figure 1.  Different Distance Measures Between Two Meta-Communities

    针对以上两个问题,本文提出一种新的空间网络社区发现算法(geographical weighted central node distance based Louvain method, GND-Louvain)。算法采用地理加权中心节点来度量子社区间的距离,并在模块度公式中加入距离衰减效应影响,利用距离模块度,发现隐含的有意义的网络社区结构。然后通过限定空间节点的输入和计算次序,在保证社区发现结果质量的同时提高了方法的稳定性。

    • 本节首先介绍空间网络中地理加权中心节点的定义和计算方法,然后给出基于地理加权中心节点的空间网络社区发现方法。

    • 复杂网络领域针对网络节点中心性的测量主要有3个指标:点度中心度、接近中心度和介数中心度[18]。其中,节点的接近中心度是该节点到其他所有节点的最短路径之和的倒数,可反映节点与网络中其他节点的接近程度。地理加权中心节点的定义借鉴接近中心度指标,并融合了空间点模式分析中加权中位数中心节点的概念[19-20]。它以网络节点间最短路径衡量节点间的距离,最终选取到其他所有网络节点的距离之和最小的(即接近中心度最大)的那个节点。图 1中节点2和1分别是子社区1和2的地理加权中心节点。

      地理加权中心节点综合考虑了空间网络所具有的空间距离和网络连接特征,被广泛应用于交通网络中各种资源的合理配置中,以最小化资源获取的代价。

    • 空间网络的社区发现以社区内网络节点间的关联最大化为目标进行网络节点的分割或合并操作。模块度最大化是广为应用的一种可量化的社区发现方法[2-3]。特别是空间网络的社区发现,基本都是基于模块度最大化算法的扩展或改进[1, 12-13]

      定义1  传统模块度(NG-modularity)[21]。对于网络一个给定的划分C={c1, c2cq},传统模块度的计算公式为:

      $$ M(C)=\frac{1}{2 m} \sum\limits_{c \in C} \sum\limits_{i, j \in \epsilon} W_{i j}-P_{i j} $$ (1)

      式中,m是网络总边数;ij是同一个社区的节点对,节点ij之间连接的权重Wij用连接数来度量;Pij是随机情况下节点ij之间连接的概率, $P_{i j}=\frac{k_{i} k_{j}}{2 m}$,其中kikj分别是节点ij的度。

      模块度的计算公式度量了真实网络与随机情况下,社区内部的边的联系紧密程度和社区之间的边的联系的紧密程度。网络划分的模块度可以用来衡量社区划分的质量。模块度取值在[-1, 1]之间,通常当模块度大于0.3时,认为网络中存在有非随机模式产生的社区结构。且模块度取值越大,社区内部的连接越紧密。

      定义2  距离模块度(D-modularity)[14]。对于网络一个给定的划分C={c1, c2cq},距离模块度的计算公式为:

      $$ M_{\mathrm{dist}}(C)=\frac{1}{2 m} \sum\limits_{c \in C} \sum\limits_{i, j \in \epsilon} W_{i j}-P_{i j} $$ (2)

      与传统模块度的随机连接概率不同,距离模块度的随机连接概率为:

      $$ P_{i j}=\frac{\hat{P}_{i j}+\hat{P}_{j i}}{2 m}, \hat{P}_{i j}=\frac{k_{i} k_{j} f\left(d\left(v_{i}, v_{j}\right)\right)}{\sum\limits_{v_{q} \in V} k_{q} f\left(d\left(v_{q}, v_{i}\right)\right)} $$ (3)

      此处增加了一个距离衰减函数f来度量节点间随距离d衰减的连接概率。本文中使用指数型的距离衰减函数[7-8],其定义如下:

      $$ f(x)=\mathrm{e}^{-(x / \sigma)^{2}} $$ (4)

      式中,x是距离值;e是自然对数底;σ是控制距离衰减幅度的变量。σ可被设定为一个数据驱动的自适应数值(例如,当前空间网络所有点对距离的平均值)。根据指数函数性质,高于此平均值的距离x的连接,将获得较大的距离衰减影响,而低于此平均值的连接,会获得较小的距离衰减影响。并且当σ接近无穷大时,距离模块度变为传统模块度。

      GND-Louvain算法扩展了经典的基于模块度的社区发现方法Louvain。它采用距离模块度作为度量社区内部连接紧密性的标准。并且,在社区发现的过程中,不断地重新计算并更新子社区的地理加权中心节点,以此度量子社区之间的距离衰减效应。具体的,GND-Louvain算法是一个类似凝聚层次聚类的迭代分层的过程,主要有3个步骤:

      1) 通过迭代方式遍历节点集合,找出使每个节点模块度变化最大的连接节点与之合并,直到当前节点集合的任意节点移动都不会再使模块度增加时,结束迭代,并形成一层社区分割结果。

      2) 将获得的社区分割结果的每个子社区视为新的节点,子社区之间的连接视为新的边,以此构成一个新的空间网络,再代入步骤1)进行迭代遍历,形成更高一层的社区分割结果。

      3) 当步骤2)的重复迭代过程不能使模块度再增加时,输出最终的社区分割结果。

    • 空间网络数据的来源是全国铁路交通网络数据。利用网络爬虫技术,从中国铁路客运服务中心网站获取了2017年4月间所有在运行的铁路客运线路数据, 包含7种列车类型(城铁、动车、高铁、普快、特快、临客和卧铺)和5 470条运行线路,然后对数据进行了预处理和网络建模。

      数据预处理包括:将所有火车站对应到所在地级市;以城市名替代原铁路线路中的站点名;以城市的内几何中心计算空间距离矩阵;以各城市地理边界计算空间邻接矩阵。海南省因与大陆城市无邻接关系,其省内的线路数据被删除。

      铁路网络的建模方式主要有两种:L空间模型和P空间模型[22]。L空间模型中,在一条经过多个点的线路上,只有相邻的两个节点才被认为是直接相连的。P空间模型中,由一条线路连接的所有节点都被认为是两两相连的。图 2描述了一条铁路线路基于两种不同空间模型所形成的网络。比较发现,P空间模型忽略了两个节点之间的拓扑邻近约束,而注重于是否有关联,因此更适于做社区发现分析[23]。利用P空间模型构建的铁路网络可用一个加权连接矩阵来表达,矩阵元素就是所有途经两个城市的列车总数。

      图  2  铁路网络的L空间模型和P空间模型

      Figure 2.  The Space L Model and Space P Model for Train Nets

      在所有7种火车类型中,由于城际铁路的运行线路少,范围分散,并且与高铁列车在速度上匹配,路程上互补,因此将其合并到高铁线路中。最终获取了315座城市所组成的6个不同类型的空间网络,共包含4 147条铁路运行线路数据。6个空间网络所含城市和连接的个数等属性信息如表 1所示。

      表 1  6个不同类型空间网络的节点和边个数

      Table 1.  The Number of Nodes and Edges of Six Networks

      空间网络 铁路类型 城市数 连接数 所有连边的平均长度/km 所有节点间平均距离(σ值)/km
      CG-net 高铁 167 5 044 740 997
      D-net 动车 175 1 824 501 1 174
      K-net 普快 294 13 920 895 1 326
      T-net 特快 212 3 812 913 1 291
      X-net 临客 203 1 370 449 1 379
      Z-net 卧铺 177 3 337 1 004 1 203
    • 本节选用广东省的城铁网络数据作为样本数据,进行GND-Louvain算法的准确性和有效性实验分析。并将其结果与基于传统模块度的Louvain方法(简称NG-Louvain)进行比较。两个算法的社区分割结果都是将城铁网络划分为了两个子社区,结果的可视化效果如下图 3所示。

      图  3  两种不同模块度的社区发现结果比较

      Figure 3.  Community Detection Result of Two Modwlarities on a Sample Network

      图 3显示出在两种不同算法下,广东省省会广州市的计算结果存在差异。在NG-Louvain算法中,使用传统模块度只考虑了空间网络的拓扑关系,此时由于广州与东南部两座距离相近的东莞和深圳市之间具有高的连接数,因此被分割到东部社区中。而在GND-Louvain算法中,综合考虑了空间网络的拓扑和距离因素,广州被分割到西部社区中。虽然广州与东莞和深圳之间的实际连接数更高,但由于距离邻近,其期望连接数也很高,导致距离模块度的值不如其与西南部城市的高。GND-Louvain算法的结果显示出,去掉距离衰减的因素影响后,西南部城市实际上获得了更多额外的与广州市联系的隐含因素。相对而言,东部城市与广州市的联系则主要依赖于其与广州市的距离更近。

      表 2采用两种模块度公式计算了两个算法社区分割结果的模块度数值。NG-Louvain算法获得了略高于GND-Louvain算法的传统模块度值,而GND-Louvain算法则获得了高出NG-Louvain算法很多的距离模块度值。由于图 3显示基于距离模块度的GND-Louvain算法能获得更有价值的隐含信息,本文接下来的实验也将采用距离模块度进行社区发现的质量评价。

      表 2  两个社区发现算法结果的模块度数值对比

      Table 2.  Modularities of Two Partition Results

      社区分割结果 传统模块度 距离模块度
      NG-Louvain社区分割结果 0.190 0.079
      GND-Louvain社区分割结果 0.181 0.118
    • 本节针对全国铁路线路数据构建的6个真实的地理空间网络,设计了5个基于不同社区距离度量方式的算法,来对比验证GND-Louvain算法的准确性和稳定性。除上节不考虑距离衰减因素的NG-Louvain算法外,另外3个都是基于距离模块度的,分别是:①基于地理几何中心节点距离的D-Louvain算法[14];②基于网络度中心节点距离的DD-Louvain算法;③基于空间邻近约束的D-REDCAP(regionalization with dynamically constrained agglomerative clustering and partitioning)算法。其中D-Louvain算法和DD-Louvain算法的实现与GND-Louvain算法类似,仅在距离计算时采用了不同的中心点。此3个算法和GND-Louvain都采用了Louvain来实现模块度的最大化,以消除各方法在社区迭代过程中可能存在的其他差异。而D-REDCAP算法是在经典的区域分割算法REDCAP[15]中用距离模块度矩阵替代了原有的模块度矩阵,并且模块度最大化采用的是层次聚类方法。该方法依据最初的节点间距离矩阵获得节点合并的距离模块度增益矩阵,并不断合并存在空间邻近关系且模块度增益最大的两个节点或子社区。在社区迭代合并过程中,需要不断更新计算的是模块度增益矩阵。参考Guo[15]的建议,子社区合并后,新社区与其他子社区之间的模块度增益采用的是二者间所有模块度增益的平均值。而最终社区发现结果质量的衡量采用的是距离模块度,其数值越高,则说明社区发现的结果越好。其中,NG-Louvain算法结果也使用了式(2)重新计算获得其距离模块度值,以方便进行统一比较。

      实验中发现,基于Louvain快速展开策略实现距离模块度最大化,虽然效率快,准确性高,但稳定性不足。不同的节点输入次序会得到差异性很大的结果。因此,对4个基于Louvain的算法进行了重复百次以上的运算(重复次数初始化为网络节点总个数),每次运算均随机产生节点输入次序。然后对获取的距离模块度值进行范围和频次统计。图 4是针对6种不同空间网络,采用5种算法的距离模块度取值结果。蓝柱是重复运算的最小模块度取值,代表算法的最差结果,其取值越大说明算法越好;红柱代表重复运算的模块度波动范围,代表了算法的稳定性,其取值越小说明算法越好。二者之和是重复运算得到的最大模块度值,代表算法的最好结果,其取值也是越大越好。

      图  4  6个空间网络社区发现结果的模块度大小比较

      Figure 4.  Modularities Comparison of Six Train Nets

      图 4可以得到如下结论:

      1) 4个基于Louvain的算法总是获得较D-REDCAP更大的距离模块度。原因除了采用凝聚层次聚类的固有缺陷外,D-REDCAP在节点合并时采用严格的空间邻域约束,此约束对模块度最大化策略影响很大。

      2) 4个基于Louvain的算法在重复百次以上运算后,都能获得相近的最大模块度取值,说明了Louvain的快速展开策略的准确性较高。而对比模块度取值范围情况,GND-Louvain算法在6个网络的社区发现中的波动范围总是最小的,也说明了算法是相对稳定的。

      3) 相关性分析结果发现,距离模块度取值范围的波动与空间网络的连接边平均长度显著的正相关。

      图 5所示,3种距离模块度Louvian算法的稳定性受到空间网络本身的影响。但与D-Louvain和DD-Louvain相比,地理加权中心节点距离的GND-Louvain算法受空间网络本身的影响总是最小的,且变化的幅度也总是最小的。因此可认为,GND-Louvain算法在准确性和稳定性上,优于其他几种距离和邻域约束的社区发现算法。

      图  5  3个距离模块度算法的模块度波动范围与网络平均边长度之间的线性回归分析

      Figure 5.  Linear Regression Analysis Between Range of Modularity and Average Distance of Connections

      此外,对比各算法重复实验后模块度取值的频率分布,GND-Louvain算法在其中4个网络(CG-net、D-net、K-net、X-net)的实验中都是在最大模块度处获得最高频率,而剩余两个网络(T-net和Z-net)中是在最大模块度处获得第二高频率。由此也说明,GND-Louvain算法较另外4种算法能更容易地获得最大模块度结果,具有更高的稳定性。

    • 本节实验的目标是在不影响算法准确性的前提下,提升GND-Louvain算法的稳定性和效率。分析距离模块度公式,在节点合并时有3个因素会影响到模块度的取值:节点度、节点间连接数和节点间距离。节点度越小,节点间连接数和距离值越大,将会获得越大的模块度增益。然而,相对于一个节点,其与其他节点的连接数和距离通常是一对多的关系,无法拿来作为节点合并次序的参考。因此,选择节点度作为影响因子,以实验方法分析节点度升序和降序排列时,GND-Louvain算法的模块度取值情况。

      图 6所示,当节点序列固定时,GND-Louvain算法针对各空间网络都能获得稳定的模块度取值。两类节点度排序情况下,GND-Louvian算法的模块度实验结果的绝对差异很小。接下来采用最大最小值标准化方法,将此模块度取值与对应空间网络重复多次运算时的模块度取值范围进行标准化,计算相对差异。标准化公式如下:

      $$ x_{\text {normalization }}=\frac{x-\min }{\max -\min } $$ (5)

      图  6  两类节点度排序情况下GND-Louvain算法的距离模块度

      Figure 6.  Modularities of Two Degree Ordered GND-Louvain

      模块度的标准化转换用了原GND-Louvain算法和D-Louvain算法重复实验结果,获得的数值体现了节点排序后模块度取值在原算法和D-Louvain算法中的排名情况。标准化数值越高,说明模块度排序值越高,即节点排序的效果越好。两类节点度排序情况下,GND-Louvain算法结果的标准化结果如图 7所示。

      图  7  两类节点度排序下GND-Louvain算法模块度标准化值

      Figure 7.  Normalized Modularities of Two Degree Ordered GND-Louvain

      图 7的实验结果可以得到如下结论:

      1) 节点度升序排列的GND-Louvain算法获得了较点度降序排列更稳定的模块度结果。虽然节点度降序排列的GND-Louvain在4个网络(D-net、K-net、X-net和Z-net)中都获得了较节点度升序排列略好和相近的排序值,但其在另两个网络(CG-net和T-net)中却获得了较节点度升序排列低很多的排序值。分析原因是节点度降序排列时,先进行社区合并运算的节点会对模块度的变化影响很大,这导致了最终模块度取值不稳定。

      2) 节点度升序排列的GND-Louvain算法在用原D-Louvain结果的模块度标准化中,总是取得较高的排名。因此利用节点度升序策略改进的GND-Louvain算法能提升基于几何中心节点距离和距离模块度的D-Louvain算法的准确性和稳定性。考虑到社区合并过程中的子社区也是一个空间网络,采用空间和网络属性相结合的地理加权中心节点度量子社区间距离的效果更好。

      图 8以城铁和高铁网络数据实验为例,展示了节点度升序排列的GND-Louvain算法的社区分割结果。算法共识别出4个社区,展示出由城铁和高铁网络构成的区域空间的交互关系和聚集模式。

      图  8  城铁和高铁网络数据及GND-Louvain社区分割结果

      Figure 8.  High-Speed Train Net and It's Community Detection Results by Using GND-Louvain

    • 与传统复杂网络的社区发现相比,空间网络的社区发现常需要将空间关系作为一个重要的约束条件,因此难度更大。本文通过实际数据的实验,对比了采用距离模块度和传统模块度进行社区发现的不同结果,以说明距离模块度在空间网络社区发现中的重要作用。首次探究了空间网络社区发现方法中采用的不同的距离度量方式对社区发现结果造成的影响程度。通过多组真实铁路网络数据的实验结果对比,验证本文所采用的基于地理加权距离的GND-Louvain算法的社区发现结果的准确性和稳定性最好。另一方面,分析了经典Louvain的快速展开模块度最大化计算策略存在不稳定性的原因和因素,并用实验证实采用节点度升序排列的GND-Louvain算法能在保证计算结果准确性的情况下,提高算法的稳定性。

      由于实验选用的铁路网络数据仅代表了一种类型的空间网络,因此GND-Louvain方法在其他空间网络上进行社区发现的适用性和有效性还需进一步的验证。后续将针对不同空间网络距离衰减函数的选取与建模、网络中心节点的选取和计算等问题开展深入的分析和实验研究。

参考文献 (23)

目录

    /

    返回文章
    返回