Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2018, Vol. 52 Issue (11): 2171-2179    DOI: 10.3785/j.issn.1008-973X.2018.11.016
计算机技术     
基于反向标签传播的移动终端用户群体发现
李志, 单洪, 马涛, 黄郡
国防科技大学 电子对抗学院, 安徽 合肥 230037
Group discovery of mobile terminal users based on reverse-label propagation algorithm
LI Zhi, SHAN Hong, MA Tao, HUANG Jun
College of Electronic Engineering, National University of Defense Technology, Hefei 230037, China
 全文: PDF(859 KB)   HTML
摘要：

针对现有方法在移动终端用户群体发现中不能兼顾社会关系和位置属性的问题，提出基于反向标签传播算法的重叠群体发现方法.根据移动终端用户的位置信息推断社会关系拓扑图，提取时空共现区.将时空共现区作为位置属性标签，标注社会关系拓扑图.在标签拓扑图上进行反向标签传播，消除节点伴随标签.经过反复迭代，在标签稳定状态下的每一个节点保留所属群体的主标签.根据用户社会关系和稳定状态下的节点主标签完成群体划分与识别.在4个真实数据集上比较反向标签传播算法与3种同类方法，实验结果表明，反向标签传播算法较好地兼顾了用户社会关系和位置属性，群体发现结果的标准互信息（NMI）与综合评价函数（F）分别比次优者平均高8.97%和3.87%.
Abstract:

A new method was proposed for overlapping group discovery based on reverse-label propagation algorithm to solve the problem that the social relationship and location attribute cannot be taken into account simultaneously when using the existing methods to discover the groups of mobile terminal users. According to the location information of mobile terminal users, the topological graph of social relationship was inferred and the spatio-temporal co-occurrence areas were extracted. The spatio-temporal co-occurrence areas were used as position attribute labels to mark the topological graph. The label graph was processed with the reverse-label propagation algorithm to remove companion-labels for nodes. With repeated iterations, each node preserved the main-labels of the groups when the state of the labels was stable. According to the user social relationship and node's main label under stable state, the groups of mobile users were divided and recognized.The experiments were carried out to compare reverse-label propagation algorithm with three similar methods on four real datasets. Results showed that the reverse-label propagation algorithm took better account of social relationship and location attribute simultaneously, and the normalized mutual information (NMI) and comprehensive evaluation function (F), the evaluating indicators of group discovery, were increased averagely by 8.97% and 3.87% respectively than the suboptimal algorithm.
收稿日期: 2018-02-10 出版日期: 2018-11-22
CLC:  TP391  
基金资助:

国防重点实验室基金资助项目（9140C130104）
通讯作者: 单洪,男,教授,博导.orcid.org/0000-0002-9669-0215.     E-mail: hshan222@163.com
作者简介: 李志(1990-),男,博士生,从事位置数据挖掘研究.orcid.org/0000-0001-5576-8306.E-mail:lizhiwelcome@126.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　

引用本文:

李志, 单洪, 马涛, 黄郡. 基于反向标签传播的移动终端用户群体发现[J]. 浙江大学学报(工学版), 2018, 52(11): 2171-2179.

LI Zhi, SHAN Hong, MA Tao, HUANG Jun. Group discovery of mobile terminal users based on reverse-label propagation algorithm. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(11): 2171-2179.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2018.11.016    或    http://www.zjujournals.com/eng/CN/Y2018/V52/I11/2171

