基于互助行為聚類的移動(dòng)社交軟件設(shè)計(jì)與實(shí)現(xiàn)

劉安戰(zhàn), 車戰(zhàn)斌, 賈曉輝

(中原工學(xué)院, 鄭州 450007)

?

基于互助行為聚類的移動(dòng)社交軟件設(shè)計(jì)與實(shí)現(xiàn)

劉安戰(zhàn), 車戰(zhàn)斌, 賈曉輝

(中原工學(xué)院, 鄭州 450007)

摘要：在分析當(dāng)前社交網(wǎng)絡(luò)應(yīng)用的基礎(chǔ)上，設(shè)計(jì)了一款基于互助行為聚類的移動(dòng)社交軟件，提出了一種基于互助行為的聚類算法。該社交軟件包括移動(dòng)客戶端和后臺(tái)服務(wù)端，移動(dòng)客戶端基于Android平臺(tái)開發(fā)，后臺(tái)服務(wù)端采用云服務(wù)的方式為客戶端提供服務(wù)。所設(shè)計(jì)的聚類算法以直接互助行為為基礎(chǔ)，采用朋友鏈的方式組成朋友圈并進(jìn)行聚類。

關(guān)鍵詞：互助行為;聚類;互助聚類;移動(dòng)社交

隨著移動(dòng)互聯(lián)網(wǎng)的發(fā)展，社交網(wǎng)絡(luò)正在以前所未有的速度迅猛發(fā)展。社交網(wǎng)絡(luò)聚類是為了更好地把某種相關(guān)用戶聯(lián)系在一起。經(jīng)典的聚類算法有Newman算法[1]、Kernighan-Lin算法等[2]，不過它們沒有考慮社交網(wǎng)絡(luò)的有向性。陳季夢(mèng)等基于SCAN提出了有向網(wǎng)絡(luò)聚類算法DirSCAN算法[3]；李敏等在用戶聚類方面關(guān)注簽到點(diǎn)和軌跡，對(duì)基于位置的社交網(wǎng)絡(luò)用戶簽到及相關(guān)行為進(jìn)行了研究[4]；張延玲等提出了一種移動(dòng)對(duì)象子軌跡段分割與聚類算法[5]；蘇孝強(qiáng)等提出了一種基于空間相依性的移動(dòng)對(duì)象聚類算法[6]。對(duì)Livejournal[7]、Facebook[8]、新浪微博[9]等社交網(wǎng)站的統(tǒng)計(jì)研究發(fā)現(xiàn)，在線社交網(wǎng)絡(luò)結(jié)構(gòu)普遍具有度冪律分布、較高聚類性和同配性等特性[10]。本文提出了基于互助行為的聚類方法，設(shè)計(jì)了一款基于該方法的移動(dòng)社交軟件。社交網(wǎng)絡(luò)朋友圈建立在實(shí)際的互助行為基礎(chǔ)上，使聚類用戶直接具有更高的聚類特性。

1用戶角色

在基于互助行為聚類的移動(dòng)社交軟件中，參與者分為3個(gè)角色，分別是超級(jí)管理員、管理員、移動(dòng)用戶。

超級(jí)管理員是后臺(tái)管理者，擁有移動(dòng)用戶管理、角色權(quán)限管理、管理員管理、日志管理、互助信息維護(hù)、移動(dòng)用戶申訴處理等管理權(quán)限。

管理員是后臺(tái)管理者，根據(jù)超級(jí)管理員分配的權(quán)限進(jìn)行相應(yīng)的管理工作，主要是對(duì)移動(dòng)用戶反饋信息、留言信息等進(jìn)行管理。

移動(dòng)用戶是移動(dòng)客戶端的使用者，通過智能移動(dòng)終端登錄系統(tǒng)，并使用系統(tǒng)所提供的功能，主要包括好友管理、互助管理、求助、幫助等功能。

2系統(tǒng)需求

