趙天宸，朱曉民，王純

（1 北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100876；2 東信北郵信息技術(shù)有限公司，北京 100191）

彩印SNS的用戶親密度算法*

趙天宸1，2，朱曉民1，2，王純1，2

（1 北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100876；2 東信北郵信息技術(shù)有限公司，北京 100191）

在彩印業(yè)務(wù)SNS用戶親密度模型中，用戶的親密度計(jì)算是核心問題。社交網(wǎng)絡(luò)的核心價(jià)值就是再現(xiàn)用戶現(xiàn)實(shí)人際關(guān)系，如今多種多樣的社交網(wǎng)絡(luò)服務(wù)中對(duì)于用戶關(guān)系的展現(xiàn)大都是粗粒度的。本文以六度分割理論為理論基礎(chǔ)，結(jié)合彩印業(yè)務(wù)的特點(diǎn)，對(duì)SNS用戶關(guān)系建模分析，進(jìn)行用戶間的距離量化計(jì)算，展現(xiàn)SNS用戶的親密度，從而提高社交網(wǎng)絡(luò)服務(wù)的業(yè)務(wù)擴(kuò)展性，實(shí)現(xiàn)SNS用戶價(jià)值。

六度分割；彩印業(yè)務(wù)；親密度

在社交網(wǎng)絡(luò)發(fā)展如火如荼的今天，人們?cè)絹碓絻A向用新媒介進(jìn)行交往和對(duì)話，而不是傳統(tǒng)意義上的面對(duì)面交流。在社交網(wǎng)絡(luò)中，個(gè)人既是網(wǎng)絡(luò)的中心，又是一個(gè)節(jié)點(diǎn)。SNS(Social Networking Services)社交網(wǎng)絡(luò)的理論基礎(chǔ)是哈佛大學(xué)心理學(xué)教授StanleyMilgram 1967年創(chuàng)立的六度分割理論，即“你和任何一個(gè)陌生人之間所間隔的人不會(huì)超過6個(gè)，也就是說，最多通過6個(gè)人你就能夠認(rèn)識(shí)任何一個(gè)陌生人?！盨NS的主要功能就是為用戶提供通過互聯(lián)網(wǎng)所聯(lián)結(jié)的人際關(guān)系網(wǎng)絡(luò)，并幫助用戶通過其個(gè)人人際關(guān)系網(wǎng)絡(luò)實(shí)現(xiàn)其它方面要求。在聚合廣大相應(yīng)類型受眾后，增加自己所具有的固定用戶的用戶黏性，并對(duì)其提供精細(xì)化服務(wù)，從而得到這一部分用戶所具有的資源，并吸引越來越多的互聯(lián)網(wǎng)受眾群體，達(dá)到精細(xì)化服務(wù)的效果，從而擴(kuò)大規(guī)模，進(jìn)一步鞏固和發(fā)展自己，這就是SNS的發(fā)展模式。在這個(gè)過程中，用戶之間的網(wǎng)狀關(guān)系鏈的擴(kuò)張是一切的基礎(chǔ)。比起構(gòu)建新的關(guān)系而言，社交網(wǎng)絡(luò)服務(wù)在過去主要被用于強(qiáng)化與已熟識(shí)的人之間的關(guān)系，但近年來開始提供便捷地服務(wù)以方便與素不相識(shí)的陌生人建立關(guān)系網(wǎng)。

彩印業(yè)務(wù)是一項(xiàng)在用戶通話過程中附加信息傳遞的增值業(yè)務(wù)。在用戶進(jìn)行通話的過程中，由系統(tǒng)自動(dòng)將用戶預(yù)先設(shè)定好的彩印信息（笑話、心情、商情等）推送到對(duì)方手機(jī)上，使對(duì)方用戶在通話結(jié)束后看到彩印信息，以達(dá)到彰顯個(gè)性、分享心情、商情傳遞、營(yíng)銷推廣等目的。傳統(tǒng)增值業(yè)務(wù)用戶量很大，但業(yè)務(wù)活動(dòng)率不高。究其原因，是因?yàn)閭鹘y(tǒng)增值業(yè)務(wù)的系統(tǒng)僅停留在人機(jī)交互的層次。人們需要的是更有人情味的交互方式，更放松的方式去參與業(yè)務(wù)的二次活動(dòng)。同時(shí)，在互聯(lián)網(wǎng)已經(jīng)滲入到人們生活每個(gè)角落的今天，傳統(tǒng)電信增值業(yè)務(wù)需要滲透到互聯(lián)網(wǎng)領(lǐng)域中，開拓新的業(yè)務(wù)模式，以實(shí)現(xiàn)更好地為人們生活服務(wù)的同時(shí)業(yè)務(wù)本身價(jià)值的最大化。根據(jù)六度空間理論可知，人與人之間的距離是有限的，即是可度量的。本文根據(jù)用戶信息的各個(gè)維度，建立量化的用戶親密度模型，提出彩印SNS中用戶親密度的算法，更加細(xì)粒度地反映出用戶的現(xiàn)實(shí)親密度，提高業(yè)務(wù)可拓展性。

