【摘要】：針對全局社區(qū)發(fā)現(xiàn)方法計算復(fù)雜度過高,而局部社區(qū)發(fā)現(xiàn)方法社區(qū)發(fā)現(xiàn)質(zhì)量偏低的不足,提出了一種快速有效的社區(qū)劃分算法。算法預(yù)先探測網(wǎng)絡(luò)中屬于不同社區(qū)的核心節(jié)點,利用基于相似性傳遞的節(jié)點相似性度量方法度量核心節(jié)點與網(wǎng)絡(luò)中其他節(jié)點之間的相似性,根據(jù)相似性度量結(jié)果對網(wǎng)絡(luò)進行社區(qū)結(jié)構(gòu)劃分。在采自人人網(wǎng)的數(shù)據(jù)和公共的網(wǎng)絡(luò)數(shù)據(jù)上進行了實驗,并與經(jīng)典算法進行比較,實驗結(jié)果表明了該算法的可行性和有效性。
【圖文】：

量頂點相異度的方法。結(jié)構(gòu)同等是指兩個節(jié)點的鏈接關(guān)系相同，即兩個節(jié)點有著相同的鄰居節(jié)點，，若節(jié)點ｉ和ｊ結(jié)構(gòu)同等，則ｄｉｊ＝０。這種方法可以計算出網(wǎng)絡(luò)中任意節(jié)點之間的相異度，但是計算的結(jié)果有時并不能正確的反映節(jié)點之間的相異程度，如圖１所示。采用式（２）計算出Ｖ１２與Ｖ１的相異度為３．８７３，而Ｖ１２與Ｖ３３的相異度為３．６０５６，根據(jù)計算結(jié)果得到Ｖ１２與Ｖ３３更加近似，但是圖中顯然可以看出Ｖ１２僅與Ｖ１有邊連圖１空手道俱樂部成員間的相互關(guān)系接，計算結(jié)果顯然得出了錯誤的相異性度量。但是當(dāng)利用式（２）計算Ｖ３３，Ｖ１與Ｖ３４的相異度時，計算結(jié)果正確的反映出了節(jié)點之間的相異程度�？梢园l(fā)現(xiàn)Ｖ１２處于網(wǎng)絡(luò)的邊界位置，與該節(jié)點的鄰居節(jié)點個數(shù)很少，而Ｖ３３，Ｖ１與Ｖ３４都是大度數(shù)節(jié)點，所以發(fā)現(xiàn)采用式（２）往往不能正確得到低度數(shù)節(jié)點與其他節(jié)點的相似度，但可以用于計算大度數(shù)節(jié)點之間的相似度。局部相似性度量方法共同特點是利用節(jié)點的鄰域子圖，該類方法認(rèn)為兩個節(jié)點共有的鄰居節(jié)點越多，則兩個節(jié)點之間就更加相似［７］。節(jié)點Ｖｉ的鄰居節(jié)點集記為Ｎ（ｉ），即Ｎ（ｉ）＝｛Ｖｊ｜Ａｉｊ＝１｝。Ｖｉ的星型鄰域子圖記為Ｓｔ（ｉ），它是由Ｖｉ及其鄰居點集構(gòu)成，即Ｓｔ（ｉ）＝｛Ｖｉ｝∪Ｎ（ｉ）。如圖１所示，Ｖ６的星型鄰域子圖Ｓｔ（６）包括５個節(jié)點Ｓｔ（６）＝｛Ｖ１，Ｖ６，Ｖ７，Ｖ１１，Ｖ１７｝，Ｖ６

