網絡參與者見面概率的迭代估計方法

李永立,樊寧遠,林億民,吳 沖

(1.東北大學工商管理學院,遼寧沈陽110169;2.哈爾濱工業大學管理學院,黑龍江哈爾濱150001)

1 引 言

社會網絡構成了社會經濟生活的骨架,特別是在社會媒體平臺上,用戶之間構成的人際網絡成為了信息傳播的主要渠道[1];無獨有偶,在科學計量學領域,論文的作者構成合著網絡,成為完成一項科研工作重要的協作模式[2],以上列舉的兩個網絡都是社會網絡在生產生活中的具體體現.本文關注于社會網絡參與者見面的概率問題,該問題來源于對“有份無緣”現象的思考;也即:如果兩個人成為朋友對于雙方都有益,但如果雙方沒有見面的機會,朋友關系也不能建立.事實上,在社會媒體平臺上(如:微信、微博、Facebook等)以及合作者的選擇方面,“有份無緣”的現象比比皆是,這不利于提高用戶的交友體驗和增加科研的產出.本文旨在通過對網絡參與者見面概率的估計,找出“有份”但“無緣”的參與者,提高推薦的針對性,最終達到優化網絡產出的目標[3].本文的研究意義主要體現在兩個方面:宏觀上,本文有助于社會媒體平臺推薦合意的朋友,提高社會媒體平臺用戶對于平臺的滿意度和忠誠度,實現平臺的盈利增長;微觀上,個體依托于本文方法的推薦,有助于找到心儀的朋友或理想的合作者,實現個體利益的增加.

社會網絡中鏈接的建立,反映了參與個體的選擇偏好.而效用分析可以解釋這種偏好.在理性人假設下,參與者傾向于選擇使其效用水平最大的個體建立鏈接.為了刻畫個體間建立鏈接的福利水平,本文將引入效用分析的方法,通過考察建立鏈接后效用水平的變化對網絡參與個體的福利水平進行定量分析.這與既有的應用效用函數分析個體行為及文獻評價的研究相一致,比如:Wong等[4],Poelmans等[5],以及俞立平等[6]等.由于參與者的見面過程不易被觀察,既有的文獻通常都將網絡參與者見面的過程視為鏈路形成的一個中間環節,僅僅視為一類“黑箱問題”加以分析[7?9].為了估計出各個參與者見面的概率,找出“有份”但“無緣”的參與者,本文將可觀察到的網絡鏈接視為“顯狀態”,將不能觀察到的見面過程視為“隱狀態”,擬通過逐步迭代的方法,估計出“隱狀態”中網絡參與者見面的概率.

既有的社會網絡領域的研究往往關注于網絡的結構形成[10],社團結構[11]和節點相似性評價[12]等問題的研究,而關注網絡參與者見面概率的研究較少.由于網絡參與者的見面過程不是可以直接觀察的,對其估計的研究具有理論難度,是值得探索的研究方向.由此,本文將關注于網絡參與者見面概率的估計問題,將這一問題進行定量化和模型化.本文從建立網絡參與者的效用函數入手,通過對節點建立鏈接前后效用變化的度量,設計迭代算法用以推斷網絡參與者見面的概率.在效用函數的設計中,本文將網絡的結構效應引入效用函數,突出了研究的網絡背景;在對節點效用變化進行度量的分析中,將logistic回歸分析的思想引入對節點建立鏈接概率的估計,適應因變量為0-1變量的情形;并在迭代算法的提出中,引入隨機樣本,有效處理樣本可能存在的不平衡問題.基于一個數值算例的闡述和在真實數據集上的應用,本文展示方法的合理性和實用性,有助于深入解釋網絡鏈路形成的原因,并給出有針對性地推薦.

2 網絡參與者見面過程的效用分析模型

2.1 問題的提出

在社會網絡中,通常能夠收集到節點的屬性數據和節點間鏈接的情況,但是很難直接觀察到節點的見面過程,這一情形表述在圖1中.

圖1 個體i和j鏈路形成的示意圖Fig.1 Diagram of link formation between individual i and j

