江淼淼，孫更新，賓 晟

青島大學(xué) 數(shù)據(jù)科學(xué)與軟件工程學(xué)院，山東 青島 266071

1 引言

社交網(wǎng)絡(luò)是一種典型的復(fù)雜網(wǎng)絡(luò)[1-2]，它是由社交網(wǎng)絡(luò)中個體成員之間的關(guān)系互動而成，主要研究個體之間的聯(lián)系以及行為活動。社交網(wǎng)絡(luò)中用戶間的關(guān)系可能來源自現(xiàn)實世界，也可能來源于網(wǎng)絡(luò)用戶在社交網(wǎng)絡(luò)中的網(wǎng)絡(luò)行為和網(wǎng)絡(luò)交流，并且隨著發(fā)展逐步形成了網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)。因此，社交網(wǎng)絡(luò)必然是一個多關(guān)系網(wǎng)絡(luò)，作為網(wǎng)絡(luò)節(jié)點的用戶，他們之間必然存在著多種關(guān)系。例如，在Facebook、Twitter、新浪微博等社交網(wǎng)絡(luò)中，依據(jù)用戶的行為方式，用戶間至少存在關(guān)注、回復(fù)、轉(zhuǎn)發(fā)和閱讀四種顯式關(guān)系，如果進(jìn)一步對微博內(nèi)容和用戶間的互動行為進(jìn)行分析，可以從中發(fā)現(xiàn)用戶的興趣和偏好，從而找到用戶之間存在的各種隱式關(guān)系。

雖然多關(guān)系社交網(wǎng)絡(luò)廣泛存在于現(xiàn)實生活中，但針對多關(guān)系社交網(wǎng)絡(luò)的相關(guān)研究卻較少，其主要原因是缺乏適合表述多關(guān)系社交網(wǎng)絡(luò)的復(fù)雜網(wǎng)絡(luò)模型。傳統(tǒng)的復(fù)雜網(wǎng)絡(luò)模型僅能描述一個系統(tǒng)中的同類個體及個體間的單一關(guān)系，二分圖模型[3]僅僅可以對兩類節(jié)點間的相互關(guān)系進(jìn)行描述，而且無法表述同一類節(jié)點間的關(guān)系，層次網(wǎng)絡(luò)模型[4-7]雖然可以描述多類個體及其相互關(guān)系，但該模型首先需要將節(jié)點劃分到不同的層次后再進(jìn)行研究，然而現(xiàn)實問題往往很難分清層次關(guān)系。本文基于課題組提出的多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型[8]構(gòu)建多關(guān)系社交網(wǎng)絡(luò)，該模型通過子網(wǎng)描述了同類個體間的單一關(guān)系，基于該模型的組網(wǎng)運算，可以靈活地實現(xiàn)多個子網(wǎng)的復(fù)合，進(jìn)而方便地實現(xiàn)了在同一個復(fù)雜網(wǎng)絡(luò)中對異質(zhì)個體間的多種關(guān)系的描述。

社團(tuán)結(jié)構(gòu)是指網(wǎng)絡(luò)中的節(jié)點可以分為不同的組，組間的聯(lián)系相對稀疏，組內(nèi)的聯(lián)系相對緊密[9]。社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)在揭示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、分析網(wǎng)絡(luò)傳播特征等方面研究具有重要價值。例如，科研合作關(guān)系網(wǎng)絡(luò)是一個典型的多關(guān)系社交網(wǎng)絡(luò)，其中包含論文合著關(guān)系、論文引用關(guān)系、論文與作者對應(yīng)關(guān)系、研究領(lǐng)域相似關(guān)系等，通過發(fā)現(xiàn)該網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)可以將作者和論文歸于不同研究領(lǐng)域[10]。為了發(fā)現(xiàn)多關(guān)系網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，Cai等人[11]根據(jù)用戶查詢抽取出一組線性組合關(guān)系來挖掘出符合用戶需求的社團(tuán)。Rodriguez等人[12]提出了一種代數(shù)方法將多關(guān)系網(wǎng)絡(luò)投射到單關(guān)系網(wǎng)絡(luò)上，以避免處理多關(guān)系網(wǎng)絡(luò)上復(fù)雜的異構(gòu)數(shù)據(jù)。王金龍等人[13]利用多關(guān)系鏈對多關(guān)系社交網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)進(jìn)行挖掘分析。這些已有方法在多關(guān)系網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)時或是分析不同性質(zhì)的節(jié)點對于社團(tuán)劃分的影響，或是考慮不同關(guān)系系數(shù)及關(guān)系間的相互作用對社團(tuán)劃分的影響，但都無法將網(wǎng)絡(luò)中不同性質(zhì)的節(jié)點按照多種關(guān)系劃分到同一個社團(tuán)結(jié)構(gòu)中。

