趙天宸，朱曉民，王純

（1 北京郵電大學網絡與交換技術國家重點實驗室，北京 100876；2 東信北郵信息技術有限公司，北京 100191）

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

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

（1 北京郵電大學網絡與交換技術國家重點實驗室，北京 100876；2 東信北郵信息技術有限公司，北京 100191）

在彩印業(yè)務SNS用戶親密度模型中，用戶的親密度計算是核心問題。社交網絡的核心價值就是再現用戶現實人際關系，如今多種多樣的社交網絡服務中對于用戶關系的展現大都是粗粒度的。本文以六度分割理論為理論基礎，結合彩印業(yè)務的特點，對SNS用戶關系建模分析，進行用戶間的距離量化計算，展現SNS用戶的親密度，從而提高社交網絡服務的業(yè)務擴展性，實現SNS用戶價值。

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

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

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

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

1.1 基本親密度

在彩印SNS中，用戶與聯(lián)系人間具有基本的現實關系，具體為家人、同學、朋友、同事、商務伙伴等。這些基本的現實關系構成了用戶間的基本親密度B(F，N)，且Bfamily＞Bfriend＞Bschoolmate＞Bcolleague＞Bbusiness。同時具有多重關系的時候，基本親密度其中kj為Bj對應的重要系數?；ゲ幌嘧R的用戶間親密度B為0。

1.2 互動親密度

用戶在社交網站上會進行留言、邀請、分享等互動活動。這些互動活動的頻繁度可以真實地展示用戶之間的親密程度，這就是互動親密度C(F，N)。

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

1.3 相似親密度

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

2 親密度計算

2.1 基本親密度設定

根據SNS中用戶現實關系，將用戶基本親密度分類為以下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)取值為{當X與Y具有對應關系i時取1，否則取0}。

2.2 互動親密度設定

用一張有向帶權圖圖1表示SNS網絡中用戶交流行為，權重表示互動交流量，方向指向表示交流行為的接受方。

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

然后取兩個節(jié)點間最小的權重作為新權重構成新的無向帶權圖，如圖2所示，用以表示SNS網絡中用戶間的交流量。

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

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

2.3 相似親密度設定

相似親密度取決于用戶3個屬性：年齡、所屬地、行業(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ū)/學校，取值為：

當X和Y處于同一小區(qū)/學校時，Sl（X，Y）=0.8；

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

當X和Y只同處于一個城市時，Sl（X，Y）=0.2；

當X和Y只同屬于一個省份時，Sl（X，Y）=0.1；

否則Sl（X，Y）=0。

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

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

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

2.4 綜合親密度計算

下面根據上述3種親密度計算兩個相連接節(jié)點用戶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網絡中用戶行為和基本屬性真實性及重要性所決定，在彩印SNS中，取a1為0.3，a2為0.5。

定義用戶間的距離L為親密度的倒數1/F，則網絡中任何兩個用戶間的距離都可以計算。算法如下：

For網絡中所有節(jié)點，計算其與相鄰節(jié)點的親密度，并計算其倒數作為距離的初始值，不相鄰的用戶間初始親密度為0，距離為無窮大；

End for

For網絡中節(jié)點A

For剩下的節(jié)點B

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

End。

3 可行性和有效性分析

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

4 結論

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

算法中各權重參數的取值通過對彩印業(yè)務現網用戶的統(tǒng)計數據進行分析確定，能有效展現用戶間真實的關系。

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

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