摘 要： 在動態多模式網絡中發現社區可以幫助人們了解網絡的結構屬性，解決數據不足和不平衡問題，并且可以協助解決市場營銷和發現重要參與者的問題。一般來說，網絡和它的社區結構是不均勻進化的。通過使用時態信息來分析多模網絡，分析時態正則化架構和它的收斂屬性。提出的算法可以解釋為一個迭代的潛在語義分析過程，允許擴展到處理帶有參與者屬性和模內聯系的網絡。
關鍵詞： 數據挖掘；社區發現；社區演化；多模網絡；動態網絡
當今網絡擁有海量數據，要從海量數據中得到有用的信息是很困難的，因此網絡分析[1]和建模[2]受到越來越多的關注。目前很多研究工作都只涉及一種模式的網絡，即網絡中只存在一種類型的參與者（點），參與者之間只存在同種類型的關系（聯系）。但是，最近迅猛發展的Web數據挖掘涉及到了不止一種類型的參與者，這些參與者之間的關系也不再僅限于一種。這種類型的網絡稱為多模網絡[3]。
在多模網絡中，不同模中點的進化是不相同的。對于具有動態關系的異構實體，發現演化社區有很多的好處：(1)能夠清晰地了解迥異模式之間的聯系和長期演化模式；(2)可以形象化具有多種實體和多種關系的復雜網絡；(3)有助于在多種領域中做決策；(4)在早期如果發現不良的演化樣式，也可以發出事件警告。
在動態多模網絡中發現社區演化還是很困難的，原因有二：(1)不同的模式之間的演化是有關聯的；(2)不同模式具有獨特的演化樣式。本文采用譜聚類架構，提出一種發現動態多模網絡中演化社區的一般方法。一個動態多模網絡會包含一系列的網絡快照，利用這些快照可以找出社區是如何演化的。在這個模型下，加入正則項反映時態變化[4]，可以將有聯系模式的聚類結果和相鄰時間戳作為一個模式下的社區更新的屬性，是一個將動態多模網絡分析和常規的基于屬性的數據挖掘聯系起來的新方法。
1 問題闡述
給出含有m種類型元素X1，X2，…，Xm的m模網絡，找出每一模中的潛在社區是如何演化的[5]。在架構中，通過一系列的網絡快照只關注離散時間戳，這個方法在正則項網絡分析中得到廣泛應用。表1所示為下文中所涉符號及其表示的內容。
圖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.Discovering 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.