本文利用多關(guān)系社交網(wǎng)絡(luò)中信息傳播的特性，在分析復(fù)雜網(wǎng)絡(luò)傳統(tǒng)的社團(tuán)結(jié)構(gòu)劃分算法基礎(chǔ)上，利用多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型的混合度和混合權(quán)[14]計算多關(guān)系綜合影響強(qiáng)度，提出基于該模型的多關(guān)系社交網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)劃分算法。在海豚社會網(wǎng)絡(luò)和空手道俱樂部網(wǎng)絡(luò)[15]驗證了該算法對于單關(guān)系網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)劃分的正確性，并利用AMiner數(shù)據(jù)集構(gòu)建論文合作多關(guān)系社交網(wǎng)絡(luò)，通過多元線性回歸算法得到網(wǎng)絡(luò)中不同關(guān)系的影響強(qiáng)度，取得了良好的社團(tuán)結(jié)構(gòu)劃分結(jié)果。

2 多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型

2.1 定義

多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型能夠描述復(fù)雜系統(tǒng)中不同類個體間的多種關(guān)系[16]。該模型（簡稱復(fù)合網(wǎng)）可以使用一個四元組G=(V,E,R,F)來表示：

（1）V={v1,v2,…,vm}，表示節(jié)點的集合，m=||V是集合中元素的個數(shù)。

（2）E={vh,vl|vh,vl∈V,1≤h,l≤m}?V×V，表示節(jié)點間連邊的集合。

（3）R=R1×R2×…×Ri×…×Rn={(r1,r2,…,ri,…,rn)|ri∈Ri,1≤i≤n}，Ri表示節(jié)點間一種相互作用關(guān)系集合，ri表示節(jié)點間的一種相互作用關(guān)系,n是節(jié)點間相互作用關(guān)系的總數(shù)，若則表示網(wǎng)絡(luò)為多關(guān)系網(wǎng)絡(luò)。

（4）映射是邊集E經(jīng)過φ函數(shù)投影在F中找到唯一對應(yīng)的映射，表示邊上具有的關(guān)系類型。

2.2 子網(wǎng)加載運算

通過復(fù)合網(wǎng)中定義的子網(wǎng)加載運算可以將若干個復(fù)雜網(wǎng)絡(luò)組成新的復(fù)合復(fù)雜網(wǎng)絡(luò)。子網(wǎng)加載運算能復(fù)合兩個或兩個以上的復(fù)雜網(wǎng)絡(luò)，新的復(fù)合網(wǎng)的關(guān)系向量空間維數(shù)增大，其相關(guān)節(jié)點間相互關(guān)系的變化可通過空間向量的相關(guān)運算完成。

子網(wǎng)加載運算的具體定義如下：

（1）V=V1∪V2；

（2）E?E1∪E2∪(V1×V2)；

（3）R=R1∪R2∪R′；

（4）映射F:E→2R，當(dāng)1≤h,l≤|V|；

（5）S=dom(r1)×dom(r2)×…×dom(ri)×…×dom(rn)，ri∈R，1≤i≤n；

稱R′為加載關(guān)系集合，vh,vl∈V1×V2為外部邊，vh、vl為邊界節(jié)點。

圖1所示為由3個向量復(fù)合網(wǎng)Σ1、Σ2和Σ3通過子網(wǎng)加載運算構(gòu)建多關(guān)系復(fù)合網(wǎng)的過程。3個向量復(fù)合網(wǎng)對應(yīng)關(guān)系分別為r1、r2、r3，對應(yīng)關(guān)系強(qiáng)度dom(r1)={1},dom(r2)={2},dom(r3)={3}，以向量復(fù)合網(wǎng)Σ1為基底，將Σ2作為子網(wǎng)加載到Σ1上，加載映射關(guān)系強(qiáng)度映射為，類似地繼續(xù)加載子網(wǎng)Σ3。

