一種基于語義推理的網(wǎng)絡社區(qū)發(fā)現(xiàn)模型

任薇，阮淇昱，韓孟凱，邱玉輝

1. 西南大學 計算機與信息科學學院 軟件學院， 重慶 400715； 2. 西南大學 人工智能學院， 重慶 400715

社區(qū)發(fā)現(xiàn)(Community Discovery)是將復雜網(wǎng)絡拓撲結構分解為有意義的節(jié)點集群的任務[1]． 目前主流的社區(qū)發(fā)現(xiàn)方法基于聚類計算， 通過無監(jiān)督學習訓練發(fā)現(xiàn)共同群體[2-3]． 然而， 由于現(xiàn)有網(wǎng)絡節(jié)點屬性不同， 對于社區(qū)的定義各種各樣， 聚類結果帶有一定的隨機性， 不能實現(xiàn)精準分類[4]． 另一方面， 現(xiàn)有劃分算法只關注平面數(shù)據(jù)， 沒有充分利用個體和鏈接屬性信息的語義， 導致劃分不準確[5-6]． 同時， 當前社區(qū)發(fā)現(xiàn)算法主要通過將有向圖轉化為無向圖來進行社區(qū)發(fā)現(xiàn)， 此過程可能丟失很多細節(jié)導致社區(qū)結果劃分不準確． 為實現(xiàn)對節(jié)點關系的準確描述， 在社區(qū)網(wǎng)絡中加入有向性[7]， 通過描述不同種類的鏈接， 可以更真實模擬社交網(wǎng)絡等現(xiàn)實世界網(wǎng)絡．

Satuluri算法[8]與LSW-OCD算法[9]都是根據(jù)節(jié)點的矢量將有向圖轉化為帶方向權值的無向圖， 雖然Satuluri算法的復雜度已經(jīng)在LSW-OCD得到較大改善， 但節(jié)點中隱含著的語義與語義的關系卻沒有在算法中發(fā)揮作用． 語義研究不僅關注事物概念的含義， 還關注含義間的關系． 在社會網(wǎng)絡中， 用戶的行為都與用戶本身的特征、 愛好、 習慣等緊密相連． 社區(qū)發(fā)現(xiàn)中語義的引入， 為挖掘非數(shù)據(jù)信息提供了可能， 從而支持對網(wǎng)絡社區(qū)更精確地劃分． 基于語義對社區(qū)發(fā)現(xiàn)的應用潛力， 本文提出以語義推理為基礎的網(wǎng)絡社區(qū)發(fā)現(xiàn)模型．

1 語義網(wǎng)絡及語義搜索

語義網(wǎng)絡是當前萬維網(wǎng)的擴展． 在語義網(wǎng)絡中， 信息被賦予了明確的含義， 使計算機和人能夠更好合作[10]． 語義網(wǎng)絡中的概念節(jié)點按照層次進行組織， 可以表現(xiàn)每個層次中不同節(jié)點之間的平面關系以及不同層次中節(jié)點的縱向關系[11]．

語義搜索是語義網(wǎng)絡的核心[12-14]． 語義搜索過程依據(jù)對本體處理原理的差異， 可以分為3種： 增強型語義搜索、 知識型語義搜索及其他搜索． 我們提出基于語義關系的發(fā)現(xiàn)模型， 通過關注節(jié)點間的語義特性[相等(Equal)、 相似(Similar)、 引用(Reference)、 序列(Sequence)、 子類(Subclass)、 蘊含(Implication)]， 采用語義鏈進行增強型推理， 期望得到更貼近真實情況的社區(qū)發(fā)現(xiàn)結果．

2 基于語義關系推理的立體社區(qū)發(fā)現(xiàn)模型

人類的社交網(wǎng)絡與其他網(wǎng)絡不同， 具有語義性， 基于語義推理的社區(qū)發(fā)現(xiàn)更貼合真實情況． 在社區(qū)結構劃分的研究中， 研究者主要關注兩方面問題： 一是社區(qū)的邊界性， 即社區(qū)邊界必須是封閉的； 二是社區(qū)的內(nèi)部緊密性， 即一個拓撲結構即使看上去有封閉的邊界， 但如果內(nèi)部無緊密連接， 也不能認定為社區(qū)． 本文用總權值度量的方法衡量封閉性， 用節(jié)點相似度來考察社區(qū)的緊密性． 社區(qū)內(nèi)部節(jié)點相似度的平均值通常大于社區(qū)間的相似度平均值． 因此， 本文給出社區(qū)結構定義如下：

給定一個混合圖G， 將G劃分為n個子圖G1，G2，…，Gn， 使得任一子圖Gi滿足下列條件， 則Gi為網(wǎng)絡G中的一個社區(qū)：