基于互助行為聚類的移動(dòng)社交軟件是一款知識(shí)分享的社交軟件。和傳統(tǒng)的社交軟件相比，該軟件更加注重用戶之間的實(shí)際互助行為，更加注重地理位置分享。通過使用該軟件，用戶更容易找到志同道合的朋友，朋友圈多在發(fā)生實(shí)際互助行為的用戶之間建立起來。

軟件以求助和幫助為核心。當(dāng)一個(gè)用戶需要獲得幫助時(shí)，可以通過客戶端軟件發(fā)布求助信息。求助信息可以是需要在線解答的問題(如哪里有XX折扣店?今年國慶節(jié)放幾天假?)，也可以是需要線下解決的問題(如電腦沒法啟動(dòng)了，需要上門維修)。用戶借助平臺(tái)進(jìn)行互助的過程，正是用戶之間建立好友關(guān)系的過程。同時(shí)，系統(tǒng)采用基于地理位置的服務(wù)，可以讓用戶發(fā)現(xiàn)附近的求助和幫助信息，為用戶提供更好的線上線下互動(dòng)機(jī)會(huì)。系統(tǒng)基本用例如圖1所示。

圖1　系統(tǒng)用例圖

3系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

3.1系統(tǒng)結(jié)構(gòu)

整個(gè)系統(tǒng)包括后臺(tái)數(shù)據(jù)庫、服務(wù)端和移動(dòng)客戶端等3部分。數(shù)據(jù)庫采用MySQL數(shù)據(jù)庫，服務(wù)端采用HTTP協(xié)議提供Web服務(wù)，移動(dòng)客戶端以Android作為工作平臺(tái)。

3.1.1數(shù)據(jù)庫設(shè)計(jì)

數(shù)據(jù)庫為系統(tǒng)提供后臺(tái)數(shù)據(jù)存儲(chǔ)和服務(wù)，通過網(wǎng)絡(luò)服務(wù)為客戶提供數(shù)據(jù)信息。

根據(jù)系統(tǒng)需求，設(shè)計(jì)出數(shù)據(jù)庫主要的實(shí)體及其關(guān)系架構(gòu)。主要實(shí)體包括問題、用戶、角色、反饋信息、留言板、互助行為等。實(shí)體關(guān)系圖如圖2所示。

圖2　系統(tǒng)的主要實(shí)體關(guān)系圖

3.1.2服務(wù)端

系統(tǒng)服務(wù)端提供的服務(wù)主要包括兩部分：一是為移動(dòng)客戶端提供的服務(wù)，二是為Web管理提供的服務(wù)。為移動(dòng)客戶端提供的服務(wù)主要包括注冊(cè)、登錄、發(fā)布問題、回答問題、獲得朋友圈、給好友留言、搜索、個(gè)人設(shè)置等服務(wù)；為Web管理提供的服務(wù)主要是為了讓管理員能夠通過Web對(duì)系統(tǒng)后臺(tái)進(jìn)行管理。

為Web管理提供服務(wù)的實(shí)現(xiàn)采用Python語言和Nginx+WSGI技術(shù)；Web服務(wù)器采用Tornado，WSGI把服務(wù)器功能以 WSGI 接口的方式向外提供服務(wù)。

后臺(tái)管理程序主要由模型模塊和主模塊組成。HTTP類模塊屬于模型模塊，該類模塊負(fù)責(zé)提供HTPP網(wǎng)絡(luò)通信功能。其中，采用SendRequest方法用來發(fā)送HTTP數(shù)據(jù)請(qǐng)求，采用GetDIct方法負(fù)責(zé)把返回的內(nèi)容轉(zhuǎn)化為JSON格式。模型模塊中還包括Log、FeedBack、Statistic等類模塊，它們都繼承了HTTP類模塊。在主模塊中，程序通過application=tornado.web.Application([(r"/Feedback",FeedbackHandler)]…)進(jìn)行服務(wù)匹配，如果在URL中訪問的是FeedBack，就執(zhí)行FeedbackHandler類模塊中的服務(wù)。該類模塊繼承了Feedback類模塊。具體模塊類圖如圖3所示。