2.3 節(jié)點混合權(quán)和節(jié)點混合度

節(jié)點混合權(quán)：設(shè)節(jié)點vh∈V，關(guān)系強(qiáng)度比例系數(shù)(sf1,sf2,…,sfk)，則節(jié)點vh的混合權(quán)：

其中，為節(jié)點關(guān)于關(guān)系的權(quán)。

節(jié)點混合度：設(shè)節(jié)點vh∈V，關(guān)系強(qiáng)度比例系數(shù)(sf1,sf2,…,sfk)，則節(jié)點vh的混合度為：

以圖1為例，設(shè)定關(guān)系r1、r2、r3的權(quán)均為0.5，其關(guān)系強(qiáng)度比例系數(shù)sf1、sf2、sf3均為1，節(jié)點0關(guān)于關(guān)系r1的度，關(guān)于關(guān)系r2的度，關(guān)于關(guān)系r3的度，則節(jié)點0的混合度1=5，節(jié)點0關(guān)于關(guān)系r1的權(quán)，關(guān)于關(guān)系r2的權(quán)，關(guān)于關(guān)系r3的權(quán)，則節(jié)點0的混合權(quán)為

3 復(fù)雜網(wǎng)絡(luò)中的信息傳播

3.1 單關(guān)系復(fù)雜網(wǎng)絡(luò)上的信息傳播過程

初始時網(wǎng)絡(luò)中的所有節(jié)點都沒有攜帶信息，首次傳播開始，設(shè)置其中一個節(jié)點i為信源節(jié)點并賦予其非空信息量I，設(shè)該節(jié)點的鄰居節(jié)點集合為Vi，此時網(wǎng)絡(luò)中信息分布為X=(0,…,I,…,0)，信源節(jié)點通過連邊向Vi中的節(jié)點傳播信息，其鄰居節(jié)點接收完信息后將繼續(xù)向各自的相鄰節(jié)點集合Vii傳播信息，但作為接收方的節(jié)點并不是完全接收來自信源節(jié)點的信息，而是以一定概率p接收[17]；第二次傳播時，集合Vi=(0,…,I1,…,0,…,Ij,…,0,…,In)表示所有攜帶信息的節(jié)點集合，集合Vi中的節(jié)點既可以向鄰居節(jié)點傳送信息，也可以接收來自其相鄰節(jié)點的信息。由于接收方節(jié)點并不能接收全部外來的信息，當(dāng)網(wǎng)絡(luò)規(guī)模較大時，僅靠單次傳播，網(wǎng)絡(luò)中部分距離信源節(jié)點較遠(yuǎn)的節(jié)點接收到的信息較少，不能充分表示信源節(jié)點對這些節(jié)點的影響。因此，需要信息在網(wǎng)絡(luò)中迭代傳播T次后，網(wǎng)絡(luò)中所有節(jié)點所攜帶的信息量分布情況才能表示信源節(jié)點對整個網(wǎng)絡(luò)信息傳播的影響能力。根據(jù)每個節(jié)點作為信源節(jié)點時，網(wǎng)絡(luò)中信息量的分布向量，就可以計算網(wǎng)絡(luò)節(jié)點間的相似性。

節(jié)點之間傳遞信息可以通過一個傳播概率矩陣P表示，其具體定義如下：

其中，D為由節(jié)點的度構(gòu)成的對角矩陣，W為網(wǎng)絡(luò)的鄰接矩陣。該公式表示網(wǎng)絡(luò)中的節(jié)點i向節(jié)點j傳送信息時，節(jié)點j不是全部接收而是以如下概率接收：

圖2是一個簡單的復(fù)雜網(wǎng)絡(luò)，其傳播概率矩陣P為：

Fig.2 Example of single relationship complex network圖2 單關(guān)系復(fù)雜網(wǎng)絡(luò)示例

分別以節(jié)點0、2、7作為初始信源節(jié)點，則網(wǎng)絡(luò)中初始信息分布可以分別表示為：

