本站小編為你精心準備了基于行為模式的社會網絡論文參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

1基本定義和假設

1．1基本定義

本文所研究的用戶是針對于社會網絡中的用戶，用戶之間具有一定的交互行為，用戶總數表示為U．定義1．用戶A與用戶B在狀態、日志、照片、相冊等方面進行了一次交互操作，如用戶A對用戶B的狀態進行一次評論，即視為用戶A與用戶B發生一次交互，記為(A，B)．定義2．用戶與其它用戶的交互行為時間流稱為該用戶的行為模式．

1．2基本假設

直觀分析，社會網絡中用戶間存在一定交互行為，用戶交互時主要依賴于當前的交互，對于以前的交互特性并不敏感，也就是用戶間的交互行為滿足Markov性，所以我們假設用戶交互行為是一個Markov過程．由于用戶在長期行為中會形成穩定的行為習慣和偏好，所以用戶行為具有相對穩定性，經過較長一段時間后，用戶的行為模式將趨于穩定狀態，也就是用戶交互行為的Markov隨機過程可以收斂．用戶行為Markov模型能夠描述用戶內在的特性．采用用戶行為Markov模型進行聚類基于如下假設:假設:用戶行為具有偏好性，不同用戶在行為模式上存在一定差異，用戶間行為模式并不完全相同，但若干用戶間行為模式會存在一定相似性，這些用戶相較于其他用戶行為模式相似程度較高，存在一定相關性，相反存在若干用戶間相似程度較低．

2基于行為模式的社會網絡用戶譜聚類算法

本文提出一種基于行為模式的社會網絡用戶譜聚類算法(SpectralClusteringAlgorithmforUserBehaviorPatterns，SCBP)．SCBP算法主要包含2個階段，第一階段建立用戶行為Markov模型，學習相應參數;第二階段對用戶行為模型進行譜聚類，獲得用戶劃分結果．

2．1社會網絡用戶行為模型

SCBP方法使用一階齊次Markov模型對社會網絡用戶行為進行建模，將Markov模型的狀態與用戶間的交互行為相對應．在確定Markov模型的狀態時，主要有以下3步:1)獲取每個用戶交互行為數據．設用戶ui的交互行為數據為B=(d1，d2，…，db)，它是對用戶ui與其它用戶的歷史交互行為進行預處理后得到交互行為流，其長度為b，其中di表示按時間順序產生的第i個與用戶ui發生交互行為的用戶．2)提取交互行為數據流B中互不相同的用戶，設B中互不相同的用戶有N個(N≤b)，分別記為^d1，^d2，…，^dN，并計算這些用戶在B中出現的頻率．設第i個用戶^d2在B中的出現頻率。3)給定頻率閾值η，對于^d1，^d2，…，^db中出現頻率大于或等于頻率閾值η的用戶形成Markov模型的狀態．設在B中出現頻率大于或等于頻率閾值η的用戶共有S個．

2．1．1學習一步轉移矩陣在學習一步轉移矩陣時，采用極大似然估計法學習相關參數．首先，依據用戶行為Markov模型的狀態將交互行為序列中所有的交互行為對應為相應的狀態，獲得用戶的狀態序列．其次，依據用戶的狀態序列學習各個狀態間的轉移次數及轉移概率，從而得到一步轉移矩陣．一步轉移矩陣的學習算法表1所示．

2．1．2學習收斂后的Markov分布在學習收斂后的Markov分布時，需要獲得用戶的一步轉移矩陣和初始Markov分布．我們采用差值法判斷Markov分布是否達到收斂，計算當前Markov分布與之前一次Mark-ov分布的差值，并將所得差值與規定閾值ε進行比較，若所得差值小于或等于規定閾值，說明Markov分布已經達到收斂，此時Markov分布即為收斂后的Markov分布．在初始Markov分布的選擇上，可以選擇所有狀態均為同一概率的初始分布，也可依據已有的先驗知識，對不同狀態分配不同初始概率，以此作為初始分布．收斂后Markov分布的學習算法如表2所示，通過differentof函數計算當前Markov分布與之前一次Markov分布的差值，并將所得差值與閾值ε比較．

