集對社會網(wǎng)絡分析模型及其應用

張春英,梁瑞濤,劉璐

(河北聯(lián)合大學理學院,河北唐山063009)

0 引 言

社會網(wǎng)絡又稱人際網(wǎng)絡,是由某些特定群體(人、企業(yè)、組織)相互的關(guān)系組成的相對穩(wěn)定的關(guān)系網(wǎng)[1]。社會網(wǎng)絡作為一種較新的數(shù)據(jù)挖掘技術(shù),在管理、犯罪組織、互聯(lián)網(wǎng)等領域都得到了廣泛的應用[2,3,4]。文獻[2,3,4]以社會網(wǎng)絡為視角進行研究,找出網(wǎng)絡中個體存在的各種社會關(guān)系,針對社會關(guān)系進行網(wǎng)絡的信息挖掘。我國學者周衛(wèi)國[5]等利用社會網(wǎng)絡找出網(wǎng)站中用戶之間的朋友關(guān)系,通過開發(fā)社會網(wǎng)絡可視化平臺挖掘用戶之間的關(guān)聯(lián)關(guān)系并找出用戶之間的最短路徑。學者高鵬[6]通過分析聊天數(shù)據(jù)的時序關(guān)系推斷出用戶間的社會網(wǎng)絡關(guān)系,然后根據(jù)社會網(wǎng)絡中反映出的用戶交流關(guān)系判斷并過濾了聊天數(shù)據(jù)中的噪聲。文獻[5,6]通過個體之間的引用、交流等一些個體相同的信息來發(fā)現(xiàn)網(wǎng)絡中個體之間的關(guān)聯(lián)關(guān)系,且利用社會網(wǎng)絡從大量信息當中挖掘出有效信息。然而,在利用社會網(wǎng)絡對網(wǎng)絡中個體間的社會關(guān)系進行評估的過程中,個體之間還存在著不相同、不確定的信息元素,只利用確定的相同信息評估不能全面地反應網(wǎng)絡中個體之間的關(guān)系。同時,在現(xiàn)實社會網(wǎng)絡中節(jié)點和連接的屬性常隨時間動態(tài)變化[7],網(wǎng)絡中節(jié)點關(guān)系也會隨著各種因素的變化而發(fā)生變化,因此,只考慮網(wǎng)絡中個體之間相同元素某個時刻的靜態(tài)特征是很難進行準確的信息挖掘的。集對分析是由我國學者趙克勤[8]在1989年提出的一種處理不確定問題的系統(tǒng)分析方法。隨后由我國學者孫晉眾[9]等建立了一種基于馬爾科夫鏈的集對分析的動態(tài)模型,從而使集對分析在處理動態(tài)不確定問題上有很大的進展。因此,本文基于集對分析理論,試圖將集對分析的思想融入到社會網(wǎng)絡中提出了集對社會網(wǎng)絡分析模型、集對社會網(wǎng)絡動態(tài)變化以及相關(guān)性質(zhì),通過簡單例子的實現(xiàn)了集對社會網(wǎng)絡的應用。

1 基本概念

1.1 社會網(wǎng)絡

社會網(wǎng)絡[10]可以表示為由多個點(社會行動者)和各點之間的連線(代表行動者之間的關(guān)系)組成的集合,若令G為一個社會網(wǎng)絡,E為邊集,V為點集,則社會網(wǎng)絡可以表示為G=(V,E)。社會網(wǎng)絡體現(xiàn)著一種結(jié)構(gòu)關(guān)系,可反映行動者之間的社會關(guān)系。不同類型的關(guān)系形成了不同的社會網(wǎng)絡。如社會交際網(wǎng)、社會支持網(wǎng)、討論網(wǎng)、權(quán)利網(wǎng)等。