第３４卷第１２期牛冬冬，陳鴻昶，金鑫，等：基于核心節(jié)點的復(fù)雜網(wǎng)絡(luò)社區(qū)劃分算法社區(qū)的全部核心節(jié)點，對接下來的社區(qū)劃分具有重要意義。圖２是網(wǎng)絡(luò)Ｇ的簡單示意圖，設(shè)網(wǎng)絡(luò)Ｇ中存在著３個社區(qū)，不同社區(qū)之間用虛線連接。圖２網(wǎng)絡(luò)Ｇ社區(qū)關(guān)系如圖２所示，不同的社區(qū)內(nèi)部都會存在著一小部分節(jié)點處于社區(qū)的中心位置，并且會與網(wǎng)絡(luò)中的其他節(jié)點連接關(guān)系緊密，該類節(jié)點可認(rèn)為是網(wǎng)絡(luò)中的核心節(jié)點，本文所要探測的核心節(jié)點首先是大度數(shù)節(jié)點。定義網(wǎng)絡(luò)中節(jié)點的集合為Ｖ＝｛Ｖ１，…，Ｖｎ｝，根據(jù)網(wǎng)絡(luò)中節(jié)點之間的鏈接關(guān)系計算網(wǎng)絡(luò)中所有節(jié)點的度數(shù)，然后根據(jù)度數(shù)進行排序，定義排序后的節(jié)點集合為，然后取出集合中的前一部分節(jié)點即大度數(shù)節(jié)點構(gòu)成集合，則網(wǎng)絡(luò)中不同社區(qū)內(nèi)的核心節(jié)點一定處于集合中。在本文社區(qū)劃分算法中需要獲取的是每個社區(qū)內(nèi)部唯一的核心節(jié)點，然而同一個社區(qū)可能有多個大度數(shù)節(jié)點存在于集合中，所以需要對集合中的節(jié)點進行篩眩結(jié)合圖２進行分析不難得出由于不同社區(qū)的核心節(jié)點在網(wǎng)絡(luò)中相距較遠(yuǎn)，所以對節(jié)點進行相似性度量時，同一社區(qū)內(nèi)部的大度數(shù)節(jié)點相似度一定遠(yuǎn)大于不同社區(qū)內(nèi)部大度數(shù)節(jié)點之間的相似度。利用文中式（２）度量集合中節(jié)點兩兩之間的相似度，將相似度過高的節(jié)點從集合中剔除，余下的節(jié)點則組成新的集合，該集合即為本文探測出的核心節(jié)點集。２．２基于相似性傳遞的節(jié)點相似性度量方法本文進行社區(qū)劃分時涉及到計算網(wǎng)絡(luò)中核心節(jié)點與網(wǎng)絡(luò)中其他節(jié)點的相似性計算，但是利用式（２）無法得出正確的相似性度量結(jié)果，而利用式（３）只能度量與核心節(jié)點距離小于３的節(jié)點之間的相似性，無法度量網(wǎng)絡(luò)中所有非核心節(jié)點與核心節(jié)點的
【作者單位】： 國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心;國家計算機網(wǎng)絡(luò)與信息安全管理中心;
【基金】：國家973重點基礎(chǔ)研究發(fā)展計劃基金項目(2012CB315901、2012CB315905) 國家自然科學(xué)基金項目(61171108)
【分類號】：TP393.09

【參考文獻(xiàn)】

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

1 程學(xué)旗;沈華偉;;復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)[J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2011年01期

2 劉旭;易東云;;基于局部相似性的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J];自動化學(xué)報;2011年12期

【共引文獻(xiàn)】

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

1 張偉哲;王佰玲;何慧;譚卓鵬;;基于異質(zhì)網(wǎng)絡(luò)的意見領(lǐng)袖社區(qū)發(fā)現(xiàn)[J];電子學(xué)報;2012年10期

2 郭進時;湯紅波;王曉雷;;基于社會網(wǎng)絡(luò)增量的動態(tài)社區(qū)組織探測[J];電子與信息學(xué)報;2013年09期

3 張毅;曹晶晶;齊莉娜;吳必虎;;旅游目的地虛擬網(wǎng)絡(luò)結(jié)構(gòu)特征研究——以黃山市為例[J];北京大學(xué)學(xué)報(自然科學(xué)版);2013年06期

4 章祥蓀;張忠元;;非負(fù)矩陣分解:模型、算法和應(yīng)用[J];重慶師范大學(xué)學(xué)報(自然科學(xué)版);2013年06期

5 翁偉;朱順痣;吳蕓;;結(jié)合局部相似性的模塊密度法探測網(wǎng)絡(luò)社區(qū)[J];福建師范大學(xué)學(xué)報(自然科學(xué)版);2013年06期