設(shè)置傳播次數(shù)T=3，得到信息在全部網(wǎng)絡(luò)節(jié)點上的最終分布情況：

X0={1.00,0.42,0.62,0.62,0.03,0.10,0.10,0.03}

X2={0.62,0.42,1.00,0.62,0.03,0.10,0.10,0.03}

X7={0.03,0.16,0.03,0.03,0.60,0.50,0.50,1.00}

利用歐氏距離等相似性度量，就可以根據(jù)信息量分布向量X0、X2和X7得到節(jié)點0、2、7之間的相似性。

3.2 多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型上的信息傳播過程

可以將信息傳播擴(kuò)展到多關(guān)系社交網(wǎng)絡(luò)中，R=(r1,r2,…,ri,…,rn)表示網(wǎng)絡(luò)中存在的關(guān)系集合，基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型，構(gòu)建包含n種關(guān)系的復(fù)合網(wǎng)。與單關(guān)系復(fù)雜網(wǎng)絡(luò)類似，復(fù)合網(wǎng)中的每個節(jié)點也是按照一定的比例p接收信息，不同的是需要考慮節(jié)點與鄰居節(jié)點連邊上所具有的各種關(guān)系的相互作用對接收信息概率p的影響。

復(fù)合網(wǎng)信息傳播概率矩陣P?具體定義如下：

其中，?為節(jié)點混合度組成的對角矩陣，?為網(wǎng)絡(luò)的鄰接混合權(quán)矩陣，該矩陣中的元素可表示為：

鄰接混合權(quán)矩陣中的元素是對節(jié)點vh和節(jié)點vl間所存在的各種關(guān)系的關(guān)系強(qiáng)度的加權(quán)求和。其中，sfri表示節(jié)點vh和節(jié)點vl之間關(guān)于關(guān)系ri的關(guān)系強(qiáng)度比例系數(shù)，kri′為關(guān)系ri的關(guān)系強(qiáng)度。

在鄰接混合權(quán)矩陣的基礎(chǔ)上，節(jié)點vh的混合權(quán)也可表示為：

依次選擇網(wǎng)絡(luò)中的節(jié)點作為信源節(jié)點并賦予1個單位的信息量，網(wǎng)絡(luò)中其余節(jié)點的信息量為0。以網(wǎng)絡(luò)中一個節(jié)點s為例，設(shè)節(jié)點s為信源節(jié)點，其攜帶信息量為1，初始化s節(jié)點表示的向量為0,…,1,0)，第一次傳遞過程，由該節(jié)點向其鄰居節(jié)點傳遞信息，這一過程用數(shù)學(xué)公式表示為，向量中的元素為第一次傳遞后網(wǎng)絡(luò)各個節(jié)點所攜帶的信息量；第二次傳遞過程，接收到信息的節(jié)點向其相鄰節(jié)點傳遞信息，若其相鄰節(jié)點也具有信息，其也可以接收來自相鄰節(jié)點的信息，這一過程的數(shù)學(xué)表達(dá)式為，向量中的元素為第二次傳遞后網(wǎng)絡(luò)各個節(jié)點攜帶的信息量；類似地，每次傳播后的信息表示為在下次傳播前，設(shè)即信源節(jié)點在t+1次傳播開始時信息量始終為1。這樣通過網(wǎng)絡(luò)各節(jié)點T次傳播后的信息量分布向量，將得到能表示節(jié)點影響力的信息分布矩陣。

以圖1中的復(fù)合網(wǎng)為例，多關(guān)系復(fù)合網(wǎng)上信息傳播過程如圖3所示。

設(shè)3種關(guān)系的比例系數(shù)均為1，關(guān)系強(qiáng)度分別為1、2、3，節(jié)點0為源節(jié)點X0=(1,0,0,0,0,0,0,0)，則P?計算如下：

4 基于信息傳播的多關(guān)系社交網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法

4.1 關(guān)系強(qiáng)度和關(guān)系系數(shù)的計算