1 彩印業(yè)務(wù)用戶親密度模型

1.1 基本親密度

在彩印SNS中，用戶與聯(lián)系人間具有基本的現(xiàn)實(shí)關(guān)系，具體為家人、同學(xué)、朋友、同事、商務(wù)伙伴等。這些基本的現(xiàn)實(shí)關(guān)系構(gòu)成了用戶間的基本親密度B(F，N)，且Bfamily＞Bfriend＞Bschoolmate＞Bcolleague＞Bbusiness。同時(shí)具有多重關(guān)系的時(shí)候，基本親密度其中kj為Bj對(duì)應(yīng)的重要系數(shù)。互不相識(shí)的用戶間親密度B為0。

1.2 互動(dòng)親密度

用戶在社交網(wǎng)站上會(huì)進(jìn)行留言、邀請(qǐng)、分享等互動(dòng)活動(dòng)。這些互動(dòng)活動(dòng)的頻繁度可以真實(shí)地展示用戶之間的親密程度，這就是互動(dòng)親密度C(F，N)。

SNS網(wǎng)絡(luò)中用戶的關(guān)系可以通過有向帶權(quán)圖G（N，E，W）表示。N為網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，表示所有用戶；E為網(wǎng)絡(luò)中節(jié)點(diǎn)間的有向邊，表示用戶間的交流互動(dòng)行為，節(jié)點(diǎn)之間有邊表示用戶間有交流互動(dòng)行為，邊的弧頭指向表示交流行為的接受方；W為有向邊的權(quán)重，表示互動(dòng)行為的值，值越大表示互動(dòng)的越多。另一方面，由于交流是雙向的，一味單方面的交流行為不能代表用戶真的很親密，所以取兩節(jié)點(diǎn)間雙向權(quán)值的較小值E(X，Y)= min(W(X，Y)，W(Y，X))用以表示用戶的互動(dòng)親密度。

1.3 相似親密度

在SNS網(wǎng)絡(luò)中，有些沒有直接連接的節(jié)點(diǎn)也許會(huì)在現(xiàn)實(shí)中具有一定的親密度，比如校友、同行、老鄉(xiāng)等。這種親密度就是相似親密度，我們將其定義為S(F，N)。在彩印SNS中，影響S的屬性有年齡、所屬地、行業(yè)。本文視這3種屬性同等重要，所以S(F，N)=Sa（A，N）+Sl（L，N）+Sp（P，N）。

2 親密度計(jì)算

2.1 基本親密度設(shè)定

根據(jù)SNS中用戶現(xiàn)實(shí)關(guān)系，將用戶基本親密度分類為以下5種： Bfamily（X，Y）、Bfriend（X，Y）、Bschoolmate（X，Y）、Bcolleague（X，Y）、Bbusiness（X，Y）。分別取值為B（family）=1， B（friend）=0.8，B（schoolmate）=0.6，B（colleague）=0.4，B（business）=0.2。用戶間基本親密度B（X，Y）=k1×Bfamily（X，Y）+k2×Bfriend（X，Y）+k3×Bschoolmate（X，Y）+k4×Bcolleague（X，Y）+k5×Bbusiness（X，Y）），其中ki(i=1，2，3，4，5)取值為{當(dāng)X與Y具有對(duì)應(yīng)關(guān)系i時(shí)取1，否則取0}。

2.2 互動(dòng)親密度設(shè)定

用一張有向帶權(quán)圖圖1表示SNS網(wǎng)絡(luò)中用戶交流行為，權(quán)重表示互動(dòng)交流量，方向指向表示交流行為的接受方。

圖1 SNS用戶交流行為統(tǒng)計(jì)圖

然后取兩個(gè)節(jié)點(diǎn)間最小的權(quán)重作為新權(quán)重構(gòu)成新的無向帶權(quán)圖，如圖2所示，用以表示SNS網(wǎng)絡(luò)中用戶間的交流量。

圖2 SNS用戶間最小交流量統(tǒng)計(jì)圖

則兩用戶間的互動(dòng)親密度結(jié)果為：C（X，Y）=E（X，Y）/10（參數(shù)10的確定取決于彩印SNS網(wǎng)絡(luò)用戶的平均互動(dòng)交流量）。其中，E(X，Y)= min(W(X，Y)，W(Y，X))。

2.3 相似親密度設(shè)定

相似親密度取決于用戶3個(gè)屬性：年齡、所屬地、行業(yè)，S（X，Y）=Sa（X，Y）+Sl（X，Y）+Sp（X，Y）。

Sa（X，Y）取決于用戶的年齡差，Sa（X，Y）的取值為

Sl（X，Y）取決于用戶所屬地的共性大小，在彩印SNS中具體分為省份、城市、區(qū)縣鎮(zhèn)、小區(qū)/學(xué)校，取值為：

當(dāng)X和Y處于同一小區(qū)/學(xué)校時(shí)，Sl（X，Y）=0.8；

