基于社群智能的大规模移动社交网络数据挖掘技术研究

魏军林 韩楠 乔少杰 袁犁 丁超

摘要：将大规模移动社交网络数据作为研究对象，以社群智能、数据挖掘、GIS为主要手段，对网络宏观静态拓扑特性和微观交互规律进行研究。从模型通用性入手，对个体交互模式建模，揭示群体行为特征，为社会计算、现实世界挖掘、城市计算研究奠定基础。研究难点和关键问题包括：（1）利用复杂网络拓扑特性理论研究网络直径缩减属性和稠化定律;（2）设计基于时空相似性的个体和群体交互模式发现算法;（3）设计新型层次聚类算法解决社区发现问题。切实提高利用社群智能理论对不同类型和规模移动社交网络进行数据挖掘和知识发现的准确率和效率。

关键词：移动社交网络;社区智能;拓扑结构分析;社区发现;层次聚类;GIS

中图法分类号：TP311文献标识码：A文章编号：1672-9129（2018）06-0001-03

Research on Mining Large-scale Mobile Social Network Data Based on Social and Community Intelligence

WEI Jun-Lin¹， HAN Nan²， QIAO Shao-Jie³， YUAN Li⁴， DING Chao¹

（1.Sichuan JKC Geographical Information Technologies Co.， Ltd.， Chengdu， 610043）

（2.School of Cybersecurity， Chengdu University of Information Technology， Chengdu， 610225）

（3.School of Management， Chengdu University of Information Technology， Chengdu， 610103）

（4.Panzhihua City Geographic Information Center， Panzhihua， 617000）

Abstract：In order to analyze large-scale mobile social network data， this study employs the social and community intelligence， data mining and GIS techniques to explore the statically macroscopic topological properties and the dynamically microscopic interaction rules. In order to design a general knowledge discovery schema， this paper models the individual interactions， discloses the characteristic of social behavior， which can help set up the methodology on social computing， reality mining， and urban computing. The difficulties and essential problems in this paper include： （1） using the topological property analysis theories in complex networks to evaluate the shrinking diameter property and densification law; （2） proposing novel individual and social interaction discovery algorithms based on spatio-temporal similarity of individuals; and （3） proposing new hierarchical clustering approaches to cope with the problem of community discovery. This study can greatly help improve the effectiveness and efficiency of data mining and knowledge discovery in different kinds of mobile social networks with various sizes based on the social and community intelligence theories.

Key words：mobile social network; social and community intelligence; topological structure analysis; community discovery; hierarchical clustering; GIS

1  引言

隨着智能手机、车载移动终端等移动便携设备的流行，以及传感网、物联网技术的普及，使用移动终端设备访问社交网络逐渐成为主流。利用车载GPS、手机、公共交通卡等移动终端提供的行为轨迹信息，可以对个体行为模式（如：旅游路线推荐）;群体及社会行为（如：智慧城市）进行预测和模拟，或对基础设施等方案做出合理性分析和评估。移动社交网络带来了大量崭新的研究和应用机会，例如位置服务、异常交通轨迹检测、出租车最优载客寻找及时间最优策略等。典型应用如Facebook、Foursquare、Instagram、微信、移动QQ都是建立在具体移动功能需求上，并且积累的海量的移动社交网络数据。针对移动社交网络数据的管理和挖掘，已经成为当前学术界的一个研究热点。

社群智能（Social and Community Intelligence）是在社會计算、城市计算和现实世界挖掘等相关领域发展基础上提出的^[1]。社群智能侧重于智能信息挖掘，研究内容包括：多数据源融合，分层次智能信息提取。目的在于从大量的数字脚印（Digital Footprints）中挖掘和理解个人和群体运动模式、大规模人类活动和城市动态规律，将这些信息用于各种创新性服务，包括社会关系管理、公共安全维护、人类健康改善、城市资源管理等各个方面^[1]。将社群智能技术应用于挖掘移动社交网络中积累的大规模数据是一个崭新的研究领域，具有重要的科学意义和应用前景。HTC于2011年推出结合强大社群智能功能的手机HTC ChaCha，索尼于2012年9月推出Sony Xperia miro ST23i社交智能手机，进一步证明将社群智能技术应用于大规模移动社交网络社区挖掘可以一方面解决具有挑战性的科学问题，另一方面可以将研究成果应用于真实移动应用中。

下面以如何利用社群智能技术挖掘移动社交网络数据这一问题为背景，列举两个实例来说明本文研究的意义和概貌。