利用多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型的子網(wǎng)加載運算得到的多關(guān)系社交網(wǎng)絡(luò)中將包含多種關(guān)系R={(r1,r2,…,ri,…,rn)|ri∈R,1≤i≤n}。各節(jié)點的度和權(quán)在復(fù)合網(wǎng)模型中分別被定義為由關(guān)系強(qiáng)度和關(guān)系比例系數(shù)共同決定的混合度和混合權(quán)，而節(jié)點的混合度和混合權(quán)又直接影響到節(jié)點在網(wǎng)絡(luò)中信息傳播的能力，并最終決定了網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的劃分。因此，多關(guān)系社交網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法中至關(guān)重要的一步就是確定各種關(guān)系的關(guān)系強(qiáng)度和關(guān)系比例系數(shù)。

Fig.3 Example of information propagation in multiple relationships network圖3 多關(guān)系網(wǎng)絡(luò)中信息傳播過程示例

本文借鑒多元線性回歸算法[18]的思路，由用戶提供先驗數(shù)據(jù)集，即部分已劃分好社團(tuán)結(jié)構(gòu)的數(shù)據(jù)，使得同一社團(tuán)結(jié)構(gòu)中的節(jié)點兩兩連邊，不在同一個社團(tuán)結(jié)構(gòu)中的節(jié)點間沒有連邊，從而得到社團(tuán)結(jié)構(gòu)分明的目標(biāo)網(wǎng)絡(luò)Gtarget，目標(biāo)網(wǎng)絡(luò)的鄰接矩陣M?表示如下：

根據(jù)得到的目標(biāo)網(wǎng)絡(luò)，通過線性回歸的方法使復(fù)合網(wǎng)中的節(jié)點在子網(wǎng)加載運算后的多關(guān)系R下盡可能擁有與目標(biāo)網(wǎng)絡(luò)中節(jié)點相似的信息傳播能力。首先，根據(jù)先驗數(shù)據(jù)集的數(shù)據(jù)建立一個復(fù)合網(wǎng)，該復(fù)合網(wǎng)在多關(guān)系R下的傳播概率矩陣P?由混合度對角矩陣D?和鄰接混合權(quán)矩陣W?經(jīng)過矩陣運算得到。為了使復(fù)合網(wǎng)中各節(jié)點與目標(biāo)網(wǎng)絡(luò)中的各節(jié)點的傳播能力盡可能相似，就需要通過關(guān)系比例系數(shù)的設(shè)置使復(fù)合網(wǎng)的傳播概率矩陣P?盡可能地擬合目標(biāo)網(wǎng)絡(luò)的傳播概率矩陣P，而關(guān)系比例系數(shù)作為各種關(guān)系在多關(guān)系網(wǎng)絡(luò)中重要性的度量標(biāo)準(zhǔn)，主要影響復(fù)合網(wǎng)中節(jié)點的混合度。因為復(fù)合網(wǎng)中節(jié)點在各子網(wǎng)中的度和目標(biāo)網(wǎng)絡(luò)中的度已知，提取各子網(wǎng)和目標(biāo)網(wǎng)絡(luò)中各個節(jié)點的度分別組成向量和這樣復(fù)合網(wǎng)的混合度對角矩陣與目標(biāo)網(wǎng)絡(luò)的度對角矩陣的擬合就可以轉(zhuǎn)化為提取關(guān)系比例系數(shù)SF=(sf1,sf2,…,sfk)的線性回歸問題，即：

以圖1的復(fù)合網(wǎng)為例，若節(jié)點（0,1,2,3,8）和節(jié)點（4,5,6,7）分別劃分為一個社團(tuán)，則目標(biāo)網(wǎng)絡(luò)如圖4所示。

Fig.4 Target network圖4 目標(biāo)網(wǎng)絡(luò)

目標(biāo)網(wǎng)絡(luò)對應(yīng)的傳播概率矩陣為：

根據(jù)線性回歸算法，計算3種關(guān)系對應(yīng)的關(guān)系比例系數(shù)：

可以將矩陣簡化為：

最后可得：

4.2 多關(guān)系社交網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法

復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)是根據(jù)網(wǎng)絡(luò)節(jié)點的相似性對節(jié)點進(jìn)行劃分，又被稱為復(fù)雜網(wǎng)絡(luò)中的聚類[19]。因此，可以使用數(shù)據(jù)挖掘中的聚類方法發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。本文利用多關(guān)系復(fù)雜網(wǎng)絡(luò)中的信息傳播，將多關(guān)系社交網(wǎng)絡(luò)中的節(jié)點轉(zhuǎn)換為適合聚類算法處理的數(shù)據(jù)結(jié)構(gòu)，并且依據(jù)網(wǎng)絡(luò)中的信息傳播計算網(wǎng)絡(luò)節(jié)點間的相似性，從而將成熟的數(shù)據(jù)挖掘聚類算法應(yīng)用于多關(guān)系社交網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)。