6 周濤;張子柯;陳關(guān)榮;汪小帆;史定華;狄增如;樊瑛;方錦清;韓筱璞;劉建國;劉潤然;劉宗華;陸君安;呂金虎;呂琳媛;榮智海;汪秉宏;許小可;章忠志;;復(fù)雜網(wǎng)絡(luò)研究的機遇與挑戰(zhàn)[J];電子科技大學(xué)學(xué)報;2014年01期

7 闞佳倩;謝家榮;張海峰;;社會強化效應(yīng)及連邊權(quán)重對網(wǎng)絡(luò)信息傳播的影響分析[J];電子科技大學(xué)學(xué)報;2014年01期

8 王偉;楊慧;龔凱;唐明;都永海;;復(fù)雜網(wǎng)絡(luò)上的局域免疫研究[J];電子科技大學(xué)學(xué)報;2013年06期

9 劉瑩;劉國奇;任介夫;姜琳穎;張斌;;基于Web服務(wù)復(fù)雜網(wǎng)絡(luò)的服務(wù)社區(qū)構(gòu)建方法[J];東南大學(xué)學(xué)報(自然科學(xué)版);2013年06期

10 朱志良;林森;崔坤;于海;;基于復(fù)雜網(wǎng)絡(luò)社區(qū)劃分的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化布局算法[J];計算機輔助設(shè)計與圖形學(xué)學(xué)報;2011年11期

相關(guān)博士學(xué)位論文 前6條

1 饒衛(wèi)振;大規(guī)模動態(tài)車輛路徑問題優(yōu)化方法研究[D];大連理工大學(xué);2012年

2 段東圣;社會網(wǎng)絡(luò)中群組探測和話題建模技術(shù)研究[D];華中科技大學(xué);2013年

3 謝輝;基于復(fù)雜網(wǎng)絡(luò)的若干動態(tài)機制研究[D];西安電子科技大學(xué);2013年

4 劉瑤;社會網(wǎng)絡(luò)特征分析與社團結(jié)構(gòu)挖掘[D];電子科技大學(xué);2013年

5 史艷翠;基于通信數(shù)據(jù)的上下文移動用戶偏好動態(tài)獲取方法研究[D];北京郵電大學(xué);2013年

6 武志昊;復(fù)雜網(wǎng)絡(luò)中的重疊社團發(fā)現(xiàn)問題研究[D];北京交通大學(xué);2013年

相關(guān)碩士學(xué)位論文 前10條

1 曾王輝;微博網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)研究[D];云南大學(xué);2012年

2 熊湘云;基于二分網(wǎng)絡(luò)的多維度推薦技術(shù)研究[D];蘇州大學(xué);2013年

3 陳藝璇;基于多目標(biāo)遺傳算法的復(fù)雜網(wǎng)絡(luò)社區(qū)劃分[D];蘭州大學(xué);2013年

4 肖覓;基于移動用戶行為的移動社區(qū)發(fā)現(xiàn)方法研究與實現(xiàn)[D];北京郵電大學(xué);2013年

5 張繼偉;圈子理論：關(guān)系促進農(nóng)村信用社的發(fā)展[D];山西師范大學(xué);2013年

6 楊微;社會網(wǎng)絡(luò)中社團發(fā)現(xiàn)與協(xié)同推薦技術(shù)的研究[D];杭州電子科技大學(xué);2013年

7 劉馥源;民航集團客戶組織結(jié)構(gòu)發(fā)現(xiàn)算法研究與實現(xiàn)[D];北京交通大學(xué);2013年

8 葛軍;一種重疊社區(qū)發(fā)現(xiàn)算法及其在MapReduce上的實現(xiàn)[D];西安電子科技大學(xué);2013年

9 李笑笑;基于最小生成樹的復(fù)雜網(wǎng)絡(luò)社區(qū)檢測與圖像分割[D];西安電子科技大學(xué);2013年

10 陸蕊;網(wǎng)絡(luò)相位聚類模型及應(yīng)用[D];西安電子科技大學(xué);2013年

【二級參考文獻(xiàn)】

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

1 汪小帆;劉亞冰;;復(fù)雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)算法綜述[J];電子科技大學(xué)學(xué)報;2009年05期

2 何東曉;周栩;王佐;周春光;王U

本文編號：2525322