如圖1所示,如果觀察到兩個節點建立了鏈接,那么他們之間必然見過面,因此問題的重點是研究那些沒有形成鏈接的“節點對”,其中的兩個節點可能見過面,也可能沒見過面.以兩個代表性個體i和j鏈路形成的過程為例,如果兩者沒有見面的機會,他們一定不能形成鏈路;如果兩者見過面,則他們會基于各自的效用做出決策,也即與對方形成鏈接是否有助于自身效用的增加:如果是,則形成鏈路;如果不是,則不形成鏈路.在此過程中,涉及到“見面的狀態”,“決策的過程”和“可以觀察到的鏈路形成情況”三個組成部分.

進一步,記圖1中個體i和j見面的概率為pij,即為本文求解的目標變量;記lij為個體i和j鏈路形成的情況,則有lij=0表示兩者間沒有形成鏈接,若兩者形成了鏈接,則有lij=1.根據圖1所示,當lij=1時,必有pij=1,因為形成了鏈接,必然兩者見過面;特別地,對于lij=0的“節點對”,在效用分析的框架下,如果根據效用分析的結果,兩個個體應該以很大的概率值形成鏈接,如果實際上兩者并沒有形成鏈接,則推斷兩者沒有見過面的概率很高,這也是本文建模的基本出發點.

2.2 鏈接形成的效用分析模型

本節詳細闡述圖1中效用分析的過程.以代表性個體i為例,其效用函數為

其中被觀察到的網絡的鄰接矩陣記為L,用以反映網絡個體的鏈接情況;網絡個體的屬性矩陣記為A,用以反映可以獲得的網絡參與者的屬性信息,其中第s個個體的屬性向量記為As;θ為待估計的參數向量.

對于圖1中的鏈路形成過程,倘若代表性個體i和j獲得見面機會,則個體i建立與個體j的鏈接時,面臨的效用變化為

其中L+[lij=1]表示在原來網絡鏈接的情形下,增加個體i和個體j之間的鏈接.

根據式(2),如果個體i的效用增加,即ΔUi→j(L,A;θ)＞0時,個體i有向個體j建立鏈接的愿望.同理,對于個體j而言,其面臨的效用變化為

同樣,當建立鏈接有助于個體j的效用增加時,即ΔUj→i(L,A;θ)＞0時,個體j有向個體i建立鏈接的愿望.并且當兩者都有建立鏈接的愿望時,代表性個體i和j才能形成鏈接.

特別地,作為有限理性的網絡參與者,其對于自己效用的感知可能存在偏差及其它不可觀測的隨機干擾因素,為此令

其中εi和εj分別是代表性個體i和j對于效用感知的偏差.

根據Coles等[13]的研究,這類來自于不完全理性人的感知偏差往往滿足Type I的極值分布.從建模的角度說,引入隨機干擾因素讓模型更加接近決策的實際.與此同時,從方法的角度說,引入隨機干擾因素使得模型概率分析成為可能,這類似于線性回歸模型中對于隨機干擾因素的引入.事實上,由于鏈路是否存在恰恰是0-1變量的形式,這與logistic回歸因變量為分類變量相一致,這為在給出效用函數的具體形式下,推斷網絡參與者見面概率提供了模型基礎.

2.3 具體化的效用函數及回歸方程

考慮到本文的模型將應用于合著網絡中對合意的合作者進行挖掘,以下根據這一應用背景將具體化式(1)的效用函數.根據文獻[14]的觀點,“三度影響力是影響網絡參與者行為的主要因素”,即來自朋友(一度影響力),朋友的朋友(二度影響力),乃至朋友的朋友的朋友(三度影響力)都會對行為產生影響,并且發現這些影響力是逐漸遞減的關系.由此,本文在構建具體的效用函數時,考慮其中影響力較強的前兩度影響力,進而具體化的效用函數為

其中c是常數,n是網絡中個體的總數,‖·‖用以度量屬性之間的差異;具體地,作者的屬性用作者文章的關鍵詞及其頻數來度量.

以式(6)給出的具體形式的效用函數為基礎,根據式(2)和式(3)的關系,進一步推得個體i和個體j在建立鏈接的過程中,感知到的效用變化分別為

事實上,很難直接獲得以上兩式左端效用變化的具體數值;由此,對于式(7)或式(8)中的參數將不能通過以上兩式直接進行估計.但是,通過對網絡鏈接的觀察,可以獲得的符號;這是因為若個體i和個體j形成了鏈接,由2.2節可知,同時成立.這一問題的結構與logistic回歸問題的結構較為相似,即因變量為符號變量,進一步結合前面對隨機變量εi的分布假設,有

