Please wait a minute...
浙江大学学报(工学版)
JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE)  2018, Vol. 52 Issue (11): 2171-2179    DOI: 10.3785/j.issn.1008-973X.2018.11.016
Computer Technology     
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
Download:   PDF(859KB) HTML
Export: BibTeX | EndNote (RIS)      

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.

Received: 10 February 2018      Published: 22 November 2018
CLC:  TP391  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

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.

URL:

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


基于反向标签传播的移动终端用户群体发现

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

[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] HAN Yong, NING Lian-ju, ZHENG Xiao-lin, LIN Wei-hua, SUN Zhong-yuan. Matrix factorization recommendation based on social information and item exposure[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2019, 53(1): 89-98.
[2] ZHENG Zhou, ZHANG Xue-chang, ZHENG Si-ming, SHI Yue-ding. Liver segmentation in CT images based on region-growing and unified level set method[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(12): 2382-2396.
[3] ZHAO Li-ke, ZHENG Shun-yi, WANG Xiao-nan, HUANG Xia. Rigid object position and orientation measurement based on monocular sequence[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(12): 2372-2381.
[4] HE Jie-guang, PENG Zhi-ping, CUI De-long, LI Qi-rui. Teaching-learning-based optimization algorithm with local dimension improvement[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(11): 2159-2170.
[5] WANG Shuo-peng, YANG Peng, SUN Hao. Construction process optimization of fingerprint database for auditory localization[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(10): 1973-1979.
[6] WEI Xiao-feng, CHENG Cheng-qi, CHEN Bo, WANG Hai-yan. Chain code based on independent edge number[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(9): 1686-1693.
[7] CHEN Rong-hua, WANG Ying-han, BU Jia-jun, YU Zhi, GAO Fei. Website accessibility sampling evaluation based on KNN and local regression[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(9): 1702-1708.
[8] ZHANG Cheng-zhi, FENG Hua-jun, XU Zhi-hai, LI Qi, CHEN Yue-ting. Piecewise noise variance estimation of images based on wavelet transform[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(9): 1804-1810.
[9] LIU Zhou-zhou, LI Shi-ning, LI Bin, WANG Hao, ZHANG Qian-yun, ZHENG Ran. New elastic collision optimization algorithm and its application in sensor cloud resource scheduling[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1431-1443.
[10] WANG Yong-chao, ZHU Kai-lin, WU Qi-xuan, LU Dong-ming. Adaptive display technology of high precision model based on local rendering[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1461-1466.
[11] SUN Nian, LI Yu-qiang, LIU Ai-hua, LIU Chun, LI Wei-wei. Microblog sentiment analysis based on collaborative learning under loose conditions[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1452-1460.
[12] ZHENG Shou-guo, CUI Yan-min, WANG Qing, YANG Fei, CHENG Liang. Design of field data acquisition platform for aircraft assembly[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1526-1534.
[13] BI Xiao-jun, WANG Chao. Many-objective evolutionary algorithm based on hyperplane projection[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(7): 1284-1293.
[14] ZHANG Ting-rong, TENG Qi-zhi, LI Zheng-ji, QING Lin-bo, HE Xiao-hai. Super-resolution reconstruction for three-dimensional core CT image[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(7): 1294-1301.
[15] ZHAO Chuan-song, REN Hong-ge, SHI Tao, LI Fu-jin. Wheeled inverted pendulum reactive cognitive system with internal motivation[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(6): 1073-1080.