社會網(wǎng)絡可以分為兩類:(1)缺省的社會網(wǎng)絡(defau lt social network):社會網(wǎng)絡中行動者之間的信息存在不完備的;行動者與行動者之間的關(guān)系值是缺省的;(如圖1a)(2)完整的社會網(wǎng)絡(comp lete social network):行動者與行動者之間的關(guān)系值是完備的,也就是任意的兩個行動者之間都有關(guān)系的存在。(如圖1b)。

1.2 集對分析理論

定義1.1集對[8](set pair)就是由一定聯(lián)系的兩個集合構(gòu)成對子,在協(xié)同的不確定系統(tǒng)背景下,對于兩個有聯(lián)系的集合A和B,對他們所具有的特性展開分析,共得到N個特性,其中S個為集對中共有的,并且有P個特性相對立(相反的),在其余F個特性上關(guān)系是不確定的,則兩個集合聯(lián)系度u的數(shù)學表達式為:

其中,i為差異標記,在區(qū)間[-1,1]上視不同情況取值,在[0,1]時差異部分趨向同一,在[-1,0]時差異部分趨向相反的。j僅起標記作用,集對所要處理的是任意兩個集合之間由于不確定引起差異性,利用聯(lián)系度表示出兩個集合的關(guān)聯(lián)程度。

1.3 聯(lián)系度i的確定

在集對分析理論發(fā)展的今天,后繼者都在不斷完善集對分析理論,尤其在對i的取值上,趙克勤采用順勢取值法、逆勢取值法、計算取值法和隨機取值法等多種方法對i進行求解,提出應該在具體問題中找到i變化的規(guī)律[8],朱兵[11]等提出了用統(tǒng)計試驗方法來確定差異不確定系數(shù)i的新途徑,給出了合理的取值。但這些方法并未從根本上提出有效的方法。而由李陶[12]提出分別將差異度與同一度和對立度的關(guān)聯(lián)度作為i的取值,運用灰色理論中的絕對關(guān)聯(lián)度計算方法對i進行求解。這個方法更能夠通過差異度、同一度、對立度給出更合理的取值。

2 集對社會網(wǎng)絡分析模型

在社會網(wǎng)絡關(guān)系中,對于兩個研究對象的屬性集合ek和es,共有N個屬性(即兩個對象的屬性之和),其中有S為兩個對象屬性集合中屬性中相同的屬性,有P為兩個對象屬性集合中不相同的屬性,有F為兩個對象屬性集合中不確定的屬性。則令

針對社會網(wǎng)絡中節(jié)點的復雜性,以及節(jié)點間關(guān)系的不確定性。我們給出了如下定義:

其中ek(t)∈U和es(t)∈U,a為兩個對象所具有的相同屬性與兩個對象所共有的屬性之比;b為兩個對象所具有的不確定屬性與兩個對象所共有的屬性之比;c為兩個對象所具有的不相同的屬性與兩個對象所共有的屬性之比;i為差異標記,在區(qū)間[-1,1]上視不同情況取值,j僅起標記作用,取值為-1。

由定義3.1我們知道在t時刻的兩個研究對象的聯(lián)系度為:

其中i∈[-1,1];j=-1;a+b+c=1

而在社會網(wǎng)絡中,網(wǎng)絡會隨時間不斷的變化,原有的屬性值就會發(fā)生變化,有的屬性值不變,有的轉(zhuǎn)化為其他的屬性。不妨設在t+1時刻,原有的St屬性中仍有S t1個處于不變狀態(tài),St2個轉(zhuǎn)化為不確定的屬性, St3個轉(zhuǎn)化為相反的屬性。則St在[t,t+1]內(nèi)的轉(zhuǎn)移向量(經(jīng)歸一化處理)為

因此,在[t,t+1]時間內(nèi)的轉(zhuǎn)移矩陣為M,在t+1時刻,兩個研究對象的聯(lián)系度為ρ(ek,es)(t+1)為:

