【摘要】：針對(duì)現(xiàn)有社區(qū)發(fā)現(xiàn)算法存在社區(qū)質(zhì)量不滿足圖可視化要求和算法效率低的問(wèn)題,提出一種改進(jìn)的啟發(fā)式社區(qū)發(fā)現(xiàn)算法.該算法基于模塊度優(yōu)化,通過(guò)結(jié)合預(yù)先選取種子節(jié)點(diǎn)的方法,抑制算法中大社區(qū)的過(guò)度合并,同時(shí)及時(shí)合并小的社區(qū);然后針對(duì)力導(dǎo)引布局算法存在社區(qū)結(jié)構(gòu)不明顯和布局效率低問(wèn)題,提出一種展示大規(guī)模社區(qū)結(jié)構(gòu)的社區(qū)布局算法,通過(guò)引入社區(qū)引力促使同一社區(qū)中的節(jié)點(diǎn)聚攏,優(yōu)化了社區(qū)引力建模,簡(jiǎn)化了布局算法步驟.實(shí)驗(yàn)結(jié)果表明,文中算法能夠清晰、高效地展示大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù).
【圖文】：

334計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)第29卷a.Louvain算法b.改進(jìn)的社區(qū)發(fā)現(xiàn)算法圖1Facebook1數(shù)據(jù)集社區(qū)劃分結(jié)果可視化對(duì)比a.Louvain算法b.改進(jìn)的社區(qū)發(fā)現(xiàn)算法圖2Hamsterster數(shù)據(jù)集社區(qū)劃分結(jié)果可視化對(duì)比a.Louvain算法b.改進(jìn)的社區(qū)發(fā)現(xiàn)算法圖3Facebook2數(shù)據(jù)集社區(qū)劃分結(jié)果可視化對(duì)比對(duì)于Hamsterster數(shù)據(jù)集,Louvain算法結(jié)果中有131個(gè)社區(qū),本文改進(jìn)算法劃分結(jié)果為30個(gè)社區(qū).從圖2可以看出,相對(duì)于Louvain算法,本文改進(jìn)的社區(qū)發(fā)現(xiàn)算法的劃分結(jié)果中小社區(qū)的數(shù)量較少;Louvain算法在迭代過(guò)程中存在小社區(qū)未及時(shí)合并到大社區(qū)的現(xiàn)象,而本文改進(jìn)算法改善了這一現(xiàn)象.對(duì)于Facebook2數(shù)據(jù)集,Louvain算法結(jié)果中有7個(gè)社區(qū),本文改進(jìn)算法劃分結(jié)果為14個(gè)社區(qū),社區(qū)數(shù)量多于Louvain算法.對(duì)比表3可以看出,本文改進(jìn)算法模塊度評(píng)價(jià)指標(biāo)優(yōu)于Louvain算法,Louvain算法在迭代過(guò)程中存在過(guò)度合并大社區(qū)的現(xiàn)象,而本文改進(jìn)的社區(qū)發(fā)現(xiàn)算法改善了這一現(xiàn)象.4.2.2社區(qū)布局算法實(shí)驗(yàn)及分析按照上述的實(shí)驗(yàn)方案,針對(duì)數(shù)據(jù)集Zachary和Dolphins,對(duì)比基于復(fù)雜社區(qū)劃分的可視化布局算法[4]和結(jié)合k-means提出的CGDA算法[3],可視化結(jié)果如圖4~5所示.可以看出,朱志良等[4]算法的可視化結(jié)果中,社區(qū)結(jié)構(gòu)不夠明顯,同時(shí)不同社區(qū)的節(jié)點(diǎn)之間排列緊密;CGDA算法社區(qū)結(jié)構(gòu)相對(duì)較明顯,但是在布局中由于沒(méi)有加入重力,導(dǎo)致布局會(huì)呈現(xiàn)拉伸形狀;本文社區(qū)布局算法中,社區(qū)結(jié)構(gòu)明顯,社區(qū)內(nèi)的節(jié)點(diǎn)排列緊密且社區(qū)間邊界分明.相對(duì)于朱志良等[4]提出的布局算法和吳渝等[3]提出的CGDA算法,本文改進(jìn)算法布局效率更高,耗時(shí)更少,對(duì)比結(jié)果如表4所示.在較大數(shù)據(jù)集布局

