發(fā)布時間：2018-01-02 18:23

  本文關(guān)鍵詞：基于三角模體的社團發(fā)現(xiàn)算法研究與應用　出處：《南京理工大學》2017年碩士論文　論文類型：學位論文

  更多相關(guān)文章： 社團發(fā)現(xiàn) 三角模體 復雜網(wǎng)絡 期望極大算法 混合隸屬度

【摘要】：隨著復雜網(wǎng)絡領域的發(fā)展,尤其是在互聯(lián)網(wǎng)高速發(fā)展下的社交網(wǎng)絡,涌現(xiàn)了一批新穎并且重要的發(fā)現(xiàn),吸引了各個學科的眾多研究者投入其中。社團結(jié)構(gòu)作為它的普遍存在的拓撲特性之一,對于它的探索有助于揭示網(wǎng)絡結(jié)構(gòu)與功能之間的關(guān)系,因此發(fā)現(xiàn)網(wǎng)絡中的社團結(jié)構(gòu)具有重要的理論和實際意義。本文主要針對現(xiàn)有社團發(fā)現(xiàn)算法進行研究,文中介紹并分析了現(xiàn)有的基于邊表示網(wǎng)絡的社團發(fā)現(xiàn)算法,針對其計算瓶頸的問題,設計了一種基于三角模體和期望極大的社團結(jié)構(gòu)發(fā)現(xiàn)(Community structure discovery based on triangular motifs and expectation-maximization,CSDTME)模型的社團發(fā)現(xiàn)算法。本文的主要工作如下:(1)針對現(xiàn)有采用邊表示網(wǎng)絡的社團發(fā)現(xiàn)算法的計算瓶頸問題,本文設計了一種基于三角模體的社團發(fā)現(xiàn)算法。本文通過三角模體對觀測網(wǎng)絡進行表示,簡化網(wǎng)絡結(jié)構(gòu)假設,為設計有效的算法提供基礎。通過對三角模體生成過程建模,設計了一個基于三角模體和期望極大的社團結(jié)構(gòu)發(fā)現(xiàn)(Community structure discovery based on triangular motifs and expectation-maximization,CSDTME)模型,以此來模擬觀測網(wǎng)絡,并提出了相應的社團發(fā)現(xiàn)算法,在算法中采用全三角模體和兩邊三角模體作為計算對象,在保證網(wǎng)絡真實結(jié)構(gòu)的同時,通過減少計算對象來提高算法的效率,返回節(jié)點的社團混合隸屬度及社團間的鏈接概率,并通過實驗證明了文中提出算法的可行性和有效性。(2)針對基于CSDTME模型的社團發(fā)現(xiàn)算法執(zhí)行效率問題,本文設計了一種基于CSDTME模型的社團發(fā)現(xiàn)算法的改進方法�；贑SDTME模型的社團發(fā)現(xiàn)算法在時間效率上已經(jīng)有了很大的改進,但是通過對該算法的進一步的研究,發(fā)現(xiàn)可以在時間和空間上還可以對該算法進行更進一步的改進,可以更快速的發(fā)現(xiàn)網(wǎng)絡中的社團結(jié)構(gòu)�；贑SDTME模型的社團發(fā)現(xiàn)算法在對參數(shù)求解的過程中在時間和空間上存在的問題,分別提出了在空間和時間上的應對策略,主要是通過減少迭代次數(shù)及中間變量的存儲,來提高算法的執(zhí)行效率。最后通過實驗,驗證了改進后的基于CSDTME模型的社團發(fā)現(xiàn)算法的可行性和有效性。并在此算法的基礎上,設計并實現(xiàn)了一個簡單的基于CSDTME模型的社團劃分系統(tǒng)。
[Abstract]:With the development of the complex network field, especially the social network with the rapid development of the Internet, a number of novel and important discoveries have emerged. Community structure is one of its ubiquitous topological characteristics, and its exploration will help to reveal the relationship between network structure and function. Therefore, it is of great theoretical and practical significance to discover the community structure in the network. This paper mainly focuses on the existing community discovery algorithm, and introduces and analyzes the existing community discovery algorithm based on edge representation network. Aiming at the problem of calculating bottleneck. A community structure discovery method based on triangular motifs and expectation maximization is proposed. Community structure discovery based on triangular motifs and. Expectation-maximization. CSDTME-based community discovery algorithm. The main work of this paper is as follows: 1) aiming at the bottleneck problem of the existing community discovery algorithm using edge representation network. In this paper, a community discovery algorithm based on triangular motifs is designed. In this paper, the observation network is represented by triangular motifs and the assumption of network structure is simplified. It provides the foundation for designing effective algorithm. Modeling the process of triangular motif generation. A community structure discovery based on triangular motifs and expectation maximization is designed. Community structure discovery based on triangular motifs and. Expectation-maximization. CSDTME-based model is used to simulate the observation network, and the corresponding community discovery algorithm is proposed. In the algorithm, the full triangle motifs and the two side triangular motifs are used as the computing objects. While ensuring the real structure of the network, the efficiency of the algorithm is improved by reducing the computing objects, and the community membership degree and the link probability between the communities are returned. The experiment proves the feasibility and effectiveness of the proposed algorithm. 2) aiming at the efficiency of community discovery algorithm based on CSDTME model. This paper designs an improved method of community discovery algorithm based on CSDTME model. The community discovery algorithm based on CSDTME model has been greatly improved in terms of time efficiency. But through the further study of the algorithm, it is found that the algorithm can be further improved in time and space. Community structure in the network can be found more quickly. Community discovery algorithm based on CSDTME model in the process of solving the parameters in the process of time and space problems. Respectively put forward in space and time coping strategies, mainly by reducing the number of iterations and the storage of intermediate variables to improve the efficiency of the algorithm. Finally, through experiments. The improved community discovery algorithm based on CSDTME model is proved to be feasible and effective. A simple community partition system based on CSDTME model is designed and implemented.
【學位授予單位】：南京理工大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O157.5