1) 對任意的節(jié)點N，din(N)是節(jié)點v在Gi中的度(權值)，dout(N)是節(jié)點v與除Gi外的其他子圖間的連接的總度， 則對于其他子圖Gj， 都有dout(N)-din(N)≤0；

圖1 語義網(wǎng)絡立體空間模型

2)Ni的內(nèi)部節(jié)點平均相似度大于其與其他子圖間的節(jié)點平均相似度．

以上定義的社區(qū)結構涵蓋了不同尺度的社區(qū)．

2.1 多層模型及社區(qū)發(fā)現(xiàn)模型

本文提出一種基于語義的網(wǎng)絡社區(qū)發(fā)現(xiàn)、 資源追蹤的立體空間模型， 在傳統(tǒng)的平面二維網(wǎng)絡模型基礎上， 針對語義網(wǎng)絡節(jié)點間語義關系的特性， 提出三維的空間立體模型(圖1)． 該立體空間模型將傳統(tǒng)意義上的網(wǎng)絡結構按語義關系類型重新構建， 模型拓撲結構分為縱面樹拓撲結構(圖2a)和平面圖拓撲結構(圖2b)．

模型采用立體空間節(jié)點拓撲結構， 利用節(jié)點語義及語義關系進行集成． 平面圖中和縱面樹中的語義節(jié)點， 其相互關系只能是特定的語義鏈中的一種或幾種． 同時， 為了減少語義模糊性， 計算節(jié)點相似度后， 將相似度高的節(jié)點進行合并． 使得語義查詢和社區(qū)發(fā)現(xiàn)可以快速轉換到合適的語義平面上， 從而可以提高搜索的速度和查全率．

圖2 語義關系拓撲結構

2.2 模型描述

本文根據(jù)語義鏈的特性構造空間立體語義鏈網(wǎng)絡模型．

2.2.1 相等、 引用與序列

在平面上， 用有向圖表示各節(jié)點間的關系． 定義空間模型中， 第n個平面上的圖為Gn=〈Vn，Equn，Refn，Seqn〉， 其中：Vn是第n個平面上所有點的集合，Equn代表第n個平面圖中所有語義鏈類型為 “相等”的節(jié)點集合，Refn與Seqn同理．

若多個節(jié)點間的語義鏈是相等的， 則合并所有的有此語義鏈關系的點為一點． 如圖3網(wǎng)絡中節(jié)點A，B，C間有“相等”語義鏈， 則合并為A(一般按第一個節(jié)點進行合并)， 節(jié)點D與B間語義鏈為其他類型， 則保留， 最后合并為兩個節(jié)點A和D． “相等”語義鏈及合并結果見圖3．

圖3 “相等”語義鏈及合并結果

假設兩節(jié)點A，B的語義相似度為α， 當α≥0.5時， 將此語義鏈的類型歸入相等， 若α<0.5時， 則認為A，B語義不相關．

Ref為圖中所有語義鏈類型為“引用”的節(jié)點關系集合，Refn=〈rn1，rn2…rnm〉，rni為第n個平面上第i條“引用”語義鏈．Seq是所有語義鏈類型為“序列”的節(jié)點集合，Seqn=〈sn1，sn2…rnm〉，sni為第i個序列． “引用”語義鏈和“序列”語義鏈的表示見圖4．

“引用”語義鏈與“序列”語義鏈屬于不同類型． “引用”語義鏈具有很強的時序性， 時間上， 要求前面的節(jié)點不能引用后面的節(jié)點．

2.2.2 蘊涵與子類

每個以樹為單位的縱面搜索是從根節(jié)點語義(Root Semantics)開始， 以蘊涵或子類語義鏈作為搜索路徑連接起來的各點． 路徑上的節(jié)點具有一定的有序性， 且可以通過一個節(jié)點查找到其他節(jié)點． 蘊涵或子類可以表示為這樣的樹的集合． 縱面上的樹結構可以表示為語義節(jié)點、 “子類”語義鏈、 “蘊涵”語義鏈的集合，T=(Vn，Sub，Imp)． “子類”語義鏈和“蘊含”語義鏈的表示見圖5．

圖4 “引用”語義鏈和“序列”語義鏈

“子類”語義鏈表示為Sub=∩〈Ni， …，Nn〉， 其中〈Ni， …，Nn〉是由節(jié)點Ni到Nn的一條“子類”語義鏈． 按定義， “子類”語義鏈有傳遞關系． 而“蘊涵”通常情況下并不單純指簡單的包含關系． 我們重點關注語義鏈關系， 即在某條或某幾條語義鏈存在的情況下， 是否有某種特殊的且研究者感興趣的語義鏈產(chǎn)生．

根據(jù)節(jié)點對象間相似度的度量和修正需要， 結合文獻[11]中語義鏈關系定義及本文中社區(qū)發(fā)現(xiàn)定義， 提出語義推理表(表1)．

