多關系社交網絡中社團結構發現算法*

江淼淼，孫更新，賓 晟

青島大學 數據科學與軟件工程學院，山東 青島 266071

1 引言

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

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

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

本文利用多關系社交網絡中信息傳播的特性，在分析復雜網絡傳統的社團結構劃分算法基礎上，利用多子網復合復雜網絡模型的混合度和混合權[14]計算多關系綜合影響強度，提出基于該模型的多關系社交網絡的社團結構劃分算法。在海豚社會網絡和空手道俱樂部網絡[15]驗證了該算法對于單關系網絡中社團結構劃分的正確性，并利用AMiner數據集構建論文合作多關系社交網絡，通過多元線性回歸算法得到網絡中不同關系的影響強度，取得了良好的社團結構劃分結果。

2 多子網復合復雜網絡模型

2.1 定義

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

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

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

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

（4）映射是邊集E經過φ函數投影在F中找到唯一對應的映射，表示邊上具有的關系類型。

2.2 子網加載運算

通過復合網中定義的子網加載運算可以將若干個復雜網絡組成新的復合復雜網絡。子網加載運算能復合兩個或兩個以上的復雜網絡，新的復合網的關系向量空間維數增大，其相關節點間相互關系的變化可通過空間向量的相關運算完成。

子網加載運算的具體定義如下：

（1）V=V1∪V2；

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

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

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

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

稱R′為加載關系集合，vh,vl∈V1×V2為外部邊，vh、vl為邊界節點。

圖1所示為由3個向量復合網Σ1、Σ2和Σ3通過子網加載運算構建多關系復合網的過程。3個向量復合網對應關系分別為r1、r2、r3，對應關系強度dom(r1)={1},dom(r2)={2},dom(r3)={3}，以向量復合網Σ1為基底，將Σ2作為子網加載到Σ1上，加載映射關系強度映射為，類似地繼續加載子網Σ3。

2.3 節點混合權和節點混合度

節點混合權：設節點vh∈V，關系強度比例系數(sf1,sf2,…,sfk)，則節點vh的混合權：

其中，為節點關于關系的權。

節點混合度：設節點vh∈V，關系強度比例系數(sf1,sf2,…,sfk)，則節點vh的混合度為：

以圖1為例，設定關系r1、r2、r3的權均為0.5，其關系強度比例系數sf1、sf2、sf3均為1，節點0關于關系r1的度，關于關系r2的度，關于關系r3的度，則節點0的混合度1=5，節點0關于關系r1的權，關于關系r2的權，關于關系r3的權，則節點0的混合權為

3 復雜網絡中的信息傳播

3.1 單關系復雜網絡上的信息傳播過程

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

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

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

圖2是一個簡單的復雜網絡，其傳播概率矩陣P為：

Fig.2 Example of single relationship complex network圖2 單關系復雜網絡示例

分別以節點0、2、7作為初始信源節點，則網絡中初始信息分布可以分別表示為：

設置傳播次數T=3，得到信息在全部網絡節點上的最終分布情況：

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}

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

3.2 多子網復合復雜網絡模型上的信息傳播過程

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

復合網信息傳播概率矩陣P?具體定義如下：

其中，?為節點混合度組成的對角矩陣，?為網絡的鄰接混合權矩陣，該矩陣中的元素可表示為：

鄰接混合權矩陣中的元素是對節點vh和節點vl間所存在的各種關系的關系強度的加權求和。其中，sfri表示節點vh和節點vl之間關于關系ri的關系強度比例系數，kri′為關系ri的關系強度。

在鄰接混合權矩陣的基礎上，節點vh的混合權也可表示為：

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

以圖1中的復合網為例，多關系復合網上信息傳播過程如圖3所示。

設3種關系的比例系數均為1，關系強度分別為1、2、3，節點0為源節點X0=(1,0,0,0,0,0,0,0)，則P?計算如下：

4 基于信息傳播的多關系社交網絡社團結構發現算法

4.1 關系強度和關系系數的計算

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

Fig.3 Example of information propagation in multiple relationships network圖3 多關系網絡中信息傳播過程示例

本文借鑒多元線性回歸算法[18]的思路，由用戶提供先驗數據集，即部分已劃分好社團結構的數據，使得同一社團結構中的節點兩兩連邊，不在同一個社團結構中的節點間沒有連邊，從而得到社團結構分明的目標網絡Gtarget，目標網絡的鄰接矩陣M?表示如下：

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

以圖1的復合網為例，若節點（0,1,2,3,8）和節點（4,5,6,7）分別劃分為一個社團，則目標網絡如圖4所示。

Fig.4 Target network圖4 目標網絡

目標網絡對應的傳播概率矩陣為：

根據線性回歸算法，計算3種關系對應的關系比例系數：

可以將矩陣簡化為：

最后可得：

4.2 多關系社交網絡社團結構發現算法

復雜網絡中的社團結構是根據網絡節點的相似性對節點進行劃分，又被稱為復雜網絡中的聚類[19]。因此，可以使用數據挖掘中的聚類方法發現復雜網絡中的社團結構。本文利用多關系復雜網絡中的信息傳播，將多關系社交網絡中的節點轉換為適合聚類算法處理的數據結構，并且依據網絡中的信息傳播計算網絡節點間的相似性，從而將成熟的數據挖掘聚類算法應用于多關系社交網絡的社團結構發現。