本文在K-means聚類算法[20]的基礎(chǔ)上提出了CSDM(community structure detection in multi-relationships social networks)算法來發(fā)現(xiàn)多關(guān)系社交網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。K-means算法的最大缺點是對初始聚類中心點的選擇敏感，作為聚類中心點的初始值將直接影響到最終聚類的結(jié)果。

復(fù)雜網(wǎng)絡(luò)中通常把節(jié)點的重要性稱為中心性，作為網(wǎng)絡(luò)中刻畫節(jié)點重要性的基礎(chǔ)指標(biāo)，度中心性認(rèn)為節(jié)點的影響力與鄰居節(jié)點的數(shù)量有關(guān)，即鄰居節(jié)點數(shù)目越多，則該節(jié)點在網(wǎng)絡(luò)中的影響力越大。設(shè)節(jié)點vh與節(jié)點vl關(guān)于關(guān)系ri的路徑長度為，定義節(jié)點vh關(guān)于關(guān)系ri的中心度為：

其中，等式右邊分子部分表示與其他所有節(jié)點關(guān)于關(guān)系ri的路徑長度之和的最小值，分母部分表示節(jié)點vh與其他節(jié)點關(guān)于關(guān)系ri的路徑長度之和。中心度的值越接近于1，說明該節(jié)點與其他所有節(jié)點的路徑長度之和越小，其中心地位越強(qiáng)；中心度的值越接近于0，說明其中心地位越弱。

CSDM算法將選取復(fù)合網(wǎng)中中心度較大的節(jié)點作為初始聚類中心點，然后按照經(jīng)典K-means聚類算法的步驟，對多關(guān)系社交網(wǎng)絡(luò)進(jìn)行社團(tuán)結(jié)構(gòu)劃分。算法的具體步驟如下：

輸入：利用復(fù)合網(wǎng)構(gòu)建的多關(guān)系社交網(wǎng)絡(luò)Gcom，網(wǎng)絡(luò)節(jié)點數(shù)N。

輸出：社團(tuán)結(jié)構(gòu)劃分集合Result。

1.根據(jù)先驗數(shù)據(jù)集，構(gòu)建目標(biāo)網(wǎng)絡(luò)Gtarget；

2.構(gòu)建復(fù)合網(wǎng)Gcom，得到復(fù)合網(wǎng)的混合度對角矩陣和鄰接混合權(quán)矩陣?；

3.利用線性回歸算法，根據(jù)目標(biāo)網(wǎng)絡(luò)對角矩陣D，得到復(fù)合網(wǎng)中關(guān)系比例系數(shù)SF=(sf1,sf2,…,sfk)；

5.Result=?；

6.在復(fù)合網(wǎng)中分別以各節(jié)點為初始信源節(jié)點進(jìn)行T次信息傳播，得到可用于聚類的信息量分布向量：

7.選取復(fù)合網(wǎng)中中心度較大的節(jié)點作為初始聚類中心點；

8.利用K-means經(jīng)典算法進(jìn)行聚類：

kmeans=KMeans(clusters).fit(Result)

9.Returnkmeans

5 實驗結(jié)果與分析

5.1 單關(guān)系社交網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)劃分

單關(guān)系網(wǎng)絡(luò)可以視為多關(guān)系復(fù)雜網(wǎng)絡(luò)的一種特例，為了驗證CSDM算法的性能，首先在海豚社會網(wǎng)絡(luò)和Zachary空手道俱樂部網(wǎng)絡(luò)這兩個用于驗證社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法正確性的通用數(shù)據(jù)集中進(jìn)行了社團(tuán)結(jié)構(gòu)劃分實驗，并與GN（Girvan-Newman）算法[21]和Newman快速算法[22]進(jìn)行了比較。

在兩個單關(guān)系網(wǎng)絡(luò)上分別應(yīng)用CSDM算法，所得社團(tuán)結(jié)構(gòu)劃分分別如圖5和圖6所示。

