基于用户移动网络接入位置的高效分布式相似矩阵计算方法

doi:10.11959/j.issn.1000-0801.2018136

电信科学 ›› 2018, Vol. 34 ›› Issue (5): 26-38.doi: 10.11959/j.issn.1000-0801.2018136

基于用户移动网络接入位置的高效分布式相似矩阵计算方法

王源¹,江昊¹,吴明²,姚冬桂³,张毅¹,羿舒文¹,汪海¹,吴静¹

¹ 武汉大学电子信息学院，湖北武汉 430072
² 武汉船舶通信研究所，湖北武汉 430070
³ 武汉技师学院，湖北武汉 430051

修回日期:2018-03-15 出版日期:2018-05-01 发布日期:2018-05-30
作者简介:王源（1993–），女，武汉大学电子信息学院硕士生，主要研究方向为大数据分析、大数据平台开发和应用等。|江昊（1976–），男，武汉大学电子信息学院教授、博士生导师，主要研究方向为无线网络、移动互联网、大数据分析与挖掘、空间综合信息网络等。|吴明（1972–），男，现就职于武汉船舶通信研究所，主要研究方向为通信与信息系统。|姚冬桂（1967–），女，武汉技师学院高级讲师，主要研究方向为大数据开发与应用。|张毅（1994–），男，武汉大学电子信息学院硕士生，主要研究方向为大数据分析、机器学习算法研究和统计方法等。|羿舒文（1992–），男，武汉大学电子信息学院博士生，主要研究方向为数据挖掘、移动无线网络等。|汪海（1992–），男，武汉大学电子信息学院博士生，主要研究方向为无线网络、软件定义网络、数据分析与挖掘。|吴静（1981–），女，武汉大学电子信息学院副教授，主要研究方向为网络管理和性能优化、网络路由技术、分布式计算技术等。
基金资助:
国家重点研发计划基金资助项目(2017YFC0503801);中国电子科技集团公司第54研究所高校合作基金资助项目;中央高校自主科研项目(2042014gf020);中央高校自主科研项目(2042014kf0256);湖北省自然科学基金面上项目(2014CFB716);湖北省自然科学基金面上项目(2011CDA042);国家自然科学基金资助项目(61371126)

A distributed high efficiency similarity matrix computation method based on users’ mobile network access location

Yuan WANG¹,Hao JIANG¹,Ming WU²,Donggui YAO³,Yi ZHANG¹,Shuwen YI¹,Hai WANG¹,Jing WU¹

¹ School of Electronics and Information,Wuhan University,Wuhan 430072,China
² Wuhan Ship Communication Research Institute,Wuhan 430070,China
³ Wuhan Institute of Technician,Wuhan 430051,China

Revised:2018-03-15 Online:2018-05-01 Published:2018-05-30
Supported by:
National Key Research and Development Project(2017YFC0503801);Higher Education Cooperation Foundation of the 54th Research Institute of China Electronics Technology Group Corporation;Autonomous Science Research Project in Central Affiliated University(2042014gf020);Autonomous Science Research Project in Central Affiliated University(2042014kf0256);Natural Science Foundation of Hubei Province of China(2014CFB716);Natural Science Foundation of Hubei Province of China(2011CDA042);The National Natural Science Foundation of China(61371126)

摘要/Abstract

摘要：

研究了一种基于用户移动网络接入位置的高效分布式相似矩阵计算方法，利用Hadoop生态系统中的MapReduce 计算框架，依据地理位置信息对用户进行划分并进行相似度计算。实验结果表明，该方法在计算效率上相较于现有相似矩阵计算方法最大提升了近25倍。将相似矩阵计算结果应用于用户社区发现，该方法与现有相似矩阵计算方法得到的相似矩阵有几乎一致的社区发现结果，一致率高达99.9%。

关键词: 相似矩阵, 矩阵乘法, Hadoop, MapReduce, 分布式计算

Abstract:

A distributed similarity matrix computation method based on users’ mobile network access location was proposed.MapReduce computing framework in the Hadoop ecosystem was used,and users’ mobile network access location information was considered as prior knowledge,then users were divided based on geographic location information and the similarity calculation was performed.The experimental results show that the computational efficiency of the proposed method is increased by nearly 25 times compared with the existing similarity matrix computation method.As for the outcome of the community detection,the proposed method get nearly the same results as the existing similar matrix computation method,the agreement rate is nearly 99.9%.

中图分类号:

TP393

王源,江昊,吴明,姚冬桂,张毅,羿舒文,汪海,吴静. 基于用户移动网络接入位置的高效分布式相似矩阵计算方法[J]. 电信科学, 2018, 34(5): 26-38.

Yuan WANG,Hao JIANG,Ming WU,Donggui YAO,Yi ZHANG,Shuwen YI,Hai WANG,Jing WU. A distributed high efficiency similarity matrix computation method based on users’ mobile network access location[J]. Telecommunications Science, 2018, 34(5): 26-38.

图/表 10

图1

图2

图3

图4

表1

表2

图5

表3

表4

图6

参考文献 26

