發(fā)布時間：2018-01-14 20:00

  本文關鍵詞：基于少量選點的社團檢測算法研究　出處：《蘭州大學》2015年碩士論文　論文類型：學位論文

  更多相關文章： 社團檢測 層次凝聚 標簽傳播 半監(jiān)督學習和主動學習

【摘要】：近年來,隨著復雜網絡數量的不斷增多,復雜網絡所涉及的領域不斷擴大,對復雜網絡性質的研究已經成為一門非常熱門的課題。復雜網絡通常具有一定的社團結構,即社團內部的關系緊密而社團與社團之間的關系稀疏,對應到網絡圖上就是社團內部的邊多而社團與社團之間的邊稀少。如何快速、有效地從復雜網絡中獲取社團結構,是大多學者研究的主要方向,也具有重要的應用價值。本文通過查閱相關的中外文獻,對現有的社團檢測算法進行研究,設計了兩種新的社團發(fā)現算法：基于少量選點的層次凝聚社團檢測算法(HCDFSN)和基于少量選點的主動半監(jiān)督社團檢測算法(ASCDFSN)。HCDFSN算法介紹了一種節(jié)點相似性度量方法、核心節(jié)點度量方法以及根據相似性處理社團間重疊節(jié)點的方法。該算法的大致思想為從核心節(jié)點出發(fā)來構建新的社團,直到所有核心節(jié)點用完為止；然后處理社團間重疊的部分；最后基于模塊度對初始社團合并得到最終社團結構。HCDFSN算法通過初始社團形成方法和社團邊界處理方法可以解決以下兩個問題：(1)層次凝聚算法中社團邊界節(jié)點一旦分錯,不能重新劃分問題；(2)層次凝聚算法中效果不理想問題。ASCDFSN算法介紹了一種得分計算方法、候選節(jié)點獲取方法以及主動半監(jiān)督策略。該算法的主要思想是通過得分計算方法獲取候選點集合；再從候選節(jié)點中選取一部分節(jié)點,進行人工標記；最后使用半監(jiān)督思想進行社團檢測。ASCDFSN算法通過得分選取策略和主動半監(jiān)督策略可以解決半監(jiān)督算法中以下三個問題：(1)隨機選取少量節(jié)點導致社團檢測效果不佳問題；(2)選點經常不能覆蓋所有社團問題。本文在多個真實網絡數據集和一個人工合成網絡數據集上進行實驗,對算法運行的過程進行可視化展示。并通過與同類型算法的實驗結果對比和復雜度分析表明,HCDFSN算法和ASCDFSN算法在社團檢測上有較好的效果且效率較高。
[Abstract]:In recent years, with the increase of the number of complex networks, the field of complex networks is expanding. The study of the nature of complex networks has become a very hot topic. Complex networks usually have a certain community structure, that is, the relationships within the community are close and the relationship between the community and the community is sparse. Corresponding to the network diagram is that there are many edges within the community and there are few edges between the community and the community. How to quickly and effectively obtain the structure of the community from the complex network is the main research direction of most scholars. Also has the important application value. This article through the related domestic and foreign literature, carries on the research to the existing community detection algorithm. Two new community discovery algorithms are designed: HCDFSN-based hierarchical aggregation community detection algorithm based on a small number of selected points and ASCDFSN-based active semi-supervised community detection algorithm based on a small number of selected points. HCDFSN algorithm introduces a node similarity measurement method. The core node measurement method and the method of dealing with overlapping nodes between communities according to similarity. The general idea of this algorithm is to construct a new community from the core node until all the core nodes are exhausted. The overlapping parts of the community are then dealt with; Finally, based on modularity, the final community structure. HCDFSN algorithm can solve the following two problems: 1: 1 through the initial community formation method and the community boundary processing method. In hierarchical aggregation algorithm, community boundary nodes are partitioned. The problem cannot be reclassified; The problem of unsatisfactory effect in hierarchical aggregation algorithm. ASCDFSN algorithm introduces a method of score calculation. The main idea of this algorithm is to obtain the set of candidate points by the method of score calculation. Then selected some nodes from the candidate nodes to carry out manual marking; Finally, the semi-supervised algorithm is used for community detection. ASCDFSN algorithm can solve the following three problems in semi-supervised algorithm by the strategy of score selection and active semi-supervision. Selecting a small number of nodes at random leads to the poor effect of community detection. In this paper, experiments are carried out on multiple real network data sets and an artificial synthetic network data set. The operation process of the algorithm is visualized and compared with the experimental results of the same kind of algorithm and the complexity analysis shows that. HCDFSN algorithm and ASCDFSN algorithm have good effect and high efficiency in community detection.
【學位授予單位】：蘭州大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5

【相似文獻】

相關期刊論文 前10條

1 謝明霞;王家耀;郭建忠;陳科;;不等距劃分的高維相似性度量方法研究[J];武漢大學學報(信息科學版);2012年07期