334計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)第29卷a.Louvain算法b.改進(jìn)的社區(qū)發(fā)現(xiàn)算法圖1Facebook1數(shù)據(jù)集社區(qū)劃分結(jié)果可視化對(duì)比a.Louvain算法b.改進(jìn)的社區(qū)發(fā)現(xiàn)算法圖2Hamsterster數(shù)據(jù)集社區(qū)劃分結(jié)果可視化對(duì)比a.Louvain算法b.改進(jìn)的社區(qū)發(fā)現(xiàn)算法圖3Facebook2數(shù)據(jù)集社區(qū)劃分結(jié)果可視化對(duì)比對(duì)于Hamsterster數(shù)據(jù)集,Louvain算法結(jié)果中有131個(gè)社區(qū),本文改進(jìn)算法劃分結(jié)果為30個(gè)社區(qū).從圖2可以看出,相對(duì)于Louvain算法,本文改進(jìn)的社區(qū)發(fā)現(xiàn)算法的劃分結(jié)果中小社區(qū)的數(shù)量較少;Louvain算法在迭代過(guò)程中存在小社區(qū)未及時(shí)合并到大社區(qū)的現(xiàn)象,而本文改進(jìn)算法改善了這一現(xiàn)象.對(duì)于Facebook2數(shù)據(jù)集,Louvain算法結(jié)果中有7個(gè)社區(qū),本文改進(jìn)算法劃分結(jié)果為14個(gè)社區(qū),社區(qū)數(shù)量多于Louvain算法.對(duì)比表3可以看出,本文改進(jìn)算法模塊度評(píng)價(jià)指標(biāo)優(yōu)于Louvain算法,Louvain算法在迭代過(guò)程中存在過(guò)度合并大社區(qū)的現(xiàn)象,而本文改進(jìn)的社區(qū)發(fā)現(xiàn)算法改善了這一現(xiàn)象.4.2.2社區(qū)布局算法實(shí)驗(yàn)及分析按照上述的實(shí)驗(yàn)方案,針對(duì)數(shù)據(jù)集Zachary和Dolphins,對(duì)比基于復(fù)雜社區(qū)劃分的可視化布局算法[4]和結(jié)合k-means提出的CGDA算法[3],可視化結(jié)果如圖4~5所示.可以看出,朱志良等[4]算法的可視化結(jié)果中,社區(qū)結(jié)構(gòu)不夠明顯,同時(shí)不同社區(qū)的節(jié)點(diǎn)之間排列緊密;CGDA算法社區(qū)結(jié)構(gòu)相對(duì)較明顯,但是在布局中由于沒(méi)有加入重力,導(dǎo)致布局會(huì)呈現(xiàn)拉伸形狀;本文社區(qū)布局算法中,社區(qū)結(jié)構(gòu)明顯,社區(qū)內(nèi)的節(jié)點(diǎn)排列緊密且社區(qū)間邊界分明.相對(duì)于朱志良等[4]提出的布局算法和吳渝等[3]提出的CGDA算法,本文改進(jìn)算法布局效率更高,耗時(shí)更少,對(duì)比結(jié)果如表4所示.在較大數(shù)據(jù)集布局
【作者單位】： 重慶郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;
【基金】：國(guó)家自然科學(xué)基金(61572092) 重慶教委科學(xué)技術(shù)研究項(xiàng)目(KJ130518) 國(guó)家社會(huì)科學(xué)基金(13CGL146)
【分類號(hào)】：TP301.6

【相似文獻(xiàn)】

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

1 ;基于位置的手機(jī)社交網(wǎng)絡(luò)“貝多”正式發(fā)布[J];中國(guó)新通信;2008年06期

2 曹增輝;;社交網(wǎng)絡(luò)更偏向于用戶工具[J];信息網(wǎng)絡(luò);2009年11期

3 ;美國(guó):印刷企業(yè)青睞社交網(wǎng)絡(luò)營(yíng)銷新方式[J];中國(guó)包裝工業(yè);2010年Z1期

4 李智惠;柳承燁;;韓國(guó)移動(dòng)社交網(wǎng)絡(luò)服務(wù)的類型分析與促進(jìn)方案[J];現(xiàn)代傳播(中國(guó)傳媒大學(xué)學(xué)報(bào));2010年08期

5 賈富;;改變一切的社交網(wǎng)絡(luò)[J];互聯(lián)網(wǎng)天地;2011年04期

6 譚拯;;社交網(wǎng)絡(luò):連接與發(fā)現(xiàn)[J];廣東通信技術(shù);2011年07期

7 陳一舟;;社交網(wǎng)絡(luò)的發(fā)展趨勢(shì)[J];傳媒;2011年12期

8 殷樂(lè);;全球社交網(wǎng)絡(luò)新態(tài)勢(shì)及文化影響[J];新聞與寫作;2012年01期

9 許麗;;社交網(wǎng)絡(luò):孤獨(dú)年代的集體狂歡[J];上海信息化;2012年09期

10 李玲麗;吳新年;;科研社交網(wǎng)絡(luò)的發(fā)展現(xiàn)狀及趨勢(shì)分析[J];圖書館學(xué)研究;2013年01期

相關(guān)會(huì)議論文 前10條

1 趙云龍;李艷兵;;社交網(wǎng)絡(luò)用戶的人格預(yù)測(cè)與關(guān)系強(qiáng)度研究[A];第七屆（2012）中國(guó)管理學(xué)年會(huì)商務(wù)智能分會(huì)場(chǎng)論文集（選編）[C];2012年

2 宮廣宇;李開(kāi)軍;;對(duì)社交網(wǎng)絡(luò)中信息傳播的分析和思考——以人人網(wǎng)為例[A];首屆華中地區(qū)新聞與傳播學(xué)科研究生學(xué)術(shù)論壇獲獎(jiǎng)?wù)撐腫C];2010年

3 楊子鵬;喬麗娟;王夢(mèng)思;楊雪迎;孟子冰;張禹;;社交網(wǎng)絡(luò)與大學(xué)生焦慮緩解[A];心理學(xué)與創(chuàng)新能力提升——第十六屆全國(guó)心理學(xué)學(xué)術(shù)會(huì)議論文集[C];2013年

4 畢雪梅;;體育虛擬社區(qū)中的體育社交網(wǎng)絡(luò)解析[A];第九屆全國(guó)體育科學(xué)大會(huì)論文摘要匯編(4)[C];2011年

5 杜p，

本文編號(hào)：2547750