式(9)等價于

式(10)左邊即為的Logit變換,進而結合的具體形式,可得

類似地,針對個體j到個體i的鏈接形成過程,得到

式(11)和式(12)恰好為logistic回歸的基本方程,可以應用logistic回歸的最大似然估計技術對效用函數中的參數進行估計.考慮到本文所分析問題的結構特征,關鍵在于如何合理的估計該參數向量,并以此為基礎推斷網絡參與者見面的概率.

3 算法實現及算例

3.1 算法步驟

將模型中的參數通過實際數據的校準是進一步進行見面概率估計的基礎;但是,直接應用觀察到的全部數據對式(11)和式(12)進行參數估計將產生有偏的估計結果,這是因為logistic回歸針對那些見過面的樣本,參數估計才有效.具體地說,等式(11)和式(12)左邊對應的是可以觀察到的鏈接情況,表現為0-1變量,但是0-1變量的值為0的原因可能是由于沒有機會見面而造成的,這個因素是不能被效用分析所解釋的.由此,本文提出逐步迭代的方法解決該問題.具體地,該方法分為如下步驟:

步驟1對于被觀察到的已經建立鏈接的樣本,同時添加原樣本數一半數量的因變量為0的隨機樣本,構成一個新的樣本集(隨機樣本的含義是指自變量隨機生成,為取值范圍內的均勻分布),應用式(11)和式(12)進行logistic回歸分析,得到參數的初始估計值

步驟2應用這一初始估計值,對那些沒有建立鏈接的樣本進行估計,得出其經過決策過程應該建立鏈接的概率,記為

步驟3將建立鏈接概率小于50%的樣本納入估計樣本,這時全體樣本由已建立鏈接的樣本和建立鏈接概率小于50%的樣本構成,再應用式(11)和式(12)進行logistic回歸分析,得到更新后的參數估計值;

步驟4重復步驟2,步驟3,直到沒有新的鏈接概率低于50%的樣本出現;進行回歸方程的參數估計;

步驟5對那些沒有建立鏈接的“節點對”,應用步驟4得到的參數計算用度量其見面的概率.

在步驟1中,考慮到如果只用那些已經建立鏈接的樣本進行分析,因為這些樣本的因變量都為1,會存在樣本分布的不平衡問題,導致第一步得到的結果存在嚴重偏差,于是引入隨機樣本,使得算法得到的初始估計值偏差小一些,有助于減少迭代次數,提高算法效率;進一步,在步驟2中試圖增加估計的樣本使得參數的估計值更接近于無偏估計,于是用步驟1得到的參數估計結果,計算那些沒有建立鏈接的樣本潛在的鏈接概率,根據模型假設和邏輯分析,如果經過決策過程其潛在建立鏈接的概率很低,說明即便見面,也不會形成鏈接.步驟3中將概率低于50%的“節點對”視為曾見過面的樣本納入參數估計;步驟4重復以上的估計過程,直到各類樣本不再變化為止,由此得到了一個較好的參數估計結果;在步驟5中,應用最終得到的參數估計結果,計算那些未形成鏈接的“節點對”經歷決策過程形成鏈接的概率,注意到該值越大,對應的“節點對”沒有見面的概率就越大,于是用度量兩者見面的概率,并進行排序.

3.2 數值算例

考慮有五個節點的網絡如圖2所示,其中每個點的屬性值標記在各個點的旁邊.

圖2 算例中包含5個節點的網絡示意圖及其屬性值Fig.2 Network diagram and attribute values of the five nodes in the example

根據前面的算法步驟,則每一步的結果如下.

在步驟 1 中,根據圖 2 的鏈接情況,選擇“節點對”(1– 2),(1– 3),(2– 3),(3– 4)和(4– 5)為樣本,同時添加 5個因變量為0的隨機樣本.利用式(11)和絕對值度量節點之間的屬性差異進行logistic回歸估計,結果如表1所示.根據表1的結果,可以發現其參數的回歸估計值在0.10置信度下通過統計檢驗.

表1 參數的估計值及統計量Table 1 Estimators and statistics of the parameters

根據步驟2,應用表1可以計算出在決策過程中圖2中沒有形成鏈接的“節點對”建立鏈接的概率,結果如表2所示.

表2 未形成鏈接的“節點對”應建立鏈接的概率Table 2 The probability of forming a link between unlinked pairs