【相似文獻】

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

1 王春連;胡秀珍;;用二次判別方法識別蛋白質(zhì)β-發(fā)夾模體[J];生物物理學報;2009年04期

2 李慧敏;胡俊;張靜;;果蠅核糖體蛋白基因中潛在轉(zhuǎn)錄協(xié)同作用模體的統(tǒng)計分析[J];云南大學學報(自然科學版);2010年03期

3 胡秀珍;李前忠;;矩陣打分的方法應用于蛋白質(zhì)β-發(fā)夾模體的識別[J];內(nèi)蒙古大學學報(自然科學版);2007年06期

4 姜雪;胡秀珍;;打分矩陣方法在β-發(fā)夾模體識別中的應用[J];生物信息學;2008年04期

5 岳俊杰;譚明峰;周圍;王夏;李北平;王月蘭;梁龍;;細菌黏附素序列模體分析[J];生物技術(shù)通訊;2008年05期

6 姜雪;;蛋白質(zhì)βαβ模體序列的統(tǒng)計分析及其識別[J];昆明理工大學學報(理工版);2010年05期

7 賈少春;胡秀珍;;基于添加功能位點信息的組合向量預測β-發(fā)夾模體[J];內(nèi)蒙古工業(yè)大學學報(自然科學版);2012年03期

8 陳丹;梁振霞;李慧敏;;組合調(diào)控中過表達模體對距離的統(tǒng)計檢驗[J];基因組學與應用生物學;2013年01期

9 宋航宇;胡秀珍;馮振興;姜卓;孫利霞;;基于統(tǒng)計特征的酶蛋白質(zhì)中特殊模體βαβ的預測[J];生物物理學報;2013年09期

10 葉玉珍,解濤,丁達夫;蛋白質(zhì)功能基團三維模體及其應用[J];科學通報;2000年12期

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

1 李彩艷;胡秀珍;;蛋白質(zhì)中兩種Strand-Loop-Strand模體的判斷[A];第十次中國生物物理學術(shù)大會論文摘要集[C];2006年

2 高燕莉;張鐳;李劍穎;;應用64排CT優(yōu)化高分辨CT掃描方案的模體研究[A];中華醫(yī)學會第十三屆全國放射學大會論文匯編（下冊）[C];2006年

3 李興東;萬國慶;田中青;;X射線CT檢測標準的研究[A];加入WTO和中國科技與可持續(xù)發(fā)展——挑戰(zhàn)與機遇、責任和對策（下冊）[C];2002年

4 安晶剛;;PET質(zhì)量檢測的方法及相應模體[A];全國醫(yī)用輻射防護與安全學術(shù)研討會論文匯編[C];2004年

相關(guān)博士學位論文 前9條

1 于強;生物序列模體發(fā)現(xiàn)算法研究[D];西安電子科技大學;2014年

2 宋濤;基于譜隱馬爾可夫模型的蛋白質(zhì)序列模體識別方法研究[D];大連理工大學;2015年

3 劉丙強;原核生物中的轉(zhuǎn)錄調(diào)控模體預測研究[D];山東大學;2010年

4 劉倩;基于貝葉斯統(tǒng)計的基因非編碼區(qū)與模體識別問題研究[D];西安電子科技大學;2014年

5 周川;原核生物調(diào)控模體和調(diào)節(jié)子預測算法研究[D];山東大學;2014年

6 周鵬;生物非鍵模體[D];浙江大學;2011年

7 張凌慧;基因組中順式調(diào)控模體的特征分析與計算預測[D];中國協(xié)和醫(yī)科大學;2005年

8 劉立芳;生物信息學中的多序列比對與模體識別問題研究[D];西安電子科技大學;2006年

9 張懿璞;轉(zhuǎn)錄因子結(jié)合位點識別問題的算法研究[D];西安電子科技大學;2014年

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

1 周燕;SRK-ARC1識別模體序列多態(tài)性與甘藍親和指數(shù)的相關(guān)性研究[D];西南大學;2015年

2 馬平;基因組序列8-mer模體使用分離與不同序列組成和物種進化的關(guān)系[D];內(nèi)蒙古大學;2015年

3 劉國君;酵母基因組8-mer模體使用的進化分離與功能分析[D];內(nèi)蒙古大學;2015年

4 王晶;ChIP-Seq中DNA模體挖掘工具的比較[D];蘇州大學;2015年

5 蘇潤梅;DNA序列中模體識別算法研究[D];電子科技大學;2014年

6 申軍軍;復雜超聲模體快速制造及其B超成像[D];石家莊鐵道大學;2015年

7 方慧婷;任務驅(qū)動社會網(wǎng)絡的模體分析與研究[D];浙江工業(yè)大學;2015年

8 李俊;基于MapReduce的軟件網(wǎng)絡模體查找算法研究[D];東北大學;2014年

9 楊志楓;原核生物調(diào)控模體預測與分析[D];山東大學;2016年

10 唐華陽;復雜網(wǎng)絡模體挖掘算法研究[D];昆明理工大學;2016年

，

本文編號：1370393