第12卷第5期 智能系统学报 Vol.12 No.5 2017年10月 CAAI Transactions on Intelligent Systems 0ct.2017 D0I:10.11992/tis.201706027 网络出版地址：http:/kns.cmki.net/kcms/detail/23.1538.TP.20170831.1058.016.html 移动社交网络异常签到在线检测算法 赵冠哲，齐建鹏，于彦伟，刘兆伟，宋鹏 (烟台大学计算机与控制工程学院，山东烟台264005) 摘要：随着智能手机、Pd等智能移动设备的广泛普及，移动社交网络的应用得到了快速发展。本文针对移动社交 网络中用户异常签到位置检测问题，提出了一类基于用户移动行为特征的异常签到在线检测方法。首先，在基于距 离的异常模型基础上，提出了基于历史位置(H-Outlier)和基于好友圈(F-Outlier)两种异常签到模型：然后，针对H- Outlier提出了一种优化的检测算法H-Opt,利用所提的签到状态模型与优化的邻居搜索机制降低检测时间：针对F. Outlier提出了一种基于触发的优化检测算法F-Opt,将连续的在线异常检测转化成了基于触发的异常检测方式：最 后，在真实的移动社交网络用户签到数据集上，验证了所提算法的有效性。实验结果显示，F-Opt显著降低了H-Op 的异常检测错误率：同时，相比于LUE算法，F-0pt和H-0pt的效率分别平均提升了2.34倍和2.45倍。 关键词：移动社交网络；异常检测：签到位置：基于距离的异常：好友圈：签到状态：邻居搜索：时间触发检测 中图分类号：TP391文献标志码：A文章编号：1673-4785(2017)05-0752-08 中文引用格式：赵冠哲，齐建鹏，于彦伟，等.移动社交网络异常签到在线检测算法[J].智能系统学报，2017,12(5)：752-759. 英文引用格式：ZHA0 Guanzhe,QI Jianpeng,YU Yanwei,,etal.Online check-in outlier detection method in mobile social networks[J].CAAI transactions on intelligent systems,2017,12(5):752-759. Online check-in outlier detection method in mobile social networks ZHAO Guanzhe,QI Jianpeng,YU Yanwei,LIU Zhaowei,SONG Peng (School of Computer and Control Engineering,Yantai University,Yantai 264005,China) Abstract:With the increasing popularization of smartphone,Pads and other smart mobile devices,the use of mobile social networks has also developed rapidly.In this paper,we propose an online method for detecting check- in outliers based on user mobility behavior in mobile social networks.First.based on a distance-based outlier model,we propose two check-in outlier models with respect to historical location(H-Outlier)and friend circle (F- Outlier),respectively.Second,for the H-Outlier,we propose an optimized detection algorithm called H-Opt, which utilizes the proposed check-in status model and an optimized neighbor searching mechanism to reduce computation time.For the F-Outlier,we propose a trigger-based optimized detection algorithm called F-Opt,which transforms continuous online outlier detection into trigger-based outlier detection.Lastly,we present our experimental results,based on a real-world check-in dataset,which demonstrate the effectiveness of the proposed algorithm.Our experimental results show that F-Opt significantly reduces the error rate of H-Opt outlier detection. In addition,compared with the LUE algorithm,the F-Opt and H-Opt algorithms improved efficiency by 2.34 and 2.45 times,respectively. Keywords:location-based social networks;outlier detection;check-in location;distance-based outlier;friend circle;status of check-in;neighbor searching;time-triggered detection 随着GPS终端、Pad、智能手机等位置感知设备 了快速发展。移动社交网络也称基于位置的社交 的广泛普及，各类新型社交网络手机应用不断涌 网络(location-based social networks,LBSN),本质是 现，促使移动社交网络(mobile social networks)得到 提供一个在人群中分享兴趣、爱好、状态和活动等 收稿日期：2017-06-08.网络出版日期：2017-08-31. 信息的平台)。如国内的腾讯QQ、微信、新浪微 基金项目：国家自然科学基金项目(61403328,61572419)：山东省重点 博、人人网，国外的Twitter、Facebook、Gowalla、 研发计划项目(2015GSF115009):山东省自然科学基金项目 (ZR2014Q016):烟台大学研究生科技创新基金项目Foursquare等，这些LBSN应用聚集了大量移动用 (YDZD1712). 通信作者：于彦伟.E-mail:yuyanwei(@ytu.cdu.cm. 户。据We Are Social公司在2016年数字报告[)中第 １２ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．５ ２０１７ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１７０６０２７ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０８３１．１０５８．０１６．ｈｔｍｌ 移动社交网络异常签到在线检测算法 赵冠哲，齐建鹏，于彦伟，刘兆伟，宋鹏 （烟台大学 计算机与控制工程学院，山东 烟台 ２６４００５） 摘 要：随着智能手机、Ｐａｄ 等智能移动设备的广泛普及，移动社交网络的应用得到了快速发展。 本文针对移动社交 网络中用户异常签到位置检测问题，提出了一类基于用户移动行为特征的异常签到在线检测方法。 首先，在基于距 离的异常模型基础上，提出了基于历史位置 （Ｈ⁃Ｏｕｔｌｉｅｒ）和基于好友圈 （Ｆ⁃Ｏｕｔｌｉｅｒ）两种异常签到模型；然后，针对 Ｈ⁃ Ｏｕｔｌｉｅｒ 提出了一种优化的检测算法 Ｈ⁃Ｏｐｔ，利用所提的签到状态模型与优化的邻居搜索机制降低检测时间；针对 Ｆ⁃ Ｏｕｔｌｉｅｒ 提出了一种基于触发的优化检测算法 Ｆ⁃Ｏｐｔ，将连续的在线异常检测转化成了基于触发的异常检测方式；最 后，在真实的移动社交网络用户签到数据集上，验证了所提算法的有效性。 实验结果显示，Ｆ⁃Ｏｐｔ 显著降低了 Ｈ⁃Ｏｐｔ 的异常检测错误率；同时，相比于 ＬＵＥ 算法，Ｆ⁃Ｏｐｔ 和 Ｈ⁃Ｏｐｔ 的效率分别平均提升了 ２．３４ 倍和 ２．４５ 倍。 关键词：移动社交网络；异常检测；签到位置；基于距离的异常；好友圈；签到状态；邻居搜索；时间触发检测 中图分类号：ＴＰ３９１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０５－０７５２－０８ 中文引用格式：赵冠哲，齐建鹏，于彦伟，等．移动社交网络异常签到在线检测算法［Ｊ］． 智能系统学报， ２０１７， １２（５）： ７５２－７５９． 英文引用格式： ＺＨＡＯ Ｇｕａｎｚｈｅ， ＱＩ Ｊｉａｎｐｅｎｇ， ＹＵ Ｙａｎｗｅｉ， ｅｔ ａｌ． Ｏｎｌｉｎｅ ｃｈｅｃｋ⁃ｉｎ ｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎ ｍｅｔｈｏｄ ｉｎ ｍｏｂｉｌｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（５）： ７５２－７５９． Ｏｎｌｉｎｅ ｃｈｅｃｋ⁃ｉｎ ｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎ ｍｅｔｈｏｄ ｉｎ ｍｏｂｉｌｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ ＺＨＡＯ Ｇｕａｎｚｈｅ， ＱＩ Ｊｉａｎｐｅｎｇ， ＹＵ Ｙａｎｗｅｉ， ＬＩＵ Ｚｈａｏｗｅｉ， ＳＯＮＧ Ｐｅｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｎｔｒｏｌ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｙａｎｔａｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｙａｎｔａｉ ２６４００５， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｗｉｔｈ ｔｈｅ ｉｎｃｒｅａｓｉｎｇ ｐｏｐｕｌａｒｉｚａｔｉｏｎ ｏｆ ｓｍａｒｔｐｈｏｎｅ， Ｐａｄｓ ａｎｄ ｏｔｈｅｒ ｓｍａｒｔ ｍｏｂｉｌｅ ｄｅｖｉｃｅｓ， ｔｈｅ ｕｓｅ ｏｆ ｍｏｂｉｌｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ ｈａｓ ａｌｓｏ ｄｅｖｅｌｏｐｅｄ ｒａｐｉｄｌｙ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｗｅ ｐｒｏｐｏｓｅ ａｎ ｏｎｌｉｎｅ ｍｅｔｈｏｄ ｆｏｒ ｄｅｔｅｃｔｉｎｇ ｃｈｅｃｋ⁃ ｉｎ ｏｕｔｌｉｅｒｓ ｂａｓｅｄ ｏｎ ｕｓｅｒ ｍｏｂｉｌｉｔｙ ｂｅｈａｖｉｏｒ ｉｎ ｍｏｂｉｌｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ． Ｆｉｒｓｔ， ｂａｓｅｄ ｏｎ ａ ｄｉｓｔａｎｃｅ⁃ｂａｓｅｄ ｏｕｔｌｉｅｒ ｍｏｄｅｌ， ｗｅ ｐｒｏｐｏｓｅ ｔｗｏ ｃｈｅｃｋ⁃ｉｎ ｏｕｔｌｉｅｒ ｍｏｄｅｌｓ ｗｉｔｈ ｒｅｓｐｅｃｔ ｔｏ ｈｉｓｔｏｒｉｃａｌ ｌｏｃａｔｉｏｎ （Ｈ⁃Ｏｕｔｌｉｅｒ） ａｎｄ ｆｒｉｅｎｄ ｃｉｒｃｌｅ （Ｆ⁃ Ｏｕｔｌｉｅｒ）， ｒｅｓｐｅｃｔｉｖｅｌｙ． Ｓｅｃｏｎｄ， ｆｏｒ ｔｈｅ Ｈ⁃Ｏｕｔｌｉｅｒ， ｗｅ ｐｒｏｐｏｓｅ ａｎ ｏｐｔｉｍｉｚｅｄ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｃａｌｌｅｄ Ｈ⁃Ｏｐｔ， ｗｈｉｃｈ ｕｔｉｌｉｚｅｓ ｔｈｅ ｐｒｏｐｏｓｅｄ ｃｈｅｃｋ⁃ｉｎ ｓｔａｔｕｓ ｍｏｄｅｌ ａｎｄ ａｎ ｏｐｔｉｍｉｚｅｄ ｎｅｉｇｈｂｏｒ ｓｅａｒｃｈｉｎｇ ｍｅｃｈａｎｉｓｍ ｔｏ ｒｅｄｕｃｅ ｃｏｍｐｕｔａｔｉｏｎ ｔｉｍｅ． Ｆｏｒ ｔｈｅ Ｆ⁃Ｏｕｔｌｉｅｒ， ｗｅ ｐｒｏｐｏｓｅ ａ ｔｒｉｇｇｅｒ⁃ｂａｓｅｄ ｏｐｔｉｍｉｚｅｄ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｃａｌｌｅｄ Ｆ⁃Ｏｐｔ， ｗｈｉｃｈ ｔｒａｎｓｆｏｒｍｓ ｃｏｎｔｉｎｕｏｕｓ ｏｎｌｉｎｅ ｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎ ｉｎｔｏ ｔｒｉｇｇｅｒ⁃ｂａｓｅｄ ｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎ． Ｌａｓｔｌｙ， ｗｅ ｐｒｅｓｅｎｔ ｏｕｒ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ， ｂａｓｅｄ ｏｎ ａ ｒｅａｌ⁃ｗｏｒｌｄ ｃｈｅｃｋ⁃ｉｎ ｄａｔａｓｅｔ， ｗｈｉｃｈ ｄｅｍｏｎｓｔｒａｔｅ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ． Ｏｕｒ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ Ｆ⁃Ｏｐｔ ｓｉｇｎｉｆｉｃａｎｔｌｙ ｒｅｄｕｃｅｓ ｔｈｅ ｅｒｒｏｒ ｒａｔｅ ｏｆ Ｈ⁃Ｏｐｔ ｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎ． Ｉｎ ａｄｄｉｔｉｏｎ， ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ＬＵＥ ａｌｇｏｒｉｔｈｍ， ｔｈｅ Ｆ⁃Ｏｐｔ ａｎｄ Ｈ⁃Ｏｐｔ ａｌｇｏｒｉｔｈｍｓ ｉｍｐｒｏｖｅｄ ｅｆｆｉｃｉｅｎｃｙ ｂｙ ２．３４ ａｎｄ ２．４５ ｔｉｍｅｓ， ｒｅｓｐｅｃｔｉｖｅｌｙ． Ｋｅｙｗｏｒｄｓ：ｌｏｃａｔｉｏｎ⁃ｂａｓｅｄ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ； ｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎ； ｃｈｅｃｋ⁃ｉｎ ｌｏｃａｔｉｏｎ； ｄｉｓｔａｎｃｅ⁃ｂａｓｅｄ ｏｕｔｌｉｅｒ； ｆｒｉｅｎｄ ｃｉｒｃｌｅ； ｓｔａｔｕｓ ｏｆ ｃｈｅｃｋ⁃ｉｎ； ｎｅｉｇｈｂｏｒ ｓｅａｒｃｈｉｎｇ； ｔｉｍｅ－ｔｒｉｇｇｅｒｅｄ ｄｅｔｅｃｔｉｏｎ 收稿日期：２０１７－０６－０８． 网络出版日期：２０１７－０８－３１． 基金项目：国家自然科学基金项目（６１４０３３２８， ６１５７２４１９）； 山东省重点 研发计划项目（２０１５ＧＳＦ１１５００９）； 山东省自然科学基金项目 （ＺＲ２０１４ＦＱ０１６ ）； 烟 台 大 学 研 究 生 科 技 创 新 基 金 项 目 （ＹＤＺＤ１７１２）． 通信作者：于彦伟． Ｅ⁃ｍａｉｌ：ｙｕｙａｎｗｅｉ＠ ｙｔｕ．ｅｄｕ．ｃｎ． 随着 ＧＰＳ 终端、Ｐａｄ、智能手机等位置感知设备 的广泛普及，各类新型社交网络手机应用不断涌 现，促使移动社交网络（ｍｏｂｉｌｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ）得到 了快速发展。 移动社交网络也称基于位置的社交 网络（ｌｏｃａｔｉｏｎ⁃ｂａｓｅｄ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ， ＬＢＳＮ），本质是 提供一个在人群中分享兴趣、爱好、状态和活动等 信息的平台［１］ 。 如国内的腾讯 ＱＱ、微信、新浪微 博、 人 人 网， 国 外 的 Ｔｗｉｔｔｅｒ、 Ｆａｃｅｂｏｏｋ、 Ｇｏｗａｌｌａ、 Ｆｏｕｒｓｑｕａｒｅ 等，这些 ＬＢＳＮ 应用聚集了大量移动用 户。 据 Ｗｅ Ａｒｅ Ｓｏｃｉａｌ 公司在 ２０１６ 年数字报告［２］ 中