轉載請註明出處：

每週一篇機器學習論文筆記?

zhuanlan.zhihu.com圖標

論文來源：WWW 2018

論文下載：Understanding and Predicting Delay in Reciprocal Relations

論文作者： Junking Li、 Jillian Tang、 Jilin Wang、 Yali Wan、 Yi Chang、 Huan Liu

註：以下內容僅個人理解，如有錯誤還請指正~

ABSTRACT

有向社交網路中雙向關係的形成具有時間延遲，瞭解延遲可以更好的瞭解動態社交網路的基本機制，同時可以應用在推薦、營銷等方面。本文作者研究了Tumblr有向的社交網路，對延遲的模式進行了總結，並利用這些總結設計了一個預測雙向關係延遲的框架。

INTRODUCTION

背景：

  1. 社交關係可以粗略的分為雙向的（reciprocal）和單向的（parasocial）。單向的社交關係是指用戶A關注了用戶B，而用戶B沒有關注用戶A。雙向的社交關係則是指用戶A和用戶B相互關注。
  2. 在Twitter和Tumblr這樣的有向社交網路中，雙向的社交形式顯示了用戶追隨形成相互聯繫的傾向。

動機：

  1. 調查雙向社交關係的形成和辨別雙、單向社交關係的差異有助於深入瞭解用戶行為和社交網路的動態機制。可以應用在朋友推薦、突發預測、信息傳播和病毒式營銷等方面。
  2. 雙向社交關係的形成存在時間延長，雙向關係中的延遲可以幫助解釋動態網路是如何演變和發展的，且延遲的時間長度可以作為衡量動態網路中用戶之間親密度的指標。

本文作者主要對雙向關係的時間延遲進行調查，主要目標是回答以下兩個問題：

  1. 時間延遲是否遵循某些模式？
  2. 這些模式如何幫助自動預測雙向關係的延遲？

對於問題1，作者從時間和結果角度有如下理解總結：

  1. 時間角度：a延遲受到用戶加入社交網路的時間以及雙向關係開始時他們在網路中的時間的影響；b延遲呈現每週模式，當雙向關係開始在週末時時延較短；c來自同一用戶的兩個連續相互關係的延遲不一定是相關的，即上一延遲不是同一用戶當前延遲的良好估計值。
  2. 結構角度：a延遲與用戶的入度（indegrees）和出度（out degrees）有關，即高入度的用戶傾向於更快的獲得關注，而更慢的關注回去，高出度的用戶傾向於更快的關注別人，而別人更慢的關注回來。b共享大量關注者與被關注者的用戶之間的延遲比沒有太多共同點的用戶之間延遲短。

對於問題2，作者提出了一個可以自動預測雙向關係延遲的框架。

DATA

作者在Tumblr平臺上進行研究，Tumblr是一個有向的社交網路。使用的數據詳情如下表：

註：時間粒度為一天，t=0表示開始日期（2007.10.31），t=2093表示結束日期（2013.7.24）

Tumblr網路的演變模式如下：

圖一表示Tumblr網路正在逐漸變得密集，是廣泛認知的動態網路模式。

圖二進一步的表明Tumblr網路是一個典型的具有代表性的有向社交網路。

雙向關係延遲的分佈：

  1. 雙向關係延遲的定義：用戶A在時間t1關注用戶B，用戶B在時間t2關注用戶A，則延遲為t2-t1.
  2. 根據定義從Tumblr網路得到446，116，001的雙向關係，如下圖：

由圖可知，延遲遵循冪具有指數截止的冪律分佈，這意味著冪律法則適用於短暫的延遲，對於長時間的延遲會呈指數下降，主要原因在於開始的時間接近數據集結束的時間的雙向關係尚未完全觀察到，這種現象可以有生存分析中的右刪失問題來解釋。

ANALYSIS ON THE TIME DELAY IN RECIPROCAL RELATIONS

相關定義：

  1. 每個延遲元組： <u,v,t_1,t_2,t_2-t_1>表示源用戶u在時間 t_1 時關注目標用戶v，目標用戶v在時間 t_2 關注回源用戶u，雙向延遲為 t_2-t_1 ，且 t_1leq t_2。

Temporal Analysis：

1. 用戶加入的時間的影響？畫出了用戶加入時間與平均延遲的關係圖如下：

由圖可知平均延遲隨著用戶加入時間的增加而逐漸減少。

2. 每週延遲模式：在不同類型的用戶行為中觀察到每週模式，下圖展示了每週幾的平均延遲量和雙向關係完成量。

由圖（a）可知，週六日開始的平均延遲較短，週四的平均延遲最長。由圖（b）可知，週末比平時完成更多的雙向關係，所以週末開始的雙向關係可能會在0或1天內完成。

3. 順序模式：對於每個用戶，調查當前延遲的延長時間和先前k次延遲的平均值之間的平均絕對誤差（MAE）和均方根誤差（RMSE），其中k依次取值1，2，3，4，5，6，7，8.

註：將一個用戶在時間線中的關注回來的行為視為一個順序。

由圖可知，當k值逐漸增加，預測誤差趨於相應減小，即前一段時期的平均延遲比前一個延遲預測效果更好，當前行為與前一次行為之間的強相關不一定適用於雙向關係的延遲。