以“節點對”(1–4)為例,根據表1的參數估計值,當建立從節點1到4的鏈接時,節點1效用變化的方程為

進一步,算例中的節點差異‖·‖定義為絕對值,進而算得由此,根據式(9)得到節點1到節點4建立有向鏈接的概率為0.028 0,類似地得到節點4到節點1建立有向鏈接的概率為0.455 9,其兩者的乘積即為節點1和4之間建立鏈接的概率.同理可得表2中其它節點間的見面概率.

結合表2的結果,根據步驟3算出有四組“節點對”形成鏈接的概率小于0.5,將這四組“節點對”(1–4),(1–5),(2–5)和(3–5)納入估計樣本,修正參數估計的結果,得到logistic回歸方程的參數估計結果見表3.

表3 參數的估計值及統計量Table 3 Estimators and statistics of the parameters

進一步進行迭代,發現算法在該步收斂,即用于訓練的樣本不再變化,由表3的參數估計結果算得網絡上未形成鏈接的參與者見面的概率值及其排序,如表4所示.由此,根據表4的結果,將推薦(2–4)這一“節點對”見面,其見面將會建立相應的鏈接,有助于彼此效用的增加和網絡整體效用產出的增加.

表4 未形成鏈接的“節點對”見面的概率值及其排序Table 4 The meeting probability between the unlinked pairs and ranking

根據以上的步驟和算例可以發現,本文提出的逐步迭代方法,通過對效用函數的參數估計,逐步推斷不能直接被觀察到的網絡個體見面的概率.而在逐步迭代的每一步,應用的是logistic估計,所以從參數估計的角度說,該方法在估計的有效性上,繼承了logistic估計的特性,這是本文參數估計在理論上的依據.通過逐步迭代的過程,本文將網絡中可能見面的個體逐步加入到估計樣本中,逐步修正估計的參數,進而修正“節點對”間的見面概率,不斷更新用于分析的樣本,直到樣本不再變化,迭代過程停止.

4 方法應用

本文選取發表在www.arxiv.org上從1995–01–01～2003–06–30之間“高分子”物理領域的文獻,該數據集屬于一個開放的數據集,已被Newman[15]用于研究社會網絡的統計特性、社團特征以及鏈路預測等方面.獲取該數據的網絡地址為www-personal.umich.edu/mejn/netdata/,整個數據集包含了31 163名作者和他們發表的120 029篇論文,他們合著網絡的度分布如圖3所示.在本文計算出的合著網絡中,邊表示相連的兩位作者發生過合作關系,而沒有考慮合作的次數.為了突出研究的主體,本文關注節點度大于等于100的作者(意味著作者在統計區間內發表的論文中有不少于100名的合作者),滿足此條件的作者共計50名,其度分布由圖3中的小圖所示,以及鏈接情況如圖4所示.

進一步,根據2.3節的論述,本應用中網絡參與者個體的屬性取其發表文章的關鍵詞及關鍵詞的頻率.具體地,以代表性個體i和j為例,兩者的關鍵詞及其頻數和頻率分別由表5和表6所示.

表5和表6中的粗體字是個體重復的關鍵詞,將這些重復的關鍵詞構成一個集合并按順序編號,不失一般性地,令該集合有m個元素;進一步回顧式(8),屬性差異具體定義為

其中函數fi(r)表示集合中第r個重復的關鍵詞對于作者i的頻率,類似地可得fj(r)的含義.

圖3 全部樣本及遴選樣本的節點度分布Fig.3 Node degree distribution of the whole and the selected samples

圖4 遴選樣本合著者網絡的圖示Fig.4 Co-author network diagram of the selected samples

表5 個體i發表文章的關鍵詞及其頻數和頻率Table 5 Keywords in the papers of of individual i as well as keywords’frequency and rate

表6 個體j發表文章的關鍵詞及其頻數和頻率Table 6 Keywords in the papers of of individual j as well as keywords’frequency and rate

定義式(13)的一個特性在于當兩者重復的關鍵詞多時,兩者的屬性差異小.以給出的數據為例,經式(13)可以算得個體i和j的屬性差異為0.30.

進一步,根據本文3.1節的步驟,經四步后各個狀態的樣本不再變化,求得最終參數的統計信息以及網絡參與者見面概率的前5組“節點對”,分別由表7和表8所示.本文的計算主要在IBM SPSS Statistics 22上進行.

