一種新的模糊社交網(wǎng)絡(luò)中心性分析方法

袁國強, 徐建民, 劉明艷

(1. 河北大學(xué) 管理學(xué)院, 河北 保定 071002;2. 河北金融學(xué)院 基礎(chǔ)部, 河北 保定 071051;3. 河北大學(xué) 網(wǎng)絡(luò)空間安全與計算機學(xué)院, 河北 保定 071002)

1 背景介紹

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

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

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

2 基本概念

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

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

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

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

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

A∈P(Γ),

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

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

μ:E→(0,1],

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

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

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

3 模糊社交網(wǎng)絡(luò)中心性的計算方法

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

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

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

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

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

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

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

圖 1 經(jīng)典社交網(wǎng)絡(luò)圖

解根據(jù)經(jīng)典的社會網(wǎng)絡(luò)中心性方法[27]可得以下結(jié)論.

1) 結(jié)點中心度:

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) 緊密中心度:

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

圖 2 模糊社交網(wǎng)絡(luò)圖

1) 傳統(tǒng)模糊社會網(wǎng)絡(luò)的結(jié)點中心度:

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

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

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

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

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

4 結(jié)論與展望

本文的主要工作如下:

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

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

下一步工作的展望:

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

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