定義3.2:設矩陣R=(ρ(ek,es))k×s則稱R為集對聯(lián)系矩陣,其中ρ(ek,es)為集對聯(lián)系矩陣中的元素,R =(ρ(ek,es))k×s表示研究對象ek與研究對象es的聯(lián)系關(guān)系矩陣,或者說一個集對聯(lián)系矩陣確定網(wǎng)絡內(nèi)各研究對象的聯(lián)系度。此矩陣可表示為:

我們可以對集對社會網(wǎng)絡的聯(lián)系程度以及網(wǎng)絡中心度問題給出如下定義:

定義3.3對于一個社會網(wǎng)絡G=(V,E),則整個社會網(wǎng)絡關(guān)系的集對聯(lián)系密度為:

定義3.4:從社會網(wǎng)絡關(guān)系中任一研究對象與其他研究對象的聯(lián)系度之和取最大值與任意兩個研究對象的聯(lián)系度的差值比上差值中取最大值就是中心測度:

3 集對社會網(wǎng)絡的性質(zhì)

集對聯(lián)系矩陣性質(zhì):在社會網(wǎng)絡中任意兩個研究對象之間的聯(lián)系度為ρ(ek,es),則這個社會網(wǎng)絡研究對象之間的關(guān)系組成一個集對聯(lián)系矩陣。如圖(5*5的網(wǎng)絡)

圖2

由圖2可知:

(1)集對聯(lián)系矩陣任意的ρ(ek,es)有ρ(ek,es)=ρ(es,ek),表示研究對象ek和研究對象es的聯(lián)系度與研究對象es和研究對象ek聯(lián)系度相同。

(2)對角線上的值為常量,即ρ(ek,es)=1,表示對研究對象自身的同一度為1.,差異度和對立度為0。

(3)當ρ(ek,es)=-1時,則兩個研究對象之間沒有聯(lián)系。

在社會網(wǎng)絡關(guān)系中,任意兩個研究對象之間的聯(lián)系度隨時間的變化也在發(fā)生的變化,兩個研究對象之間的關(guān)系可能會加強,或者兩個研究對象之間的關(guān)系可能會減弱。因此,當兩個研究對象之間的聯(lián)系度隨時間變大或變小的話,兩個研究對象之間的關(guān)系就會出現(xiàn)趨強或趨弱。如圖3所示。

圖3

定理1:在集對社會網(wǎng)絡動態(tài)變化過程中:

若ρ(ek,es)逐漸增大達到某一穩(wěn)定值時,則兩個研究對象之間的關(guān)系就會趨于強關(guān)系。

若ρ(ek,es)逐漸減小達到某一穩(wěn)定值時,則兩個研究對象之間的關(guān)系就會趨于弱關(guān)系。

4 應用實例

社會網(wǎng)絡分析對挖掘隱藏在確定的社會網(wǎng)絡關(guān)系內(nèi)的有效的方法,而實際的社會為網(wǎng)絡環(huán)境里,有聯(lián)系的研究對象之間關(guān)系屬性特性上也存在著不確定性,由此我們提出了集對網(wǎng)絡分析的概念,使我們不僅僅局限于0～1的二值網(wǎng)絡關(guān)系之中,而有他們之間固有的屬性特性造成網(wǎng)絡關(guān)系中關(guān)系布局。因此,我們應該怎么樣運用集對網(wǎng)絡分析對網(wǎng)絡進行分析挖掘呢?因此提出了集對網(wǎng)絡分析的具體分析步驟:

Step1:在一個關(guān)系網(wǎng)絡里,構(gòu)造網(wǎng)絡里每個研究對象的關(guān)系屬性集合。按照集對的多種特性進行同一度、差異度和對立度分析,得到一組同一度 、差異度b和對立度c的量化值

Step2:采用灰色理論中的絕對關(guān)系度計算方法,計算聯(lián)系度i的值。

Step3:根據(jù)計算出來的i的值,得到網(wǎng)絡中任意兩個研究對象的聯(lián)系度ρ(ei,ej)(t)的值。

Step4:由step3得到的任意兩個研究對象的聯(lián)系度,從而構(gòu)造集聯(lián)矩陣M 。

