Computer Science ›› 2018, Vol. 45 ›› Issue (1): 188-195.doi: 10.11896/j.issn.1002-137X.2018.01.033

Previous Articles     Next Articles

MIMA:A Multi-identification Check-in Data Matching Algorithm Based on Spatial and Temporal Relations

ZHANG Chen, LI Zhi, ZHU Hong-song and SUN Li-min   

  • Online:2018-01-15 Published:2018-11-13

Abstract: Intelligent product often has a tag which can represent its uniqueness,such as the serial number of bus cards,the MAC address of Wi-Fi devices. The check-in data,which represent people’s discrete trajectory, consist of the tag,the time and the location used by the product.Researchers have made lots of surveys about single kind of check-in data.However,single kind of check-in data are sparse,so the adaptability and performance of the surveys are limited.This paper studied a new problem about multiple kinds of check-in data and proposed an algorithm called MIMA based on multiple kind sof check-in data to enrich check-in data and improve the performance of the surveys.Firstly,MIMA builds up the signed network through calculating the positive and negative values between tags based on the temporal and spatial relations of multiple kinds of check-in data produced by one individu al(1)Then the FEC(Finding and Extracting Communities from singed social networks) community detection algorithm is improved by deleting a cut criteria and considering the weight density to adapt to the specialty of check-in data signed network,and it achieves the goal of partitioning multiple tags which belong to one individual.The effectiveness and efficacy of the proposed algorithm are demons-trated through a set of experiments involving both real and simulated situations.

Key words: Multi-identification check-in data,Singed network,Community detection,Matching algorithm

