劉文星，范 敏+，李金海

1.昆明理工大學(xué) 數(shù)據(jù)科學(xué)研究中心，昆明 650500

2.昆明理工大學(xué) 理學(xué)院，昆明 650500

社會網(wǎng)絡(luò)分析（social network analysis，SNA）起源于物理學(xué)中的適應(yīng)性網(wǎng)絡(luò)。通過研究網(wǎng)絡(luò)關(guān)系及其結(jié)構(gòu)，有助于把個體間相互關(guān)系即“微觀”網(wǎng)絡(luò)與大規(guī)模的社會系統(tǒng)的“宏觀”結(jié)構(gòu)相結(jié)合，從而得到一些有意義的概念、模式和分析結(jié)果。近年來，把復(fù)雜網(wǎng)絡(luò)分析技術(shù)、社會網(wǎng)絡(luò)分析理論與圖論以及社會學(xué)、心理學(xué)、人類學(xué)、數(shù)學(xué)、通信科學(xué)等領(lǐng)域相結(jié)合，逐步發(fā)展成一個非常有潛力的研究分支。它在許多方面獲得了重要的研究成果，比如：生物社區(qū)研究、傳染病網(wǎng)絡(luò)研究、城市化研究、網(wǎng)絡(luò)經(jīng)濟(jì)體系研究等。

社會網(wǎng)絡(luò)分析中的社區(qū)劃分是從網(wǎng)絡(luò)中獲取概念、模式的基礎(chǔ)，也是社會網(wǎng)絡(luò)分析研究中的重點。現(xiàn)有的社會網(wǎng)絡(luò)社區(qū)劃分的研究主要集中在分布式算法設(shè)計、有先驗信息的劃分算法設(shè)計、模糊結(jié)構(gòu)社區(qū)劃分和進(jìn)化網(wǎng)絡(luò)劃分等方面。文獻(xiàn)[1]提出了一種分布式局部搜索算法，該算法是以頂點為中心的計算模型，采用了分布式圖著色策略來區(qū)分相鄰節(jié)點。文獻(xiàn)[2]提出了一種基于信息熵的劃分方法，并運(yùn)用模擬退火算法，引入了一個新的定義，即超邊切分、微切割。文獻(xiàn)[3]主要通過構(gòu)造特征矩陣和網(wǎng)絡(luò)中的先驗內(nèi)容信息提出了一種基于半監(jiān)督矩陣分解和隨機(jī)游走的算法。文獻(xiàn)[4]通過對網(wǎng)絡(luò)的擬合，提出了一種新的假設(shè)檢驗框架，能夠自動確定各種網(wǎng)絡(luò)中的社區(qū)數(shù)量，并且快速檢測模擬網(wǎng)絡(luò)和實際網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。文獻(xiàn)[5]設(shè)計了一種新的鏈路預(yù)測策略，能夠劃分具有模糊社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)。文獻(xiàn)[6]給出了一種基于懲罰矩陣分解的復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法。文獻(xiàn)[7]利用模糊粗糙方法檢測進(jìn)化網(wǎng)絡(luò)中的重疊、非重疊和內(nèi)在社區(qū)。以上研究各有特色，但是均未考慮網(wǎng)絡(luò)節(jié)點自身具有的一些屬性特征。