Fig.5 Community detection result of dolphin network圖5 海豚社會網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)劃分結(jié)果

Fig.6 Community detection result of Zachary karate club圖6 Zachary空手道俱樂部社團(tuán)結(jié)構(gòu)劃分結(jié)果

模塊度Q[23]經(jīng)常被選作衡量復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法劃分結(jié)果優(yōu)良的標(biāo)準(zhǔn)，Q值越大，則說明復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)劃分越合理，相應(yīng)的社團(tuán)劃分算法越有效。

表1是CSDM算法、GN算法與Newman快速算法在海豚社會網(wǎng)絡(luò)和Zachary空手道俱樂部網(wǎng)絡(luò)中的社團(tuán)劃分結(jié)果的模塊度值的比較?？梢钥闯鲈赯achary空手道俱樂部網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)劃分上，CSDM算法的模塊度略低于GN算法，但在海豚社會網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)劃分上，CSDM算法的模塊度是最高的。

Table 1 Comparison of modularity value among various algorithms表1 不同算法模塊度值比較

5.2 多關(guān)系社交網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)劃分

CSDM算法主要是為了進(jìn)行多關(guān)系社交網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)劃分的，在實驗中利用AMiner[24]提供的DBLP_citation_network數(shù)據(jù)集來構(gòu)建多關(guān)系社交網(wǎng)絡(luò)以驗證CSDM算法的正確性。

AMiner是一個利用數(shù)據(jù)挖掘和社會網(wǎng)絡(luò)分析等技術(shù)提供語義信息抽取、專家搜索、權(quán)威機(jī)構(gòu)搜索等功能的搜索引擎，其提供的DBLP_citation_network數(shù)據(jù)集[25]包括2 244 021篇論文，4 354 534條引用關(guān)系，AMiner將該數(shù)據(jù)集中的數(shù)據(jù)按照研究領(lǐng)域分為information security、database data mining information retrieval等10個類別，每個類別中包含了文獻(xiàn)名、作者、文獻(xiàn)索引、引用文獻(xiàn)等信息，本實驗從information security、human computer interaction ubiquitous computing、database data mining information retrieval這 3個類別中，共抽取600條出現(xiàn)頻率最高的文獻(xiàn)，與該文獻(xiàn)的作者和其參考文獻(xiàn)索引組成實驗數(shù)據(jù)集。

首先，根據(jù)論文引用關(guān)系建立共引論文關(guān)系網(wǎng)絡(luò)，根據(jù)論文作者關(guān)系建立論文共著關(guān)系網(wǎng)和論文與作者對應(yīng)關(guān)系網(wǎng)。完成三個子網(wǎng)構(gòu)建后，運用多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)的子網(wǎng)加載運算構(gòu)建多關(guān)系復(fù)合網(wǎng)。復(fù)合網(wǎng)中包含論文和作者兩類節(jié)點，論文節(jié)點間的共引論文關(guān)系，作者節(jié)點間的論文共著關(guān)系以及論文和作者節(jié)點間的論文與作者對應(yīng)關(guān)系等三種關(guān)系。

根據(jù)AMiner網(wǎng)站中輸入不同類別關(guān)鍵字進(jìn)行搜索得到的論文和學(xué)者的檢索結(jié)果，剔除某些明顯異常值后作為計算三種關(guān)系對應(yīng)的關(guān)系比例系數(shù)線性回歸分析的數(shù)據(jù)樣本，共選取了200組樣本數(shù)據(jù)進(jìn)行預(yù)測。針對實驗數(shù)據(jù)中多關(guān)系社交網(wǎng)絡(luò)中存在的論文共著關(guān)系r1、論文與作者對應(yīng)關(guān)系r2、共引論文關(guān)系r3，構(gòu)建的三元線性回歸模型如下：

其中，a0、sf1、sf2和sf3為回歸系數(shù)。由于都已經(jīng)將各種關(guān)系的權(quán)重值轉(zhuǎn)化到統(tǒng)一的單位上來，因此就不再有常數(shù)項a0了。

使用最小二乘法進(jìn)行參數(shù)估計，建立方程組如下：

