基于Leiden算法的共享单车活动社区识别方法——南京案例分析

成骋; 陈文栋; 马洪生; 刘锡泽; 陈学武

doi:10.3963/j.jssn.1674-4861.2023.02.011

基于Leiden算法的共享单车活动社区识别方法——南京案例分析

doi: 10.3963/j.jssn.1674-4861.2023.02.011

成骋^{1, 2, 3,},
陈文栋^{1, 2, 3},
马洪生⁴,
刘锡泽^{1, 2, 3},
陈学武^{1, 2, 3, ,}

1.
东南大学江苏省城市智能交通重点实验室南京 211189
2.
东南大学现代城市交通技术江苏高校协同创新中心南京 211189
3.
东南大学交通学院南京 211189
4.
深圳市综合交通与市政工程设计研究总院有限公司广东深圳 518003

基金项目:

国家自然科学基金面上项目 52172316

详细信息

作者简介:
成骋（1996—），硕士研究生. 研究方向：交通运输规划与管理.E-mail: 448648293@qq.com

通讯作者:
陈学武（1968—），博士，教授. 研究方向：交通运输规划与管理、公共交通规划等. E-mail: chenxuewu@seu.edu.cn

中图分类号: U491.5+4
计量
- 文章访问数: 815
- HTML全文浏览量: 292
- PDF下载量: 45
- 被引次数: 0
出版历程
- 收稿日期: 2022-09-10
- 网络出版日期: 2023-06-19

A Method for Identifying Operation Zones of Free-floating Shared Bikes Based on Leiden Algorithm: A Case Study of the City of Nanjing

CHENG Cheng^{1, 2, 3
,},
CHEN Wendong^{1, 2, 3},
MA Hongsheng⁴,
LIU Xize^{1, 2, 3},
CHEN Xuewu^{1, 2, 3
, ,}

1.
Jiangsu Key Laboratory of Urban ITS, Southeast University, Nanjing 211189, China
2.
Jiangsu Province Collaborative Innovation Center of Modern Urban Traffic Technologies, Southeast University, Nanjing 211189, China
3.
School of Transportation, Southeast University, Nanjing 211189, China
4.
Shenzhen General Integrated Transportation and Municipal Engineering Design & Research Institute Co., Ltd, Shenzhen 518003, Guangdong, China

摘要

