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

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

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

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 杜p，

本文編號：2547750