查看原文
其他

论文解读:网络社团划分算法居然还能解决区域划分争端?(内附combo代码下载)

王佳纯 集智俱乐部 2021-02-09


导语

区域划分问题本质上是一个政治问题,但辅以经济、文化、历史等信息作参考,能得到更有意义的划分结果。人们通常采用通勤区方法来界定劳动力市场区,从而划分区域。在这篇论文中,作者提出一种新的区域划分方法,将Combo算法应用到通勤数据上,从经济学角度利用网络社团划分方法来做区域划分。


论文题目:

Regions from the ground up: a network partitioning approach to c

论文地址:

https://doi.org/10.1177%2F2399808318804226



区域划分新方法


历史上,各地区的规模和大小问题一直是一个很重要的专题。区域是国家政治的基本结构,其固有的政治性质表明了区域划分问题本质上是一个现实的政策问题。但辅以经济、文化、历史等信息作参考,我们能综合考量各个地区的特点,确定更合理的区域边界,得到更有意义的划分结果。


在经济学和区域研究中,有各种不同的定义区域的方法。这是一个丰富多样的研究领域,但也意味着我们需要弄清楚所使用的区域构建块和相关基本概念。最基本的一点,区域是一个国家的次级地理单元


       

     

中国七大区


这篇论文尝试利用网络社团划分方法来做区域划分。在过去的15年里,网络分析领域的社团发现(community detection)问题受到广泛关注,科研人员提出各种不同算法来解决这个问题,其中包括性能优异的Combo算法。


社团发现算法已经成功应用到各种数据集上。虽然还未形成统一的方法和术语,但对于网络的描述是明确的:它包含一组节点,节点之间有边连接。在论文的案例中,节点是通勤的起点和终点,边是它们之间的连接。一个社团(或者集群)被定义为起点-终点对的集合。社团内部的节点连接密度很高,社团间的节点连接密度很低,这与通勤区(Travel to Work Area, TTWA)方法的“自治(self-containment)”概念相似。


通勤区方法是英国政府和地方当局常常使用的统计工具,通勤区被定义为人口通勤到大城镇、城市、大都市就业的区域。在该区域中,从事经济活动的居民中至少有75%的人在该地区工作,而且,在该地区工作的人中,至少有75%的人居住在该地区。


这篇论文从经济学的角度,利用网络社团划分方法Combo算法来做区域划分。不仅就如何界定经济区域问题作出方法上的贡献,还就当前政策背景下的区域重组争议作出经验上的贡献。



案例分析:

苏格兰的区域划分


这篇论文以苏格兰作案例研究。之所以选择苏格兰,是因为近年来各利益相关方接连提出地方政府重组问题。虽然苏格兰政府尚未就此做出任何决定,但作者希望这项研究能为这一重要的政治议题提供参考依据。


2016年法国将22个大都市区缩减为13个,其经验表明,区域地理学(regional geography)不仅仅是一项深奥的学术研究,它的的确确有着非常重要的经济和政治影响,具有实际应用价值。


作者将Combos算法应用到2011年苏格兰的通勤数据上,得到一组新的区域。这里使用的通勤数据是英国2011年人口普查得到的所有16岁以上受访者的居住地和工作地。


社团评估的三个维度


我们可以用模块度(modularity score)来评估社团划分的好坏,用集群密度(cluster density)、流通比(bleed ratio)来描述社团的特点。


  • 模块度是一种衡量网络社团划分的结构强度的方法,较高的模块度意味着各个社团内联系紧密,划分效果好; 相反,较低的模块度意味着社团间有较大的相互作用,划分效果差。


  • 集群密度是一个集群内实际连接与所有可能连接的比例(若集群中所有节点两两之间都有边相连,则集群密度为1),值越高,内部联系越紧密。


  • 流通比是通勤的起点或终点在给定社团以外的占比,衡量一个社团对其它地区的“吸引力”。较低的流通比表示较高程度的区域自治,而较高的流通比表示与其他区域的流通程度较高。


通勤区方法 VS Combo算法


论文实验将苏格兰划分为17个区域,这数量介于目前的32个行政区和1973年至1996年期间的九个行政区之间,同时与近期提议改革的19个行政区数目很接近,然而远远低于现有的45个通勤区。


       

     

将苏格兰划分为17个区域


从实验结果可以看出,划分出的这17个Combo区域与通勤数据的地理特性是一致的,也与当前的行政区非常相似。新的17个区域之间在大小和人口方面有很大差别,但考虑到苏格兰的经济多样性和地形多样性,这是合理的。


            17个区域的集群密度、流通比、人口


社团划分的整体模块度为0.74。岛屿群(Orkney、Shetland 和Western Isles)的集群密度高,流通比低,这表明内部联系紧密,高度自治。 


相比之下,位于Glasgow西部的Inverclyde集群密度高,但流通比(0.43)也远远高于其它地区。


Greater Glasgow拥有最低的集群密度和相对较高的流通比,这表明,该地区拥有大量就业机会,吸引来自更远地区的通勤者。


       

     

行政区、通勤区、Combo区域对比


在上图中,a图是现有的32个行政区,b图是45个通勤区,c图是Combo算法得到的17个区域。


将Combo算法得到的区域与苏格兰现有的行政区进行比较,可以知道Combo算法的结果是合乎逻辑的。如果苏格兰未来的区域重组改革目标是减少区域数量,那么Combo算法可以提供一种与现有行政区域密切匹配的方法。


将Combo算法得到的区域与通勤区进行比较,显然它们有很大区别。最明显的区别体现在苏格兰北部,那里的通勤区非常分散,这是通勤区方法使用的构建块和统计参数决定的,表明该区域内部联系程度高。


