動態多模網絡中演化社區發現算法改進

胡 昊，張小燕，蘇 勇

（江蘇科技大學 計算機科學與工程學院，江蘇 鎮江212003）

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

在多模網絡中，不同模中點的進化是不相同的。對于具有動態關系的異構實體，發現演化社區有很多的好處：(1)能夠清晰地了解迥異模式之間的聯系和長期演化模式；(2)可以形象化具有多種實體和多種關系的復雜網絡；(3)有助于在多種領域中做決策；(4)在早期如果發現不良的演化樣式，也可以發出事件警告。

在動態多模網絡中發現社區演化還是很困難的，原因有二：(1)不同的模式之間的演化是有關聯的；(2)不同模式具有獨特的演化樣式。本文采用譜聚類架構，提出一種發現動態多模網絡中演化社區的一般方法。一個動態多模網絡會包含一系列的網絡快照，利用這些快照可以找出社區是如何演化的。在這個模型下，加入正則項反映時態變化[4]，可以將有聯系模式的聚類結果和相鄰時間戳作為一個模式下的社區更新的屬性，是一個將動態多模網絡分析和常規的基于屬性的數據挖掘聯系起來的新方法。

1 問題闡述

給出含有 m種類型元素X1，X2，…，Xm的m模網絡，找出每一模中的潛在社區是如何演化的[5]。在架構中，通過一系列的網絡快照只關注離散時間戳，這個方法在正則項網絡分析中得到廣泛應用。表1所示為下文中所涉符號及其表示的內容。

1.1 使用網絡序列發現社區

在動態多模網絡中，有多種多樣的網絡快照。不考慮時態效應的目標函數F1可以寫為：

表1 符號及其表示的內容

有如下定理：

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

1.2 使用時態正則化發現社區

公式F1并沒有關注連續時間戳之間的關系?？梢詫1歸結為每一個快照單獨地進行聚類。實際生活中的社區演化是非常緩慢的，為了得到平滑的社區演化，將增加時態正則項Ω，它可以迫使聚類序列通過不同的時間戳時變得平滑。

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

正如定理 1指出的，C(i，t)在正交變換下是相等的，因 此 ， 可 以 在 式(4)中 直 接 比 較 C(i，t)和 C(i，t-1)， 而 不 必 得出它們在不同時間戳下聚類指示符的不同。相比較而言，式(3)中正則項與正交變換無關，因此應該得到相鄰時間戳下社區結構的不同。因為正則化，發現演化社區的問題就可以闡述成：

2 時態正則化多模聚類

2.1 A的估計

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

2.2 C的計算

同時：

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

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

2.3 屬性視圖中的算法

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

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

圖1 樹形視圖中的算法：迭代的LSA

3 動態數據上的實驗

實驗中進行下面三種方法的比較：靜態聚類、在線聚類和本文提出的時態正則化多模聚類。靜態聚類是一種基線方法，它不關心任何的時態規則化。靜態聚類通過對式(1)中的F1求解對每一個網絡快照單獨進行聚類。

因為真實的數據不包含驗證信息，即在不同時間戳下的社區聯系，因此，使用合成數據驗證提出算法的有效性。

3.1 實驗設置

構建一個三模動態網絡，模分別有2、3、4個社區和50、100、200個元素。每兩個模型之間都可以發生聯系，為了產生迭代，條件設置為：(1)為每個元素決定潛在的社區；(2)實體之間基于團體同一性產生的關系符合伯努利分布。

為了模擬演化，在不同的時間戳下按照如下規則發生聯系：

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

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

(3)在每個時間戳下添加噪音。例如噪音強度是0.2，則聯系矩陣中大概有20%的詞條被隨機設為0，另外20%的詞條被隨機設為1。噪音和潛在的組結構是獨立的，因此，噪音強度越高，在聯系中的社區結構越不容易被發現。

3.2 實驗結果

表2列出了超過100次運行的結果取平均值，其中，粗體表示結果中最好的。從表中數據可見，聚類效果隨著噪音的加強變得越來越壞。總體來看，規則化聚類比在線聚類的效果好，在線聚類比靜態聚類的效果好。從結果中也注意到，當噪音強度比較大（即噪音強度為0.55）時，社區結構的平滑性遭到了破壞，也因此時態正則化聚類效果比靜態聚類還差。

表2 不同噪音強度下各種聚類比較

圖2顯示平均計算時間。噪音越大，計算時間越長。靜態聚類需要的時間是最短的，在線聚類的時間相對較長，時態正則化聚類的時間是最長的，特別是當噪音強度非常大時，時間變得不可接受。在這種情況下，時態平滑性已經被損害，算法需要更多的迭代找到最優解。

為了顯示參數調整的效果，選擇中等噪音強度的數據集，使用在線聚類和正則化聚類，時態權重wb從0.01～1 000進行調整，wa固定為 1。如圖3所示，時態權重過大反而得到不好的效果，即時態正則化處于首要地位。大部分時間，時態規則化有利于聚類考慮時態信息，時態權重在0.01～100的范圍內體現的尤為明顯。

在實際應用中，異構參與者之間的互相作用形成了多模網絡。正是在這樣的網絡中，不同模的參與者構成社區并慢慢演化。本文提出了時態正則化多模聚類算法在動態多模網絡中發現演化社區。這個算法可以理解為迭代的LSA過程，在不同模和時間戳下的屬性構成社區矩陣?；谶@種屬性視圖，提出的算法也能擴展到處理帶有屬性的網絡、模內聯系以及休眠點和活躍點。實驗結果證明該算法能夠根據一系列的快照找到更精確的社區結構和社區演化。

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

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

[3]WASSERMAN S，FAUST 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]王林，戴冠中.基于復雜網絡中社區結構的論壇熱點主題發現[J].計算機工程，2008，34(11)：214-21.