Step5:由集聯(lián)矩陣M計算網(wǎng)絡的中心度測度C。找出網(wǎng)絡中處于核心的研究對象。

Step6:提出結(jié)論,由網(wǎng)絡的中心度情況給出整個網(wǎng)絡的現(xiàn)在情況。

例:

由圖建立集對網(wǎng)絡模型

A={A,B,C}B={A,B,C}C={A,B,C,D}D={C,D,E,F}E={D,E,F}

F={D,E,F}任意兩個研究對象的聯(lián)系度為ρ(A,B)(t)ρ(A,C)(t)等。

采用灰色理論中的絕對關(guān)系度計算方法,計算可得i=0.770

構(gòu)建集聯(lián)矩陣

A B C D E F A 1 0.885 0.589 -0.641 -1 -1 B 0.885 1 0.589 0.667 -1 -1 C 0.589 0.589 1 -0.333-0.667-0.667 D -0.641 0.667 -0.333 1 0.589 0.589 E -1 -1 -0.667 0.589 1 1 F -1 -1 -0.667 0.589 1 1

通過計算D點的聯(lián)系度最高,所以D的是簡單網(wǎng)絡的核心,中心測度為C=0.403。

5 結(jié) 語

本文首先提出了社會網(wǎng)絡和集對分析的相關(guān)概念,對集對社會網(wǎng)絡的定義的提出給出了有力的支持,同時根據(jù)集對社會網(wǎng)絡的定義、網(wǎng)絡的動態(tài)變化提出集對社會網(wǎng)絡的相關(guān)性質(zhì),對解決社會網(wǎng)路中的不確定的問題以及網(wǎng)絡的動態(tài)問題提出了新的方法?，F(xiàn)在的集對社會網(wǎng)絡理論還不太完善,還有許多工作需要完成。

[1] Gou H ong-mei,Huang Bi-qing.A framew ork for virtualen terprise Operationmanagement[J].Compu ters in Industry,2003,50(3): 333～352.

[2] 潘虹,翟東升.基于社會網(wǎng)絡的信任模型研究[J].計算機工程與應用,2008,44(12),215～220.

[3] 盧志國,馬國棟,任樹懷.社會網(wǎng)絡在美國大學圖書館的應用分析[J].圖書館工作與研究,2009,155(1),69～72.

[4] 邱峰,葉新東.網(wǎng)絡學習社區(qū)的社會網(wǎng)絡研究[J].現(xiàn)代教育技術(shù),2010,20(2),37～41.

[5] 周衛(wèi)國,史戎堅,葉婷.基于Web2.0網(wǎng)站中社會網(wǎng)絡的信息挖掘[J].微計算機信息,2009,25(2-3):146～147.

[6] 高鵬,曹先彬.基于社會網(wǎng)絡的聊天數(shù)據(jù)噪聲過濾[J].計算機工程,2008,34(5):166～168.

[7] Gao Lin,Liu Jiming,Zhang Shiwu,et a1.Discovering the Dynamics in a Social Mem ory Network[C]//Proc.of 2008 International Conference on Web Intelligence and Intelligent Agen t Technology.Sydney,Australia:[s,n],2008.

[8] 趙克勤.集對分析及其初步應用[M].杭州:浙江科學技術(shù)出版社2000:8～90.

[9] 孫晉眾,陳世權(quán).一種集對分析的動態(tài)模型及其應用[J].系統(tǒng)工程,2004,22(5),35～38.

[10] John Scott著,劉軍譯,等.社會網(wǎng)絡分析法[M].重慶:重慶大學出版社,2007.

[11] 朱兵,王文圣,王紅芳,等.集對分析中差異不確定系數(shù)的探討[J].四川大學學報(工程科學版),2008,40(1):5～9.

[12] 李陶,付強,丁紅.基于灰色關(guān)聯(lián)度的集對分析差異系數(shù)研究[J].黑龍江水專學報,2010,37(1)97～99.