基于互助行为聚类的移动社交软件设计与实现

刘安战, 车战斌, 贾晓辉

(中原工学院, 郑州 450007)



基于互助行为聚类的移动社交软件设计与实现

刘安战, 车战斌, 贾晓辉

(中原工学院, 郑州 450007)

摘要：在分析当前社交网络应用的基础上，设计了一款基于互助行为聚类的移动社交软件，提出了一种基于互助行为的聚类算法。该社交软件包括移动客户端和后台服务端，移动客户端基于Android平台开发，后台服务端采用云服务的方式为客户端提供服务。所设计的聚类算法以直接互助行为为基础，采用朋友链的方式组成朋友圈并进行聚类。

关键词：互助行为;聚类;互助聚类;移动社交

随着移动互联网的发展，社交网络正在以前所未有的速度迅猛发展。社交网络聚类是为了更好地把某种相关用户联系在一起。经典的聚类算法有Newman算法[1]、Kernighan-Lin算法等[2]，不过它们没有考虑社交网络的有向性。陈季梦等基于SCAN提出了有向网络聚类算法DirSCAN算法[3]；李敏等在用户聚类方面关注签到点和轨迹，对基于位置的社交网络用户签到及相关行为进行了研究[4]；张延玲等提出了一种移动对象子轨迹段分割与聚类算法[5]；苏孝强等提出了一种基于空间相依性的移动对象聚类算法[6]。对Livejournal[7]、Facebook[8]、新浪微博[9]等社交网站的统计研究发现，在线社交网络结构普遍具有度幂律分布、较高聚类性和同配性等特性[10]。本文提出了基于互助行为的聚类方法，设计了一款基于该方法的移动社交软件。社交网络朋友圈建立在实际的互助行为基础上，使聚类用户直接具有更高的聚类特性。

1用户角色

在基于互助行为聚类的移动社交软件中，参与者分为3个角色，分别是超级管理员、管理员、移动用户。

超级管理员是后台管理者，拥有移动用户管理、角色权限管理、管理员管理、日志管理、互助信息维护、移动用户申诉处理等管理权限。

管理员是后台管理者，根据超级管理员分配的权限进行相应的管理工作，主要是对移动用户反馈信息、留言信息等进行管理。

移动用户是移动客户端的使用者，通过智能移动终端登录系统，并使用系统所提供的功能，主要包括好友管理、互助管理、求助、帮助等功能。

2系统需求

基于互助行为聚类的移动社交软件是一款知识分享的社交软件。和传统的社交软件相比，该软件更加注重用户之间的实际互助行为，更加注重地理位置分享。通过使用该软件，用户更容易找到志同道合的朋友，朋友圈多在发生实际互助行为的用户之间建立起来。

软件以求助和帮助为核心。当一个用户需要获得帮助时，可以通过客户端软件发布求助信息。求助信息可以是需要在线解答的问题(如哪里有XX折扣店?今年国庆节放几天假?)，也可以是需要线下解决的问题(如电脑没法启动了，需要上门维修)。用户借助平台进行互助的过程，正是用户之间建立好友关系的过程。同时，系统采用基于地理位置的服务，可以让用户发现附近的求助和帮助信息，为用户提供更好的线上线下互动机会。系统基本用例如图1所示。

图1　系统用例图

3系统设计与实现

3.1系统结构

整个系统包括后台数据库、服务端和移动客户端等3部分。数据库采用MySQL数据库，服务端采用HTTP协议提供Web服务，移动客户端以Android作为工作平台。

3.1.1数据库设计

数据库为系统提供后台数据存储和服务，通过网络服务为客户提供数据信息。

根据系统需求，设计出数据库主要的实体及其关系架构。主要实体包括问题、用户、角色、反馈信息、留言板、互助行为等。实体关系图如图2所示。

图2　系统的主要实体关系图

3.1.2服务端

系统服务端提供的服务主要包括两部分：一是为移动客户端提供的服务，二是为Web管理提供的服务。为移动客户端提供的服务主要包括注册、登录、发布问题、回答问题、获得朋友圈、给好友留言、搜索、个人设置等服务；为Web管理提供的服务主要是为了让管理员能够通过Web对系统后台进行管理。