[1]	SCRIPPS J , TREFFTZ C . Parallelizing an algorithm to find communities using the Jaccard metric[C]// IEEE International Conference on Electro/Information Technology,June 8-12,2015,London,UK. Piscataway:IEEE Press, 2015.
[2]	HURLEY N , DURIAKOVA E . Reformulations of the map equation for community finding and blockmodelling[C]// IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining,August 25-28,2015,Paris,France. Piscataway:IEEE Press, 2015.
[3]	RESTREPO A , SOLANO A , SCRIPPS J ,et al. High-performance implementations of a clustering algorithm for finding network communities[C]// IEEE International Conference on Electro/Information Technology,May 6-8,2012,Indianapolis,USA. Piscataway:IEEE Press, 2012.
[4]	GUNTHER J H , HOFFMAN K H . Numerische mathematik[M]. Berlin: SpringerPress, 1991.
[5]	STEWART G W . Jampack:a Java package for matrix computations[J]. 2017.
[6]	JOE H , CLEVE M , PETER W . JAMA:a Java matrix package[EB]. 2017.
[7]	NGUYEN D K , LAVALLEE I , BUI M ,et al. A general scalable parallelizing of strassen’s algorithm for matrix multiplication on distributed memory computers[C]// ACIS International Conference on Computer and Information Science,July 14-16,2005,Washington,DC,USA. Piscataway:IEEE Press, 2005.
[8]	LIN C , HUANG Z H , YANG F ,et al. Identify content quality in online social networks[J]. IET Communications, 2012,6(12): 1618-1624.
[9]	孙远帅, 陈垚, 官新均 ,等. 基于Hadoop的大矩阵乘法处理方法[J]. 计算机应用, 2013,33(12): 3339-3344.
	SUN Y S , CHEN Y , GUAN X J ,et al. Approach of large matrix multiplication based on Hadoop[J]. Journal of Computer Applications, 2013,33(12): 3339-3344.
[10]	REZA M , SINHA A , NAG R ,et al. CUDA-enabled Hadoop cluster for sparse matrix vector multiplication[C]// IEEE International Conference on Recent Trends in Information Systems,July 9-11,2015,Kolkata,India. Piscataway:IEEE Press, 2015.
[11]	MALYSIAK D , KOPINSKI T . A generic and adaptive approach for workload distribution in multi-tier cluster systems with an application to distributed matrix multiplication[C]// IEEE International Symposium on Computational Intelligence and Informatics,November 19-21,2015,Budapest,Hungary. Piscataway:IEEE Press, 2015.
[12]	GIZA-BELCIUG F , PENTIUC S G . Parallelization of similarity matrix calculus in ontology mapping systems[C]// Roedunet International Conference-Networking in Education and Research,September 24-26,2015,Craiova,Romania. Piscataway:IEEE Press, 2015.
[13]	ZHANG R , WANG Y . An enhanced agglomerative fuzzy k-means clustering method with MapReduce implementation on Hadoop platform[C]// International Conference on Progress in Informatics and Computing,May 16-18,2014,Shanghai,China. Piscataway:IEEE Press, 2014.
[14]	MANN K S , KAUR N . Cloud-deployable health data mining using secured framework for clinical decision support system[C]// International Conference and Workshop on Computing and Communication,October 15-17,2015,Vancouver,BC,Canada. Piscataway:IEEE Press, 2015.
[15]	SHAHRIVARI S , JALILI S . Single-pass and linear-time k-means clustering based on MapReduce[J]. Information Systems, 2016(60): 1-12.
[16]	LU S , TONG W , CHEN Z . Implementation of the KNN algorithm based on Hadoop[C]// International Conference on Smart and Sustainable City and Big Data,July 26-27,2015,Shanghai,China. Birmingham:IET Press, 2015.
[17]	SONG G , ROCHAS J , BEZE L ,et al. K nearest neighbour joins for big data on MapReduce:a theoretical and experimental analysis[J]. IEEE Transactions on Knowledge ＆ Data Engineering, 2016,28(9): 2376-2392.
[18]	MIEGHEM P V , BLENN N , DOERR C . Lognormal distribution in the digg online social network[J]. European Physical Journal B, 2011,83(2): 251-261.
[19]	MAHANTI A , CARLSSON N , MAHANTI A ,et al. A tale of the tails:power-laws in internet measurements[J]. IEEE Network, 2013,27(1): 59-64.
[20]	ZHOU C , JIANG H , CHEN Y ,et al. TCB:a feature transformation method based central behavior for user interest prediction on mobile big data[J]. International Journal of Distributed Sensor Networks, 2016,12(9).
[21]	WU L , JIANG H , ZHENG H ,et al. Long tail and small world characteristic of mobile internet traffic dynamics[C]// IEEE International Conference on Systems,Man and Cybernetics,October 5-8,2014,San Diego,CA,USA. Piscataway:IEEE Press, 2014.
[22]	WU L , LI Y , ZHOU C ,et al. Statistic analysis of data access behavior in the mobile internet[C]// IEEE/CIC International Conference on Communications in China,August 12-14,2013,Xi’an,China. Piscataway:IEEE Press, 2013.
[23]	ZHANG N , ZHENG G , CHEN H ,et al. HBaseSpatial:a scalable spatial data storage based on HBase[C]// IEEE International Conference on Trust,Security and Privacy in Computing and Communications,September 24-26,2014,Beijing,China. Piscataway:IEEE Press, 2014.
[24]	王荣 . 基于三元组表表示的稀疏矩阵的快速转置算法及其改进[J]. 现代电子技术, 2008,31(22): 78-79.
	WANG R . Improvement on fast transposition algorithm to sparse matrix expressed by triple list[J]. Modern Electronics Technique, 2008,31(22): 78-79.