表7 參數的估計值及統計量Table 7 Estimators and Statistics of the parameters

表8 集中網絡參與者見面概率的前5對Table 8 The top 5 pairs according to meeting probability

表8中列出了最可能由于沒有見面機會而沒有形成鏈接的作者“節點對”.通過效用分析的結果,這些“節點對”形成鏈接后,將有助于彼此的效用增加,從宏觀上有助于整體的科研產出.經過以上分析,可以進一步考慮建立某種推送或推薦機制,使得表8中列出的作者有見面和合作的機會.

5 結束語

不同于絕大多數的社會網絡領域的既有研究,本文將研究視角關注于網絡參與者見面的概率問題,注意到網絡參與者見面是形成鏈接的前提.為解決網絡參與者見面的概率問題,本文引入了效用分析的方法,并在理論上將效用函數的估計問題與logistic回歸分析聯系起來,在深入分析網絡參與者鏈接形成過程的基礎上,提出了迭代估計算法,并在一個算例上進行方法的展示,在合著者網絡中對方法進行應用研究.結果表明本文提出的方法可以解決網絡參與者見面的概率估計問題.雖然本文將模型在情報文獻學領域做了一個簡單的應用,但是該模型依然有巨大的應用空間,特別是在電子商務、信息管理和市場營銷領域.期待進一步的研究在大量的真實數據集上對模型的實踐效能進行全面地評估和驗證.

[1]李倩倩,顧基發.用戶行為驅動的在線社交網絡建模.系統工程學報,2015,30(1):9–15.Li Q Q,Gu J F.Activity driven modeling of online social network.Journal of Systems Engineering,2015,30(1):9–15.(in Chinese)

[2]Chan K C,Chang C H,Chang Y.The network effects of publishing in finance.The North American Journal of Economics and Finance,2015,33(6):305–316.

[3]陳 冀,陳典發,宋 敏.復雜網絡結構下異質性銀行系統穩定性研究.系統工程學報,2014,29(2):171–181.Chen J,Chen D F,Song M.Heterogeneous bank system stability research under complex networks structure.Journal of Systems Engineering,2014,29(2):171–181.(in Chinese)

[4]Wong C Y,Goh K L.The sustainability of functionality development of science and technology:Papers and patents of emerging economies.Journal of Informetrics,2012,6(1):55–65.

[5]Poelmans E,Rousseau S.Factors determining authors’willingness to wait for editorial decisions from economic history journals.Scientometrics,2015,102(2):1347–1374.

[6]俞立平,張 全.期刊評價中兩類效用函數合成方法的本質研究.情報學報,2014,33(10):1077–1082.Yu L P,Zhang Q.Two methods for utility function synthesis in the evaluation of journals.Journal of the China Society for Scientific and Technical Information,2014,33(10):1077–1082.(in Chinese)

[7]Boucher V.Structural homophily.International Economic Review,2015,56(1):235–264.

[8]Leung M P.Two-step estimation of network-formation models with incomplete information.Journal of Econometrics,2015,188(1):182–195.

[9]Sauer N C,Kauffeld S.The ties of meeting leaders:A social network analysis.Psychology,2015,6(4):415–416.

[10]胡海波,劉 璇.在線社會網絡增長中的優先連接.系統工程學報,2014,29(3):289–298.Hu H B,Liu X.Preferential linking in the growth of online social networks.Journal of Systems Engineering,2014,29(3):289–298.(in Chinese)

[11]Li Y,Zhang G,Feng Y,et al.An entropy-based social network community detecting method and its application to scientometrics.Scientometrics,2015,102(1):1003–1017.

[12]李永立,吳 沖.基于圖模型和最優化的評價方法.系統工程學報,2013,28(3):403–409.Li Y L,Wu C.Inventing an evaluation method based on graph model and optimization.Journal of Systems Engineering,2013,28(3):403–409.(in Chinese)

[13]Coles S,Bawa J,Trenner L,et al.An Introduction to Statistical Modeling of Extreme Values.London:Springer,2001.

[14]Christakis N A,Fowler J H.Connected:The Surprising Power of Our Social Networks and How They Shape Our Lives.New York,NY:Little,Brown and Company,2009.

[15]Newman M E J.The structure of scientific collaboration networks.Proceedings of the National Academy of Sciences,2001,98(2):404–409.