为Web管理提供服务的实现采用Python语言和Nginx+WSGI技术；Web服务器采用Tornado，WSGI把服务器功能以 WSGI 接口的方式向外提供服务。

后台管理程序主要由模型模块和主模块组成。HTTP类模块属于模型模块，该类模块负责提供HTPP网络通信功能。其中，采用SendRequest方法用来发送HTTP数据请求，采用GetDIct方法负责把返回的内容转化为JSON格式。模型模块中还包括Log、FeedBack、Statistic等类模块，它们都继承了HTTP类模块。在主模块中，程序通过application=tornado.web.Application([(r"/Feedback",FeedbackHandler)]…)进行服务匹配，如果在URL中访问的是FeedBack，就执行FeedbackHandler类模块中的服务。该类模块继承了Feedback类模块。具体模块类图如图3所示。

图3　后台管理的部分模块类图

3.1.3移动客户端

移动客户端包括4个主要模块，分别是我的求助、朋友管理、搜索和个人设置。每个模块又分为若干个子模块。移动客户端功能模块划分如图4所示。

图4　移动客户端功能模块划分图

(1)我的求助。该模块主要包括问题列表和发布问题两个子模块。问题以列表的形式被呈现，每一个问题都可以进行删除和设置最佳解答等功能操作。发布问题是移动用户通过移动客户端进行求助的主要方式，用户可以对自己已经发布的问题进行维护。

(2)朋友管理。该模块主要包括查看信息、帮助朋友、维护朋友等3个子模块。系统把好友分为我的助友、助我之友和主题朋友圈。我的助友是我直接帮助过的用户，助我之友是直接帮助过我的用户，主题朋友圈则是在一定的主题下通过聚类算法形成的朋友用户列表。通过朋友列表，朋友之间可以方便地进行在线交流。帮助朋友模块可以为求助的用户提供帮助,提供帮助的形式包括线上解决问题、线下帮助。

(3)搜索。该模块承担为用户提供搜索资源的功能，主要包括问题查询、附近问题查询、按主题查询和用户查询等功能。系统不仅提供模糊查询功能，还采用GPS定位服务提供按地理位置查询功能，通过优化排序，使用户搜索到的信息更加有效。

(4)个人设置。该模块具有编辑个人信息、维护留言信息和系统设置等功能。留言采用推送的方式实现，使得其他用户的留言能够实时地推送到移动用户终端。系统设置为用户提供了一些个性化的客户端设置功能，如是否允许推送、问题搜索范围、关注的主题、是否允许通过姓名搜索到自己等。

3.2聚类算法

在该软件系统中，互助关系包括3种：一是用户主动帮助别人，二是用户被别人帮助，三是用户直接互相帮助。

定义1：如果用户A通过系统为用户B提供了直接帮助，则B就是被A直接帮助过的用户，记作B∈HO(A)，HO(A)表示A直接帮助过的所有用户组成的集合；相应地，A就是直接帮助过B的用户，记作A∈HI(B)，HI(B)表示所有直接接受过A帮助的用户组成的集合。

定义2：在某个主题S下，如果用户A为用户B提供了直接帮助，则B是A在该主题S下直接帮助过的用户,记作B∈HO(A,S),HO(A,S)表示A在主题S下直接帮助过的所有用户组成的集合；同样，A∈HI(B,S)。根据定义1可知,HO(A,S)⊂HO(A)，HI(A,S)⊂HI(A)。

定义3：如果Bn∈HO(Bn-1,S)，Bn-1∈HO(Bn-2,S),…,B1∈HO(A,S)，则表示A在主题S下间接帮助了Bn，记作Bn∈HO[A,S]，HO[A,S]表示A在主题S下间接帮助过的所有用户组成的集合。这里B1，…,Bn-1,Bn称为A的S主题帮链。

定义4：一条从A出发到A结束的A的S主题帮链称为A的一个S主题朋友环，A的所有S主题朋友环上的用户组成的集合称为A的S主题朋友圈。

基于上述定义，朋友圈具有更强的主题特性和互助行为特征，一个用户的朋友圈里的所有用户都是自己直接或间接帮助过的用户，这些用户也是直接或间接帮助过自己的用户。

在算法实现方面，采用深度搜索算法。具体的算法描述如下：

(1)从HO(A,S)中第一个节点V开始标记为已搜索；

(2)将V进栈；