案例1（智慧校园）：智慧校园旨在利用云计算、虚拟化和物联网等新技术来改变党校学员、工作人员和校园资源相互交互的方式，将学校的教学、科研、管理与校园资源和应用系统进行整合，以提高应用交互的明确性、灵活性和响应速度。

问题：作为人口密集场所，当严重流感如H7N9来袭时，如何寻求有效办法限制其传播？当确定A患上某疑似病例后，需要及时地把最近接触过A的人找到。在现有条件下，获取这些有关个人活动情境、空间动态、人际交互信息还没有较好的技术解决方案，需依赖耗时且易出错的人工查询来完成。

解决方法：这一问题可以通过分析来自校园的静态传感设施和移动电话数据以及发布在万维网上的人与人之间关系信息来解决。以流感防控问题为例，记录与A接触过的人、接触时的距离以及时间长短、社会关系（如亲戚、朋友或陌生人）等信息都是非常重要的，诸如此类信息可以通过智能分析和挖掘移动电话感知数据获得。

案例2（个人旅行路线模式挖掘）：为了能够为游客提供个性化舒适的服务，旅游公司希望能进一步了解每一个人的旅行规律。个人旅行往往通过照片记录旅游行程及沿途景观，其带有作者、时间和地点信息，可以从数据中恢复出用户的旅行路线。针对不同的旅行目的地从数据集中找出频繁出现的路线，为游客提供有益的参考和借鉴。

问题：如何利用人工标注的照片预测个体和群体的旅行规律？已知某游客在某地的旅游行为特征预测其在其他城市不同的旅游目的地，实现个性化旅游线路推荐等问题。

解决方法：通过分析游客的行为特征，计算个体之间的行为形似度，设计并利用层次型聚类算法挖掘热点区域或者感兴趣的旅游线路，实现准确的旅游线路推荐。

2  相关工作

社群智能的具体研究内容包括^[1]：1） 多源数据融合，实现多个多模态、异构数据源的融合;2） 分层次智能信息，利用数据挖掘技术从海量数据中提取多维度的智能信息。社群智能技术尤其适用于挖掘更能体现人类行为和社会交互时空特性的移动社交网络数据。社群智能是新近提出的研究方向，当前研究成果较少，部分工作与城市计算领域相关。

城市计算主要依靠静态感知设施来研究人与环境的交互及环境动态信息^[2]。与其不同的是社群智能综合利用人类与现实物理空间内多源信息交互留下的数字脚印信息，进而挖掘更为广泛的情境信息。从小的角度讲包括个人情境、小范围群体行为、周边环境信息，从大的角度讲包括大规模人群、城市及社会的动态变化情况和规律（如公共安全和突发事件、热点地区监测等）。Ferguson等人^[3]对用户提交的健康搜索关键词进行深层次挖掘，推测全球各地区流行病的实时传播情况，研究成果发表在Nature上。Campbell研究组利用以人为中心的移动电话感知技术进行社会关系分析和周边环境监测^[4]。郑宇等人^[5]利用GPS数据，理解个人历史行为轨迹，在大量时空数据基础上，发掘兴趣点（point of interest，POI），为用户提供个性化位置服务，在此基础上实现了GeoLife系统。其团队最近的代表性工作包括T-Share^[6]和U-Air^[7]，T-Share为了解决行车高峰期通行往来的需求，如避免交通拥堵、节约出行和打车时间，应用了大规模出租车行驶信息共享的高效算法。U-Air利用地面监测站有限的空气质量数据，结合交通流、道路结构、兴趣点分布、气象条件等数据，基于机器学习算法建立数据和空气质量的映射关系，进而推断出整个城市细粒度的空气质量。近期，文献[8-12]提出新型机器学习和数据挖掘算法挖掘移动用户的出行规律，为了解人类行为特征提供辅助决策支持。

城市计算研究中虽然越来越重视分析移动社交网络中用户衣食住行等行为规律的挖掘，但是尚未见报到将社群智能应用于挖掘移动社交网络或者社交网络中个体时空交互模式的研究。借助社群智能技术可以进行智能信息抽取，挖掘高级智能信息，如个人情境、社会事件、人与人之间关系、带语义的位置（如在高铁上、在闹市区）等，解决挖掘结果的准确性问题。此外，对于数据规模大、数据库实时更新要求高的移动社交网络应用来说，结果的时效性也尤为重要，上述评价指标正是目前研究需要重点考虑的。

