楊 揚，張 馳

（中國科學技術大學 電子工程與信息科學系 中國科學院電磁空間信息重點實驗室，安徽 合肥 230027）

0 引 言

信息產業(yè)的高速發(fā)展，使得互聯(lián)網(wǎng)逐漸深入人們的生產生活。在線的社交逐漸成為人們交流信息、交換利益和建立社會關系的重要方式。同時，這些社交的關系數(shù)據(jù)事實上蘊含了現(xiàn)實中對象的大量信息。通過對各種各樣社交網(wǎng)絡中的關系數(shù)據(jù)進行挖掘，可以發(fā)掘出網(wǎng)絡中對象的社交圈、行為模式和社會角色。通常，實際中的網(wǎng)絡出于隱私保護的需求，其節(jié)點和邊都經(jīng)過匿名化的處理。因此，對于網(wǎng)絡拓撲結構數(shù)據(jù)的研究是挖掘網(wǎng)絡信息一個重要手段[1]。

在當今數(shù)據(jù)時代，數(shù)據(jù)量和信息量爆炸，所面對的網(wǎng)絡數(shù)據(jù)也極為巨大。面對紛繁復雜的網(wǎng)絡結構數(shù)據(jù)，從中挖掘出有用的信息也有極大的理論和實際意義。因此，需要將大規(guī)模的網(wǎng)絡數(shù)據(jù)進行簡化和去冗余，提取圖中的語義信息，為進一步研究、理論分析和應用提供基礎和幫助。

1 基本概念、研究現(xiàn)狀及問題

1.1 圖、子結構和結構語義

用一個二元組G=(V,E)來表示圖或者網(wǎng)絡，其中V和E分別表示圖中的點集合邊集，對應網(wǎng)絡中的對象集合和它們之間的關系集合。兩個點u、v之間有關系，如果它們之間存在一條邊e={u,v}相連。僅研究網(wǎng)絡的拓撲結構而不考慮其所具有的標簽和權值，這在現(xiàn)實中可以對應匿名的社交網(wǎng)絡，或者其他一切無標簽或者去標簽的網(wǎng)絡。

通常來說，圖中的某些子圖或子結構具有顯著的特征，這個“特征”可以是多種多樣的，如稠密性特征可以對應到派系（Clique），相似性特征可以反映到二部圖（Bipartite）上，相對稠密度則可以定義社區(qū)或社團（Community）的概念。子結構和子圖指的是同一個對象，只不過在強調子圖的結構方面時也稱子圖為子結構。

在社交網(wǎng)絡或者更多網(wǎng)絡中，子結構包含了圖中點的一些語義信息，這是由于不同的結構類型具有不同的意義，蘊含了不同的連接模式信息。此外，局部的子結構通過一些重疊關系組合而成整體的網(wǎng)絡[2-3]。它們之間的這種重疊關系也反映了網(wǎng)絡從局部結構到整體之間的關系，也是網(wǎng)絡拓撲信息的一部分?？梢哉f，網(wǎng)絡的子圖特征和組合方式是網(wǎng)絡結構數(shù)據(jù)的拓撲語義。

一直以來，社交網(wǎng)絡的主要結構被認為是社團或者簇（Cluster）。對于社團的挖掘算法，是基于對社團的不同理解和定義[4]。然而，對于社團的進一步結構語義并沒有更多挖掘。事實上，社團也是一種特殊的子結構，即內部連接相對外部更緊密的結構。按照這種稠密性定義，社團的語義是指具有較多相互聯(lián)系團體。當然，社團也有不同的定義，但認為社團是一個基于某種相似目標或者共性而連接較為緊密的團體。通過這種語義，社團內部的點是無法區(qū)分的。

事實上，圖中的子結構并不僅限于社團，圖中的稀疏結構仍然具有一定的意義。典型的星（Star）結構是一個稀疏的子圖。它的語義是指一對多的一種團體關系。在團體內部，樞紐點（Hub-node）是這個子圖的中心或者領頭，信息通常通過這個點發(fā)布最快，而剩余的輻點（Spokes）是這個子圖的信息接收點或者采集點。派系是聚集的朋友圈的代表，其語義是具有兩兩社交關系的團體，在團體內部的點與其他點都具有關系，也是一種特殊的社團。通常的派系并不見得完美，即會存在一些派系中的點與其他點之間沒有直接的連接關系。但是，這不妨礙它成為一個緊密聯(lián)系的團體，稱為近派系。其他的稀疏子圖如樹（Tree）和鏈（Chain），則分別刻畫了一種層次的上下級連接關系和前后相繼的傳遞關系語義。二部圖則表明兩個相對的團體，團體內部是具有相似鄰居集合的點集。由于在現(xiàn)實中的網(wǎng)絡中較為常見，將這5種子圖（如圖1所示）以及近派系作為基本的語義模板（Template）。由于后面將通過這個模板來編碼子圖，也稱它為字典模板。