2．1．3學習收斂后的n步轉移矩陣在學習收斂后的n步轉移矩陣時，需要輸入用戶的一步轉移矩陣和誤差閾值ε．為了加快算法執行，采用迭代次數作為算法退出條件．通過不斷迭代計算新的n步轉移矩陣，直至達到n步轉移矩陣穩定或者達到迭代次數，獲得收斂后的n步轉移矩陣．收斂后n步轉移矩陣的學習算法如表3所示，依據一步轉移矩陣和當前n步轉移矩陣計算新的即下一步n步轉移矩陣，然后依據isconvergent函數判斷相鄰兩次n步轉移矩陣差值，若所得差值小于閾值ε，則停止迭代．

2．2SCBP聚類算法

通過建立用戶行為Markov模型，我們對每個用戶的行為模式構建一步轉移矩陣、收斂后Markov模型和收斂后n步轉移矩陣3種形式化表達，在3種表達基礎上，利用譜聚類思想，構建了面向用戶行為Markov模型的譜聚類(SCBP)算法．SCBP聚類算法的輸入是對象間的相似度矩陣，所以需要定義一步轉移矩陣、收斂后Markov分布和收斂后n步轉移矩陣對應的相似度矩陣．我們分別采用矩陣L2范數和KL散度定義一步轉移矩陣、收斂后n步轉移矩陣和收斂后Markov分布基礎上的用戶行為相似度．根據差值矩陣的L2范數和Markov分布的KL散度，我們定義用戶p與用戶q的相似度，給定用戶p和用戶q的一步轉移矩陣或者n步轉移矩陣，則定義用戶p與用戶q的轉移矩陣相似度為:

3實驗與結果分析

3．1實驗設計與評價指標

實驗數據分別采用人人網(Renren)和Facebook用戶的行為數據集，人人網是中國最大、最具影響力的SNS網站．而Facebook為國外知名社交網站，具有龐大的用戶數量．人人網數據集包含了435名用戶在三年間的活動記錄，預處理得到用戶間交互行為信息，包含相冊交互數據6613條，日志交互數據2921條，照片交互數據130591條，狀態交互數據557963條．Facebook數據集為新奧爾良網絡數據集1．該數據集包含45813個用戶，但其中很多用戶的交互行為較少，我們對其中的交互次數大于30的用戶進行篩選，選擇出2000個用戶作為實驗數據集．由于SCBP后期采用了KMeans聚類，所以我們采用KNN作為比較方法，KNN是帶監督的學習方法，我們從人人網數據中選擇行為模式差異較大的50個用戶進行標注，分成5類，作為初始學習類別．對于Facebook數據集，則選擇行為模式差異較大的50個用戶分成5類作為初始分類點．我們設計了2組實驗:1)精確聚類結果比較，聚類結果與人工標注結果對比．2)無標注聚類結果比較．將所有用戶采用不同聚類方法進行聚類，然后分析各聚類方法結果的合理性．我們采用指標F值和D值對比聚類效果．F值和D值是衡量聚類效果的常見指標．聚類結果評價指標F值和D值的計算方法．1)F-Value(F值)，也稱為聚類密集性，F-value的計算方法如下。其中ci是類i的中心，cj是類j的中心，D值代表類與類之間的差異程度，D值越大表示類與類之間的距離值越大，類之間越分離，聚類效果越好．

3．2實驗結果與比較

3．2．1精確聚類結果比較本文對50名人人網用戶根據行為特征進行人工標注，得到人工聚類結果．然后根據一步轉移矩陣(One)、收斂后Markov分布(M)和收斂后n步轉移矩陣(n)進行不同度量下聚類，得到SCBP和KNN的聚類結果．通過將各個聚類對象得出的結果與人工標注的分類結果進行對比，計算各個聚類的精度(Precision，P)和召回率(Recall，R)．不同度量、不同方法的精度和召回率如圖1所示．從圖1上可以看出:1)SCBP聚類的精度和召回率均在0．8以上，相較于KNN，SCBP聚類的精度和召回率明顯更高，更加符合依據用戶行為劃分準則的結果．兩種算法在收斂后Markov分布上的差異較大;2)SCBP和KNN使用收斂后的Markov分布聚類的精度和召回率均稍高于使用一步轉移矩陣和收斂后n步轉移矩陣進行聚類，說明采用收斂后Markov分布進行聚類更有效;3)SCBP聚類算法在三種度量上所得的精度和召回率差異相對較小，且SCBP聚類算法中所得的精度和召回率相比KNN算法中的結果均更高．由此可見SCBP聚類算法能夠適應不同的聚類基礎，在實際應用中具有較好的適應性．