[1] GAO H J,TANG J L,HU X,et al.Modeling temporal effects of human mobile behavior on location-based social networks[C]∥Proceedings of the 22nd ACM International Conference on Conference on Information & Knowledge Management.2013:1673-1678.
[2] CHENG Z Y,CAVERLEE J,LEE K.You are where you tweet:a content-based approach to geolocating twitter users[C]∥Proceedings of the 19th ACM International Conference on Inforamtion and Knowledge Management.2010:759-768.
[3] BENEVENUTO F,RODRIGUES T,CHA T,et al(1)Characterizing user behavior in online social networks[C]∥Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement Conference.2009:49-62.
[4] SALVATORE S,ANASTASIOS N,CECILLIA M.Exploringplace features in link prediction on location based social networks[C]∥Proceedings of the 17th ACM SIGKDD InternationalConference on Knowledge Discovery and Data Mining.2011:1046-1054.
[5] MAO Y,DONG S,WANG C L,et al(1)On the semantic annotation of places in location-based social networks[C]∥Procee-dings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2011:520-528.
[6] ANASTASIOS N,SALVATORE S,CECILIA M,et al.Exploring semantic annotations for clustering geographic areas and users in location-based social networks[C]∥Proceedings of SMW11.2011.
[7] MARISA V,SAULO R,JUSSARA A,et al.Tips,dones and todos:uncovering iser profiles in Foursquare[C]∥Proceedings of the 5th ACM International Conference on Web Search and Data Mining.2012:653-662.
[8] MA X,WU Y J,WANG Y,et al.Mining smart card data for transit riders’ travel patterns[J].Transportation Research Part C Emerging Technologies,2013,36:1-12.
[9] AGARD B.Mining public transport user behaviour from smart card data[C]∥Information Control Problems in Manufacturing.2006:399-404.
[10] BONSALL P W.The changing face of parking-related data collection and analysis:The role of new technologies[J].Transportation,1991,18(1):83-106.
[11] LIANG W,MENG B,HE X,et al.GCM:A Greedy-Based Cross-Matching Algorithm for Identifying Users Across Multiple Online Social Networks[M]∥Intelligence and Security Informa-tics.2015:51-70.
[12] DU S,HUA J,GAO Y,et al.EV-Linker:Mapping eavesdropped Wi-Fi packets to individuals via electronic and visual signal matching [J].Journal of Computer & System Sciences,2015,82(1):156-172.
[13] YANG B,LIU D Y,LIU J,et al.Complex network clustering algorithms[J].Journal of Software,2009,0(1):54-66.
[14] AXELROD R,BENNETT D S.A Landscape Theory of Aggregation[J].British Journal of Political Science,1993,23(2):211-233.
[15] CHENG S Q,SHEN H W,ZHANG G Q,et al.Survey of signed network research[J].Journal of Software,2014,5(1):1-15.(in Chinese) 程苏琦,沈华伟,张国清,等.符号网络研究综述[J].软件学报,2014,5(1):1-15.
[16] SHEN H W.Community Structure of Complex Networks[J].Complex Systems & Complexity Science,2013,72(5):168-191.
[17] PALLA B G,DERENHI I,FARKAS I,et al(1):Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,5(7043):814.
[18] HASSAN A,ABU-JBARA A,RADEV D.Extracting signed social networks from text[C]∥Workshop Proceedings of TextGraphs-7 on Graph-based Methods for Natural Language Processing.Association for Computational Linguistics.2012:6-14.
[19] DOREIAN P,MRVAR A.A partitioning approach to structural balance[J].Social Networks,1996,18(2):149-168.
[20] BOGDANOV P,LARUSSO N D,SINGH A.Towards Community Discovery in Signed Collaborative Interaction Networks[C]∥IEEE International Conference on Data Mining Workshops.IEEE Computer Society,2010:288-295.
[21] TRAAG V A,BRUGGEMAN J.Community detection in networks with positive and negative links[J].Physical Review E Statistical Nonlinear & Soft Matterphysics,2009,80(3):036115.
[22] KUNEGIES J,SCHMIDT S,LOMMATZSCH A,et al.Spectral Analysis of Signed Graphs for Clustering,Prediction and Visuali-zation[C]∥Siam International Conference on Data Mining.2011:559 .
[23] ZHENG Q,SKILLICORN D B.Spectral Embedding of Signed Networks[C]∥Proceedings of the 2015 SIAM International Conference on Data Mining.2015.
[24] NEWMAN M E J.Fast Algorithm for Detecting CommunityStructure in Networks[ J].Phys Rev E,2004,69(6):066133.
[25] GMEZ S,JENSEN P,ARENAS A.Analysis of communitystructure in networks of correlated data.[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2009,80(2):016114.
[26] LI Y,LIU J,LIU C.A comparative analysis of evolutionary and memetic algorithms for community detection from signed social networks[J].Soft Computing,2014,18(2):329-348.
[27] ANCHURI P,MAGDON-ISMAIL M.Communities and Balance in Signed Networks:A Spectral Approach[C]∥IEEE/ACM International Conference on Advances in Social Networks Analy-sis and Mining.IEEE,2012:235-242.
[28] FORTUNATO S,BARTHELEMY M.Resolution limit in community detection[J].Proceedings of the National Academy of Science,2006,4(1):36-41.
[29] YANG B,CHEUNG W K,LIU J.Community Mining fromSigned Social Networks[J].IEEE Transactions on Knowledge &Data Engineering,2007,19(10):1333-1348.
[30] KONG L Q,YANG M L.Improvement of clustering algorithm FEC for signed networks[J].Journal of Computer Applications,2011,31(5):1395-1399.
[31] TANG J,CHANG Y,AGGARWAL C,et al.A Survey ofSigned Network Mining in Social Media.http://yichang-cs.com/yahoo/CSUR16-SurveySignedNetwork.pdf.
[32] Heider F.Attitudes and cognitive organization.[J].Journal of Psychology Interdisciplinary & Applied,1946,21(1):107-112.
[33] CARTWRIGHT D,HARARY F.Structural balance:a generalization of Heider’s theory[J].Psychological Review,1956,63(5):277-293.
[34] DAVIS J A.Clustering and structural b alance in graphs[J].Human Relations,1967,20(2):181-187.
[35] TONG C,NIU J W,LONG X,et al.Survey on Mobility Model[J].Computer Science,2009,36(10):5-10.(in Chinese) 童超,牛建伟,龙翔,等.移动模型研究综述[J].计算机科学,2009,36(10):5-10.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!