動(dòng)態(tài)多模網(wǎng)絡(luò)中演化社區(qū)發(fā)現(xiàn)算法改進(jìn)

胡 昊，張小燕，蘇 勇

（江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江212003）

當(dāng)今網(wǎng)絡(luò)擁有海量數(shù)據(jù)，要從海量數(shù)據(jù)中得到有用的信息是很困難的，因此網(wǎng)絡(luò)分析[1]和建模[2]受到越來(lái)越多的關(guān)注。目前很多研究工作都只涉及一種模式的網(wǎng)絡(luò)，即網(wǎng)絡(luò)中只存在一種類型的參與者（點(diǎn)），參與者之間只存在同種類型的關(guān)系（聯(lián)系）。但是，最近迅猛發(fā)展的Web數(shù)據(jù)挖掘涉及到了不止一種類型的參與者，這些參與者之間的關(guān)系也不再僅限于一種。這種類型的網(wǎng)絡(luò)稱為多模網(wǎng)絡(luò)[3]。

在多模網(wǎng)絡(luò)中，不同模中點(diǎn)的進(jìn)化是不相同的。對(duì)于具有動(dòng)態(tài)關(guān)系的異構(gòu)實(shí)體，發(fā)現(xiàn)演化社區(qū)有很多的好處：(1)能夠清晰地了解迥異模式之間的聯(lián)系和長(zhǎng)期演化模式；(2)可以形象化具有多種實(shí)體和多種關(guān)系的復(fù)雜網(wǎng)絡(luò)；(3)有助于在多種領(lǐng)域中做決策；(4)在早期如果發(fā)現(xiàn)不良的演化樣式，也可以發(fā)出事件警告。

在動(dòng)態(tài)多模網(wǎng)絡(luò)中發(fā)現(xiàn)社區(qū)演化還是很困難的，原因有二：(1)不同的模式之間的演化是有關(guān)聯(lián)的；(2)不同模式具有獨(dú)特的演化樣式。本文采用譜聚類架構(gòu)，提出一種發(fā)現(xiàn)動(dòng)態(tài)多模網(wǎng)絡(luò)中演化社區(qū)的一般方法。一個(gè)動(dòng)態(tài)多模網(wǎng)絡(luò)會(huì)包含一系列的網(wǎng)絡(luò)快照，利用這些快照可以找出社區(qū)是如何演化的。在這個(gè)模型下，加入正則項(xiàng)反映時(shí)態(tài)變化[4]，可以將有聯(lián)系模式的聚類結(jié)果和相鄰時(shí)間戳作為一個(gè)模式下的社區(qū)更新的屬性，是一個(gè)將動(dòng)態(tài)多模網(wǎng)絡(luò)分析和常規(guī)的基于屬性的數(shù)據(jù)挖掘聯(lián)系起來(lái)的新方法。

1 問(wèn)題闡述

給出含有 m種類型元素X1，X2，…，Xm的m模網(wǎng)絡(luò)，找出每一模中的潛在社區(qū)是如何演化的[5]。在架構(gòu)中，通過(guò)一系列的網(wǎng)絡(luò)快照只關(guān)注離散時(shí)間戳，這個(gè)方法在正則項(xiàng)網(wǎng)絡(luò)分析中得到廣泛應(yīng)用。表1所示為下文中所涉符號(hào)及其表示的內(nèi)容。

1.1 使用網(wǎng)絡(luò)序列發(fā)現(xiàn)社區(qū)

在動(dòng)態(tài)多模網(wǎng)絡(luò)中，有多種多樣的網(wǎng)絡(luò)快照。不考慮時(shí)態(tài)效應(yīng)的目標(biāo)函數(shù)F1可以寫為：

表1 符號(hào)及其表示的內(nèi)容

有如下定理：

定理 1： 如果 C(i，t)，1≤i≤m，1≤t≤T 是方程 F1的有效解，那么(i，t)也是具有相同目標(biāo)值的有效解，其中(i，t)定 義 如 下 ：

1.2 使用時(shí)態(tài)正則化發(fā)現(xiàn)社區(qū)

公式F1并沒(méi)有關(guān)注連續(xù)時(shí)間戳之間的關(guān)系?？梢詫1歸結(jié)為每一個(gè)快照單獨(dú)地進(jìn)行聚類。實(shí)際生活中的社區(qū)演化是非常緩慢的，為了得到平滑的社區(qū)演化，將增加時(shí)態(tài)正則項(xiàng)Ω，它可以迫使聚類序列通過(guò)不同的時(shí)間戳?xí)r變得平滑。

式(3)中，“1/2”只是為了下面求導(dǎo)方便做的計(jì)數(shù)。實(shí)際上，這里進(jìn)行一階馬爾科夫假設(shè)，要求當(dāng)前的聚類與前一個(gè)時(shí)間戳的聚類很相似。

