地点网络中的社区发现

doi:10.11896/j.issn.1002-137X.2018.06.008

计算机科学 ›› 2018, Vol. 45 ›› Issue (6): 46-50.doi: 10.11896/j.issn.1002-137X.2018.06.008

• 第十四届全国Web信息系统及其应用学术会议 • 上一篇下一篇

地点网络中的社区发现

郑香平, 於志勇, 温广槟

福州大学数学与计算机科学学院福州 350116;
福州大学福建省网络计算与智能信息处理重点实验室福州 350116

收稿日期:2017-03-11 出版日期:2018-06-15 发布日期:2018-07-24
作者简介:郑香平(1992-),男,硕士生,主要研究方向为移动社交网络;於志勇(1982-),男,博士,副教授,CCF会员,主要研究方向为普适计算、移动社交网络,E-mail:yuzhiyong@fzu.edu.cn(通信作者);温广槟(1991-),男,硕士生,主要研究方向为移动社交网络等
基金资助:
本文受国家自然科学基金(61300103)资助

Community Discovery in Location Network

ZHENG Xiang-ping, YU Zhi-yong, WEN Guang-bin

College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350116,China;
Fujian Provincial Key Laboratory of Network Computing and Intelligent Information Processing,Fuzhou University,Fuzhou 350116,China

Received:2017-03-11 Online:2018-06-15 Published:2018-07-24

摘要/Abstract

摘要： 地点网络可从一些独特的视角来刻画城市的空间结构。通过研究城市地点网络的特点及其与传统社交网络的区别,提出了基于地点网络的社区发现算法。该算法综合考虑地点临近性、地点间的连接和用户出行行为的相似性,先进行初始社区的划分,再反复迭代计算各地点隶属于本社区的程度,对隶属度较低的地点进行调整直到收敛,从而发现有意义的城市社区。通过分析社区内部地点的属性和关联,验证了算法的有效性。

关键词: 地点网络, 群智感知, 社区发现

Abstract: The location network can portray the spatial structure of city from some unique perspectives.By studying the characteristics of urban location network and its difference with traditional social network,a community discovery algorithm based on location network was proposed.The algorithm takes into account the proximity of location,the connection between the locations and the similarity of user’s travel behavior.Firstly,the initial community is divided.Then,the extent of each site belonging to this community is interatively calculated the places with lower membership degree are adjusted until convergence,so as to find significant urban communities.The validity of the algorithm was verified by analyzing the attributes and correlations of the internal sites.

Key words: Community discovery, Crowd sensing, Location network

中图分类号:

TP391

郑香平, 於志勇, 温广槟. 地点网络中的社区发现[J]. 计算机科学, 2018, 45(6): 46-50. https://doi.org/10.11896/j.issn.1002-137X.2018.06.008

ZHENG Xiang-ping, YU Zhi-yong, WEN Guang-bin. Community Discovery in Location Network[J]. Computer Science, 2018, 45(6): 46-50. https://doi.org/10.11896/j.issn.1002-137X.2018.06.008

参考文献

