一種新的模糊社交網絡中心性分析方法

袁國強, 徐建民, 劉明艷

(1. 河北大學 管理學院, 河北 保定 071002;2. 河北金融學院 基礎部, 河北 保定 071051;3. 河北大學 網絡空間安全與計算機學院, 河北 保定 071002)

1 背景介紹

近年來,國外的Facebook、Twitter以及國內的新浪、騰訊和網易微博等在線社交網絡為在線用戶及時發布和共享有關日常生活、教育、新聞消息和重大事件等各種信息提供了重要的在線交流平臺.研究社交網絡中用戶的各種交互行為對于分析社交網絡具有極其重要的作用,因此,有效合理分析用戶間的各種交互行為數據并確定用戶的中心性地位已經逐漸成為當前社交網絡分析研究中的熱點問題.

社交網絡中心性分析問題一直是社交網絡研究中的重要問題之一.在經典的社會網絡研究中,一般采用確定性的圖論方法對網絡進行建模,圖論模型中的結點代表用戶,邊代表用戶之間的連接.一些學者已經采用點度中心性、緊密度中心性、介數中心性和特征向量中心性等方法[1-2]研究社交網絡的拓撲結構[3-4].另外,通過這些經典方法不但可以研究社交網絡特征,也可用于部分算法的研究.2002年,Girvan等[5]基于介數中心性設計了一種尋找社交網絡社區邊界的搜索算法.2013年,Badie等[6]利用緊密度中心性發展了一種能夠檢測復雜社交網絡中重疊和非重疊社區結構的新算法.在上述經典的社交網絡分析研究中,眾多學者主要關注了網絡的拓撲結構,并且這種由確定性圖論方法得到的研究成果在一定程度上淡化了用戶間交互行為所帶來的模糊關系,然而,這樣的模糊關系在很大程度上會對網絡的中心性研究帶來很大的影響,尤其當前的社交網絡不同于以往的社會網絡,由于用戶的在線活動一般具有不可預測性、不確定性和時間多變性等特點,因此使用確定性圖論方法建立的模型無法有效合理分析大多數的現實社交網絡問題.基于以上分析,為了處理當前社交網絡中由用戶交互行為和時間變化產生的部分不穩定性因素,本文將采用模糊集理論來對社交網絡中的用戶行為進行分析和建模.自從1965年Zadeh[7]首次提出模糊集的概念以來,許多學者在管理科學[8]、金融工程[9]、網絡分析[10]和生物醫學[11]等諸多領域運用模糊方法進行了大量的研究工作,并取得了可喜的成果.正是由于模糊方法在現代科學研究中的廣泛應用,從而也使得模糊社交網絡中心性分析問題的研究工作得到了很好的發展.廖麗平等[12]基于模糊方法定義了模糊結點中心度、模糊緊密中心度和模糊間距中心度等概念.岳振軍等[13]提出了一種新的由自然語言表述的模糊關系社會網絡,并研究了其中心性分析問題.Hu等[14]利用模糊方法討論了有向社交網絡中的點度中心性和接近中心性問題.Lu等[15]對于人際空間關系問題建立了一類模糊社交網絡的中心性分析模型.2018年,Wu等[16]利用區間二型模糊集理論解決了復雜和不確定社交網絡中的大規模群決策問題.鑒于上述模糊社交網絡中心性問題的研究,現有文獻中模糊結點度均采用了該點連接邊的隸屬度求和方法,該方法主要源于確定性社交網絡中心性分析中點度中心性的計算方法,主要目的是利用與結點相連接結點的數量來確定結點的中心性.然而,當社交網絡中用戶間邊的權重設置為隸屬度仍沿用確定性圖論中的中心性確定方法,就會顯得與現實存在一定偏差,原因在于簡單隸屬度求和有時并不能完全代表該結點在模糊社交網絡中的中心地位.