摘要: 目前共享单车分区运营管理中多以行政区为基础划分运营分区，未充分考虑共享单车出行需求的空间分布特征，导致较多跨区调度工作，严重影响运营效率。结合南京共享单车出行订单数据，研究了基于Leiden算法的共享单车活动社区识别方法，构建“出行起讫点-交通小区-空间交互网络”的3层数据结构；采用Leiden社区识别算法，识别共享单车活动社区，以活动社区作为共享单车的运营子区，进行运营区域划分；通过对比不同年份的共享单车活动社区识别结果，揭示共享单车出行空间分布的时变特征；选取网络模块度与计算效率2项指标，比较多种社区识别算法的性能，以验证Leiden算法在该研究问题中的有效性与优越性。结果表明：①针对2019年的单车出行数据，算法共识别出23个活动社区，共享单车区内出行的比例达到82.9%，相比传统分区方法增加了11%，表明本算法能够使得共享单车出行更多被划分于社区内部，可以提高区域内部的共享单车自循环率，改善分区运营效率；②相比于2019年，2022年社区尺度规模有所减小，社区数量有所增加，反映共享单车用户出行距离缩短，跨区出行比例降低。③Leiden算法的社区识别结果中，网络模块度达到0.55，相比传统的CNM算法（0.2）、Walktrap算法（0.31）和Louvain算法（0.42）有较大提高；运算时间为1.1 s，其他3种算法分别为6.4，1.6，1.4 s，在计算速度上也有明显提升。上述指标表明Leiden算法在分区质量和计算效率上优于同类其他算法。该方法揭示了共享单车出行的空间特征，可以获得更优的活动分区管理方案，为共享单车分区运营方案的合理确定提供了理论指导。
- 交通规划与管理 /
- 共享单车 /
- 活动社区识别 /
- Leiden算法 /
- 空间交互网络
Abstract: In the operation and management of the free-floating shared bike (FFSB) industry, the operation zones are mainly determined based on administrative boundaries of districts without fully considering the spatial distribu-tions of travel demand of FFSB, resulting in a large number of inter-zone transfer tasks which seriously deteriorates the efficiency of its operation. To this end, a new method for identifying operation zones of FFSB based on a Leiden community detection algorithm is developed using the bike order data from the City of Nanjing. A three-layer data structure of"travel OD (origin-destination)-traffic zone-spatial interaction network"is developed. The Leiden com-munity detection algorithm is used to identify the FFSB communities, which are taken as the operation sub-zones of FFBS to divide the operation zones. By comparing the communities of FFBS in different years, the temporal charac-teristics of the spatial distribution of FFBS travel are revealed. In addition, two indicators, network modularity and computational efficiency, are adopted to compare the performance of various community detection algorithms and to further verify the effectiveness and superiority of the Leiden algorithm in this research problem. The results show that: ①regarding the FFBS travel in 2019, the proposed algorithm identifies 23 activity communities, and the pro-portion of FFBS travel within the communities reaches 82.9%, which is higher than the traditional partition method by 11%. This indicates that the proposed algorithm can make more FFBS travel be classified within communities, in-crease the self-cycle rate of shared bikes within a zone, and improve the operational efficiency. ② Comparing to the case in 2019, the scale of communities decreased and the number of communities increases in 2022, implying a re-duction in the travel distance of FFBS users and a decrease in the proportion of inter-zone travel. ③ In terms of the results from the proposed algorithm, the network modularity reaches 0.55, which is significantly improved, compar-ing with the results of traditional CNM algorithm (0.2), Walktrap algorithm (0.31) and Louvain algorithm (0.42). The computation time of the proposed algorithm is 1.1 s, while for the other three algorithms, this value is 6.4, 1.6, and 1.4 s, respectively, which demonstrates the proposed algorithm has a significant improvement in computing effi-ciency. The above results show that the Leiden algorithm is superior to others in terms of partition quality and com-putational efficiency. The proposed method reveals that the spatial characteristics of FFBS travel and can obtain a better zonal management scheme for FFBS, which provides the theoretical guidance for the reasonable determina-tion of partition operation schemes of FFBS.
- traffic planning and management /
- free-floating shared bike /
- activity community identification /
- Leiden algorithm /
- spatial interactive network

HTML全文

图 1 方法框架

Figure 1. Methodology framework

下载: 全尺寸图片幻灯片

图 2 算法原理

Figure 2. Algorithmic process

下载: 全尺寸图片幻灯片

图 3 研究区域及交通小区

Figure 3. Study area and traffic analysis zones

下载: 全尺寸图片幻灯片

图 4 2019年划分结果

Figure 4. 2019 Division result

下载: 全尺寸图片幻灯片

图 5 不同划分方法的出行分布

Figure 5. Travel distribution of different division

下载: 全尺寸图片幻灯片

图 6 不同年份社区识别结果对比

Figure 6. Comparison of communty identification results in different yea

下载: 全尺寸图片幻灯片

表 1 igraph网络对象参数

Table 1. Igraph network object parameters

参数名称	取值
source	Zone_Number_O
target	Zone_Number_D
edge_attr	Float
create_using	None

下载: 导出CSV

表 2 订单数据字段及示例数据

Table 2. Order data fields and example

字段	示例
订单编号	hellobike16463135671001005290501
车辆编号	2800298581
开始时间	2022-03-03 21:19:32
起点经度	{" lon" : 118.921 960}
起点纬度	{" lat" : 32.054 643}
结束时间	2022-03-03 21:23:10
终点经度	{" lon" : 118.914 415}
终点纬度	{" lat" : 32.057 882}

下载: 导出CSV

表 3 不同划分方法的出行分布

Table 3. Travel proportion of different division methods