[25]	AFSHANG M , DHILLON H S , CHONG P H J . Fundamentals of cluster-centric content placement in cache-enabled device-to-device networks[J]. IEEE Transactions on Communications, 2015,64(6): 2511-2526.
[26]	ZHOU B , CUI Y , TAO M . Stochastic content-centric multicast scheduling for cache-enabled heterogeneous cellular networks[J]. IEEE Transactions on Wireless Communications, 2016,15(9): 6284-6297.

RowKey			columnFamily
RowKey	sTime	eTime	lacID	cellID	x	y	url
uid1+startTime1	startTime1	endTime1	lacID1	cellID1	x1	y1	url1
uid2+startTime2	startTime2	endTime2	lacID2	cellID2	x2	y2	url2
…	…	…	…	…	…	…	…
uidn+startTimen	startTimen	endTime n	lacIDn	cellID n	xn	yn	urln

字段名	含义
uid	加密后的用户ID，唯一标识用户身份
lacID	基站所在地区的区域代码
cellID	扇区编号（lacID和cellID唯一标识基站）
sTime	数据流起始时间
eTime	数据流持续时间
url	截短后的访问内容地址
longitude	基站所在位置经度
latitude	基站所在位置纬度

对比项	划分前	划分后	百分比
社区内边数/条	16 438 105	7 315 487	44.5%
好边数/条	16 438 105	7 277 559	44.3%
正确用户数/个	20 846	20 824	99.9%

对比项	划分前	划分后	百分比
社区内边数/条	109 498	74 581	68.1%
好边数/条	109 498	56 400	51.5%
正确用户数/个	3 468	3 327	95.9%

基于用户移动网络接入位置的高效分布式相似矩阵计算方法

A distributed high efficiency similarity matrix computation method based on users’ mobile network access location

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 26

相关文章 15

Metrics

推荐阅读 0

[1]	谢萍,刘孝颂. 基于区块链的SDN物联网部署安全[J]. 电信科学, 2020, 36(12): 139-146.
[2]	李成岭,郑雨翔,洪祎祺,李雯,郭慧敏. 电网数据存储技术选型的研究[J]. 电信科学, 2018, 34(5): 183-191.
[3]	彭巍,贺晓东,陆小铭,汲传鑫. 运营商DNS海量数据分析技术优化和应用[J]. 电信科学, 2018, 34(3): 138-144.
[4]	徐海勇,黄岩. 基于PaaS技术的大数据云化平台实践[J]. 电信科学, 2018, 34(1): 148-157.
[5]	方艾,张玉忠,徐雄,金铎. 基于MapR的IPTV用户收视行为分析的方案与实践[J]. 电信科学, 2017, 33(2): 138-144.
[6]	汪保友,钱晶,袁时金. 基于Hadoop的电信大数据采集方案研究与实现[J]. 电信科学, 2017, 33(1): 135-142.
[7]	刘南海,雷蕾,王睿. 大数据时代运营商分析支撑域转型的实践与思考[J]. 电信科学, 2016, 32(8): 146-158.
[8]	谭造乐,郝志峰,蔡瑞初,肖晓军,卢宇. 基于信息增益的Hadoop瓶颈检测算法[J]. 电信科学, 2016, 32(7): 115-120.
[9]	李远宁,刘森,张诗军,陈丰,王志英. 分布式数据质量管理系统在电力企业的实践和应用[J]. 电信科学, 2016, 32(4): 169-174.
[10]	公怀予,徐劲松,王攀. 一种关联感知的大数据导入方法[J]. 电信科学, 2016, 32(3): 130-134.
[11]	谷红勋,杨珂. 基于大数据的移动用户行为分析系统与应用案例[J]. 电信科学, 2016, 32(3): 139-146.
[12]	赵会敏,雒江涛,杨军超,徐正,雷晓,罗林. 集成BP神经网络预测模型的研究与应用[J]. 电信科学, 2016, 32(2): 60-67.
[13]	王忠伟,陈叶芳,肖四友,钱江波. 一种高维大数据全k近邻查询算法[J]. 电信科学, 2015, 31(7): 52-62.
[14]	任建新,陈华辉. 一种自适应子空间相似性搜索方法[J]. 电信科学, 2015, 31(7): 63-74.
[15]	陈丽,王锐. 基于Hadoop的信令详单实时查询平台构建方法[J]. 电信科学, 2015, 31(7): 145-151.