(3)当栈不空时，重复以下步骤：

①如果V=A，则把所有栈中元素标记为A的朋友圈用户，结束搜索，否则继续搜索；

②从栈顶元素V的HO(V,S)中的下一个节点W开始继续进行深度搜索。

基于上述算法形成的朋友圈，随着用户的增加会不断增大。因此，系统可通过设置不同的主题、子主题、地理位置、互助阈值等进一步限制朋友圈的形成条件，以防止过多的用户聚类到同一个朋友圈而造成臃肿，进而使互助行为发生的效果降低。

4测试结果

将所设计和开发的系统移动客户端通过模拟器和真机进行测试。真机采用的是华为荣耀3X，其操作系统为Android4.2，CPU为MKT 6592，机身内存为2GB RAM+8GB ROM，网络为WiFi、WCDM和GPRS。服务端运行在新浪云平台Sina App Engine(SAE)，采用Apache+Mysql服务。经过实际测试，客户端运行良好。部分运行界面如图5所示。

图5　移动客户端部分界面

5结语

本文设计了一款基于互助行为聚类的移动

社交软件，提出了一种基于互助行为的聚类算法。通过该聚类算法，用户之间的朋友关系建立在实际的互助行为基础之上，朋友圈内的朋友具有更好的主题相关性。该软件主要包括移动客户端和后台服务端，移动客户端运行于智能终端，服务端部署于新浪云平台。经测试，软件运行良好。

参考文献:

[1]Newman M E J.Fast Algorithm for Detecting Community Structure in Networks[J].Physical Review E，2004，69(6):066133.

[2]Lancichinetti A, Fortunato S, Kert～sz J.Detecting the Overlapping and Hierarchical Community Structure in Complex Networks[J].New Journal of Physics, 2009, 11(3):033015.

[3]陈季梦,陈佳俊,刘杰，等.基于结构相似度的大规模社交网络聚类算法[J].电子与信息学报,2015,37(2):449-454.

[4]李敏,王晓聪.基于位置的社交网络用户签到及相关行为研究[J].计算机科学,2013,40(10):72-76.

[5]张延玲,刘金鹏,姜保庆.移动对象子轨迹段分割与聚类算法[J].计算机工程与应用,2009,45(10):65-68.

[6]苏孝强,倪宏.一种基于空间相依性的移动对象聚类算法[J].微计算机应用,2011,32(5):39-44.

[7]Mislove A, Marcon M, Gummadi K P, et al. Measurement and Analysis of Online Social Networks[C]//Proceedings of the 7th ACM Special Interest Group on Data Communication Conference on Internet Measurement. New York:ACM,2007:29-42.

[8]Viswanath B, Mislove A, Cha M, et al.On the Evolution of User Interaction in Facebook[C]//Proceedings of the 2nd ACM Workshop on Online Social Networks.New York:ACM,2009:37-42.

[9]Chen Z, Liu P, Wang X, et al. Follow Whom: Chinese Users Have Different Choice[EB/OL]. [2015—11—28].http://arxiv.org/abs/1212.0167.

[10]李倩倩,顾基发.用户行为驱动的在线社交网络建模[J].系统工程学报,2015,30(1):9-15.

(责任编辑：张同学)

收稿日期：2015—12—23

基金项目：河南省教育厅高等学校重点科研项目(15B520041)；河南省科技攻关项目(152102210150)

作者简介：刘安战(1980—)，男，河南新乡人，讲师，硕士，主要研究方向为软件工程、移动计算。

文章编号：1671-6906(2016)03-0090-05

中图分类号：TP311

文献标志码：A

DOI:10.3969/j.issn.1671-6906.2016.03.020

Design and Implementation of Mobile Social Software Based on Mutual Behavior Clustering

LIU An-zhan， CHE Zhan-bin， JIA Xiao-hui

(Zhongyuan University of Technology, Zhengzhou 450007, China)

Abstract:After analyzing the current social software, this paper designs and implements a mobile social software based on the mutual behavior, presents a clustering algorithm based on mutual assistance behavior. The software includes mobile client and background services, mobile client running on android smart phone platform, the background service using cloud services to provide services for the client. The clustering algorithm is based on the direct mutual behavior, using the way of friends to build friends circle.

Key words:mutual behavior; clustering; mutual clustering; mobile social