本文選題：復(fù)雜網(wǎng)絡(luò)　切入點(diǎn)：社區(qū)結(jié)構(gòu)　出處：《山東大學(xué)》2017年博士論文

【摘要】：許多真實(shí)系統(tǒng),比如工程中的電力網(wǎng)絡(luò),生物學(xué)中的基因調(diào)控網(wǎng)絡(luò),像Facebook 一樣的社會(huì)網(wǎng)絡(luò)等,都可以用圖或者網(wǎng)絡(luò)來描述,其中節(jié)點(diǎn)代表一個(gè)實(shí)體,若兩個(gè)實(shí)體之間有聯(lián)系則連一條邊。復(fù)雜系統(tǒng)不是隨機(jī)的,而是有許多局部的或者整體的特征。一個(gè)重要的特征就是許多網(wǎng)絡(luò)中都存在的社區(qū)結(jié)構(gòu),即社區(qū)內(nèi)部節(jié)點(diǎn)連接稠密,社區(qū)與社區(qū)之間連接稀疏。社區(qū)結(jié)構(gòu)是一個(gè)非常重要的性質(zhì),因?yàn)樗麄冃纬闪司W(wǎng)絡(luò)的功能模塊。例如,社會(huì)網(wǎng)絡(luò)中的各個(gè)群體擁有他們自己的標(biāo)準(zhǔn)、方向和文化。在一個(gè)細(xì)胞中,一些蛋白質(zhì)相互作用形成了蛋白質(zhì)復(fù)合體發(fā)揮它們的作用。我們的主要研究對(duì)象就是復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu),尤其是內(nèi)部結(jié)構(gòu)。本文總共分為六章,第一章為緒論,簡單介紹了復(fù)雜網(wǎng)絡(luò)的相關(guān)概念及主要研究方向,尤其是社區(qū)結(jié)構(gòu)。第二章至第五章為文章的主體部分,也是本文的主要?jiǎng)?chuàng)新點(diǎn)。第六章中我們首先對(duì)我們所做的工作做了總結(jié),其次給出了在我們的研究基礎(chǔ)上還有哪些問題值得進(jìn)一步研究。首先,我們引入領(lǐng)導(dǎo)者社區(qū)與自組織社區(qū)的概念,并研究了社區(qū)中領(lǐng)導(dǎo)者節(jié)點(diǎn)的重要作用。社區(qū)結(jié)構(gòu)對(duì)于復(fù)雜網(wǎng)絡(luò)的特性及動(dòng)力系統(tǒng)起著重要的作用。然而,據(jù)我們所知,很少有學(xué)者對(duì)社區(qū)的內(nèi)部結(jié)構(gòu)進(jìn)行研究。本文第二章中,我們用十種社區(qū)劃分算法對(duì)二十種真實(shí)世界網(wǎng)絡(luò)進(jìn)行社區(qū)劃分,發(fā)現(xiàn)大部分社區(qū)內(nèi)都含有少數(shù)幾個(gè)領(lǐng)導(dǎo)者,即幾個(gè)度數(shù)特別大的節(jié)點(diǎn)。我們用一個(gè)統(tǒng)計(jì)參數(shù),即方差,來區(qū)分領(lǐng)導(dǎo)者社區(qū)與自組織社區(qū)。其中,領(lǐng)導(dǎo)者社區(qū)內(nèi)部含有幾個(gè)度數(shù)特別大的節(jié)點(diǎn),幾乎連接了社區(qū)中其余節(jié)點(diǎn);而自組織社區(qū)是指社區(qū)內(nèi)部節(jié)點(diǎn)的度數(shù)都差不多,不存在哪個(gè)節(jié)點(diǎn)在社區(qū)中具有控制作用。我們發(fā)現(xiàn),在社會(huì)網(wǎng)絡(luò)及引文網(wǎng)絡(luò)中,領(lǐng)導(dǎo)者社區(qū)要多于自組織社區(qū)。在領(lǐng)導(dǎo)者社區(qū)內(nèi),我們定義度數(shù)最大的前10%的節(jié)點(diǎn)為領(lǐng)導(dǎo)者節(jié)點(diǎn)。在我們的實(shí)驗(yàn)中,我們將領(lǐng)導(dǎo)者節(jié)點(diǎn)去掉之后,社區(qū)內(nèi)部的連邊數(shù)平均意義上減少了 40%,社區(qū)與社區(qū)之間的邊數(shù)平均意義上減少了 20%以上。另外,社區(qū)的平均聚類系數(shù)有所下降。這些現(xiàn)象說明,領(lǐng)導(dǎo)者節(jié)點(diǎn)在保持社區(qū)稠密與聚類中起著重要作用,并且,領(lǐng)導(dǎo)者節(jié)點(diǎn)相對(duì)于其他節(jié)點(diǎn)更傾向于與其他社區(qū)連邊。最后,我們發(fā)現(xiàn)在幾種隨機(jī)網(wǎng)絡(luò)上可以得到相似的結(jié)果并給出了一個(gè)刪除了領(lǐng)導(dǎo)者節(jié)點(diǎn)社區(qū)內(nèi)部邊丟失的理論下界。我們的研究為社區(qū)內(nèi)部結(jié)構(gòu)的研究與應(yīng)用提供了新的思路。其次,我們提出一種新的指標(biāo),即度方差比ρ,用來準(zhǔn)確區(qū)分復(fù)雜網(wǎng)絡(luò)中的領(lǐng)導(dǎo)者社區(qū)與自組織社區(qū)。不久前,領(lǐng)導(dǎo)者社區(qū)與自組織社區(qū)已經(jīng)被提出來,可以用來研究社區(qū)的生成機(jī)制。然而,如何有效識(shí)別自組織社區(qū)與領(lǐng)導(dǎo)者社區(qū)在技術(shù)上還是一個(gè)挑戰(zhàn),因?yàn)槟壳斑�沒有一個(gè)很好的度量可以區(qū)分兩種社區(qū)。我們提出一種新的度量,稱為度方差比,來區(qū)分兩種社區(qū)結(jié)構(gòu),并給出了一個(gè)隨機(jī)模型來解釋我們的度量的合理性。通過在多個(gè)真實(shí)世界網(wǎng)絡(luò)中以及在多個(gè)社區(qū)劃分算法下的實(shí)驗(yàn),我們驗(yàn)證了用度方差比來識(shí)別自組織社區(qū)與領(lǐng)導(dǎo)者社區(qū)的有效性與穩(wěn)定性。我們發(fā)現(xiàn)社會(huì)網(wǎng)絡(luò)與引文網(wǎng)絡(luò)中的領(lǐng)導(dǎo)者社區(qū)要多于自組織社區(qū),而在技術(shù)網(wǎng)絡(luò)如電力網(wǎng)絡(luò)中自組織社區(qū)要多于領(lǐng)導(dǎo)者社區(qū)。另外,我們的結(jié)果還顯示自組織社區(qū)的節(jié)點(diǎn)個(gè)數(shù)往往要小于領(lǐng)導(dǎo)者社區(qū)的節(jié)點(diǎn)個(gè)數(shù)。該項(xiàng)工作為研究社區(qū)的內(nèi)部結(jié)構(gòu)與社區(qū)的生成機(jī)制提供了新的思路。再次,我們研究了社區(qū)與社區(qū)之間的關(guān)系。社區(qū)結(jié)構(gòu)和核與外圍結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的兩個(gè)普遍存在的特征,兩種結(jié)構(gòu)的獨(dú)立研究都已有十幾年的歷史,但是很少有學(xué)者將兩者結(jié)合起來研究。我們首先探索了社區(qū)中的核與外圍結(jié)構(gòu),提出一種在社區(qū)內(nèi)部劃分核與外圍的線性時(shí)間算法,即將一個(gè)社區(qū)劃分成一個(gè)內(nèi)部連接稠密的核與一個(gè)內(nèi)部連接非常稀疏的外圍�；谏鐓^(qū)內(nèi)部的核與外圍結(jié)構(gòu),我們定量分析了社區(qū)之間的連邊并提出兩種社區(qū)關(guān)系,即統(tǒng)一化與多極化。兩個(gè)社區(qū)被稱為是統(tǒng)一的如果兩個(gè)社區(qū)的連邊中核與核之間的連邊多于外圍與外圍之間的連邊,否則兩個(gè)社區(qū)被稱為是多極化的。我們還提出了一種隨機(jī)模型,稱為廣義的GN(Girvan-Newman)模型,不僅可以生成社區(qū)是多極化的社區(qū)網(wǎng)絡(luò),還可以生成社區(qū)是統(tǒng)一化的社區(qū)網(wǎng)絡(luò)。該項(xiàng)工作也為研究網(wǎng)絡(luò)的多核與多外圍結(jié)構(gòu)提出了一個(gè)新的思路。最后,我們也給出一種劃分社區(qū)的算法。社區(qū)結(jié)構(gòu)發(fā)現(xiàn)對(duì)于理解社會(huì)學(xué)、生物學(xué)、工程技術(shù)領(lǐng)域的真實(shí)世界網(wǎng)絡(luò)的結(jié)構(gòu)和動(dòng)力系統(tǒng)是非常關(guān)鍵的一步。我們提出一種深度隨機(jī)模型,并基于非負(fù)矩陣分解得到一種新的社區(qū)劃分算法。該模型中含有兩組參數(shù),一組是社區(qū)成員矩陣,它的一行中的每個(gè)元素代表這個(gè)節(jié)點(diǎn)分別屬于每個(gè)社區(qū)的概率;另外一組是社區(qū)-社區(qū)連接矩陣,第i行第j列元素代表分別從i社區(qū)與j社區(qū)中隨機(jī)取一個(gè)節(jié)點(diǎn),它們之間有連邊的概率。這兩組參數(shù)可以通過一個(gè)有效的迭代算法得到,并且該迭代算法是收斂的。我們算法中的社區(qū)-社區(qū)連接矩陣比傳統(tǒng)的基于非負(fù)矩陣分解的算法的社區(qū)-社區(qū)連接矩陣要更加精確。另外,非負(fù)矩陣分解算法可以看成我們模型的一種特殊情況。最后,在人造網(wǎng)絡(luò)與真實(shí)世界網(wǎng)絡(luò)上面的實(shí)驗(yàn)驗(yàn)證了我們算法的有效性。
[Abstract]:......
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

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

1 胡小強(qiáng);李玲;林太志;王鈺;;混合居住社區(qū)內(nèi)部分異實(shí)證研究[A];規(guī)劃創(chuàng)新：2010中國城市規(guī)劃年會(huì)論文集[C];2010年

相關(guān)重要報(bào)紙文章 前2條

1 記者 顧曉紅;閔行引入社會(huì)組織參與專業(yè)服務(wù)[N];聯(lián)合時(shí)報(bào);2011年

2 李曉軍 本報(bào)記者 毛學(xué)農(nóng);構(gòu)建居家養(yǎng)老“大三角”[N];江淮時(shí)報(bào);2012年

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

1 付京成;復(fù)雜網(wǎng)絡(luò)中的社區(qū)內(nèi)部結(jié)構(gòu)研究[D];山東大學(xué);2017年

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

1 王湘懿;城市化進(jìn)程中農(nóng)轉(zhuǎn)城社區(qū)內(nèi)部治理研究[D];東北財(cái)經(jīng)大學(xué);2016年

，

本文編號(hào)：1712081