圖1 基本的語義模板

圖的拓撲結構語義不僅包括子圖的類型或者說子圖的局部結構語義，還包括子圖之間的關系。子圖之間的關系最重要的是重疊關系。當兩個子圖共享一個點時，表明這個公共點可能存在兩個不同的身份或角色，亦或是連接兩個團體的中間人。當兩個子圖存在重疊邊時，表明這個連接關系對應的兩個點已經(jīng)同時隸屬兩個團體，且它們在不同的團體中同時存在關系。子圖重疊程度的判斷，是一個困難的問題，需要從圖的實際情況出發(fā)，挖掘出其所具有的真實結構。

1.2 研究現(xiàn)狀與問題

現(xiàn)有的社區(qū)發(fā)現(xiàn)算法、圖分解算法和圖聚類算法，是解構網(wǎng)絡拓撲結構的有效手段之一。常用的社區(qū)發(fā)現(xiàn)算法雖然基于稠密度[5]、相似度[6]和模塊度[7]特征得到了一些不同語義的社區(qū)，但是網(wǎng)絡中的結構多樣，不限于社區(qū)。為此，存在很多專門挖掘網(wǎng)絡中局部子圖的方法[8-9]，但其總是針對具體的單一子結構，有的挖掘算法具有較高的復雜度，且每種子結構的挖掘標準不同。Navlakha等人[10]首次將信息論中的最小描述長度（Minimum Description Length，MDL）準則[11]作為統(tǒng)一的標準來評判結構挖掘算法的優(yōu)劣，然而僅涉及了網(wǎng)絡中的二部圖結構。之后，Koutra等人[12]結合最小描述長度準則提出了Vog的網(wǎng)絡的拓撲語義理解框架，將多種子結構采用統(tǒng)一的方法進行挖掘，但忽略了稀疏的子結構，同時并沒有很好地處理對于子圖間的重疊語義。

圖分解問題。大規(guī)模的圖首先需要分解成合適的子圖，再進一步提取它們的語義。Vog的框架的表現(xiàn)優(yōu)劣仍然取決于分法的好壞，所用的Slashburn分解算法甚至不能解決簡單的分解重疊問題。如圖2所示，Slashburn不能鑒別出明顯的重疊邊，而是將它作為一個星形子結構的一條邊（1），但事實上a是兩個星的重疊邊（3）。另外，Slashburn通過樞紐點挖掘，完全忽略了這個大的子結構（2）中的一個派系結構（4）。為此，通過直接挖取圖中樞紐點并進行子結構合并，得到了圖的子圖集合。

圖2 Slashburn忽略了子圖重疊

子圖的語義判別問題。子圖的語義判別需要合理的語義模板和編碼算法。為此，引入多樣化的子結構模板，包含稠密和稀疏的各種子結構，通過合適的編碼方式，結合MDL，快速確定子圖語義。

子圖重疊問題。子圖的重疊程度判定問題一直是一個困難的問題。通過從每個樞紐點的自網(wǎng)絡（Ego-net）出發(fā)，利用MDL來確定重疊的子圖是否應該合并，然后逐步迭代，直到確定圖的所有子結構的重疊語義。

2 網(wǎng)絡結構語義挖掘方法

網(wǎng)絡由許多子結構構成。為挖掘圖所蘊含的結構語義，總體思路如下。

第一步，鑒于Slashburn分解算法忽略一些重疊語義，通過基于樞紐點的聚合方法（Hub-based subgraph Mining，HM算法）保留圖的重疊語義，得到待識別語義的子圖集合D。這些樞紐點的自網(wǎng)絡，可以通過MDL編碼識別為星、派系和近派系等直徑不超過2的子圖。一個點的自網(wǎng)絡，是指這個點的所有鄰居點以及它本身作成的子圖。由于還要形成直徑較大的子圖，再通過進一步合并形成潛在的樹、二部圖或者鏈這些長直徑子圖，而具體的子結構類型判斷參照第二步。合并結束，子圖間的重疊語義已經(jīng)被確定。