3．2．2人人網無標注聚類結果比較我們將所有用戶采用不同聚類方法進行聚類，聚類結果的D值和F值對比分析結果如下頁圖2所示．從圖上可以看出:1)對比三種聚類度量下的F值和D值可以看出，無論是KNN還是SCBP，使用收斂后Markov分布進行聚類的F值均小于使用一步轉移矩陣和收斂后n步轉移矩陣聚類的F值，并且使用收斂后Markov分布進行聚類的D值均大于使用一步轉移矩陣和收斂后n步轉移矩陣聚類的D值．這個結果與50個用戶上的聚類結果一致，說明采用收斂后Markov分布進行聚類最合理;2)SCBP聚類中使用收斂后的Markov分布相較于使用一步轉移矩陣和收斂后n步轉移矩陣聚類的F值下降很大，而D值保持較高值，說明SCBP聚類結果中每個類內部成員更為緊湊，并且類與類之間的差異更大．這個結果與50個用戶上的聚類結果也一致，說明SCBP聚類算法能夠適應不同的度量;3)對比SCBP聚類和KNN方法的F值和D值，SCBP聚類的F值均小于KNN方法的F值，并且SCBP聚類的D值均大于KNN方法的D值，即SCBP聚類相較于KNN方法，每個類內部成員更為緊湊，并且類與類之間的差異更大．通過對比兩種聚類方法的F值和D值，可以明顯得出SCBP聚類效果優于KNN方法．

3．2．3Facebook數據集實驗結果分析由于Facebook數據集的用戶沒有個人信息，難以準確判別用戶關系，所以沒有進行人工分類，直接對其進行聚類．根據人人網數據集上的實驗結果，可以知道基于收斂后Markov分布上的聚類結果表現較好，所以我們在收斂后Markov分布上進行SCBP聚類和KNN方法，然后分析結果．SCBP聚類和KNN方法的F值和D值結果如圖3所示．從圖3可以看出，使用收斂后的Markov分布，SCBP在Facebook數據集上的F值和KNN方法差異較小，SCBP略低于KNN．在表示聚類不同簇間差異性的D值上，SCBP卻明顯高于KNN．實驗結果說明SCBP聚類結果中每個類內部成員緊湊，并且類與類之間的差異程度很高，類之間的區分度大．由于Facebook數據集內的用戶間交互存在一定的偶然性，一個聚類簇內的用戶在行為上具有一致性，不同簇間的差異性越高，說明能夠區分不同行為特征的用戶群．相較于KNN方法，SCBP聚類方法不同簇中的用戶在行為模式上差別較大，使不同類別的用戶得到了較好、較為準確的劃分，在一定程度上減少了誤分類的情況，提高了用戶劃分準確度．同時，也說明SCBP方法能夠滿足社會網絡上具有一定噪聲和隨機性的用戶聚類，這對于發現用戶興趣、用戶推薦、社區挖掘等具有重要的價值．

4結論與總結

本文提出了基于行為模式的社會網絡用戶譜聚類方法．本文聚類方法的效果優于傳統聚類方法，而收斂后Markov分布的聚類效果優于一步轉移矩陣的聚類效果．基于行為的用戶聚類可應用于個性化推薦等領域，從而為用戶提供更優質的社交服務．在未來工作中，考慮將不同聚類方法和聚類對象整合，進行提升處理．同時，在對用戶進行聚類時，嘗試融入用戶的基本屬性信息，以補充用戶行為信息中缺失的因素，以保證聚類結果更加準確．

作者：韓忠明張晨李斌莫倩單位：北京工商大學計算機與信息工程學院