国内外学者对移动社交网络的研究产生了巨大的热潮，中国计算机学会通讯杂志于2012年第5期设专辑介绍移动社交网络的概念、问题及研究进展^[13]。其中，於志文等人^[14]介绍了移动社交网络的特征，指出“移动社交网络将成为一种全新的连接个体和群体物理空间和网络空间的真实社会网络模式”，给出移动社交网络中感知计算模型的系统架构、平台及其上的应用。唐杰等人^[15]针对移动社交网络提出动态平滑概率因子图模型对用户动态行为建模和预测，模型综合考虑用户属性、网络结构及用户偏好。文献[16]探讨面向移动社交网络的虚拟社区间的协作式内容分发机制，提出了两种优化策略：用户组中内容分发的最大传播时间最小化策略、非服务性用户的内容平均传播时间最小化策略。

乔少杰等人^[17]基于Spark分布式圖计算模型，提出大规模复杂网络社区并行发现算法，基于模块度的聚类思想，对社交网络节点进行合并操作，更新节点对之间的模块度增量，进而实现大规模复杂网络社区识别，社区识别准确率较传统社区发现算法提高了7.4%。近期的另一项典型工作是：提出一种新的面向复杂网络大数据的重叠社区检测算法^[18]，利用平衡二叉树建立模块度增量索引，为了实现模块度最优，提出了一种新型重叠社区检测算法。相对于传统重叠节点检测算法，对每个节点分析的频率大大降低，社区发现的准确率得到提升。

3  移动社交网络拓扑结构特性分析

利用真实移动社交网络数据构建复杂社会网络，借助复杂网络的拓扑特性理论分析移动社交网络的直径缩减属性和稠化定律，挖掘不同网络的拓扑性质：幂率分布、层次性和同配性。

本文研究移动社交网络的平均距离随时间变化，利用有效直径（至少90%相互连接节点对间的距离最大不超过网络直径，它的最小值即为有效直径）。如果移动社交网络随时间增加网络有效直径逐渐减小，说明其满足社会网络的直径缩减属性。另外，讨论网络中节点和边随时间的变化情况。如果网络中边的数量e（t）相对于节点数目n（t）呈非线性增长，形式上服从幂率分布e（t）∝n（t）^α，其中α∈[1， 2]，说明这一网络满足网络稠化定律。

4  基于社群智能的移动社交网络时空交互模式发现方法

基于社群智能的移动社交网络时空交互模式发现方法主要包含如下步骤：

（1）利用数据库理论研究社群智能的多数据源融合技术，数据来源于：互联网与万维网挖掘、静态传感器感知、移动及可穿戴计算;

（2）采用SVM和HMM模型等技术将原始数据转换为个体时空交互语义情境信息;对不同的特征或情境信息进行集成，得到社群智能信息;

（3）从社群智能库挖掘个体时空交互模式，构建用户&位置关联矩阵，基于Hausdorff 距离计算k 个连续时空点构成运动轨迹的相似度，并构建社会关系网;

（4）对网络进行深度分析和挖掘个体社会行为，发现特定目标个体或社群的交互模式，社会交互的时空特性，以及信息、物质和行为传播的时空规律，最后可通过数据可视化和GIS等技术展示。具体算法流程如图1所示。

5  基于层次聚类的移动社交网络社区发现算法

提出基于个体位置、环境特征、移动轨迹相似性的层次型聚类算法采用自下而上的方式将较小的cluster合并聚集或者自上而下地将较大的cluster进行划分。簇之间的距离度量采用average-linkage或者编辑距离，即计算两个cluster各自数据点两两距离的平均值。最终实现对大规模移动社交网络节点的精准划分，具体方法如下图所示^[5]。

6  移动社交网络数据集

当前主流的移动社交网络、移动对象数据库、大规模轨迹数据集主要包括：

（1）PROXIMITY移动社交网络数据库：https：//kdl.cs.umass.edu.

该数据集来源于无线移动电话通信关系挖掘实验。每次实验中个体配备了被称为mote的便携通信设备，其每隔10秒钟尝试联系其他mote对象。mote可以进入或者离开其他mote的通信范围。数据集中记录了成功的mote-to-mote连接关系。

（2）LiveJournal Social Network：http：//snap.stanford.edu/data/soc-LiveJou rnal1.html.

数据集记录了1千多万条社交网络用户的交互信息，包含了用户的交友，论坛和博客信息，数据集大小为247.6 MB。LiveJournal最大特点是朋友列表提供了各种企业联合和隐私服务。每个用户都有朋友页，收集最新的分录他或她的朋友列表。

（3）Online Social Networks Research@the Max Planck Institute for Software Systems数据集：http：//socialnetworks.mpi-sws.org.

7  结论