本文在K-means聚類算法[20]的基礎上提出了CSDM(community structure detection in multi-relationships social networks)算法來發現多關系社交網絡中的社團結構。K-means算法的最大缺點是對初始聚類中心點的選擇敏感，作為聚類中心點的初始值將直接影響到最終聚類的結果。

復雜網絡中通常把節點的重要性稱為中心性，作為網絡中刻畫節點重要性的基礎指標，度中心性認為節點的影響力與鄰居節點的數量有關，即鄰居節點數目越多，則該節點在網絡中的影響力越大。設節點vh與節點vl關于關系ri的路徑長度為，定義節點vh關于關系ri的中心度為：

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

CSDM算法將選取復合網中中心度較大的節點作為初始聚類中心點，然后按照經典K-means聚類算法的步驟，對多關系社交網絡進行社團結構劃分。算法的具體步驟如下：

輸入：利用復合網構建的多關系社交網絡Gcom，網絡節點數N。

輸出：社團結構劃分集合Result。

1.根據先驗數據集，構建目標網絡Gtarget；

2.構建復合網Gcom，得到復合網的混合度對角矩陣和鄰接混合權矩陣?；

3.利用線性回歸算法，根據目標網絡對角矩陣D，得到復合網中關系比例系數SF=(sf1,sf2,…,sfk)；

5.Result=?；

6.在復合網中分別以各節點為初始信源節點進行T次信息傳播，得到可用于聚類的信息量分布向量：

7.選取復合網中中心度較大的節點作為初始聚類中心點；

8.利用K-means經典算法進行聚類：

kmeans=KMeans(clusters).fit(Result)

9.Returnkmeans

5 實驗結果與分析

5.1 單關系社交網絡社團結構劃分

單關系網絡可以視為多關系復雜網絡的一種特例，為了驗證CSDM算法的性能，首先在海豚社會網絡和Zachary空手道俱樂部網絡這兩個用于驗證社團結構發現算法正確性的通用數據集中進行了社團結構劃分實驗，并與GN（Girvan-Newman）算法[21]和Newman快速算法[22]進行了比較。

在兩個單關系網絡上分別應用CSDM算法，所得社團結構劃分分別如圖5和圖6所示。

Fig.5 Community detection result of dolphin network圖5 海豚社會網絡社團結構劃分結果

Fig.6 Community detection result of Zachary karate club圖6 Zachary空手道俱樂部社團結構劃分結果

模塊度Q[23]經常被選作衡量復雜網絡社團結構發現算法劃分結果優良的標準，Q值越大，則說明復雜網絡社團結構劃分越合理，相應的社團劃分算法越有效。

表1是CSDM算法、GN算法與Newman快速算法在海豚社會網絡和Zachary空手道俱樂部網絡中的社團劃分結果的模塊度值的比較。可以看出在Zachary空手道俱樂部網絡的社團結構劃分上，CSDM算法的模塊度略低于GN算法，但在海豚社會網絡社團結構劃分上，CSDM算法的模塊度是最高的。

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

5.2 多關系社交網絡社團結構劃分

CSDM算法主要是為了進行多關系社交網絡中社團結構劃分的，在實驗中利用AMiner[24]提供的DBLP_citation_network數據集來構建多關系社交網絡以驗證CSDM算法的正確性。

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

首先，根據論文引用關系建立共引論文關系網絡，根據論文作者關系建立論文共著關系網和論文與作者對應關系網。完成三個子網構建后，運用多子網復合復雜網絡的子網加載運算構建多關系復合網。復合網中包含論文和作者兩類節點，論文節點間的共引論文關系，作者節點間的論文共著關系以及論文和作者節點間的論文與作者對應關系等三種關系。

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

其中，a0、sf1、sf2和sf3為回歸系數。由于都已經將各種關系的權重值轉化到統一的單位上來，因此就不再有常數項a0了。

使用最小二乘法進行參數估計，建立方程組如下：

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

針對實驗中構建的多關系社交網絡進行社團結構劃分時，設三種關系的關系比例系數為SF=(1.102,0.206,0.208)，關系強度均為1，則社團結構劃分如圖7所示。

為了衡量多關系社交網絡社團結構劃分效果，定義查準率和純凈度[26]如下：

其中，f∈F為本次社團結構劃分中的一個社團結構，a∈A為依據AMiner官方數據進行分類的一個類別集合。各個社團的查準率precision是其相對于官方分類各集合能取到的最大準確率，純凈度purity是劃分結果中各個社團查準率的加權平均值，能較為全面地衡量社團結構劃分結果的優良。

Regression-based算法[27]是通過用戶的需求來得到關系的最優組合的關系抽取算法，是一種尋找符合用戶需求的社團結構較好的方法。將CSDM算法與Regression-based算法在多關系社交網絡中社團結構劃分結果的純凈度進行比較，如表2所示。

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

從表2可以看到，相比于Regression-based算法，CSDM算法的查準率略有提高。這說明利用CSDM算法劃分的社團結構與實際情況更加吻合。

6 結束語

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

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