其中：Imp=∩〈Ni， …，Nn〉表示可能產(chǎn)生推理的各個語義節(jié)點集合，Equ代表相等關系，Sim代表相似關系，Ref代表引用關系，Sub代表子類關系，Non代表無關系．

2.2.3 相似度計算

用一個詞空間的向量Vector(e)表示本文中的一個實體e， 每個維度對應一個詞， 維度大小取值表明了這個詞在刻畫e時的相對重要性． 用詞空間中的向量Vector(q)表示一條基于關鍵詞的查詢q．e和q的相似程度可以被描述為Vector(e)和Vector(q)的夾角余弦值．

語義結構的相似度取決于兩個基本的要素： ① 語義節(jié)點組成社區(qū)的葉子結點， 且查詢也是由葉子結點構成， 所以與社區(qū)的語義結構相關； ② 節(jié)點的祖先節(jié)點的相似程度．

表2給出了實現(xiàn)相似度算法所調(diào)用函數(shù)及其注釋．

表2 函數(shù)及其注釋

Ni與Nj語義結構相似度計算如下：

算法1Semantic-Structure-Similarity-Degrees (Ni，Nj)

IFNi屬于社區(qū)中某一個最大語義群

THEN

T=Max-Semantic-Clique (Ni，Nj)

ELSE

T=Min-Common-Sub-Tree (Ni，Nj)

END IF

RootSetNi=T

NodeSet={Ni， …， Root (Ni)}∪RootSetNi

IF Length (Ni，Nj)=1

THEN

Semantic-Structure-Similarity-Degrees (Ni，Nj)=Semantic-Node-Similarity-Degrees (Ni，Nj)

Return()

ELSE

FORNkIN NodeSet

IFNk=Nj

ELSE IFNkIN RootSetNj

ELSE IFNk≠Nj

END IF

得到節(jié)點的相似度向量后， 還需要得到節(jié)點的權重向量，WNk則表示節(jié)點Ni與節(jié)點之間的重要程度．

算法2基于算法1， 在用戶自定義權重W的影響下， 輸出集合Setnm中的各個節(jié)點與Ni節(jié)點的語義結構相似度組成的向量．

算法2Semantic-Structure-Similarity-Degrees-extend (Ni， NodeSet)

NodeSetnm={Nn， …，Nm}

FOR (Njin NodeSet)：

Similarity-DegreesNj=Semantic-Structure-Similarity-Degrees(Ni，Nj)

2.2.4 語義鏈網(wǎng)絡立體空間構建

算法3描述語義鏈網(wǎng)絡空間模型的構建．

算法3構建語義鏈網(wǎng)絡立體空間模型(DataSet)

Filter(DataSet)； //網(wǎng)頁抓取的數(shù)據(jù)通過本體集合過濾

Set_data=Init(DataSet)； //初始化輸入集合Set_data

T，G=Trans(Set_data) //采用本體之間的關系遍歷整個社區(qū)集， 確定一部分節(jié)點的Vn，Equ，Ref，Seq，Sub，Imp， 使用推理表格遍歷已構造的圖譜， 加速節(jié)點間關系的收斂．

M=Construct(G，T) //將用戶的ID作為主體主鍵， 通過Semantic-Structure-Similarity-Degrees-extend算法構造空間立體模型M=(G，T)， 其中G=〈Vn，Eqa，Ref，Seq〉，T=(Vn，Sub，Imp)；

NodeSim=Norm(M.SimVec) //歸一化各節(jié)點語義結構相似度

Sort(NodeSim{NSim1， …，NSimn}) //對其進行排序

Mark=0 //標記已被計算的節(jié)點(矩陣)為0

IFNSimi==1

THEN FORNiinG.EqaSetorT.SubSet∈NSimi

Ni?OutPut

Mark[i]=1

ELSEIFNSimi=<0.2

THEN FORNiinT.SubSetorG.EqaSet∈NSimi

Ni?OutPut

Mark[i]=1

FORMark[i]==0 andSimNi>0.5 //節(jié)點間關聯(lián)度對相似度的修正

ImportantNi=1

ImportantNj=0.8

FORNjinImpSet

ImportantNj=ImportantNj+SimNi*(1-α)ImportantNi

FORNjinSeqSet

ImportantNj=ImportantNj+SimNi* (1-β)ImportantNi

FORNjinRefSet

ImportantNj=ImportantNj+SimNi* (1-γ)ImportantNi

FORMark[j]==0

SimNj=Important*SimNj

IFSimNj>0.5

Nj?OutPut

Mark[j]=1

Return qutPut

3 實驗及分析