圖3　后臺(tái)管理的部分模塊類圖

3.1.3移動(dòng)客戶端

移動(dòng)客戶端包括4個(gè)主要模塊，分別是我的求助、朋友管理、搜索和個(gè)人設(shè)置。每個(gè)模塊又分為若干個(gè)子模塊。移動(dòng)客戶端功能模塊劃分如圖4所示。

圖4　移動(dòng)客戶端功能模塊劃分圖

(1)我的求助。該模塊主要包括問題列表和發(fā)布問題兩個(gè)子模塊。問題以列表的形式被呈現(xiàn)，每一個(gè)問題都可以進(jìn)行刪除和設(shè)置最佳解答等功能操作。發(fā)布問題是移動(dòng)用戶通過移動(dòng)客戶端進(jìn)行求助的主要方式，用戶可以對(duì)自己已經(jīng)發(fā)布的問題進(jìn)行維護(hù)。

(2)朋友管理。該模塊主要包括查看信息、幫助朋友、維護(hù)朋友等3個(gè)子模塊。系統(tǒng)把好友分為我的助友、助我之友和主題朋友圈。我的助友是我直接幫助過的用戶，助我之友是直接幫助過我的用戶，主題朋友圈則是在一定的主題下通過聚類算法形成的朋友用戶列表。通過朋友列表，朋友之間可以方便地進(jìn)行在線交流。幫助朋友模塊可以為求助的用戶提供幫助,提供幫助的形式包括線上解決問題、線下幫助。

(3)搜索。該模塊承擔(dān)為用戶提供搜索資源的功能，主要包括問題查詢、附近問題查詢、按主題查詢和用戶查詢等功能。系統(tǒng)不僅提供模糊查詢功能，還采用GPS定位服務(wù)提供按地理位置查詢功能，通過優(yōu)化排序，使用戶搜索到的信息更加有效。

(4)個(gè)人設(shè)置。該模塊具有編輯個(gè)人信息、維護(hù)留言信息和系統(tǒng)設(shè)置等功能。留言采用推送的方式實(shí)現(xiàn)，使得其他用戶的留言能夠?qū)崟r(shí)地推送到移動(dòng)用戶終端。系統(tǒng)設(shè)置為用戶提供了一些個(gè)性化的客戶端設(shè)置功能，如是否允許推送、問題搜索范圍、關(guān)注的主題、是否允許通過姓名搜索到自己等。

3.2聚類算法

在該軟件系統(tǒng)中，互助關(guān)系包括3種：一是用戶主動(dòng)幫助別人，二是用戶被別人幫助，三是用戶直接互相幫助。

定義1：如果用戶A通過系統(tǒng)為用戶B提供了直接幫助，則B就是被A直接幫助過的用戶，記作B∈HO(A)，HO(A)表示A直接幫助過的所有用戶組成的集合；相應(yīng)地，A就是直接幫助過B的用戶，記作A∈HI(B)，HI(B)表示所有直接接受過A幫助的用戶組成的集合。

定義2：在某個(gè)主題S下，如果用戶A為用戶B提供了直接幫助，則B是A在該主題S下直接幫助過的用戶,記作B∈HO(A,S),HO(A,S)表示A在主題S下直接幫助過的所有用戶組成的集合；同樣，A∈HI(B,S)。根據(jù)定義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出發(fā)到A結(jié)束的A的S主題幫鏈稱為A的一個(gè)S主題朋友環(huán)，A的所有S主題朋友環(huán)上的用戶組成的集合稱為A的S主題朋友圈。

基于上述定義，朋友圈具有更強(qiáng)的主題特性和互助行為特征，一個(gè)用戶的朋友圈里的所有用戶都是自己直接或間接幫助過的用戶，這些用戶也是直接或間接幫助過自己的用戶。

在算法實(shí)現(xiàn)方面，采用深度搜索算法。具體的算法描述如下：

(1)從HO(A,S)中第一個(gè)節(jié)點(diǎn)V開始標(biāo)記為已搜索；