第二步，對D中的每一個子圖，通過MDL來確定子圖的結構語義。在確定子圖語義時，采用基本的字典語義模板，因此稱為基于模板的圖語義挖掘（Template-based graph Semantic Mining，TSM）算法（如圖3所示）。

第三步，希望得到原圖的一個模板表示，但顯然這么大的圖并沒有一個模板是合適的。因此，通過將原圖分解得到子圖集合對應的語義模板集合進行組合選擇。根據(jù)MDL準則，可以得到最佳的模板集合，作為對圖的整體語義的一個理解。

圖3 TSM算法流程

2.1 HM算法

HM算法流程如下。

輸入：圖G

輸出：子圖集合D

1:對每個2-degree點的鄰居點和兩條邊作成的子圖V2(x)進行合并，得到子圖

2:取H的每個連通分支，添加到D2

3:對degree＞2的每個點，取其自網(wǎng)絡，去掉重復一樣的子圖，得到子圖集合D1={S1,S2,…,Sp}.

4:D1=shm(D1)#shm()是一個遞歸函數(shù)

5:return D=D1∪D2

6:def shm(D1):

7: while True：

8: if |D1|==1:

9: return D1

10: else:

11: if D1不存在真包含關系的子圖：

12： if P(D1)不存在正項：

13: return D1

14: D1=f(D1)

15: elseif D1存在真包含關系的子圖：

16: 選擇最小真包含子圖集合U0={S1,S2,…,St}以及其母圖S*

17: U=shm(U0)

18: U1=g(U,S*)

19: D1=(D1-(U0∪ S*))∪ U1

20: #f(A)和g(B,C)分別表示將子圖集合A進行一次合并處理、將B和C進行一次真包含處理。

首先，需要得到圖的子圖。大部分現(xiàn)實中的網(wǎng)絡都服從冪率分布[13-14]，即存在少數(shù)度相對較大的樞紐點。J.Leskovec等人[15]的研究表明，樞紐點將網(wǎng)絡中的一個個子結構連接起來，使得傳統(tǒng)的圖分割算法難以奏效。因此，樞紐點的結構是一種圖的結構語義。在難以判斷該結構的具體類型時，直接挖掘派系和星形模板的短直徑共性，將所有度大于2的點包含它的自網(wǎng)絡挖掘出來，作為第一步的初始子圖集合D1。而度為2的點只有3種情形（見圖4），要么是一條鏈的節(jié)點（1），要么已經(jīng)被某個度大于2的樞紐點通過自網(wǎng)絡包括進來（2），要么就是一個獨立連通的三角形中的一個點（3）。（2）的情況已經(jīng)在前面處理，因此對每個度為2的點x，它的兩條邊以及兩個鄰居點組成一個子圖。將所有這些子圖合并（合并是指合并后的點集是子圖的點集之并，邊集是子圖的邊集之并；并不是合并后的點集的導出子圖，因為通過后面的取法知道，邊一定會被收入到某個自網(wǎng)絡之中，并不會遺漏需要編碼的邊而產生很多誤差），重復的邊只計數(shù)一次，得到一個大的圖，記為H，通常具有多個連通分支。取H的所有連通子圖，將它們作為待識別的語義子圖添加到候選集D2中。最后，度為1的點顯然都已經(jīng)存在于D=D1∪D2的子圖中。

圖4 真包含關系子圖的合并

盡管這里D1是記為一個集合，但事實上通過前面的添加方式會有很多重復的子圖，因此需要去掉一樣的子圖。不妨，記去重后的子圖集合仍為D1。由于D2中的子圖傾向于鏈結構，因此它們的語義類似于將D1中的子圖串起來。所以，僅僅合并D1中的子圖，以便形成語義明顯的大型結構。

任取兩個子圖S1,S2∈D1，記T=S1∪S2，K=S1∩S2，考慮S1，S2的合并。兩個子圖間的關系有真包含、不相交和“通常重疊”三種。“通常重疊”是指不是真包含關系的重疊。先研究兩個子圖間的真包含和“通常重疊”關系處理，對于實際子圖合并的情況在后面討論，而不相交的子圖顯然不考慮合并問題。

兩個子圖間真包含關系表明了一種層次語義，合并時的處理與一般的重疊不同，要另外處理。設Si真包含于Sj，考慮兩種情形，一種是將圖看作成一個子圖Sj，另一種是看成Si和W∪(Sj-Si)多個子圖重疊在一起，其中即與Sj-Si中有邊相連的點的全體。通過計算兩種情形的子圖集合編碼，并由MDL準則選擇編碼長度最小的一種。注意，W∪(Sj-Si)有可能是具有多個連通分支的子圖集合，這時把每個連通分支作為一個子圖，然后對每個子圖用字典模板編碼，最后將這些字典模板合起來（根據(jù)式（1）和式（2））對整個圖進行編碼，這個過程稱為一次“真包含處理”。