究竟哪种方法是正确的呢?这取决于区域划分的目的。对于像苏格兰北部这样的农村地区,从功能经济学(functional economic)角度来看,通勤区方法更有意义;从行政角度来看,Combo算法更有意义。


结果差异


下图提供更详细的信息,展示了Greater Glasgow的Combo区域、行政区和通勤区。


Combo区域和现有行政区在规模和人口方面差别很大,而Combo区域和通勤区在规模和人口方面更为接近,考虑到不同区域划分方法有其自身的功能特性,这样的结果是合乎逻辑的。


有趣的是,Combo方法排除了通勤区的南部和东北部地区,这是因为这两个地区有大量前往Glasgow以外地区的通勤。这也说明,对同一个问题采用不同的经验方法会有不同的结果。

       

Greater Glasgow的Combo区域、行政区和通勤区


通勤区方法和Combo算法的结果差异取决于所采用的方法特性和基本参数不同。 就通勤区方法而言,它可能受到使用75%的自治阈值的影响,而在Combo方法中,它纯粹基于连接强度来将节点分配给对应的集群。


这两种方法都不是完美的,但都有助于我们理解区域的功能地理学(functional geography)。然而,当涉及区域重组问题时,Combo方法可能更有用,因为它能够从头开始,利用任何类型的网络数据生成更大的地理单位。



基于模块度的Combo算法


Combo算法是Sobolevsky等人在2014年提出的一种网络社团划分方法。Combo算法搜索一个最佳的社团划分方案,最大限度地增加社团内部的连接,减少社团间的连接,这就是模块化(modularity)。


通常采用模块度(即模块化度量值来衡量网络社团划分的模块化程度,最早由Mark NewMan 提出。社团内联系紧密,社团间联系疏松,则模块化程度高,模块度趋近于1。


       

     

网络社团划分示意图


Combo算法使用迭代过程,在每次迭代中,识别连接紧密的起点-终点对,将它们分到同一个社团中。通勤区方法也是使用起点-终点对,但遵循不同的处理过程。


Combo算法描述


输入:图网络。在论文的案例中,网络的节点就是通勤起点和终点区域的几何中心。默认情况下,初始化所有节点属于同一个社团。


步骤1对于每个起点-终点对,计算把节点从原始社团移动到目标社团的最佳增益,搜索最优的社团划分方式(即迭代测试每个节点被划分到不同社团的情况)。


步骤2:根据最优划分方式,将节点分配到目标社团。


步骤3:社团节点更新后,再次计算移动节点到不同社团的最佳增益,搜索最优的社团划分方式。


步骤4:测试最终划分方案是否足够好,如果达到预设标准,就结束;否则,回到步骤2。这一步确保网络社团划分的模块度尽可能高。


输出:Combo算法的最终输出是一组社团,在论文的案例中,就是得到苏格兰的一组新的区域。


仅用算法来划分区域是否可行呢?


答案是否定的。我们应该在算法计算和政策制定之间找到平衡点。仅依赖算法,虽然结果与经验一致,但缺乏政治可行性,无法在现实世界中推广;仅依赖当局政策,可能不适合我们的生活方式和管理方式。


举个例子,Inverclyde是苏格兰中部一个不太富裕、相对孤立的地区,近几十年来,该地区一直致力于克服后工业化(deindustrialisation)问题。


Combo算法告诉我们,这是一个经济独立的区域,但从政策角度来看,如果它想拥有更广泛的就业机会和房地产投资机会,它应该成为Greater Glasgow的一部分,这有利于加强基础设施建设和改善交通运输条件。


因此,算法方法可以提供很好的经验描述,但在区域的政治规范问题上无能为力。另外,在划分区域时还要考虑区域的历史和文化信息,否则可能引起当地人民的不满。


一言蔽之,算法可以帮助我们解决区域划分问题,但不能完全决定最终的区域划分。 这似乎是一个显而易见的问题,但在算法技术盛行的时代,值得再次重复。


Combo算法:

http://senseable.mit.edu/community_detection/

后台回复“Combo”即刻获得 Combo 代码下载


作者:王佳纯

编辑:王怡蔺




知乎Live预告


重磅Live,为你安排!


10月26日下午三点,杰弗里·韦斯特与张江助你一小时建立终身受用的思维框架!本次 Live 主要从三个模块重塑系统思维:


  • 模块一

    • 打破学科边界,跳脱固有思维框架

    • 什么是线性思维?

    • 生活中有哪些似是而非的错误结论?

  • 模块二

    • 发现规模法则,建立终身受用的思维框架

    • 规模法则是什么?

    • 应对复杂世界,有哪些普通人可以迅速掌握的简单法则?

  • 模块三

    • 如何判断你所在公司城市和国家的未来?

    • 如何用规模法则预测公司的未来?

    • 为什么城市的规模越大,你的收入越高?

    • 如何理解中国经济的过去和未来?


扫码直达

PC端:https://www.zhihu.com/lives/1037805317488357376



杭州讲座预告


集智俱乐部特别邀请到著名学者Geoffrey West教授,于10月30日在杭州师范大学做一场主题演讲,详细解读复杂系统中的规模法则。详情请见:杭州西溪,圣塔菲前所长、《规模》作者Geoffrey West,揭密公司生长死亡的规模法则!



集智AI学园:

https://campus.swarma.org





集智俱乐部QQ群|877391004

商务合作及投稿转载|swarma@swarma.org

◆ ◆ ◆

搜索公众号:集智俱乐部


加入“没有围墙的研究所”

让苹果砸得更猛烈些吧!

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存