【摘要】：社交網(wǎng)絡(luò)的動(dòng)態(tài)變化使社區(qū)發(fā)現(xiàn)的精確度面臨更高挑戰(zhàn)。目前提出的大部分算法都是以尋求模塊度最優(yōu)解來發(fā)現(xiàn)社區(qū),但往往會(huì)忽略所發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)是否穩(wěn)定。根據(jù)力學(xué)平衡原理即當(dāng)一個(gè)物體所受內(nèi)部力和外部力平衡的條件下可達(dá)穩(wěn)定狀態(tài),因此基于點(diǎn)的穩(wěn)定性機(jī)制,判斷節(jié)點(diǎn)來自社區(qū)內(nèi)部連邊數(shù)量與來自外部社區(qū)連邊數(shù)量的最大值是否保持平衡,提出一種可探測穩(wěn)定結(jié)構(gòu)的局部社區(qū)發(fā)現(xiàn)算法。網(wǎng)絡(luò)的穩(wěn)定性大小與社區(qū)的結(jié)構(gòu)有很大的關(guān)系,因此將網(wǎng)絡(luò)的穩(wěn)定性作為一種新的評(píng)價(jià)社區(qū)結(jié)構(gòu)優(yōu)良的標(biāo)準(zhǔn)。通過在真實(shí)網(wǎng)絡(luò)和人工集成網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn)對(duì)比發(fā)現(xiàn)提出的算法的社區(qū)結(jié)構(gòu)穩(wěn)定度比其他算法高,同時(shí)能發(fā)現(xiàn)精確度高的社區(qū)。
【圖文】：

的社交關(guān)系；該俱樂部有34個(gè)會(huì)員，但由于主管與校長由于人事問題產(chǎn)生了分歧，因此俱樂部分成兩大派。本文提出的算法與CFinder算法、LFM算法和Infomap算法在該經(jīng)典網(wǎng)絡(luò)中做了測試，各個(gè)算法的評(píng)價(jià)指標(biāo)值如表2所示。從表中可以看到本文算法的穩(wěn)定度最高。本文算法經(jīng)過4次迭代后網(wǎng)絡(luò)的穩(wěn)定值達(dá)到穩(wěn)定，網(wǎng)絡(luò)的聚集度為0.3153，所發(fā)現(xiàn)的社區(qū)個(gè)數(shù)是2個(gè)，與真實(shí)社區(qū)相符。其余3種算法發(fā)現(xiàn)的社區(qū)個(gè)數(shù)是3個(gè)，證明本文算法的準(zhǔn)確度比較高（右邊的括號(hào)表示的是按照值的大小排序的位置標(biāo)號(hào)）。本文算法對(duì)KarateClub的分區(qū)結(jié)果，如圖7所示。（2）DolphinNet，海豚網(wǎng)絡(luò)是一個(gè)真實(shí)存在用于研究社交關(guān)系的經(jīng)典網(wǎng)絡(luò)，是科學(xué)家通過研究新西蘭神奇海灣62只海豚的生活，所描述的海豚之間的社交聯(lián)系。在本文中依然采用本文算法，CFinder（k=3）算法，LFM算法和Infomap在網(wǎng)絡(luò)上進(jìn)行測試，測試結(jié)果如表3所示，可以看出Infomap算法雖然可以達(dá)到很高的模塊度但穩(wěn)定度沒有本文算法高。本文算法對(duì)DolphinNet的分區(qū)結(jié)果，如圖8所示。本文算法經(jīng)過4次迭代后網(wǎng)絡(luò)的穩(wěn)定值達(dá)到穩(wěn)定，網(wǎng)絡(luò)的聚集度為0.2692，所發(fā)現(xiàn)的社區(qū)個(gè)數(shù)是3個(gè)，但有兩個(gè)節(jié)點(diǎn)（8，20）是獨(dú)立社團(tuán)，將該獨(dú)立社團(tuán)加入任何一個(gè)都不會(huì)引起模塊度的變化，但將該獨(dú)立社團(tuán)加入社區(qū)1后，穩(wěn)定度由0.45003變?yōu)?.45017，所以將（8，20）分到社區(qū)1中，結(jié)果與真實(shí)社區(qū)結(jié)果相符。CFinde（rk=3）發(fā)現(xiàn)的社區(qū)個(gè)數(shù)是4個(gè)，LFM算法發(fā)現(xiàn)的社區(qū)個(gè)數(shù)是9個(gè)，Infomap算法所發(fā)現(xiàn)的社區(qū)個(gè)數(shù)是7個(gè)，社區(qū)發(fā)現(xiàn)效果均不如本文算法。（3）Colledgefootball，是基于足球隊(duì)之間的常規(guī)賽形成的一個(gè)足球社交網(wǎng)絡(luò)，該足球隊(duì)有115個(gè)隊(duì)員形成12個(gè)聯(lián)盟，，賽程安排規(guī)定足球聯(lián)盟隊(duì)內(nèi)的比賽多于隊(duì)間的比賽，因此形成明顯的社區(qū)結(jié)構(gòu)，可以