形式背景下的概念認(rèn)知學(xué)習(xí)是一個新興的交叉研究領(lǐng)域，它由形式概念分析、粗糙集、粒計算和認(rèn)知計算等理論融合而來。近年來，在大數(shù)據(jù)環(huán)境下的概念認(rèn)知學(xué)習(xí)中表現(xiàn)出諸多的認(rèn)知優(yōu)勢，也取得了許多有價值的研究成果[8-10]。比如，文獻(xiàn)[11]提出的概念認(rèn)知模型為后續(xù)進(jìn)一步研究提供了參考[12]。文獻(xiàn)[13]闡述了從多個視角研究概念認(rèn)知的重要性。文獻(xiàn)[14]討論了概念認(rèn)知系統(tǒng)的迭代算法。形式背景下的概念分類是進(jìn)行概念認(rèn)知的基礎(chǔ)和前提。文獻(xiàn)[15]在文獻(xiàn)[16]的基礎(chǔ)上設(shè)計了一個新的并行概念學(xué)習(xí)框架，以滿足增量式分類任務(wù)的要求。文獻(xiàn)[17]從屬性拓?fù)涞慕嵌忍接懥烁拍钫J(rèn)知學(xué)習(xí)。文獻(xiàn)[18]采用按類標(biāo)號進(jìn)行劃分的方法對形式背景進(jìn)行劃分，并把劃分后的形式背景按屬性項分割。文獻(xiàn)[19]指出形式背景拆分的方法可以采用粗糙集中等價類劃分的方法來完成?，F(xiàn)有的概念認(rèn)知研究為網(wǎng)絡(luò)上的概念認(rèn)知和網(wǎng)絡(luò)社區(qū)劃分提供了堅實的理論基礎(chǔ)。

基于上述討論，不難發(fā)現(xiàn)傳統(tǒng)的社會網(wǎng)絡(luò)社區(qū)劃分沒有考慮網(wǎng)絡(luò)節(jié)點的屬性信息，而這些信息在某些方面的作用明顯，因為它反映了節(jié)點的內(nèi)涵與特征，對社區(qū)劃分具有重要意義。而傳統(tǒng)的形式背景下的劃分，沒有考慮研究對象所處的網(wǎng)絡(luò)及其結(jié)構(gòu)。因此，有必要把二者結(jié)合起來，對網(wǎng)絡(luò)形式背景下的網(wǎng)絡(luò)社區(qū)劃分進(jìn)行研究，從而使得生成的網(wǎng)絡(luò)社區(qū)分類既能描述其網(wǎng)絡(luò)特征，又能體現(xiàn)出其概念內(nèi)涵特征，這對網(wǎng)絡(luò)數(shù)據(jù)挖掘與網(wǎng)絡(luò)概念認(rèn)知具有重要的理論意義和實際應(yīng)用價值。

現(xiàn)有研究還表明，社會網(wǎng)絡(luò)的不同角色在網(wǎng)絡(luò)中的地位不同。某些網(wǎng)絡(luò)，從其中一個角色出發(fā)形成的社區(qū)更有意義。比如：營銷網(wǎng)絡(luò)中以賣家出發(fā)形成的社區(qū)就更有意義，這種特點對應(yīng)著單角色網(wǎng)絡(luò)社區(qū)劃分。而有些網(wǎng)絡(luò)中，不同角色形成的社區(qū)具有不同的含義。比如：學(xué)術(shù)網(wǎng)絡(luò)中，引用者形成的社區(qū)和被引用者形成的社區(qū)就有不同的含義，這種特點對應(yīng)著雙角色網(wǎng)絡(luò)社區(qū)劃分。同時某些作者引用別人和被別人引用都比較多，那么綜合這兩種角色形成的學(xué)術(shù)活躍度相似社區(qū)也能夠被刻畫出來。因此，在進(jìn)行網(wǎng)絡(luò)社區(qū)劃分之前，先應(yīng)該區(qū)分該網(wǎng)絡(luò)的特點：適用于單角色網(wǎng)絡(luò)社區(qū)劃分還是雙角色網(wǎng)絡(luò)社區(qū)劃分。在此基礎(chǔ)上，結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點屬性對網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，這將使得網(wǎng)絡(luò)劃分更高效地貼合實際情況。

文獻(xiàn)[8]構(gòu)造了網(wǎng)絡(luò)形式背景，主要得到了網(wǎng)絡(luò)概念等。本文將在文獻(xiàn)[8]的基礎(chǔ)上，把網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與屬性相結(jié)合，對網(wǎng)絡(luò)社區(qū)劃分進(jìn)行研究。

1 基礎(chǔ)理論

本章介紹網(wǎng)絡(luò)形式背景中的基本概念，如形式概念、節(jié)點的中心度、網(wǎng)絡(luò)的中心勢、網(wǎng)絡(luò)社區(qū)概念，詳見文獻(xiàn)[8,20-21]。