正如定理 1指出的，C(i，t)在正交變換下是相等的，因 此 ， 可 以 在 式(4)中 直 接 比 較 C(i，t)和 C(i，t-1)， 而 不 必 得出它們?cè)诓煌瑫r(shí)間戳下聚類指示符的不同。相比較而言，式(3)中正則項(xiàng)與正交變換無(wú)關(guān)，因此應(yīng)該得到相鄰時(shí)間戳下社區(qū)結(jié)構(gòu)的不同。因?yàn)檎齽t化，發(fā)現(xiàn)演化社區(qū)的問(wèn)題就可以闡述成：

2 時(shí)態(tài)正則化多模聚類

2.1 A的估計(jì)

定理 2：對(duì)于給定的 C(i，t)，最佳的社區(qū)作用矩陣可以使用下式得到：

2.2 C的計(jì)算

同時(shí)：

注 意 ，C(i，t)、C(j，t)以 及 C(i，t-1)都 是 有 聯(lián) 系 的 。 一 般 來(lái)說(shuō)，這個(gè)函數(shù)沒(méi)有解析的閉合形式解。但是如果有給定的C(j，t)和 C(i，t±1)，則 可 以 根 據(jù) 定 理 3 直 接 得 到 最 佳 的 C(i，t)。

定 理 3： 如 果 給 定 C(j，t)和 C(i，t±1)， 那 么 C(i，t)就 可 以作為矩陣的頂左奇異向量求解，通過(guò)以下矩陣在列方向的級(jí)聯(lián)得到。

2.3 屬性視圖中的算法

借助輪換尋優(yōu)思想解決式(9)中的F3問(wèn)題。即求解C(i，t)時(shí)，固定其他變量的值。這個(gè)過(guò)程一直迭代，直到函數(shù)收斂。收斂之后，{C(i，t)}就是近似的社區(qū)指示符矩陣。通常使用后處理視圖恢復(fù)社區(qū)中不相鄰部分，即對(duì)社區(qū)指示符采用k-均值聚類。綜上所述，時(shí)態(tài)正則化多模聚類算法如下：

在屬性視圖中解釋這個(gè)算法，更新C(i，t)的每一步都和潛在的語(yǔ)義分析過(guò)程一致。根據(jù)定理3，社區(qū)指示符和矩陣的左奇異向量是一致的，在式(10)中也做了定義。如果將作為正規(guī)實(shí)例-屬性矩陣，則找出社區(qū)指示符和進(jìn)行潛在的語(yǔ)義分析LSA(Latent Semantic Analysis)同樣重要。圖1指出了整個(gè)算法的過(guò)程。

圖1 樹(shù)形視圖中的算法：迭代的LSA

3 動(dòng)態(tài)數(shù)據(jù)上的實(shí)驗(yàn)

實(shí)驗(yàn)中進(jìn)行下面三種方法的比較：靜態(tài)聚類、在線聚類和本文提出的時(shí)態(tài)正則化多模聚類。靜態(tài)聚類是一種基線方法，它不關(guān)心任何的時(shí)態(tài)規(guī)則化。靜態(tài)聚類通過(guò)對(duì)式(1)中的F1求解對(duì)每一個(gè)網(wǎng)絡(luò)快照單獨(dú)進(jìn)行聚類。

因?yàn)檎鎸?shí)的數(shù)據(jù)不包含驗(yàn)證信息，即在不同時(shí)間戳下的社區(qū)聯(lián)系，因此，使用合成數(shù)據(jù)驗(yàn)證提出算法的有效性。

3.1 實(shí)驗(yàn)設(shè)置

構(gòu)建一個(gè)三模動(dòng)態(tài)網(wǎng)絡(luò)，模分別有2、3、4個(gè)社區(qū)和50、100、200個(gè)元素。每?jī)蓚€(gè)模型之間都可以發(fā)生聯(lián)系，為了產(chǎn)生迭代，條件設(shè)置為：(1)為每個(gè)元素決定潛在的社區(qū)；(2)實(shí)體之間基于團(tuán)體同一性產(chǎn)生的關(guān)系符合伯努利分布。

為了模擬演化，在不同的時(shí)間戳下按照如下規(guī)則發(fā)生聯(lián)系：

(1)在每個(gè)時(shí)間戳下，參與者的部分(20%～50%)要轉(zhuǎn)化為與先前時(shí)間戳下的組完全不同的組中，這是為了模擬社區(qū)演化。

(2)兩個(gè)組之間發(fā)生聯(lián)系的概率是高斯分布的樣本，主要和先前時(shí)間戳下的概率有關(guān)。這是為了模擬聯(lián)系的改變。