依據(jù)200組樣本數(shù)據(jù)，對方程組求解得到參數(shù)估值的平均值為sf1=1.102，sf2=0.206，sf3=0.208。

針對實驗中構(gòu)建的多關(guān)系社交網(wǎng)絡(luò)進(jìn)行社團(tuán)結(jié)構(gòu)劃分時，設(shè)三種關(guān)系的關(guān)系比例系數(shù)為SF=(1.102,0.206,0.208)，關(guān)系強(qiáng)度均為1，則社團(tuán)結(jié)構(gòu)劃分如圖7所示。

為了衡量多關(guān)系社交網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)劃分效果，定義查準(zhǔn)率和純凈度[26]如下：

其中，f∈F為本次社團(tuán)結(jié)構(gòu)劃分中的一個社團(tuán)結(jié)構(gòu)，a∈A為依據(jù)AMiner官方數(shù)據(jù)進(jìn)行分類的一個類別集合。各個社團(tuán)的查準(zhǔn)率precision是其相對于官方分類各集合能取到的最大準(zhǔn)確率，純凈度purity是劃分結(jié)果中各個社團(tuán)查準(zhǔn)率的加權(quán)平均值，能較為全面地衡量社團(tuán)結(jié)構(gòu)劃分結(jié)果的優(yōu)良。

Regression-based算法[27]是通過用戶的需求來得到關(guān)系的最優(yōu)組合的關(guān)系抽取算法，是一種尋找符合用戶需求的社團(tuán)結(jié)構(gòu)較好的方法。將CSDM算法與Regression-based算法在多關(guān)系社交網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)劃分結(jié)果的純凈度進(jìn)行比較，如表2所示。

Table 2 Comparison of purity value among various algorithms表2 不同算法純凈度比較

從表2可以看到，相比于Regression-based算法，CSDM算法的查準(zhǔn)率略有提高。這說明利用CSDM算法劃分的社團(tuán)結(jié)構(gòu)與實際情況更加吻合。

6 結(jié)束語

現(xiàn)實社交網(wǎng)絡(luò)的節(jié)點間存在著多種關(guān)系，只通過其中某一種關(guān)系對網(wǎng)絡(luò)進(jìn)行社團(tuán)結(jié)構(gòu)劃分難以取得與實際情況較為一致的結(jié)果。本文基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型，通過信息傳播方法將多關(guān)系社交網(wǎng)絡(luò)中的節(jié)點轉(zhuǎn)化成能夠被聚類算法處理的向量形式，進(jìn)而利用傳統(tǒng)聚類算法完成多關(guān)系社交網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)劃分。提出的CSDM算法綜合考慮了現(xiàn)實社交網(wǎng)絡(luò)中多種關(guān)系的相互作用以及異質(zhì)節(jié)點間的相互影響，充分利用網(wǎng)絡(luò)中存在的多種關(guān)系對不同性質(zhì)節(jié)點進(jìn)行準(zhǔn)確的社團(tuán)結(jié)構(gòu)劃分，通過在實際數(shù)據(jù)集上的實驗分析，證明了CSDM算法具有良好的社團(tuán)結(jié)構(gòu)劃分效果。這種將網(wǎng)絡(luò)中異質(zhì)節(jié)點劃分到同一社團(tuán)結(jié)構(gòu)中的技術(shù)，可以應(yīng)用于基于社交網(wǎng)絡(luò)的推薦系統(tǒng)中，用來解決協(xié)同過濾技術(shù)中的稀疏問題和冷啟動問題。

雖然本文所提算法在多關(guān)系社交網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)劃分中具有良好的劃分結(jié)果，但沒有充分考慮各種關(guān)系強(qiáng)度對社團(tuán)結(jié)構(gòu)劃分的影響，每次都需要計算所有子網(wǎng)關(guān)系去調(diào)整各種關(guān)系強(qiáng)度。此外，算法時間復(fù)雜度較高，在分析規(guī)模較大的網(wǎng)絡(luò)時需要較多的時間。因此，如何縮小參數(shù)范圍、去除冗余關(guān)系、降低算法時間復(fù)雜度、改進(jìn)聚類算法是未來的主要工作，如何融合多關(guān)系社交網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)技術(shù)與協(xié)同推薦技術(shù)也是非常值得研究的問題。