定義1四元組(U,M,A,I)稱為網(wǎng)絡(luò)形式背景，其中U={x1,x2,…,xn}是非空有限節(jié)點集，M={M1,M2,…,Mk}是網(wǎng)絡(luò)的結(jié)構(gòu)矩陣，Mt(t=1,2,…,k) 為網(wǎng)絡(luò)的t階鄰接矩陣,A={a1,a2,…,am} 是非空有限屬性集，I={I1,I2,…,Ik,Ik+1}，I1,I2,…,Ik是笛卡兒積U×U上的二元關(guān)系，Ik+1是笛卡兒積U×A上的二元關(guān)系。約定，(xi,xj)∈Il(l=1,2,…,k)表示節(jié)點xi和xj是l階鄰接的，(xi,ap)∈Ik+1表示節(jié)點xi擁有屬性ap。

表1 給出了網(wǎng)絡(luò)形式背景的二維表。實際上，一個網(wǎng)絡(luò)形式背景對應(yīng)著一個網(wǎng)絡(luò)。因此，如無特別說明，下文中提到的網(wǎng)絡(luò)均指網(wǎng)絡(luò)形式背景對應(yīng)的網(wǎng)絡(luò)。

Table 1 Network formal context (U,M,A,I)表1 網(wǎng)絡(luò)形式背景(U,M,A,I)

定義2給定網(wǎng)絡(luò)形式背景(U,M,A,I)，對于任意X?U,B?A，定義：

其中，X*表示X中所有對象共同擁有的屬性組成的集合；B*表示擁有B中所有屬性的對象組成的集合。如果X*=B且B*=X，那么稱(X,B)為形式概念。

在有向圖中，需要討論網(wǎng)絡(luò)節(jié)點的入度中心度和出度中心度。

定義3節(jié)點xi的入度中心度和出度中心度分別定義為：

其中，Jin表示與xi形成入度的節(jié)點的下標(biāo)構(gòu)成的集合，Jout表示與xi形成出度的節(jié)點的下標(biāo)構(gòu)成的集合。特別地，在無向圖中，中心度記為cD(i)。

在有向圖中，節(jié)點的相對中心度區(qū)分為入度相對中心度和出度相對中心度：

定義4網(wǎng)絡(luò)的中心勢定義為：

定義5對于網(wǎng)絡(luò)形式背景(U,M,A,I)，稱三元組(M,C,C*)為網(wǎng)絡(luò)社區(qū)C的對象概念，簡稱為社區(qū)對象概念；同理，稱為屬性B對應(yīng)的網(wǎng)絡(luò)屬性概念，簡稱為社區(qū)屬性概念。(M,C,C*)、統(tǒng)稱為網(wǎng)絡(luò)社區(qū)概念。

此外，M={M1,M2}為網(wǎng)絡(luò)社區(qū)概念的網(wǎng)絡(luò)特征值，為社區(qū)概念的平均度，它表示社區(qū)概念內(nèi)部平均重要度，為社區(qū)概念的平均勢，它表示社區(qū)概念內(nèi)部的差異程度。

(M,C,C*)中的C*可能為空，此時說明這些對象雖然能劃分在同一社區(qū)，但沒有共同屬性。換言之，將共有算子進(jìn)一步弱化成似然算子，就可以從另一個角度定義另一種網(wǎng)絡(luò)社區(qū)概念。

其次，在有向圖中，網(wǎng)絡(luò)的中心勢區(qū)分為入度中心勢和出度中心勢：

在有向網(wǎng)絡(luò)中，網(wǎng)絡(luò)社區(qū)概念的網(wǎng)絡(luò)特征參數(shù)M 也需要區(qū)分入度和出度的情況：，。因此，網(wǎng)絡(luò)社區(qū)概念在有向圖中分為入度網(wǎng)絡(luò)概念和出度網(wǎng)絡(luò)概念，分別記為(Min,C,C*)、。