2 賀玲;吳玲達;蔡益朝;;高維空間中數據的相似性度量[J];數學的實踐與認識;2006年09期

3 隋正偉;鄔陽;劉瑜;;基于簽到數據的用戶空間出行相似性度量方法研究[J];地理信息世界;2013年03期

4 李海林;郭崇慧;;基于多維形態(tài)特征表示的時間序列相似性度量[J];系統(tǒng)工程理論與實踐;2013年04期

5 楊艷春;孟祥武;;基于關鍵詞的對等網絡節(jié)點群相似性度量模型研究[J];武漢大學學報(理學版);2011年06期

6 李永寧;一種基于紋理的圖象相似性度量模型(英文)[J];四川大學學報(自然科學版);2003年02期

7 胡茂海;;基于相關輸出相似性度量的目標識別算法[J];中國激光;2012年04期

8 劉丹;衛(wèi)金茂;張杰;;GO術語間語義相似性度量方法[J];東北師大學報(自然科學版);2010年01期

9 杜培軍;唐宏;方濤;;高光譜遙感光譜相似性度量算法與若干新方法研究[J];武漢大學學報(信息科學版);2006年02期

10 郭銘銘;竇建華;楊彬;;基于形式化概念分析和概念相似性度量的程序重組方法(英文)[J];南京大學學報(自然科學版);2011年05期

相關會議論文 前10條

1 劉喜平;萬常選;;一種二維的樹型文檔結構相似性度量[A];第二十五屆中國數據庫學術會議論文集（二）[C];2008年

2 劉俊義;王潤生;;仿射不變的多邊形相似性度量[A];中國圖象圖形科學技術新進展——第九屆全國圖象圖形科技大會論文集[C];1998年

3 楊艷春;孟祥武;;P2P網絡服務環(huán)境中的節(jié)點相似性度量研究[A];CCF NCSC 2011——第二屆中國計算機學會服務計算學術會議論文集[C];2011年

4 李彬彬;羅樂;;基于信源學的光譜相似性度量方法的比較研究[A];2009全國計算機網絡與通信學術會議論文集[C];2009年

5 羅陽;趙偉;;相似性度量研究及最優(yōu)相似系數[A];中國氣象學會2008年年會天氣預報準確率與公共氣象服務分會場論文集[C];2008年

6 周曉蕾;唐明浩;於思俊;;服裝款式系統(tǒng)中的相似性度量算法研究[A];2008年中國高校通信類院系學術研討會論文集（下冊）[C];2009年

7 劉寶生;閆莉萍;周東華;;圖像匹配中相似性度量[A];第16屆中國過程控制學術年會暨第4屆全國故障診斷與安全性學術會議論文集[C];2005年

8 李新光;鄭君君;祝一薇;劉建軍;夏勝平;譚立球;;基于屬性圖模型的圖像相似性度量[A];第十五屆全國圖象圖形學學術會議論文集[C];2010年

9 沈君;馬生全;;兩種新的相似性度量在模糊推理中的應用[A];中國運籌學會模糊信息與模糊工程分會第五屆學術年會論文集[C];2010年

10 廉鑫;林偉堅;張海威;袁曉潔;;基于雙向路徑約束模型的XML文檔結構相似性度量[A];NDBC2010第27屆中國數據庫學術會議論文集(B輯)[C];2010年

相關博士學位論文 前5條

1 白雪;聚類分析中的相似性度量及其應用研究[D];北京交通大學;2012年

2 張明;基于內容的圖象相似性度量技術研究及其在水利中的應用[D];河海大學;2003年

3 邱明;語義相似性度量及其在設計管理系統(tǒng)中的應用[D];浙江大學;2006年

4 周瑜;視頻跟蹤中的目標建模及相似性度量研究[D];華中科技大學;2014年

5 戚文靜;基于范例的圖案創(chuàng)作關鍵技術研究[D];山東大學;2012年

相關碩士學位論文 前10條

1 曹莉莉;基于GC-MS的高速譜庫搜索算法研究[D];安徽大學;2015年

2 蔣欣;基于粒子濾波的故障預報算法研究[D];福建師范大學;2015年

3 張豪;符號序列相似性度量及聚類新算法[D];福建師范大學;2015年

4 周漢海;基于少量選點的社團檢測算法研究[D];蘭州大學;2015年

5 黃_g;相似性度量的研究及其在數據挖掘中的應用[D];福建師范大學;2009年

6 練仕榴;生物醫(yī)學信號的相似性度量研究[D];天津理工大學;2011年

7 朱波;程序代碼相似性度量方法研究[D];長春工業(yè)大學;2015年

8 湯淵;面向詞袋模型的相似性度量方法在特征降維中的應用[D];廣東工業(yè)大學;2015年

9 孟曉峰;基于異質信息網絡的相似性度量研究[D];北京郵電大學;2015年

10 鄭斐;時間序列相似性度量方法及其在生理信息挖掘中的應用[D];北京交通大學;2012年

，

本文編號：1425057