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

    當(dāng)今網(wǎng)絡(luò)擁有海量數(shù)據(jù)，要從海量數(shù)據(jù)中得到有用的信息是很困難的,，因此網(wǎng)絡(luò)分析[1]和建模[2]受到越來(lái)越多的關(guān)注,。目前很多研究工作都只涉及一種模式的網(wǎng)絡(luò)，即網(wǎng)絡(luò)中只存在一種類(lèi)型的參與者（點(diǎn)）,，參與者之間只存在同種類(lèi)型的關(guān)系（聯(lián)系）,。但是，最近迅猛發(fā)展的Web數(shù)據(jù)挖掘涉及到了不止一種類(lèi)型的參與者,，這些參與者之間的關(guān)系也不再僅限于一種,。這種類(lèi)型的網(wǎng)絡(luò)稱(chēng)為多模網(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ú)特的演化樣式。本文采用譜聚類(lèi)架構(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)系模式的聚類(lèi)結(jié)果和相鄰時(shí)間戳作為一個(gè)模式下的社區(qū)更新的屬性,，是一個(gè)將動(dòng)態(tài)多模網(wǎng)絡(luò)分析和常規(guī)的基于屬性的數(shù)據(jù)挖掘聯(lián)系起來(lái)的新方法,。
1 問(wèn)題闡述
    給出含有m種類(lèi)型元素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)容,。

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

    為了顯示參數(shù)調(diào)整的效果,，選擇中等噪音強(qiáng)度的數(shù)據(jù)集,，使用在線(xiàn)聚類(lèi)和正則化聚類(lèi)，時(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ī)則化有利于聚類(lèi)考慮時(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)正則化多模聚類(lè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ū)演化,。
參考文獻(xiàn)
[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] 王林,，戴冠中.基于復(fù)雜網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的論壇熱點(diǎn)主題發(fā)現(xiàn)[J].計(jì)算機(jī)工程,，2008，34(11)：214-21.