進一步的研究發現：

  1. 用戶趨向於同時關注他們的最近和最早關注者；
  2. 用戶不用遵循初始命令來完成雙向關係。

Network Structural Analysis

1. 入度和出度的影響：社交網路中的名人趨向於有更多的關注者和普通用戶和活躍用戶趨向於去關注更多的人。用戶的入度表示他們的社會地位，用戶的出度表示他們的社交活動。根據入度和出度對用戶進行如下分類：

首先展示源用戶和目標用戶關於入度的平均延遲，如下圖：

由圖可知：

  1. （a）隨著源用戶入度的增加，平均延遲變得更短，即名人發起的關注獲得關注回來的延遲比普通用戶要短。
  2. （b）隨著目標用戶入度的增加，平均延遲變得更長，即關註名人的普通用戶通常名人關注回來需要更長的時間。

總結：作為源用戶，更高的入度意味著更短的延遲；作為目標用戶，更高的入度意味著更長的延遲。

源用戶和目標用戶關於出度的平均延遲，如下圖：

高出度通常意味著用戶更活躍和擁有更高的知名度，由圖可知，作為源用戶，更高的出度意味著更短的延遲，作為目標用戶，更高的出度意味著更長的延遲。

2. 結構相似性的影響：

研究源用戶和目標用戶不同的共同關注者數量和共同追隨者（被關注）數量對延遲的影響，如下圖：

由圖可知，隨著兩個普通用戶的結構相似性增加，平均延遲趨於下降。社交同質性（social homophile）表明，類似的用戶可能會建立雙向關係。社交同質性表明類似用戶建立雙向關係的延遲可能較短。

DELAY PREDICTION IN RECIPROCAL RELATIONS

對於每個雙向關係 <u,v,t_1,?,?-t_1> 其中 ? 表示想要預測的關注回來的時間，提取時序和結構信息。

延遲預測問題的表述：給定一個特徵矩陣 Xin R^{n imes d} ,其中 n 是訓練的雙向關係數量，對應的延遲向量 yin R^n ,本文的目標是學習一個將 X 映射到 y 回歸模型 f 。

The Proposed Delay Prediction Framework

建立的模型要同時兼顧雙向關係的共同特徵和個性化特徵。

相關定義：

  1. X=[X_1,X_2,...,X_n]^T(X_iin R^d, i=1,...,n) 是 n 個雙向關係的集合，每個雙向關係對應 <u,v,t_1,t_2,t_2-t_1> ，其中 u 是源用戶， v 是目標用戶， t_1 是初始時間， t_2 是完成時間， t_2-t_1 是延遲。
  2. 假設 K 是目標用戶的總數量，通常 Kleq n .
  3. Ain {0,1}^{n imes n} ，如果用戶 X_i 和用戶 X_j 的目標用戶相同，則A_{i,j}=1 ，否則 A_{i,j}=0。

假設每個雙向關係 X_i 與其相應的延遲 y_i 之間存在一個通用的回歸參數全局權重 W，首先用嶺回歸（ ridge regression ）模型來近似所有雙向關係延遲的共同特徵，如下：

其中 Win R^d 是回歸參數全局權重，正則項可以防止模型過擬合。

假設每個雙向關係 X_i 雙向行為的個性化特徵由一個局部權重表示，則延遲預測模型更新為：

考慮結構相似性，使用network lasso penalization term來迫使兩個相似用戶的局部權重接近：

引入network lasso penalization term的優點：

  1. l_2 範式使兩個相似用戶的局部變數更加接近，如果對應的 A_{i,j}=1 則激勵他們完全一樣。
  2. l_2 範式使學習更加準確。

整合以上公式，最後獲得的雙向關係延遲預測框架（ delay prediction

in reciprocal relations ，DPRR ）的目標函數如下：

其中 eta 是控制所有局部權重的影響，如果 eta ightarrowinfty 則所有局部權重趨向於達成共識解，即 forall i,j 有 W_i^` = W_j^` ；如果 eta ightarrow0 則消除了結構相似性，每個局部權重單獨學習。

為新的雙向關係進行延遲預測，主要分為兩種情況：

  1. 目標用戶在訓練集中不存在雙向關係，就只用全局權重進行預測，即 X_k^TW ；
  2. 目標用戶在訓練集中存在雙向關係，就由全局權重和局部權重進行預測，局部權重如下：

The Optimization Algorithm

目標函數主要在於全局權重和局部權重的求解，這裡使用交替方向乘法器（ Alternating Direction Method of Multipliers，ADMM）進行求解。添加一些輔助變數，重寫式（5）如下：

其中輔助變數 Z_{i,j}(j=1,...,n) 是局部權重 W_i^` 的副本。

可通過如下ADMM問題求解

其中 ho>0 是懲罰項， u 是對偶變數。

更新 a ：

更新 W ：

更新 Z :

更新 u ：

EXPERIMENTS

對比演算法：

實驗結果：

由圖可知提出的模型優於所有的對比演算法。

總結

這篇論文從側面印證了社交網路中全局特徵和個性化特徵的重要性，結合先前看的論文，個人感覺在有向社交網路的各種問題研究中考慮全局特徵和個性化特徵的效果都會更好，當然作者目標函數的求解及優化確實很厲害！


推薦閱讀：
相关文章