為了進一步尋求更加有效的結點中心性的度量方法,本文將采用可信性理論對社交網絡的結點中心性進行分析建模.可信性函數是Liu等[17]在2002年基于可能性測度提出的一類具有自對偶性質的函數.近十幾年來,可信性理論不但有效豐富了模糊集理論,而且已經在經濟、管理、工程和生產等各個領域得到了廣泛應用[18-21],尤其是2006年高曉沨[22]在碩士論文中基于可信性理論研究了幾類新的可靠性網絡的拓撲優化模型.與文獻[22]不同的是,本文主要工作在可信性理論基礎上建立一種新的模糊社交網絡中心性分析模型.

2 基本概念

美國控制論學家Zadeh[7]利用隸屬函數首次提出模糊集的概念.隨著模糊集理論的發展,Zadeh[23]進一步提出了可能性測度用來度量模糊事件的大小.在過去的幾十年中,可能性理論已經在模糊決策、模糊關系和模糊控制等領域得到了廣泛的發展和應用,但是自對偶性質的可能性測度在理論和應用方面仍需進一步完善.基于此,Liu等[17]在2002年提出了一類具有自對偶性質的可信性測度.下面首先回顧一下模糊集、可信性理論和模糊圖中的一些基本概念.

給定一個論域Γ,Pos是一個定義在冪集Ρ(Γ)上的集函數.若Pos滿足條件:

1)Ρos(Φ)=0,Ρos(Γ)=1;

基于可能性測度Pos,Liu等[17]定義了具有自對偶性質的集函數Cr.

定義2.1設三元組(Γ,P(Γ),Pos)是一個可能性空間,若

A∈P(Γ),

則稱集函數Cr是事件A的可信性測度,其中Ac是集合A的補集,這里,稱三元組(Γ,P(Γ),Cr)是一個可信性空間.

定義2.2[24]在有限圖G=(V,E)中,對每條邊賦以(0,1]中的數值作為權重,即規定一個權函數

μ:E→(0,1],

5) 頂點vi和vj之間的連通強度S(vi,vj)定義為

其中Lvi,vj表示vi和vj之間的所有通路.

關于模糊集、可信性理論和模糊圖的更多知識可以參閱文獻[24-26].

3 模糊社交網絡中心性的計算方法

在實際的社交網絡中,用戶(結點)之間一般不會相互獨立,而是彼此之間通過各種交互行為(邊或鏈接)連接起來.與普通社會網絡不同的是,當社交網絡用戶之間建立連接后,他們之間就會相互影響.更確切地說,用戶之間的影響程度大小是社交網絡中用戶間親密度的一種表現,這種影響力可以增強或減弱.若沿用經典的社會網絡方法研究社交網絡,不足之處在于原有方法注重網絡的拓撲結構,這樣就不能很好地體現用戶之間由交互行為而產生的親密度強弱關系.基于此,本文采用模糊方法處理社交網絡中用戶之間連接的親密度關系,并有效確定用戶在整個網絡中的中心影響力.為了給出模糊社交網絡的相關概念,首先給出符號說明(見表1).

表 1 符號說明Tab.1 The description of symbol

3.1模糊結點中心性和緊密中心性設社交網絡中存在n個用戶,并且用戶之間存在m(0mn(n+1))條邊,分別表示為V和E.當社交網絡中存在模糊因素時,用戶vi和vj之間的連接(親密度)用邊表示,交互信息也可以由用戶vi通過邊傳遞給用戶vj,同時,傳遞邊在這樣的模糊社交網絡中則帶有1個以隸屬度定義的權重來表示用戶vi和vj之間的親密度，因此,模糊社交網絡的相關定義如下.

上面已經給出了模糊社交網絡的相關定義,而在實際社交網絡中人們關心的是哪些用戶對于整個網絡的影響力更大,因此,要想度量某個用戶的影響力,僅僅定義模糊社交網絡顯然還不夠.一般來說,經典的社會網絡中1個結點的重要性與該結點的連接結點的數量存在必然聯系.換句話說,1個結點的連接結點數量越大,該結點就越重要,并且網絡的中心地位就越高.在社會網絡中,利用經典圖論分析結點影響力一般采用結點度的定義.由于模糊社交網絡的特殊性,簡單套用原有結點度定義是不可行的.在模糊社交網絡中,邊的意義是用戶間的交互親密度的體現.一般來說,1個用戶的重要性與該用戶連接用戶的整體親密度有關系,即用戶的整體親密度越大,該用戶在網絡中的位置就越重要,信息通過該用戶傳播的可信性越大.本文將采用可信性理論評價用戶網絡影響力(結點中心度),因此,模糊社交網絡的用戶(結點)中心度定義如下.