[1]QI J S,LIANG X,WANG Y.Overlapping community detection algorithm based on selection of seed nodes[J].Application Research of Computers,2017,34(12):3534-3537.(in Chinese)
齐金山,梁循,王怡.基于种子节点选择的重叠社区发现算法[J].计算机应用研究,2017,34(12):3534-3537.
[2]WU Z G,LU Z.A community discovery algorithm based on local similarity [J].Computer Engineering,2016,42(12):196-203.(in Chinese)
吴钟刚,吕钊.一种基于局部相似性的社区发现算法[J].计算机工程,2016,42(12):196-203.
[3]LIU Y,JI X S,LIU C X.Network community discovery optimization:based on random walk edge weight pretreatment method [J].Journal of Electronics & Information Technology,2013,35(10):2335-2340.(in Chinese)
刘阳,季新生,刘彩霞.网络社区发现优化:基于随机游走的边权预处理方法[J].电子与信息学报,2013,35(10):2335-2340.
[4]SONG C,ZHANG X K,FEI S,et al.Improved tag propagation algorithm based on random walk similarity matrix [J].Journal of Computer Applications and Software,2016,33(8):269-272.(in Chinese)
宋琛,张贤坤,费松,等.基于随机游走相似度矩阵的改进标签传播算法[J].计算机应用与软件,2016,33(8):269-272.
[5]HUANG F L,ZHANG S C,ZHU X F.Discovering Network Community Based on Multi-objective Optimization[J].Journal of Software,2013,24(9):2062-2077.(in Chinese)
黄发良,张师超,朱晓峰.基于多目标优化的网络社区发现方法[J].软件学报,2013,24(9):2062-2077.
[6]QIAO S J,GUO J,HAN N,et al.Large-scale complex network community parallel discovery algorithm [J].Journal of Compu-ter Science,2017,40(3):687-700.(in Chinese)
乔少杰,郭俊,韩楠,等.大规模复杂网络社区并行发现算法[J].计算机学报,2017,40(3):687-700.
[7]LIU H X,PENG S L.A method of community discovery based on neighboring nodes influencing intensity tag propagation [J].Modern Library and Information Technology,2015,31(4):58-64.(in Chinese)
刘郝霞,彭商濂.一种基于邻近节点影响强度标签传播社区发现方法[J].现代图书情报技术,2015,31(4):58-64.
[8]HAN L,ZHANG H.Community Discovery Method Based on Neighborhood Information [J].Pure Mathematics and Applied Mathematics,2015,31(1):85-92.(in Chinese)
韩路,张海.基于邻域信息的社区发现方法[J].纯粹数学与应用数学,2015,31(1):85-92.
[9]YAN F,ZHANG M,TAN Y W,et al.Community Discovery Method of Comprehensive Social Action Interest and Network Topology [J].Journal of Computer Research and Development,2010,47(z1):357-362.(in Chinese)
燕飞,张铭,谭裕韦,等.综合社会行动者兴趣和网络拓扑的社区发现方法[J].计算机研究与发展,2010,47(z1):357-362.
[10]YANG T B,JIN R,CHI Y,et al.Combining Link and content for community detection[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2009:927-936.
[11]KEWALRAMANI M N.Community detection in Twitter[D]. University of Maryland,2011.
[12]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.
[13]NEWMAN M E,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2004,69(2):026113.
[14]WILKINSON D M,HUBERMAN B A.A Method for Finding Communities of Related Genes[J].Proceedings of the National Academy of Sciences of the United States of America,2004,101(Suppl.1):5241-5248.
[15]PALLA G,VICSEK T.Quantifying social group evolution[J].Nature,2007,446(7136):664-667.
[16]RAGHAVAN U N,ALBERT R,KUMARA S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(2):036106:

相关文章 15

[1]	何亦琛, 毛宜军, 谢贤芬, 古万荣. 基于点割集图分割的矩阵变换与分解的推荐算法 Matrix Transformation and Factorization Based on Graph Partitioning by Vertex Separator for Recommendation 计算机科学, 2022, 49(6A): 272-279. https://doi.org/10.11896/jsjkx.210600159
[2]	李利, 何欣, 韩志杰. 群智感知的隐私保护研究综述 Review of Privacy-preserving Mechanisms in Crowdsensing 计算机科学, 2022, 49(5): 303-310. https://doi.org/10.11896/jsjkx.210400077
[3]	李晓东, 於志勇, 黄昉菀, 朱伟平, 涂淳钰, 郑伟楠. 面向河道环境监测的群智感知参与者选择策略 Participant Selection Strategies Based on Crowd Sensing for River Environmental Monitoring 计算机科学, 2022, 49(5): 371-379. https://doi.org/10.11896/jsjkx.210200005
[4]	王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[5]	唐春阳, 肖玉芝, 赵海兴, 冶忠林, 张娜. 面向双层网络的EWCC社区发现算法 EWCC Community Discovery Algorithm for Two-Layer Network 计算机科学, 2022, 49(4): 49-55. https://doi.org/10.11896/jsjkx.210800275
[6]	杨旭华, 王磊, 叶蕾, 张端, 周艳波, 龙海霞. 基于节点相似性和网络嵌入的复杂网络社区发现算法 Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding 计算机科学, 2022, 49(3): 121-128. https://doi.org/10.11896/jsjkx.210200009
[7]	陈湘涛, 赵美杰, 杨梅. 基于子图结构的局部社区发现算法 Overlapping Community Detection Algorithm Based on Subgraph Structure 计算机科学, 2021, 48(9): 244-250. https://doi.org/10.11896/jsjkx.201100010
[8]	王乐业. 群智感知中的地理位置本地化差分隐私机制:现状与机遇 Geographic Local Differential Privacy in Crowdsensing:Current States and Future Opportunities 计算机科学, 2021, 48(6): 301-305. https://doi.org/10.11896/jsjkx.201200223
[9]	徐新黎, 肖云月, 龙海霞, 杨旭华, 毛剑飞. 基于矩阵分解的属性网络嵌入和社区发现算法 Attributed Network Embedding Based on Matrix Factorization and Community Detection 计算机科学, 2021, 48(12): 204-211. https://doi.org/10.11896/jsjkx.210300060
[10]	宁懿昕, 谢辉, 姜火文. 图神经网络社区发现研究综述 Survey of Graph Neural Network in Community Detection 计算机科学, 2021, 48(11A): 11-16. https://doi.org/10.11896/jsjkx.210500151
[11]	张清琪, 刘漫丹. 复杂网络社区发现的多目标五行环优化算法 Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery 计算机科学, 2020, 47(8): 284-290. https://doi.org/10.11896/jsjkx.190700082
[12]	董明刚, 弓佳明, 敬超. 基于谱聚类的多目标进化社区发现算法研究 Multi-obJective Evolutionary Algorithm Based on Community Detection Spectral Clustering 计算机科学, 2020, 47(6A): 461-466. https://doi.org/10.11896/JsJkx.191100215
[13]	李建军, 汪校铃, 杨玉, 付佳. 基于CQPSO移动群智感知紧急任务分配方法研究 Emergency Task Assignment Method Based on CQPSO Mobile Crowd Sensing 计算机科学, 2020, 47(6A): 273-277. https://doi.org/10.11896/JsJkx.190700040
[14]	张琴, 陈红梅, 封云飞. 一种基于粗糙集和密度峰值的重叠社区发现方法 Overlapping Community Detection Method Based on Rough Sets and Density Peaks 计算机科学, 2020, 47(5): 72-78. https://doi.org/10.11896/jsjkx.190400160
[15]	赵卫绩,张凤斌,刘井莲. 复杂网络社区发现研究进展 Review on Community Detection in Complex Networks 计算机科学, 2020, 47(2): 10-20. https://doi.org/10.11896/jsjkx.190100214

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

地点网络中的社区发现

Community Discovery in Location Network

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0