2 網(wǎng)絡(luò)社區(qū)劃分

本章主要從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與屬性相結(jié)合的角度對網(wǎng)絡(luò)社區(qū)進(jìn)行劃分研究。具體地，先找到網(wǎng)絡(luò)中度最大的節(jié)點，再找到與其相連的其他節(jié)點，并將具有一定屬性相似度的相連節(jié)點劃為一類。

2.1 單角色網(wǎng)絡(luò)社區(qū)劃分

定義6對象xi的k階鄰接集定義為：

它表示與對象xi有k階鄰接關(guān)系的對象構(gòu)成的集合。特別地，一階的情形記為Link(xi)。

定義7對象xi的β∈[0,1]屬性相似集定義為：

它表示與對象xi有屬性相似程度達(dá)到β以上的對象構(gòu)成的集合。

下面給出基于網(wǎng)絡(luò)結(jié)構(gòu)與節(jié)點屬性相結(jié)合的網(wǎng)絡(luò)劃分算法。

算法1基于網(wǎng)絡(luò)結(jié)構(gòu)與節(jié)點屬性的單角色網(wǎng)絡(luò)劃分算法

輸入：網(wǎng)絡(luò)形式背景(U,M,A,I)和β值。

輸出：劃分的對象塊CL。

步驟1計算網(wǎng)絡(luò)中每個節(jié)點的出（入）度。

步驟2從出（入）度最大的節(jié)點xi開始，計算Link(xi)。