在現實社交網絡中,與非中心用戶相比,1個中心用戶應該將信息傳遞給網絡其它用戶的可信度更高.一般社會網絡中,緊密度中心性用于評價1個用戶到其它所有用戶的緊密程度,而模糊社交網絡采用模糊緊密中心性來說明中心用戶傳遞信息的可信程度.模糊緊密中心性需要計算某個用戶向網絡其它用戶傳遞信息可信度的平均值,定義如下:

3.2模糊社交網絡中心度數值算例為了說明本文所設計模糊社交網絡中心性分析方法的有效性,下面分別給出經典社會網絡和模糊社交網絡的結點中心度和緊密中心度數值算例.通過比較2個例題的計算結果,分析不同網絡中的中心度,從而說明本文提出的中心度計算方法具有一定的現實意義,方法也是有效和可行的.

例3.1圖1是1個經典無向社交網絡,它有9個結點vi(i=1,2,…,9),12條邊e12、e13、e14、e23、e35、e36、e37、e39、e56、e67、e68、e89,下面運用經典的中心性分析方法計算各結點的中心度.

圖 1 經典社交網絡圖

解根據經典的社會網絡中心性方法[27]可得以下結論.

1) 結點中心度:

CD(v1)=3,CD(v2)=2,CD(v3)=6,

CD(v4)=1,CD(v5)=2,CD(v6)=4,

CD(v7)=2,CD(v8)=2,CD(v9)=2.

2) 緊密中心度:

解由于其它模糊社會網絡的緊密性中心度計算時需要選擇距離公式,不同的距離公式會產生不同的結果,從而不具有可比性,因此,下面根據文獻[12]僅計算結點中心度,且由本文提出的方法計算結點中心度和緊密性中心度.

圖 2 模糊社交網絡圖

1) 傳統模糊社會網絡的結點中心度:

2) 本文方法的結點中心度:

3) 本文方法的緊密性中心度(僅以結點v1和v2為例):

分析例3.1和例3.2可以看出:

1) 從結點中心性的角度看,例3.1中結點v3的中心度最大,是因為與其相連接的結點數量最大.但是,在例3.2的模糊社交網絡中,結點v3的模糊中心度并不是最大的,而結點v6的模糊中心度是最大的.計算結果說明傳統社會網絡的中心性分析方法并不能完全解決模糊社會網絡的中心性分析問題.

2) 在傳統模糊社會網絡中,結點v3的中心度排名第四,而利用本文提出的方法計算結點v3的中心度排名最小.從圖2可以看出,雖然與結點v3相連接的結點數量最多,但是邊的權重卻很小,也說明這些結點與結點v3的親密度很小,而其它結點連接邊的權重相對結點v3都比較大,所以利用本文的方法可以有效地區分出各個結點的中心度大小,并說明本文方法是可行的.

4 結論與展望

本文的主要工作如下:

1) 基于可信性理論給出新的模糊社交網絡的概念以及結點連通強度、模糊結點中心度和模糊緊密性中心度的定義.

2) 通過數值算例說明模糊結點中心度的合理性,并對本文提出的方法進行了有效性和合理性的驗證.

下一步工作的展望:

1) 本文雖然給出了模糊結點中心度和緊密性中心度的計算方法,但是沒有進一步對介數中心性和特征向量中心性等其它中心性問題進行分析,因此,這些問題將是本文下一步工作的1個主要研究方向.

2) 本文給出了2個數值算例對模糊社交網絡的中心度進行了計算,但是該方法還有待進一步進行實際社交網絡的驗證,因此,在各種微博網絡、在線社區平臺、在線討論區等社交網絡平臺進行實驗研究也是本文下一步的主要工作方向.