区域划分方式		出行分布比例/%
区域划分方式		区内出行	区间出行
按行政区划分	秦淮区	79.0	21.0
	玄武区	75.3	24.7
	鼓楼区	76.0	24.0
	建邺区	85.4	14.6
	雨花台区	63.8	36.2
	栖霞区	90.9	9.1
	江宁区	75.2	24.8
	浦口区	45.8	54.2
	六合区	98.7	1.3
按社区识别划分	社区1	83.3	16.7
	社区2	92.8	7.6
	社区3	81.0	19.0
	社区4	92.4	7.6
	社区5	78.9	21.1
	⋮	⋮	⋮
	社区20	85.0	15.0
	社区21	78.2	21.8
	社区22	84.2	15.8
	社区23	88.0	12.0

下载: 导出CSV

表 4 不同算法的性能表现

Table 4. Result performance of different algorithms

性能指标	CNM算法	Walktrap算法	Louvain算法	Leiden算法
模块度	0.20	0.31	0.42	0.55
运算时间/s	6.4	1.6	1.4	1.1

下载: 导出CSV

参考文献(34)

[1]	ZHU D, HUANG Z, SHI L, et al. Inferring spatial interaction patterns from sequential snapshots of spatial distributions[J]. International Journal of Geographical Information Science, 2018, 32(4): 783-805. doi: 10.1080/13658816.2017.1413192
[2]	吴雪颖. 地铁站域无桩共享单车骑行时空间特征及其影响因素研究[D]. 哈尔滨: 哈尔滨工业大学, 2019. WU X Y. Exploring the spatio-temporal characteristics and in-fluencing factors of sharing bike integrated with metro sta-tions[D]. Harbin: Harbin Institute of Technology, 2019. (in Chinese)
[3]	程小丹. 基于GWR的共享单车出行特征及影响因素空间异质性研究[D]. 西安: 长安大学, 2019. CHENG X D. Spatial heterogeneity of influencing factors and characteristics of shared bicycle travel based on GWR[D]. Xi'an: Chang'an University, 2019. (in Chinese)
[4]	崔树强, 朱佩娟, 张美芳, 等. 城市建成环境对共享单车使用空间分布的影响: 以长沙市为例[J]. 西南大学学报(自然科学版), 2020, 42(6): 89-99. https://www.cnki.com.cn/Article/CJFDTOTAL-XNND202006011.htm CUI S Q, ZHU P J, ZHANG M F, et al. Influence of urban built environment on the spatial distribution of bike sharing use: The case of Changsha city[J]. Journal of Southwestern University(Natural Science Edition), 2020, 42(6): 89-99. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XNND202006011.htm
[5]	袁朋伟, 董晓庆, 翟怀远, 等. 基于Nested Logit模型的共享单车选择行为研究[J]. 交通运输系统工程与信息, 2018, 18(5): 191-196. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201805028.htm YUAN P W, DONG X Q, ZHAI H Y, et al. Research on choice behavior of bike-sharing based on nested logit mod-el[J]. Journal of Transportation Systems Engineering and In-formation Technology, 2018, 18(5): 191-196. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201805028.htm
[6]	张昕明, 弓棣, 谢秉磊, 等. 计划行为理论视角下基于出行行为的公交防疫策略影响效果研究[J]. 交通信息与安全, 2021, 39(6): 117-125. doi: 10.3963/j.jssn.1674-4861.2021.06.014 ZHANG X M, GONG D, XIE B L, et al. A study of the effec-tiveness of epidemic prevention policies on public transit us-age based on the theory of planned behaviors[J]. Journal of Transport Information and Safety, 2021, 39(6): 117-125. (in Chinese) doi: 10.3963/j.jssn.1674-4861.2021.06.014
[7]	余周林. 共享单车影响下大学生出行行为分析及建模[D]. 西安: 长安大学, 2018. YU Z L. Analysis and modeling of college students'travel be-havior under the influence of shared bicycles[D]. Xi'an: Chang'an University, 2018. (in Chinese)
[8]	HUA M, CHEN X W, ZHENG S J, et al. Estimating the park-ing demand of free-floating bike sharing: A journey-da-ta-based study of Nanjing, China[J]. Journal of Cleaner Pro-duction, 2020, (244): 118764.
[9]	陈文栋. 城市轨道交通站点共享自行车停放设施配置研究——以南京市为例[D]. 南京: 东南大学, 2019. CHEN W D. Research on the configuration of bike-sharing parking facilities in urban rail transit stations: Taking Nanjing as an example[D]. Nanjing: Southeast University, 2019. (in Chinese)
[10]	张芳, 陈彬, 汤杨华, 等. 基于兴趣点聚类的无桩共享单车时空模式分析[J]. 系统仿真学报, 2019, 31(12): 2829-2836. doi: 10.16182/j.issn1004731x.joss.19-FZ0327 ZHANG F, CHEN B, TANG Y H, et al. Spatio-temporal pat-tern analysis of free-floating bike sharing based on interest point clustering[J]. Journal of System Simulation, 2019, 31(12): 2829-2836. (in Chinese) doi: 10.16182/j.issn1004731x.joss.19-FZ0327
[11]	郭彦茹, 罗志雄, 王家川, 等. 数据驱动的共享单车停放区规划方法研究[J]. 交通运输系统工程与信息, 2021, 21(6): 9-16. doi: 10.16097/j.cnki.1009-6744.2021.06.002 GUO Y R, LUO Z X, WANG J C, et al. Data-driven plan-ning and design for bike sharing parking spots[J]. Journal of Transportation Systems Engineering and Information Tech-nology, 2021, 21(6): 9-16. (in Chinese) doi: 10.16097/j.cnki.1009-6744.2021.06.002
[12]	李福, 徐良杰, 陈国俊, 等. 共享单车用户骑行起讫点时空特征分析[J]. 交通信息与安全, 2022, 40(3): 146-153, 170. doi: 10.3963/j.jssn.1674-4861.2022.03.015 LI F, XU L J, CHEN G J, et al. An analysis of spatial-tempo-ral characteristics of origin and destination of shared-bike us-ers[J]. Journal of Transport Information and Safety 2022, 40(3): 146-153, 170. (in Chinese) doi: 10.3963/j.jssn.1674-4861.2022.03.015
[13]	杨俊闯, 赵超. K-means聚类算法研究综述[J]. 计算机工程与应用, 2019, 55(23): 7-14, 63. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201923003.htm YANG J B, ZHAO C. Survey on k-means clustering algo-rithm[J]. Computer Engineering and Applications, 2019, 55(23): 7-14, 63.( in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201923003.htm
[14]	周强. 复杂网络社区发现算法研究[D]. 成都: 电子科技大学, 2020. ZHOU Q. Research on community discovery algorithms in complex networks[D]. Chengdu: University of Electronic Science and Technology, 2020. (in Chinese)
[15]	王欢. 基于网络社团结构的轨道交通线网生成研究[D]. 北京: 北京交通大学, 2019. WANG H. Rail transit network generation based on network community structure[D]. Beijing: Beijing Jiaotong Universi-ty, 2019. (in Chinese)
[16]	XU J, LI A, LI D, et al. Difference of urban development in China from the perspective of passenger transport around Spring Festival[J]. Applied Geography, 2017(87): 85-96.
[17]	余庆, 李玮峰, 杨东援. 基于手机信令数据的扬子江城市群空间联系结构分析[J]. 交通与运输, 2022, 38(3): 81-86. https://www.cnki.com.cn/Article/CJFDTOTAL-YSJT202203017.htm YU Q, LI W F, YANG D Y. Analysis of spatial structure in Yang-tze-River urban agglomeration using mobile phone data [J]. Traffic & Transportation, 2022, 38(3): 81-86. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSJT202203017.htm
[18]	ZHANG W, FANG C, ZHOU L, et al. Measuring megare-gional structure in the Pearl River Delta by mobile phone sig-naling data: A complex network approach[J]. Cities, 2020(104): 102809.
[19]	柯文前, 陈伟, 杨青. 基于高速公路流的区域城市网络空间组织模式: 以江苏省为例[J]. 地理研究, 2018, 37(9): 1832-1847. https://www.cnki.com.cn/Article/CJFDTOTAL-DLYJ201809015.htm KE W Q, CHEN W, YANG Q. Regional urban network space organization mode based on expressway flow: Taking Jiangsu Province as an example[J]. Geographical Research, 2018, 37(9): 1832-1847. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-DLYJ201809015.htm
[20]	徐进, 邓乐龄. 基于Louvain算法的铁路旅客社会网络社区划分研究[J]. 山东农业大学学报(自然科学版), 2018, 49(4): 722-725. https://www.cnki.com.cn/Article/CJFDTOTAL-SCHO201804035.htm XU J, DENG L L. Study on community detection of railway passenger social networks based on louvain algorithm[J]. Journal of Shandong Agricultural University (Natural Sci-ence Edition), 2018, 49(4): 722-725. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-SCHO201804035.htm
[21]	蒋云, 杨文东. 改进Louvain算法的多层航线网络社区划分[J]. 北京交通大学学报, 2022, 46(2): 89-97. https://www.cnki.com.cn/Article/CJFDTOTAL-BFJT202202011.htm JIANG Y, YANG W D. Community detection of multi-layer air transport network with improved louvain algorithm[J]. Journal of Beijing Jiaotong University, 2022, 46(2): 89-97. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-BFJT202202011.htm
[22]	YILDIRIMOGLU M, KIM J. Identification of communities in urban mobility networks using multi-layer graphs of net-work traffic[J]. Transportation Research Part C: Emerging Technologies, 2018(89): 254-267.
[23]	KIM K. Identifying the structure of cities by clustering using a new similarity measure based on smart card data[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 21(5): 2002-2011.
[24]	ZHANG Y, MARSHALL S, CAO M, et al. Discovering the evolution of urban structure using smart card data: The case of London[J]. Cities, 2021 (112): 103157.
[25]	WU C, SMITH D, WANG M. Simulating the urban spatial structure with spatial interaction: A case study of urban polycentricity under different scenarios[J]. Computers, Environment and Urban Systems, 2021 (89): 101677.
[26]	DASTJERDI A M, MORENCY C. Bike-sharing demand prediction at community level under covid-19 using deep learning[J]. Sensors, 2022, 22(3): 1060
[27]	SONG J, ZHANG L, QIN Z, et al. A spatiotemporal dynamic analyses approach for dockless bike-share system[J]. Computers, Environment and Urban Systems, 2021 (85): 101566.
[28]	TRAAG V A, WALTMAN L, VAN ECK N J. From louvain to leiden: Guaranteeing well-connected communities[J]. Scientific Reports, 2019, 9 (1): 5233.
[29]	CHEN W D, CHEN X W, CHENG L, et al. Delineating borders of urban activity zones with free-floating bike sharing spatial interaction network[J]. Journal of Transport Geography, 2022 (104): 103442.
[30]	中华人民共和国住房城乡建设部. 城市综合交通体系规划标准: GB/T 51328—2018[S]. 北京: 中国城市设计规划研究院, 2018. Ministry of Housing and Urban Rural Development of the People's Republic of China. Standard for urban comprehensive transportation system planning: GB/T 51328—2018[S]. Beijing: China Academy of Urban Design and Planning, 2018. (in Chinese)
[31]	中国城市规划设计研究院. 2021年中国主要城市共享单车/电单车骑行报告[EB/OL]. (2021-9)[2022-9-10]. https://www.thepaper.cn/newsDetail_forward_15381012 . China Academy of Urban Planning and Design. 2021 China principal cities sharing bikes and sharing electric bikes riding report[EB/OL]. (2021-9)[2022-9-10]. https://www.thepaper.cn/newsDetail_forward_15381012 .
[32]	CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70 (6): 66111.
[33]	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, 2008 (10): P10008.
[34]	PONS P, LATAPY M. Computing communities in large networks using random walks[C]. International Symposium on Computer and Information Sciences, Istanbul, Turkey: Springer, 2005.