通常，最小描述長度準則是指通過子結構或者子結構集合M來描述圖數(shù)據(jù)G。編碼所需的比特數(shù)目越小，意味著對圖數(shù)據(jù)的壓縮越好，也就是對數(shù)據(jù)的理解越好，是更好的編碼。通常，編碼分為兩個部分，子結構集合的編碼和誤差的編碼，即無損壓縮：

其中L(M)和L(G|M)分別是對子結構集合的編碼比特和對誤差的編碼比特數(shù)目，且有：

對于剩余的重疊情況，即“通常重疊”情況，有兩個問題：（1）兩個子圖合并的條件是什么？（2）這么多子圖的合并順序是怎樣？計算每兩個子圖間的合并編碼收益，記號同前；設G(T)為T在G中的導出子圖，則定義Si、Sj的合并編碼收益為：

即合并前的編碼比特數(shù)減去合并后的編碼比特數(shù)。若差值大于0，則合并減少了局部的編碼比特。由MDL知，合并是有益的，則將兩個子圖合并；否則不合并。對于以上處理，稱為一次“合并處理”。

對于第二個問題，設k=|D1|，則任意兩個子圖計算編碼收益可以得到編碼收益矩陣P=(?(Si,Sj))k×k。在合并迭代的每一步，選擇P中最大正數(shù)對應的兩個子圖合并，同時對合并后的子圖更新它與其他子圖的合并收益，然后重復迭代，直到P中不再出現(xiàn)正項。此時，D1是動態(tài)變化的，但是仍記為D1。

圖5 子圖間的一般關系

事實上，真包含的關系并不簡單（圖5），即可能存在一個子圖真包含一個子圖再真包含著一個子圖的多層真包含關系（圖5（a）），也存在一個子圖包含多個非真包含關系的子圖（圖5（b））。重疊也有多個子圖兩兩重疊的情形。一般地，從最小的子圖開始（即考慮圖5例子（a）中的最小真包含子圖部分（b）），即設一系列子圖U0={S1,S2,…,St}是子圖S*的所有真包含子圖，而Si，i=1,2,…,t不再真包含D1中的其他子圖。于是，Si、Sj之間的關系僅有不相交或“通常重疊”兩種。用前面同樣的辦法處理“通常重疊”，結束后得到一系列不能再合并的子圖集合 U={S′1,S′2,…,S′g}。最后，對U中的每個子圖S，通過兩個真包含子圖的類似處理，計算它與S*之間的真包含關系比特，即解優(yōu)化問題：

然后，將以上對于子圖集合D1的合并迭代逐步進行，直到圖中不再有真包含的子圖，同時子圖間的合并收益矩陣P不再有正項。整個子圖合并算法結束后，得到一個待識別語義的子圖集合D=D1∪D2，其中的子圖可以是重疊的。

2.2 子圖語義判別方法

對于子圖集合D，需要判別每個子圖的具體子結構類型，即提取圖的拓撲語義。子圖的拓撲語義或者說子結構類型是基本字典中的某個模板類型。

通過最小描述長度準則，將子圖g∈D的子結構類型判別問題公式化：

其中∑是六種基本模板所組成的字典，包括星（st）、派系（cl）、近派系（nc）、二部圖（bp）、鏈（ch）和樹（tr）。無歧義地，記∑={st,cl,nc,bp,ch,tr}；L(m)和L(g|m)分別是對模板m和模板與子圖間誤差的編碼。

顯然，這個算法的關鍵取決于模板和誤差的編碼兩部分。通過最優(yōu)前綴碼對模板進行編碼?？傮w而言，總是編碼模板的大小，然后確定模板中每個點對應在子圖中的位置。模板的編碼公式如下。

（1）派系（Clique，cl）

（2）近派系（Near Clique，nc）

（3）星（Star，st）

（4）二部圖（Bipartite graph，bp）：

（5）樹 (Tree，tr)：

（6）鏈（Chain，ch）：

對于誤差的編碼，首先通過模板m與子圖g對應的鄰接矩陣作異或和計算得到誤差矩陣e，然后將誤差矩陣e分為兩個部分e=e++e-，分別表示模板有而圖不具有的邊、圖具有而模板不具有的邊。因為它們的分布是不同的，所以需要把它們分開來編碼。編碼公式如下：

