本文關(guān)鍵詞： 復(fù)雜網(wǎng)絡(luò) 社區(qū)發(fā)現(xiàn) 圖聚類 重疊聚類 稠密子圖　出處：《軟件學(xué)報(bào)》2017年11期 　論文類型：期刊論文

【摘要】：目前,針對(duì)復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法大多僅根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)來確定社區(qū),然而現(xiàn)實(shí)復(fù)雜網(wǎng)絡(luò)中的邊可能帶有表示連接緊密程度或者可信度意義的權(quán)重,這些先驗(yàn)信息對(duì)社區(qū)發(fā)現(xiàn)的準(zhǔn)確性至關(guān)重要.針對(duì)該問題,提出了基于加權(quán)稠密子圖的重疊聚類算法(overlap community detection on weighted networks,簡稱OCDW).首先,綜合考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及真實(shí)網(wǎng)絡(luò)中邊權(quán)重的影響,給出了一種網(wǎng)絡(luò)中邊的權(quán)重定義方法;進(jìn)而給出種子節(jié)點(diǎn)選取方式和權(quán)重更新策略;最終得到聚類結(jié)果.OCDW算法在無權(quán)網(wǎng)絡(luò)和加權(quán)網(wǎng)絡(luò)都適用.通過與一些經(jīng)典的社區(qū)發(fā)現(xiàn)算法在9個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行分析比較,結(jié)果表明算法OCDW在F度量、準(zhǔn)確度、分離度、標(biāo)準(zhǔn)互信息、調(diào)整蘭德系數(shù)、模塊性及運(yùn)行時(shí)間等方面均表現(xiàn)出較好的性能.
[Abstract]:At present, community discovery algorithms for complex networks are mostly based on the topology of the network to determine the community. However, the edges of complex networks may be weighted to indicate the degree of connection tightness or the significance of credibility. This priori information is very important to the accuracy of community discovery. In order to solve this problem, an overlap community detection on weighted networks algorithm based on weighted dense subgraph is proposed. Considering the influence of network topology and the influence of edge weight in real network, a method of defining edge weight in network is given, and the selection method of seed node and the strategy of weight updating are given. Finally, we get the clustering result. OCDW algorithm is applicable in both weighted and unweighted networks. By comparing with some classical community discovery algorithms on nine real network data sets, the results show that the algorithm OCDW is in F metric, accuracy, separation degree. Standard mutual information, adjustment of Rand coefficient, modularity and running time all show good performance.
【作者單位】： 山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院;山西大學(xué)計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室;
【分類號(hào)】：O157.5;TP301.6

【相似文獻(xiàn)】

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

1 徐以凡;;層分解和子圖識(shí)別問題[A];2001年全國數(shù)學(xué)規(guī)劃及運(yùn)籌研討會(huì)論文集[C];2001年

2 陶劍文;丁佩芬;趙杰煜;;csgIndex:一種可擴(kuò)展的對(duì)比子圖索引模型[A];第二十七屆中國控制會(huì)議論文集[C];2008年

3 吳衛(wèi)江;李國和;;Apriori算法思想在頻繁子圖挖掘中應(yīng)用的研究[A];第六屆全國信息獲取與處理學(xué)術(shù)會(huì)議論文集（2）[C];2008年

4 吳穎華;周皓峰;袁晴晴;洪銘勝;汪衛(wèi);施伯樂;;Topology:一個(gè)快速的頻繁連通子圖的挖掘算法[A];第二十屆全國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（技術(shù)報(bào)告篇）[C];2003年

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

1 李斌龍;重子圖條件下圖的Hamilton性及相關(guān)問題[D];西北工業(yè)大學(xué);2016年

2 藺厚元;禁用子圖與圖的哈密爾頓性[D];華中師范大學(xué);2012年

3 毛玲;基于層次因子圖的心電圖自動(dòng)診斷方法研究[D];國防科學(xué)技術(shù)大學(xué);2009年

4 崔慶;Tutte子圖方法及其應(yīng)用[D];南開大學(xué);2009年

5 吳云建;一致星因子圖與籠的連通性[D];南開大學(xué);2009年

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

1 范淦;高效的龐大圖的頻繁子圖挖掘方法研究[D];遼寧大學(xué);2015年

2 魏真真;大規(guī)模不確定圖緊密子圖挖掘算法研究[D];燕山大學(xué);2015年

3 齊寶雷;面向不確定圖數(shù)據(jù)的子圖模式挖掘算法的研究與實(shí)現(xiàn)[D];東北大學(xué);2013年

4 王會(huì)會(huì);精確子圖數(shù)據(jù)庫查詢技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2014年

5 白楊;復(fù)雜網(wǎng)絡(luò)圖中高密度子圖檢測(cè)方法與實(shí)現(xiàn)[D];西安電子科技大學(xué);2014年

6 王鵬;基于局部鄰域的最大密度子圖檢測(cè)方法研究與實(shí)現(xiàn)[D];西安電子科技大學(xué);2014年

7 王璐璐;不確定圖上Top-k子圖相似性查詢技術(shù)研究[D];東北大學(xué);2014年

8 張?zhí)烀?大圖上頻繁子圖挖掘算法的研究[D];東北大學(xué);2014年

9 王峰;基于眾核平臺(tái)子圖匹配算法研究[D];北京理工大學(xué);2016年

10 滕鵬舉;向心路徑結(jié)點(diǎn)定義的子圖劃分與聚類子圖邊交叉數(shù)計(jì)算[D];北京林業(yè)大學(xué);2016年

，

本文編號(hào)：1510106