值納縝釱鍪?是3個(gè)，證明本文算法的準(zhǔn)確度比較高（右邊的括號(hào)表示的是按照值的大小排序的位置標(biāo)號(hào)）。本文算法對(duì)KarateClub的分區(qū)結(jié)果，如圖7所示。（2）DolphinNet，海豚網(wǎng)絡(luò)是一個(gè)真實(shí)存在用于研究社交關(guān)系的經(jīng)典網(wǎng)絡(luò)，是科學(xué)家通過研究新西蘭神奇海灣62只海豚的生活，所描述的海豚之間的社交聯(lián)系。在本文中依然采用本文算法，CFinder（k=3）算法，LFM算法和Infomap在網(wǎng)絡(luò)上進(jìn)行測試，測試結(jié)果如表3所示，可以看出Infomap算法雖然可以達(dá)到很高的模塊度但穩(wěn)定度沒有本文算法高。本文算法對(duì)DolphinNet的分區(qū)結(jié)果，如圖8所示。本文算法經(jīng)過4次迭代后網(wǎng)絡(luò)的穩(wěn)定值達(dá)到穩(wěn)定，網(wǎng)絡(luò)的聚集度為0.2692，所發(fā)現(xiàn)的社區(qū)個(gè)數(shù)是3個(gè)，但有兩個(gè)節(jié)點(diǎn)（8，20）是獨(dú)立社團(tuán)，將該獨(dú)立社團(tuán)加入任何一個(gè)都不會(huì)引起模塊度的變化，但將該獨(dú)立社團(tuán)加入社區(qū)1后，穩(wěn)定度由0.45003變?yōu)?.45017，所以將（8，20）分到社區(qū)1中，結(jié)果與真實(shí)社區(qū)結(jié)果相符。CFinde（rk=3）發(fā)現(xiàn)的社區(qū)個(gè)數(shù)是4個(gè)，LFM算法發(fā)現(xiàn)的社區(qū)個(gè)數(shù)是9個(gè)，Infomap算法所發(fā)現(xiàn)的社區(qū)個(gè)數(shù)是7個(gè)，社區(qū)發(fā)現(xiàn)效果均不如本文算法。（3）Colledgefootball，是基于足球隊(duì)之間的常規(guī)賽形成的一個(gè)足球社交網(wǎng)絡(luò)，該足球隊(duì)有115個(gè)隊(duì)員形成12個(gè)聯(lián)盟，賽程安排規(guī)定足球聯(lián)盟隊(duì)內(nèi)的比賽多于隊(duì)間的比賽，因此形成明顯的社區(qū)結(jié)構(gòu)，可以進(jìn)行算法研究。采用本文算法，CFinder（k=3）算法，LFM算法和Infomap算法在網(wǎng)絡(luò)上進(jìn)行測試，測試結(jié)果發(fā)現(xiàn)本文算法的社區(qū)結(jié)構(gòu)比較穩(wěn)定，如表4所示。4種算法都能很好地發(fā)現(xiàn)足球聯(lián)隊(duì)之間的社區(qū)結(jié)構(gòu)，即各個(gè)足球聯(lián)隊(duì)之間的分布明顯。本文算法發(fā)現(xiàn)的社區(qū)模塊度不如其他算法，但是統(tǒng)計(jì)最大社區(qū)個(gè)數(shù)發(fā)現(xiàn)，本文算法能發(fā)現(xiàn)的是社區(qū)最多是13個(gè)，與真實(shí)社區(qū)（12個(gè)）的相似度為0.92，而Info

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 任慶生,葉中行,曾進(jìn);進(jìn)化算法的收斂速度[J];上海交通大學(xué)學(xué)報(bào);1999年06期

2 唐浩;;蟻群算法的研究與展望[J];牡丹江教育學(xué)院學(xué)報(bào);2009年06期

3 鄧小波;曹聰聰;龍倫海;康耀紅;;蟻群算法搜索熵研究[J];海南大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年04期

4 張康;顧幸生;;全局組搜索優(yōu)化算法及其應(yīng)用研究[J];青島科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年05期

5 李東曉;蔣珉;柴干;;蟻群算法優(yōu)化及其在高速公路緊急救援中的應(yīng)用[J];計(jì)算機(jī)技術(shù)與發(fā)展;2010年11期

6 李德勝;張才仙;陳淑銘;;選擇策略對(duì)進(jìn)化算法性能的影響[J];科技資訊;2007年11期

7 韓明紅;鄧家y

本文編號(hào)：2586157