[1] DEY A, HIGHTOWER J, LARA E D, et al. Location-based services[J]. IEEE Pervasive Computing, 2017, 9(1):11-12.
[2] 潘理, 吴鹏, 黄丹华. 在线社交网络群体发现研究进展[J]. 电子与信息学报, 2017, 39(9):2097-2107 PAN Li, WU Peng, HUANG Dan-hua. Reviews on group detection in online social networks[J]. Journal of Electronics and Information Technology, 2017, 39(9):2097-2107
[3] 方滨兴, 贾焰, 韩毅. 社交网络分析核心科学问题、研究现状及未来展望[J]. 中国科学院院刊, 2015(2):187-199 FANG Bin-xing, JIA Yan, HAN Yi. The core scientific problems, research status and future prospects of social network analysis[J]. Bulletin of Chinese Academy of Sciences, 2015(2):187-199
[4] 王桦, 韩同阳, 周可. 公安情报中基于关键图谱的群体发现算法[J]. 浙江大学学报:工学版, 2017, 51(6):1173-1180 WANG Hua, HAN Tong-yang, ZHOU Ke. Key graph-based community detection algorithm for public security intelligence[J]. Journal of Zhejiang University:Engineering Science, 2017, 51(6):1173-1180
[5] KIM J, LEE J G. Community detection in multi-layer graphs:a survey[J]. ACM SIGMOD Record, 2015, 44(3):37-48.
[6] HUNG C C, CHANG C W, PENG W C. Mining trajectory profiles for discovering user communities[C]//Proceedings of the 2009 International Workshop on Location Based Social Networks. Seattle:ACM, 2009:1-8.
[7] BOSTON D, MARDENFELD S, PAN J, et al. Leveraging Bluetooth co-location traces in group discovery algorithms[J]. Pervasive and Mobile Computing, 2014, 11(6):88-105.
[8] JAYADEVAN V, BHARADWAJ K, KUMAR A, et al. Discovering local social groups using mobility data[J]. International Journal of Computer Applications, 2015, 120:15-19.
[9] LIM K H, CHAN J, LECKIE C, et al. Detecting location-centric communities using social-spatial links with temporal constraints[C]//Advances in Information Retrieval:37th European Conference on IR Research. Vienna:ECIR, 2015:489-494.
[10] BROWN C, NICOSIA V, SCELLATO S, et al. Social and place-focused communities in location-based online social networks[J]. European Physical Journal B, 2013, 86(6):1-10.
[11] BROWN C, NICOSIA V, SCELLATO S, et al. The importance of being placefriends:discovering location-focused online communities[C]//ACM Workshop on Online Social Networks. Helsinki:ACM, 2012:31-36.
[12] LIU J, LI Y, LING G, et al. Community detection in location-based social networks:an entropy-based approach[C]//IEEE International Conference on Computer and Information Technology. Nadi:IEEE, 2017:452-459.
[13] CRANDALL D J, BACKSTROM L, COSLEY D, et al. Inferring social ties from geographic coincidences[J]. Proceedings of the National Academy of Sciences of the United States of America, 2010, 107(52):22436-22441.
[14] XIAO X, ZHENG Y, LUO Q, et al. Inferring social ties between users with human location history[J]. Journal of Ambient Intelligence and Humanized Computing, 2014, 5(1):3-19.
[15] TAN R, GU J, CHEN P, et al. Link prediction using protected location history[C]//2013 International Conference on Computational and Information Sciences. Shiyang:IEEE, 2013:795-798.
[16] WANG D, PEDRESCHI D, SONG C, et al. Human mobility, social ties, and link prediction[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego:ACM, 2011:1100-1108.
[17] 马春来, 单洪, 马涛, 等. 随机森林改进算法在LBS用户社会关系推断中的应用[J]. 小型微型计算机系统, 2016, 37(12):2708-2712. MA Chun-lai, SHAN Hong, MA Tao, et al. An improved random forests algorithm with application to social ties inferring of LBS users[J]. Journal of Chinese Computer Systems, 2016, 37(12):2708-2712.
[18] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191):1492-1496.
[19] 陈晶, 万云. 社交网络中基于模块度最大化的标签传播算法的研究[J]. 通信学报, 2017, 38(2):25-33 CHEN Jing, WAN Yun. Research on label propagation algorithm based on modularity maximization in the social network[J]. Journal on Communications, 2017, 38(2):25-33
[20] WANG Z, ZHANG D, ZHOU X, et al. Discovering and profiling overlapping communities in location-based social networks[J]. IEEE Transactions on Systems Man and Cybernetics Systems, 2014, 44(4):499-509.
[21] LIU D, WEI W, SONG G, et al. Community discovery with location-interaction disparity in mobile social networks[J]. ZTE Communications, 2015(2):53-61.
[22] CHO E, MYERS S A, LESKOVEC J. Friendship and mobility:user movement in location-based social networks[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego:ACM, 2011:1082-1090.
[23] BAO J, ZHENG Y, MOKBEL M F. Location-based and preference-aware recommendation using sparse geo-social networking data[C]//International Conference on Advances in Geographic Information Systems. Redondo Beach:ACM, 2012:199-208.
[24] LANCICHINETTI A, FORTUNATO S, KERTÉSZ J. Detecting the overlapping and hierarchical community structure of complex networks[J]. New Journal of Physics, 2008, 11(3):19-44.
[25] 黄健斌, 钟翔, 孙鹤立, 等. 基于相似性模块度最大约束标记传播的网络社团发现算法[J]. 北京大学学报:自然科学版, 2013, 49(3):389-396 HUANG Jian-bin, ZHONG Xiang, SUN He-li, et al. A network community detection algorithm via constrained label propagation with maximization of similarity-based modularity[J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2013, 49(3):389-396
[26] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E Statistical Nonlinear and Soft Matter Physics, 2004, 69(2):026113.
[27] NICOSIA V, MANGIONI G, CARCHIOLO V, et al. Extending the definition of modularity to directed graphs with overlapping communities[J]. Journal of Statistical Mechanics Theory and Experiment, 2009(3):3166-3168.
[1] 韩勇, 宁连举, 郑小林, 林炜华, 孙中原. 基于社交信息和物品曝光度的矩阵分解推荐[J]. 浙江大学学报(工学版), 2019, 53(1): 89-98.
[2] 郑洲, 张学昌, 郑四鸣, 施岳定. 基于区域增长与统一化水平集的CT肝脏图像分割[J]. 浙江大学学报(工学版), 2018, 52(12): 2382-2396.
[3] 赵丽科, 郑顺义, 王晓南, 黄霞. 单目序列的刚体目标位姿测量[J]. 浙江大学学报(工学版), 2018, 52(12): 2372-2381.
[4] 何杰光, 彭志平, 崔得龙, 李启锐. 局部维度改进的教与学优化算法[J]. 浙江大学学报(工学版), 2018, 52(11): 2159-2170.
[5] 王硕朋, 杨鹏, 孙昊. 听觉定位数据库构建过程优化[J]. 浙江大学学报(工学版), 2018, 52(10): 1973-1979.
[6] 魏小峰, 程承旗, 陈波, 王海岩. 基于独立边数的链码方法[J]. 浙江大学学报(工学版), 2018, 52(9): 1686-1693.
[7] 陈荣华, 王鹰汉, 卜佳俊, 于智, 高斐. 基于KNN算法与局部回归的网站无障碍采样评估[J]. 浙江大学学报(工学版), 2018, 52(9): 1702-1708.
[8] 张承志, 冯华君, 徐之海, 李奇, 陈跃庭. 图像噪声方差分段估计法[J]. 浙江大学学报(工学版), 2018, 52(9): 1804-1810.
[9] 刘洲洲, 李士宁, 李彬, 王皓, 张倩昀, 郑然. 基于弹性碰撞优化算法的传感云资源调度[J]. 浙江大学学报(工学版), 2018, 52(8): 1431-1443.
[10] 王勇超, 祝凯林, 吴奇轩, 鲁东明. 基于局部渲染的高精度模型自适应展示技术[J]. 浙江大学学报(工学版), 2018, 52(8): 1461-1466.
[11] 孙念, 李玉强, 刘爱华, 刘春, 黎威威. 基于松散条件下协同学习的中文微博情感分析[J]. 浙江大学学报(工学版), 2018, 52(8): 1452-1460.
[12] 郑守国, 崔雁民, 王青, 杨飞, 程亮. 飞机装配现场数据采集平台设计[J]. 浙江大学学报(工学版), 2018, 52(8): 1526-1534.
[13] 毕晓君, 王朝. 基于超平面投影的高维多目标进化算法[J]. 浙江大学学报(工学版), 2018, 52(7): 1284-1293.
[14] 张廷蓉, 滕奇志, 李征骥, 卿粼波, 何小海. 岩心三维CT图像超分辨率重建[J]. 浙江大学学报(工学版), 2018, 52(7): 1294-1301.
[15] 赵传松, 任红格, 史涛, 李福进. 内在动机轮式倒立摆反应式认知系统[J]. 浙江大学学报(工学版), 2018, 52(6): 1073-1080.