随着移动终端设备日趋普及，积累了大量的移动社交网络数据，这些数据对于分析人类行为规律、社会关系服务、城市计算、公共安全等问题具有重要的研究价值和实际意义。本文研究是从大规模移动社交网络、数据库理论研究、卫星定位和GIS、人工智能、城市计算中提炼出的基础性问题：1） 研究移动社交网络新型高效的社区发现算法;2） 将社群智能技术应用于发现大规模移动社交网络个体时空交互模式。这两个问题均属于数据挖掘中的新问题，本文给出了新思路、新方法并在未来工作中通过实验发现新的现象，推动移动社交网络数据挖掘新理论的产生。

参考文献

[1]      郭斌， 张大庆， 於志文， 周兴社. 数字脚印与社群智能. 中国计算机学会通讯， 2011， 7（3）： 53-60.

[2]      郑宇. 城市计算与大数据. 中国计算机学会通讯， 2013， 9（8）： 8-18.

[3]      Ferguson N， Cummings D， et al. Strategies for Mitigating an Influenza Pandemic. Nature， 2006， 442（7101）： 448-452.

[4]      Campbell A， Choudhury T. From Smart to Cognitive Phones. IEEE Pervasive Computing， 2012， 11（3）： 7-11.

[5]      Zheng Y， Zhou X. Computing with Spatial Trajectories， Springer Press， 2011.

[6]      Ma S， Zheng Y， Wolfson O. T-Share： A Large-Scale Dynamic Taxi Ridesharing Service. In： Proceedings of ICDE 2013， Brisbane， Australia， 2013： 410-421.

[7]      Zheng Y， Liu F， Hsie H. U-Air： When Urban Air Quality Inference Meets Big Data. In： Proceedings of KDD 2013， Chicago， USA， 2013： 1436-1444.

[8]      喬少杰， 韩楠， 丁治明， 金澈清， 孙未未， 舒红平. 多模式移动对象不确定性轨迹预测模型. 自动化学报， 2018， 44（4）： 608-618

[9]      乔少杰， 韩楠， 朱新文， 舒红平， 郑皎凌， 元昌安. 基于卡尔曼滤波的动态轨迹预测算法. 电子学报， 2018， 46（2）： 418-423

[10]    乔少杰， 韩楠， 李天瑞， 李荣华， 李斌勇， 王晓腾， Gutierrez LA. 基于前缀投影技术的大规模轨迹预测模型. 软件学报， 2017， 28（11）： 3043-3057

[11]    乔少杰， 李天瑞， 韩楠， 高云君， 元昌安， 王晓腾， 唐常杰. 大数据环境下移动对象自适应轨迹预测模型. 软件学报， 2015， 26（11）： 2869-2883

[12]    乔少杰， 金琨， 韩楠， 唐常杰， 格桑多吉， Louis Alberto Gutierrez. 一种基于高斯混合模型的轨迹预测算法. 软件学报， 2015， 26（5）： 1048-1063

[13]    谢幸， 连德富. 移动社交网络与用户位置. 中国计算机学会通讯， 2012， 8（5）： 26-31.

[14]    於志文， 周兴社， 郭斌. 移动社交网络中的感知计算模型、平台与实践置. 中国计算机学会通讯， 2012， 8（5）： 12-21.

[15]    Tang J， Wu S， Sun J， Su H. Cross-domain Collaboration Recommendation. In： Proceedings of KDD 2012， Beijing， China， 2012： 1285-1293.

[16]    胡海洋， 李忠金， 胡华， 赵格华. 面向移动社交网络的协作式内容分发机制.计算机学报， 2013， 36（3）： 613-625.

[17]    乔少杰， 郭俊， 韩楠， 张小松， 元昌安， 唐常杰. 大规模复杂网络社区并行发现算法， 计算机学报， 2017， 40（3）： 688-700.

[18]    乔少杰， 韩楠， 张凯峰， 邹磊， 王宏志， Louis Alberto GUTIERREZ. 复杂网络大数据中重叠社区检测算法. 软件学报， 2017， 28（3）： 631-647.

[19]    Calabrese F， Pereira F C， Lorenzo G D， Liu L， Ratti C. The Geography of Taste： Analyzing Cell-phone Mobility and Social Events. In： Proceedings of the 8th International Conference on Pervasive Computing， Helsinki， Finland， 2010： 22-37.

[20]    Calabrese F， Smoreda Z， Blondel V D， Ratti C. Interplay between Telecommunications and Face-to-face Interactions： A Study using Mobile Phone Data. PLoS ONE， 6（7）： e20814， 2011.