(2)將V進(jìn)棧；

(3)當(dāng)棧不空時(shí)，重復(fù)以下步驟：

①如果V=A，則把所有棧中元素標(biāo)記為A的朋友圈用戶，結(jié)束搜索，否則繼續(xù)搜索；

②從棧頂元素V的HO(V,S)中的下一個(gè)節(jié)點(diǎn)W開始繼續(xù)進(jìn)行深度搜索。

基于上述算法形成的朋友圈，隨著用戶的增加會(huì)不斷增大。因此，系統(tǒng)可通過設(shè)置不同的主題、子主題、地理位置、互助閾值等進(jìn)一步限制朋友圈的形成條件，以防止過多的用戶聚類到同一個(gè)朋友圈而造成臃腫，進(jìn)而使互助行為發(fā)生的效果降低。

4測(cè)試結(jié)果

將所設(shè)計(jì)和開發(fā)的系統(tǒng)移動(dòng)客戶端通過模擬器和真機(jī)進(jìn)行測(cè)試。真機(jī)采用的是華為榮耀3X，其操作系統(tǒng)為Android4.2，CPU為MKT 6592，機(jī)身內(nèi)存為2GB RAM+8GB ROM，網(wǎng)絡(luò)為WiFi、WCDM和GPRS。服務(wù)端運(yùn)行在新浪云平臺(tái)Sina App Engine(SAE)，采用Apache+Mysql服務(wù)。經(jīng)過實(shí)際測(cè)試，客戶端運(yùn)行良好。部分運(yùn)行界面如圖5所示。

圖5　移動(dòng)客戶端部分界面

5結(jié)語

本文設(shè)計(jì)了一款基于互助行為聚類的移動(dòng)

社交軟件，提出了一種基于互助行為的聚類算法。通過該聚類算法，用戶之間的朋友關(guān)系建立在實(shí)際的互助行為基礎(chǔ)之上，朋友圈內(nèi)的朋友具有更好的主題相關(guān)性。該軟件主要包括移動(dòng)客戶端和后臺(tái)服務(wù)端，移動(dòng)客戶端運(yùn)行于智能終端，服務(wù)端部署于新浪云平臺(tái)。經(jīng)測(cè)試，軟件運(yùn)行良好。

參考文獻(xiàn):

[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]陳季夢(mèng),陳佳俊,劉杰，等.基于結(jié)構(gòu)相似度的大規(guī)模社交網(wǎng)絡(luò)聚類算法[J].電子與信息學(xué)報(bào),2015,37(2):449-454.

[4]李敏,王曉聰.基于位置的社交網(wǎng)絡(luò)用戶簽到及相關(guān)行為研究[J].計(jì)算機(jī)科學(xué),2013,40(10):72-76.

[5]張延玲,劉金鵬,姜保慶.移動(dòng)對(duì)象子軌跡段分割與聚類算法[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(10):65-68.

[6]蘇孝強(qiáng),倪宏.一種基于空間相依性的移動(dòng)對(duì)象聚類算法[J].微計(jì)算機(jī)應(yīng)用,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]李倩倩,顧基發(fā).用戶行為驅(qū)動(dòng)的在線社交網(wǎng)絡(luò)建模[J].系統(tǒng)工程學(xué)報(bào),2015,30(1):9-15.

(責(zé)任編輯：張同學(xué))

收稿日期：2015—12—23

基金項(xiàng)目：河南省教育廳高等學(xué)校重點(diǎn)科研項(xiàng)目(15B520041)；河南省科技攻關(guān)項(xiàng)目(152102210150)

作者簡(jiǎn)介：劉安戰(zhàn)(1980—)，男，河南新鄉(xiāng)人，講師，碩士，主要研究方向?yàn)檐浖こ獭⒁苿?dòng)計(jì)算。

文章編號(hào)：1671-6906(2016)03-0090-05

中圖分類號(hào)：TP311

文獻(xiàn)標(biāo)志碼：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