這也相當于在矩陣e+或e-中編碼它的上三角部分，可以看做是按行編碼，即將它逐行作為一個0-1比特串來編碼。|e+|是矩陣e+對應的圖中不重復邊的數(shù)目，也就是e+上三角部分中1的數(shù)目；||e+||和||e+||′分別表示上三角部分中1和0的數(shù)目；而

是每個比特最優(yōu)前綴碼的碼長。e-的編碼類似。最后，由于并不是單純地編碼比特串而是矩陣，因此需要再加上對矩陣階數(shù)的編碼。于是，最終的誤差編碼長度為：

這樣，即可自動計算出G中每個子圖的g的結構語義模板類型。對于得到編碼后的模板集合，記為 O={m1,m2,…,mk}。

2.3 子圖組合算法

從前面的兩個步驟已經(jīng)確定了圖的子圖語義和子圖間的重疊語義，但是整體而言，圖G也需要一個簡潔的模板表示。也就是說，需要把這些子圖對應的語義模板放在一起，組合成原圖的一個整體語義，通過MDL來確定這個模板集合中模板之間的語義，即應該選擇哪些模板得到整體的拓撲語義。通常，對于確定的模板集合O，其解空間的遍歷也需要O(k2)的時間復雜度，其中k=|O|是子結構的數(shù)量。當子結構數(shù)量較多時，這并不是好的選擇。為此，采用2種模板選擇近似算法。這兩種模板選擇算法結合TSM算法，稱之為TSM-AA和TSM-GA算法，完全對應于Vog中的PLAIN和GREEDY’N FORGET組合方法。選擇模板組合時，當兩個模板重疊時，對于重疊邊采用邏輯加，即重復出現(xiàn)的邊只計算一次。與Vog不同的是，認為模板的順序并不重要，重復的懲罰因子隱含在模板數(shù)量和模板的編碼中。

3 實驗對比與分析

實驗采用了幾個社交網(wǎng)絡和文獻引用網(wǎng)絡，分別是Citnet[16]（文獻引用網(wǎng)絡）、Euall[17]（文獻引用網(wǎng)絡）、Enron[18]（郵件往來網(wǎng)絡）和Facebook[19]（社交網(wǎng)絡）。對這四個數(shù)據(jù)集采用TSM-AA和TSM-GA算法，計算每種組合用來編碼原圖所需的比特。由MDL準則可知，比特數(shù)越少，表明該子圖集合越好。然而，由于MDL傾向于懲罰重疊的部分，因此會盡量選擇不重疊的模板。所以，TSM算法得到的結果不見得比Vog好。這四個網(wǎng)絡的基本數(shù)據(jù)見表1。

表1 圖數(shù)據(jù)概況

首先比較三種算法，將圖編碼成純誤差。TSM-AA，即將分解得到模板集合全體作為整體的圖編碼模板；TSM-GA，即根據(jù)局部收益進行貪婪算法選擇最終的模板集合。由實驗結果（如表2所示），TSM-AA算法由于大量的冗余，用它編碼圖所需的比特遠超其他兩種算法；TSM-GA編碼圖僅需更少的比特數(shù)目。根據(jù)MDL準則，它是對圖結構的較好理解。

然后，通過計算Vog算法在圖數(shù)據(jù)上的比特進行比較發(fā)現(xiàn)，同是貪婪算法，盡管可能存在更多的子結構重疊，但所提算法計算得到的編碼比特數(shù)目更少，表明是對圖語義結構的更好理解和算法改進，如表3所示。

表2 三種算法編碼圖所需的總比特

表3 與Vog的算法比較

總之，相比于Vog算法，所提算法能夠挖掘出圖中更多的子圖重疊語義，組建成具有更少編碼比特的圖拓撲語義模板集合，得到對原圖的拓撲語義更好的理解，從而為其他應用和進一步的分析提供基礎。

4 結 語

本文考慮對社交網(wǎng)絡的拓撲結構，或者說無權無向圖的結構進行拓撲語義挖掘。圖的拓撲語義事實上包含在其子圖的結構中，包括子圖的結構語義、子圖間的重疊語義以及圖的整體語義。通過對圖性質的分析，通過逐步合并的方式獲得圖的子圖集合，并通過MDL客觀確定了以上各種語義，特別是子圖的結構語義和子圖間的重疊語義。綜上所述，對于網(wǎng)絡的拓撲語義挖掘是網(wǎng)絡結構信息挖掘的重要方式，也是圖數(shù)據(jù)理解的重要手段之一。