摘  要： 在動態(tài)多模式網(wǎng)絡中發(fā)現(xiàn)社區(qū)可以幫助人們了解網(wǎng)絡的結(jié)構屬性,，解決數(shù)據(jù)不足和不平衡問題，并且可以協(xié)助解決市場營銷和發(fā)現(xiàn)重要參與者的問題,。一般來說,，網(wǎng)絡和它的社區(qū)結(jié)構是不均勻進化的。通過使用時態(tài)信息來分析多模網(wǎng)絡,，分析時態(tài)正則化架構和它的收斂屬性,。提出的算法可以解釋為一個迭代的潛在語義分析過程,，允許擴展到處理帶有參與者屬性和模內(nèi)聯(lián)系的網(wǎng)絡。
關鍵詞： 數(shù)據(jù)挖掘,；社區(qū)發(fā)現(xiàn),；社區(qū)演化；多模網(wǎng)絡,；動態(tài)網(wǎng)絡

    當今網(wǎng)絡擁有海量數(shù)據(jù),，要從海量數(shù)據(jù)中得到有用的信息是很困難的，因此網(wǎng)絡分析[1]和建模[2]受到越來越多的關注,。目前很多研究工作都只涉及一種模式的網(wǎng)絡,，即網(wǎng)絡中只存在一種類型的參與者（點），參與者之間只存在同種類型的關系（聯(lián)系）,。但是,，最近迅猛發(fā)展的Web數(shù)據(jù)挖掘涉及到了不止一種類型的參與者，這些參與者之間的關系也不再僅限于一種,。這種類型的網(wǎng)絡稱為多模網(wǎng)絡[3],。
    在多模網(wǎng)絡中，不同模中點的進化是不相同的,。對于具有動態(tài)關系的異構實體,，發(fā)現(xiàn)演化社區(qū)有很多的好處：(1)能夠清晰地了解迥異模式之間的聯(lián)系和長期演化模式；(2)可以形象化具有多種實體和多種關系的復雜網(wǎng)絡,；(3)有助于在多種領域中做決策,；(4)在早期如果發(fā)現(xiàn)不良的演化樣式，也可以發(fā)出事件警告,。
    在動態(tài)多模網(wǎng)絡中發(fā)現(xiàn)社區(qū)演化還是很困難的,，原因有二：(1)不同的模式之間的演化是有關聯(lián)的；(2)不同模式具有獨特的演化樣式,。本文采用譜聚類架構,，提出一種發(fā)現(xiàn)動態(tài)多模網(wǎng)絡中演化社區(qū)的一般方法。一個動態(tài)多模網(wǎng)絡會包含一系列的網(wǎng)絡快照,，利用這些快照可以找出社區(qū)是如何演化的,。在這個模型下，加入正則項反映時態(tài)變化[4],，可以將有聯(lián)系模式的聚類結(jié)果和相鄰時間戳作為一個模式下的社區(qū)更新的屬性,，是一個將動態(tài)多模網(wǎng)絡分析和常規(guī)的基于屬性的數(shù)據(jù)挖掘聯(lián)系起來的新方法。
1 問題闡述
    給出含有m種類型元素X1,，X2,，…，Xm的m模網(wǎng)絡，找出每一模中的潛在社區(qū)是如何演化的[5],。在架構中,，通過一系列的網(wǎng)絡快照只關注離散時間戳，這個方法在正則項網(wǎng)絡分析中得到廣泛應用,。表1所示為下文中所涉符號及其表示的內(nèi)容,。

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

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

    在實際應用中,，異構參與者之間的互相作用形成了多模網(wǎng)絡。正是在這樣的網(wǎng)絡中,，不同模的參與者構成社區(qū)并慢慢演化,。本文提出了時態(tài)正則化多模聚類算法在動態(tài)多模網(wǎng)絡中發(fā)現(xiàn)演化社區(qū)。這個算法可以理解為迭代的LSA過程,，在不同模和時間戳下的屬性構成社區(qū)矩陣,。基于這種屬性視圖,，提出的算法也能擴展到處理帶有屬性的網(wǎng)絡,、模內(nèi)聯(lián)系以及休眠點和活躍點。實驗結(jié)果證明該算法能夠根據(jù)一系列的快照找到更精確的社區(qū)結(jié)構和社區(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.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] 王林，戴冠中.基于復雜網(wǎng)絡中社區(qū)結(jié)構的論壇熱點主題發(fā)現(xiàn)[J].計算機工程,，2008,，34(11)：214-21.