(3)在每個(gè)時(shí)間戳下添加噪音。例如噪音強(qiáng)度是0.2，則聯(lián)系矩陣中大概有20%的詞條被隨機(jī)設(shè)為0，另外20%的詞條被隨機(jī)設(shè)為1。噪音和潛在的組結(jié)構(gòu)是獨(dú)立的，因此，噪音強(qiáng)度越高，在聯(lián)系中的社區(qū)結(jié)構(gòu)越不容易被發(fā)現(xiàn)。

3.2 實(shí)驗(yàn)結(jié)果

表2列出了超過(guò)100次運(yùn)行的結(jié)果取平均值，其中，粗體表示結(jié)果中最好的。從表中數(shù)據(jù)可見(jiàn)，聚類效果隨著噪音的加強(qiáng)變得越來(lái)越壞?？傮w來(lái)看，規(guī)則化聚類比在線聚類的效果好，在線聚類比靜態(tài)聚類的效果好。從結(jié)果中也注意到，當(dāng)噪音強(qiáng)度比較大（即噪音強(qiáng)度為0.55）時(shí)，社區(qū)結(jié)構(gòu)的平滑性遭到了破壞，也因此時(shí)態(tài)正則化聚類效果比靜態(tài)聚類還差。

表2 不同噪音強(qiáng)度下各種聚類比較

圖2顯示平均計(jì)算時(shí)間。噪音越大，計(jì)算時(shí)間越長(zhǎng)。靜態(tài)聚類需要的時(shí)間是最短的，在線聚類的時(shí)間相對(duì)較長(zhǎng)，時(shí)態(tài)正則化聚類的時(shí)間是最長(zhǎng)的，特別是當(dāng)噪音強(qiáng)度非常大時(shí)，時(shí)間變得不可接受。在這種情況下，時(shí)態(tài)平滑性已經(jīng)被損害，算法需要更多的迭代找到最優(yōu)解。

為了顯示參數(shù)調(diào)整的效果，選擇中等噪音強(qiáng)度的數(shù)據(jù)集，使用在線聚類和正則化聚類，時(shí)態(tài)權(quán)重wb從0.01～1 000進(jìn)行調(diào)整，wa固定為 1。如圖3所示，時(shí)態(tài)權(quán)重過(guò)大反而得到不好的效果，即時(shí)態(tài)正則化處于首要地位。大部分時(shí)間，時(shí)態(tài)規(guī)則化有利于聚類考慮時(shí)態(tài)信息，時(shí)態(tài)權(quán)重在0.01～100的范圍內(nèi)體現(xiàn)的尤為明顯。

在實(shí)際應(yīng)用中，異構(gòu)參與者之間的互相作用形成了多模網(wǎng)絡(luò)。正是在這樣的網(wǎng)絡(luò)中，不同模的參與者構(gòu)成社區(qū)并慢慢演化。本文提出了時(shí)態(tài)正則化多模聚類算法在動(dòng)態(tài)多模網(wǎng)絡(luò)中發(fā)現(xiàn)演化社區(qū)。這個(gè)算法可以理解為迭代的LSA過(guò)程，在不同模和時(shí)間戳下的屬性構(gòu)成社區(qū)矩陣?；谶@種屬性視圖，提出的算法也能擴(kuò)展到處理帶有屬性的網(wǎng)絡(luò)、模內(nèi)聯(lián)系以及休眠點(diǎn)和活躍點(diǎn)。實(shí)驗(yàn)結(jié)果證明該算法能夠根據(jù)一系列的快照找到更精確的社區(qū)結(jié)構(gòu)和社區(qū)演化。

[1]NEWMAN M.The structure and function of complex networks[J].SIAM Review，2003，45(2)：167-256.

[2]CHAKRABARTI D，F(xiàn)ALOUTSOS C.Graph mining：laws，generators，and algorithms[J].ACM Comput.Surv.，2006，38(1)：65-78.

[3]WASSERMAN S，F(xiàn)AUST K.Social network analysis：methods and applications[M].Cambridge University Press，1994.

[4]BAUMES J，GOLDBERG M，WALLACE W，et al.Discover-ing hidden groups in communication networks[C].In 2nd NSF/NIJ Symposium on intelligence and Security Informatics，2004.

[5]LONG B，ZHANG Z M，WU X，et al.Spectral clustering for multi-type relational data[C].In ICML’06：Proceedings of the 23rd international conference on Machine learning.ACM，2006：585-592.

[6]王林，戴冠中.基于復(fù)雜網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的論壇熱點(diǎn)主題發(fā)現(xiàn)[J].計(jì)算機(jī)工程，2008，34(11)：214-21.