在本實驗中， 我們通過模擬實驗驗證社區(qū)發(fā)現(xiàn)算法的準確性． 通過選取Facebook中的樣本隨機建立二層社交網(wǎng)絡． 通過語義推理得到稠密矩陣， 并轉化為無向圖， 再對無向圖進行社區(qū)劃分證明本算法的有效性． 然后， 選取主流的社區(qū)發(fā)現(xiàn)算法K-means和隱語義模型(latent factor model， LFM)作為本模型算法的對比算法， 進行對比實驗． 結果發(fā)現(xiàn)， K-means的社區(qū)劃分準確性比其他兩個算法更低， LFM和本文算法的社區(qū)劃分準確度近似， 但當社區(qū)大小增長到1 000過后， 本文算法的模塊度逐漸顯示出優(yōu)勢． 模塊度是衡量社區(qū)劃分的強度指標， 以模塊度值的大小來評價社區(qū)劃分的優(yōu)劣， 模塊度值越接近1， 表示對社區(qū)結構的劃分越好． 模塊度值越大， 社區(qū)內(nèi)部連接越緊密， 社區(qū)間連接越稀疏， 劃分效果越好[1]．

實驗采用斯坦福大學提供的ego-Facebook的數(shù)據(jù)集． ego-Facebook數(shù)據(jù)集是從App端采集的Facebook用戶的數(shù)據(jù)， 包含了用戶的屬性、 社交圈(Circles)和ego network， 數(shù)據(jù)已被做了脫敏處理． 數(shù)據(jù)共有4 039個用戶和88 234條連邊． 其社交網(wǎng)絡圖的密度是0.005 409 92， 圖直徑為17， 平均距離為4.337 746， 能夠很好代表現(xiàn)實世界中的好友關系．

本文實驗在CPU為AMD Ryzen 7 5800Hz， 內(nèi)存為16GB， 系統(tǒng)為Win10的電腦上運行．

3.1 社區(qū)發(fā)現(xiàn)模型的實驗結果和分析

3.1.1 社區(qū)發(fā)現(xiàn)模型有效性

為了證明本文提出的社區(qū)發(fā)現(xiàn)模型的有效性， 本文先隨機選取ego-Facebook中的一個用戶， 建立兩層社交網(wǎng)絡關系圖， 圖中包含252個節(jié)與4875條邊． 本文構造原始的不帶權有向圖， 推理得到稠密矩陣， 此時的邊數(shù)為10 376， 包含了所有的語義關系． 本文將稠密矩陣作為相似度計算的輸入得到無向圖． 本文對無向圖中的社區(qū)節(jié)點進行劃分得到社區(qū)發(fā)現(xiàn)結果． 圖6給出了原始的Facebook好友有向圖、 轉化的Facebook好友有向圖、 Facebook好友無向圖、 Facebook好友社區(qū)發(fā)現(xiàn)結果．

圖6 基于Facebook的社區(qū)發(fā)現(xiàn)步驟及結果

圖7 算法對比

3.1.2 算法性能對比

我們選取社區(qū)發(fā)現(xiàn)主流的k-means算法和隱語義模型作為本模型算法的對比算法． 實驗中， 從0個節(jié)點開始， 每次從數(shù)據(jù)庫中隨機取出40個新的Facebook用戶節(jié)點添加到原有的網(wǎng)絡中． 通過模擬發(fā)現(xiàn)， 3個算法在擬合下都是線性增長． 隨著網(wǎng)絡節(jié)點的增加，k-means算法對社區(qū)的劃分結果不穩(wěn)定， 呈現(xiàn)大幅波動狀態(tài)． 3種算法對比結果見圖7．

LFM和本文結果在社區(qū)劃分結果方面差不多， 但當社區(qū)大小增長到1 000過后， 本文算法的模塊化程度逐漸顯示出優(yōu)勢．

穩(wěn)定性方面， 如圖8， 本文算法模塊化方差為5.267 942e-06低于LFM算法模塊化方差5.814 608e-06， 由此可見本文的算法更加穩(wěn)定．

圖8 本文算法與LFM算法個人circle結果比較

4 結論

本文提出基于語義推理的網(wǎng)絡社區(qū)發(fā)現(xiàn)模型， 創(chuàng)新地從語義網(wǎng)絡的角度， 探討網(wǎng)絡社區(qū)的構成及分割． 模型基于語義的平面和縱面兩種特性， 利用圖加樹的空間拓撲結構， 進行基于語義推理的社區(qū)發(fā)現(xiàn)． 同時， 本模型通過語義本身特性， 將基于語義鏈的搜索簡化到了層次范疇． 實驗結果顯示， 在模塊度的評價指標下， 本文提出的模型對社區(qū)劃分結果優(yōu)于LFW和k-means算法． 另一方面， 由于語義的分割及關系的復雜性會影響本模型速度， 期望在下一步的研究中解決該問題．