當(dāng)X和Y只同處于一個(gè)區(qū)縣鎮(zhèn)時(shí)，Sl（X，Y）=0.4；

當(dāng)X和Y只同處于一個(gè)城市時(shí)，Sl（X，Y）=0.2；

當(dāng)X和Y只同屬于一個(gè)省份時(shí)，Sl（X，Y）=0.1；

否則Sl（X，Y）=0。

Sp（X，Y）取決于用戶的行業(yè)/專業(yè)共性，取值為：

當(dāng)X和Y屬于同一行業(yè)/專業(yè)時(shí)，Sp（X，Y）=1；

否則，Sp（X，Y）=0。

2.4 綜合親密度計(jì)算

下面根據(jù)上述3種親密度計(jì)算兩個(gè)相連接節(jié)點(diǎn)用戶X和用戶Y的綜合親密度F（X，Y）=a1B（X，Y）+a2C（X，Y）+（1-a1-a2）S（X，Y）。其中，a1＞0，a2＞0，a1+a2≤1。a1和a2的確定為SNS網(wǎng)絡(luò)中用戶行為和基本屬性真實(shí)性及重要性所決定，在彩印SNS中，取a1為0.3，a2為0.5。

定義用戶間的距離L為親密度的倒數(shù)1/F，則網(wǎng)絡(luò)中任何兩個(gè)用戶間的距離都可以計(jì)算。算法如下：

For網(wǎng)絡(luò)中所有節(jié)點(diǎn)，計(jì)算其與相鄰節(jié)點(diǎn)的親密度，并計(jì)算其倒數(shù)作為距離的初始值，不相鄰的用戶間初始親密度為0，距離為無窮大；

End for

For網(wǎng)絡(luò)中節(jié)點(diǎn)A

For剩下的節(jié)點(diǎn)B

若A與B不直接連接，則通過Dijkstra算法計(jì)算A通過可能的路徑到達(dá)B的最短距離L(A，B)；則F（A，B）=1/L(A，B)；

End。

3 可行性和有效性分析

通過研究當(dāng)今主流社交網(wǎng)站的用戶關(guān)系模型，確立用戶基本信息內(nèi)容和活動(dòng)內(nèi)容，并針對(duì)調(diào)查各社交網(wǎng)站的用戶特性與服務(wù)類型，獲取用戶行為的規(guī)律。通過對(duì)數(shù)據(jù)挖掘中相關(guān)技術(shù)的研究，包括關(guān)聯(lián)規(guī)則和分類技術(shù)，建立合理科學(xué)的親密度模型和關(guān)聯(lián)算法。常見的關(guān)聯(lián)規(guī)則挖掘算法基于數(shù)據(jù)集中每個(gè)屬性都有相同的重要性，但在實(shí)際的應(yīng)用情況中，往往是某些屬性的重要度比普通屬性大、而有些屬性的重要性比普通屬性小，這就需要針對(duì)應(yīng)用討論各屬性權(quán)值的合理確立。通過對(duì)彩印業(yè)務(wù)的用戶活動(dòng)內(nèi)容的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行分析和預(yù)測(cè)，可以總結(jié)出彩印用戶的特性，基于特性可以把握用戶行為的規(guī)律。這樣可以為關(guān)聯(lián)規(guī)則中的屬性權(quán)值的確立提供合理的依據(jù)。

4 結(jié)論

本文提出了一種彩印SNS中用戶間關(guān)系親密度的量化模型和計(jì)算方法，算法基于帶權(quán)圖中用戶最短距離的Dijkstra算法。在計(jì)算用戶間最短距離之前，通過用戶間的初始親密度初始化用戶間的距離，然后進(jìn)行遍歷計(jì)算。

算法中各權(quán)重參數(shù)的取值通過對(duì)彩印業(yè)務(wù)現(xiàn)網(wǎng)用戶的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行分析確定，能有效展現(xiàn)用戶間真實(shí)的關(guān)系。

Algorithm of users’ friendliness in Caiyin SNS

ZHAO Tian-chen1,2, ZHU Xiao-min1,2, WANG Chun1,2
(1 State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China; 2 EBUPT Information Technology Co., Ltd., Beijing 100191, China)

The calculation of users’ friendliness in Caiyin social networking services is the key for the user friendliness model. SNS counts for revelation of persons’ relation in real life.However, the revelation between people in SNS may always be out of focus. This paper will introduce the model for SNS users’relation based on the users character in caiyin SNS, and will tell how to calculate the distance bewteen users in caiyin SNS based on the six degrees of separation,which will improve the value of the service.

six degrees of separation; the service of Caiyin; user friendliness

TN929.5

A

1008-5599（2012）10-0078-04

2012-09-16

國(guó)家自然科學(xué)基金（No. 61072057，61101119，61121001，60902051）；長(zhǎng)江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃資助（No. IRT1049）；國(guó)家科技重大專項(xiàng)（No. 2011ZX03002-001-01，移動(dòng)互聯(lián)網(wǎng)總體架構(gòu)研究）。