步驟3在Link(xi)中計算，令CL={Link(xi),，并刪除M中的CL。

步驟4判斷M中是否存在不為0 的元素，若有則返回步驟2；否則，輸出CL，算法結(jié)束。未進(jìn)行分類的對象，單獨劃為一類。

在上述算法中，步驟1 的時間復(fù)雜度為O(n)（n為網(wǎng)絡(luò)形式背景中的對象個數(shù)），步驟2 的時間復(fù)雜度為O(n2)，步驟3 和步驟4 的時間復(fù)雜度為O(n2)，因此算法1 的時間復(fù)雜度為O(n2)。

算法1 是在單角色網(wǎng)絡(luò)中考慮網(wǎng)絡(luò)的出（入）度，研究網(wǎng)絡(luò)社區(qū)劃分；同樣，也可以考慮在無向網(wǎng)絡(luò)中討論社區(qū)劃分問題，只需把算法1 中節(jié)點的出（入）度替換成節(jié)點的度即可。

2.2 雙角色網(wǎng)絡(luò)社區(qū)劃分

類似于2.1 節(jié)，也可以給出基于網(wǎng)絡(luò)結(jié)構(gòu)與節(jié)點屬性的雙角色網(wǎng)絡(luò)劃分算法。

算法2基于網(wǎng)絡(luò)結(jié)構(gòu)與節(jié)點屬性的雙角色網(wǎng)絡(luò)劃分算法

輸入：網(wǎng)絡(luò)形式背景(U,M,A,I)和β值。

輸出：劃分的對象塊CL。

步驟1重復(fù)調(diào)用算法1，將其輸出結(jié)果分別記為CL1和CL2，其中CL1為出度劃分結(jié)果，CL2為入度劃分結(jié)果。

步驟2計算網(wǎng)絡(luò)中每個節(jié)點的度，它是入度與出度之和。

步驟3從度最大的節(jié)點xi開始，計算Link(xi)。

步驟4在Link(xi)中計算，記CL3={Link(xi),，并刪除M中的CL3。

步驟5判斷M中是否存在不為0 的元素，若有則返回步驟2；否則，輸出CL3，算法結(jié)束。未進(jìn)行分類的對象，單獨劃為一類。

由于算法2 與算法1 的基本步驟相同，只是同時計算了節(jié)點的入度和出度，因此算法2 的時間復(fù)雜度也為O(n2)。

3 實例分析

例1圖1 是一個社交營銷網(wǎng)絡(luò)，其中x1～x10表示研究對象，xi到xj的弧表示xi將貨物賣給xj。由圖1可得表2 中的網(wǎng)絡(luò)形式背景。下面利用算法1 對該網(wǎng)絡(luò)進(jìn)行劃分。

考慮出度的情況下計算網(wǎng)絡(luò)分類，具體過程如下：

（1）計算網(wǎng)絡(luò)中10 個節(jié)點的出度，則節(jié)點x1～x10的出度依次為4、0、2、0、0、0、1、0、1、0。

Fig.1 Network C圖1 網(wǎng)絡(luò)C

（2）找到出度最大的節(jié)點為x1，計算Link(x1)={x2,x4,x5,x8}。

（3）在集合Link(x1)={x2,x4,x5,x8}中計算出{x2,x4,x5,x8}，則第一個分類為CL={x1,x2,x4,x5,x8}，刪除節(jié)點x1,x2,x4,x5和x8的度，此時節(jié)點x1～x10的度依次為0、0、2、0、0、0、1、0、1、0。

（4）計算出此時度最大的節(jié)點為x3，Link(x3)={x10}，在Link(x3)中計算，則第二個分類為CL={x3,x10}，刪除節(jié)點x3和x10的度，此時節(jié)點x1～x10的度依次為0、0、0、0、0、0、1、0、1、0。

（5）計算出此時度最大的第一個節(jié)點為x7，Link(x7)=?，則第三個分類為CL={x7}，刪除節(jié)點x7的度，此時節(jié)點x1～x10的度依次為0、0、0、0、0、0、1、0、1、0。

（6）計算出此時度最大的第一個節(jié)點為x9，計算Link(x9)=?，則第四個分類為CL={x9}，刪除節(jié)點x9的度，此時節(jié)點x1～x10的度依次為0、0、0、0、0、0、0、0、0、0。

（7）此時，網(wǎng)絡(luò)中10 個節(jié)點的出度均為0，孤立點x6單獨歸為一類，即第五個類CL={x6}。綜上，得到以下社區(qū)劃分結(jié)果：

即該網(wǎng)絡(luò)總共分為5 個營銷社區(qū)。

下面繼續(xù)對5 個社區(qū)的網(wǎng)絡(luò)特征值進(jìn)行分析：

Table 2 Network formal context (U,M,A,I) of network in Fig.1表2 圖1 的網(wǎng)絡(luò)對應(yīng)的網(wǎng)絡(luò)形式背景(U,M,A,I)

在該社交營銷網(wǎng)絡(luò)中，社區(qū)C1和C2的平均度差別不大，說明兩個賣家社區(qū)在網(wǎng)絡(luò)當(dāng)中的重要性差別不大。但C1和C2的平均勢差別較大，說明兩個社區(qū)內(nèi)部的賣家之間的重要性差別較大，這是因為在社區(qū)C1中含有x1，其重要性很大。

在該網(wǎng)絡(luò)中買家x6、x7和x9沒有售賣商品，因此在售賣網(wǎng)絡(luò)中重要性為0，故它們的網(wǎng)絡(luò)特征值M1=M2=0。

下面的例2 給出了一個雙角色網(wǎng)絡(luò)的社區(qū)劃分，以說明算法2 具體如何實施。

例2圖2 是一個學(xué)術(shù)引用網(wǎng)絡(luò)，網(wǎng)絡(luò)中節(jié)點x1～x20表示20 位作者，字母a～i表示網(wǎng)絡(luò)中作者經(jīng)常使用的關(guān)鍵字。從節(jié)點x1指向節(jié)點x10的箭頭表示作者x1引用了作者x10的文章。圖2 對應(yīng)的網(wǎng)絡(luò)形式背景(U,M,A,I)可由表3 和表4 合并得到，其中表3 為網(wǎng)絡(luò)中節(jié)點之間的連接關(guān)系，即作者間的引用關(guān)系，表4 為網(wǎng)絡(luò)中各對象所擁有的屬性。

Fig.2 Academic citation network圖2 學(xué)術(shù)引用網(wǎng)絡(luò)

（1）依據(jù)算法2，先考慮基于出度的劃分，設(shè)β=0.2。從網(wǎng)絡(luò)中出度最大的節(jié)點x2開始劃分，可以得到以下分類：

Table 3 Connection relation of network formal context (U,M,A,I) of Fig.2表3 圖2 對應(yīng)的網(wǎng)絡(luò)形式背景(U,M,A,I)的連接關(guān)系

Table 4 Attributes possessed by objects in network formal context (U,M,A,I) of Fig.2表4 圖2 對應(yīng)的網(wǎng)絡(luò)形式背景(U,M,A,I)所含對象擁有的屬性

選取社區(qū)C2,C6和C7進(jìn)行網(wǎng)絡(luò)特征值的討論，先分析社區(qū)C2：

同理可以得到出度對象形式概念：

引用者社區(qū)C6和C7的平均度差別較大，說明它們在網(wǎng)絡(luò)中的重要性差別較大。而兩社區(qū)平均勢差小，說明兩者內(nèi)部的引用者之間的差異小。

（2）考慮基于入度的劃分，設(shè)β=0.2。可以得到以下分類：

此處，選取C4進(jìn)行網(wǎng)絡(luò)特征值分析：

節(jié)點x12的入度為13，而節(jié)點x2的入度為14，兩者均為度較大的節(jié)點。同理，設(shè)β=0.2，以節(jié)點x12作為起始節(jié)點進(jìn)行分類，可得以下分類結(jié)果：

節(jié)點x8的入度為11，在整個網(wǎng)絡(luò)中屬于度較大的節(jié)點，指向它的節(jié)點為：

而這些節(jié)點大部分未與節(jié)點x8分為一類，主要原因是這些節(jié)點雖然與節(jié)點x8相連，但并不具有相同的屬性。因此，在劃分時，不僅要考慮節(jié)點的Link值，還要考慮節(jié)點所擁有的屬性。

（3）考慮基于綜合度的劃分，設(shè)β=0.2，可得以下分類：

這里僅選取C2進(jìn)行網(wǎng)絡(luò)特征值分析：

則M1=2.14,M2=0.21。故可得綜合度對象形式概念為({2.14,0.21},{x10,x18,x19},{a,j})，其中表示社區(qū)C2中的作者共同使用的關(guān)鍵字為a和j，M1=2.14 表示平均度，社區(qū)C2中節(jié)點重要性為2.14，M2=0.21 表示社區(qū)C2中節(jié)點之間影響力差異為0.21。

可以發(fā)現(xiàn)，在網(wǎng)絡(luò)社區(qū)劃分研究中，從不同的角度解決問題，如考慮入度、出度和綜合度，得到的社區(qū)劃分結(jié)果是不同的。

4 結(jié)束語

本文主要提出了網(wǎng)絡(luò)結(jié)構(gòu)和屬性信息相結(jié)合的網(wǎng)絡(luò)社區(qū)劃分方法。該方法兼顧了網(wǎng)絡(luò)的結(jié)構(gòu)特點和網(wǎng)絡(luò)中節(jié)點所擁有的內(nèi)涵屬性。它可以針對不同網(wǎng)絡(luò)中結(jié)構(gòu)與屬性的特點，選取不同的相似閾值對網(wǎng)絡(luò)進(jìn)行社區(qū)劃分以得到社區(qū)特征值，從而更好地對網(wǎng)絡(luò)社區(qū)進(jìn)行認(rèn)知學(xué)習(xí)。在本文給出的網(wǎng)絡(luò)劃分算法的基礎(chǔ)上，今后可以進(jìn)一步研究以下問題：（1）基于網(wǎng)絡(luò)形式背景的網(wǎng)絡(luò)規(guī)則提?。唬?）非冗余網(wǎng)絡(luò)規(guī)則的快速提取算法；（3）保持非冗余網(wǎng)絡(luò)規(guī)則不變的知識約簡；（4）節(jié)點屬性特征矩陣為先驗信息的網(wǎng)絡(luò)劃分以及關(guān)聯(lián)規(guī)則挖掘等。