基于時(shí)間局部性的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)算法

摘 要：【目的】隨著社交網(wǎng)絡(luò)技術(shù)的快速發(fā)展，大規(guī)模復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)獲取成為電子、網(wǎng)絡(luò)、生物和醫(yī)學(xué)等多個(gè)學(xué)科領(lǐng)域亟待解決的問題。大規(guī)模復(fù)雜網(wǎng)絡(luò)由參與節(jié)點(diǎn)和虛擬連接組成，其中節(jié)點(diǎn)代表個(gè)體、家庭與社會等角色，而連接則刻畫了這些角色間的復(fù)雜關(guān)系。一般而言，復(fù)雜網(wǎng)絡(luò)中存在嚴(yán)重的同源性現(xiàn)象，即存在大量的重復(fù)或相似組成架構(gòu)，這極大地增加網(wǎng)絡(luò)動態(tài)結(jié)構(gòu)發(fā)現(xiàn)的難度。【方法】在時(shí)間局部性原理基礎(chǔ)上，提出一種啟發(fā)式網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，旨在進(jìn)一步優(yōu)化拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)的精確度和運(yùn)行耗時(shí)。通過修改相鄰時(shí)間范圍內(nèi)節(jié)點(diǎn)的計(jì)算規(guī)則，利用余弦相似性判定準(zhǔn)則與拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)算法深入描述網(wǎng)絡(luò)中多個(gè)參與節(jié)點(diǎn)之間復(fù)雜關(guān)系的可預(yù)測性。算法結(jié)合經(jīng)典Ｌｏｕｖａｉｎ算法，通過計(jì)算增量模塊度和余弦相似性優(yōu)化社區(qū)檢測的精確度和耗時(shí)。此外，算法使用模塊度概念，對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行準(zhǔn)確衡量，同時(shí)引入增量模塊度指標(biāo)計(jì)算表達(dá)式，以實(shí)時(shí)掌握拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)算法指標(biāo)的變化情況?！窘Y(jié)果】為驗(yàn)證所提算法的有效性，利用智能電網(wǎng)實(shí)際通信數(shù)據(jù)集進(jìn)行仿真，數(shù)據(jù)集包含１１５個(gè)用電單位的６１６條通信連接數(shù)據(jù)。仿真結(jié)果表明，與經(jīng)典Ｌｏｕｖａｉｎ算法相比，所提算法在檢測效率和運(yùn)行耗時(shí)上均有顯著優(yōu)勢。歸一化互信息量指標(biāo)的對比分析顯示，所提算法在參與節(jié)點(diǎn)數(shù)量較多時(shí)，具有更高的歸一化互信息量和更低的平均運(yùn)行耗時(shí)。算法在大規(guī)模網(wǎng)絡(luò)中具有優(yōu)勢，盡管在小規(guī)模網(wǎng)絡(luò)中表現(xiàn)稍遜。通過實(shí)際數(shù)據(jù)集仿真可知，基于時(shí)間局部性的拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)算法在大規(guī)模智能配電網(wǎng)絡(luò)的精準(zhǔn)發(fā)現(xiàn)方面具有明顯優(yōu)勢，性能表現(xiàn)突出，為智能電網(wǎng)領(lǐng)域提供優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)的策略?！窘Y(jié)論】綜上所述，基于時(shí)間局部性拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)算法的創(chuàng)新性在于將時(shí)間局部性原理應(yīng)用于網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)，為復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法的研究提供了新的視角和方法，對相關(guān)領(lǐng)域的研究具有參考意義。未來將考慮該算法在小規(guī)模網(wǎng)絡(luò)中的應(yīng)用問題，并進(jìn)一步分析算法的魯棒性。

關(guān) 鍵 詞：復(fù)雜網(wǎng)絡(luò)；拓?fù)浣Y(jié)構(gòu)；Ｌｏｕｖａｉｎ算法；社區(qū)發(fā)現(xiàn)算法；判定準(zhǔn)則；時(shí)間局部性；運(yùn)行耗時(shí)；模塊度

中圖分類號：ＴＰ３１１.１３ 文獻(xiàn)標(biāo)志碼：Ａ 文章編號：１０００－１６４６（２０２５）０１－００９２－０６

隨著社交網(wǎng)絡(luò)的快速發(fā)展和普及，如何快速獲取大規(guī)模復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)逐漸成為了多個(gè)學(xué)科亟待解決的問題［１－３］，并受到電子、網(wǎng)絡(luò)、生物和醫(yī)學(xué)等領(lǐng)域中眾多研究者的高度關(guān)注。通常而言，人類的大規(guī)模社交網(wǎng)絡(luò)主要由大量的參與節(jié)點(diǎn)和虛擬連接組成，其中，參與節(jié)點(diǎn)包含個(gè)體、家庭與社會等角色，虛擬連接則展示了多種角色間的復(fù)雜關(guān)系［４－６］。而在大規(guī)模復(fù)雜社交網(wǎng)絡(luò)的運(yùn)行過程中，海量的參與節(jié)點(diǎn)及虛擬連接必然存在重復(fù)或相似的組成架構(gòu)，這種情況被稱為相關(guān)網(wǎng)絡(luò)的同源性［７－１０］。但伴隨著網(wǎng)絡(luò)中多項(xiàng)因素的變化，復(fù)雜社交網(wǎng)絡(luò)的同源性結(jié)構(gòu)和特征經(jīng)常受到較大的影響。在諸多影響因素中，復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)及參與節(jié)點(diǎn)的時(shí)間屬性間存在著較為緊密的聯(lián)系，這也直接導(dǎo)致網(wǎng)絡(luò)動態(tài)結(jié)構(gòu)發(fā)現(xiàn)難度較大。

針對復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的發(fā)掘問題，國內(nèi)外學(xué)者做出了大量的嘗試與研究［１１－１５］。２０１６年，ＧＨＡＳＥＭＩＡＮ等［１６］在可檢測閾值的基礎(chǔ)上，提出了基于線性化ＢＰ方程的快速光譜聚類算法，從而提高了復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的探測精確度；２０１７年，ＤＩＴＵＲＳＩ等［１７］將傳統(tǒng)的局部社區(qū)檢測方法推廣到動態(tài)社交網(wǎng)絡(luò)的檢測過程中，并提出具有高內(nèi)部與低外部互動的動態(tài)社區(qū)發(fā)現(xiàn)算法，進(jìn)而優(yōu)化了社區(qū)拓?fù)浣Y(jié)構(gòu)算法的檢測質(zhì)量和運(yùn)行時(shí)間。然而上述算法的精確度仍較低，未能完全實(shí)現(xiàn)復(fù)雜網(wǎng)絡(luò)的快速、高效拓?fù)錂z測。為了優(yōu)化社區(qū)檢測算法的精確度和運(yùn)行耗時(shí)，本文利用時(shí)間局部性原理，同時(shí)選取余弦相似性判定準(zhǔn)則，提出了適用于復(fù)雜社區(qū)網(wǎng)絡(luò)的啟發(fā)式發(fā)現(xiàn)算法。相關(guān)仿真結(jié)果表明，所提算法提高了精確度并減少了運(yùn)行耗時(shí)。