隨著互聯(lián)網(wǎng)技術(shù)的不斷提高和普及,越來(lái)越多的用戶加入社交網(wǎng)絡(luò)平臺(tái),從而形成了大規(guī)模的社交網(wǎng)絡(luò),分析和挖掘社交網(wǎng)絡(luò)隱藏的信息是非常具有研究?jī)r(jià)值的。最大團(tuán)是社交網(wǎng)絡(luò)中聯(lián)系最緊密的結(jié)構(gòu),因此通過(guò)最大團(tuán)來(lái)分析社交網(wǎng)絡(luò)是非常有效的方式。最大團(tuán)問(wèn)題(Maximal Clique Problem,MCP)是一類經(jīng)典的NP-完全問(wèn)題,在現(xiàn)實(shí)生活領(lǐng)域獲得廣泛的應(yīng)用。本文通過(guò)研究K-Core算法,發(fā)現(xiàn)K-Core算法通過(guò)不斷迭代剪枝能夠獲取到一個(gè)最大近似團(tuán),并且在最大近似團(tuán)中可能包含有最大團(tuán)。因此,本文提出先使用K-Core算法對(duì)圖進(jìn)行剪枝獲得最大近似團(tuán),然后使用分支限界法獲得最大團(tuán)的研究方法。并且,為了處理具有海量數(shù)據(jù)的社交網(wǎng)絡(luò)的場(chǎng)景,本文通過(guò)使用Spark分布式內(nèi)存框架,實(shí)現(xiàn)了分布式K-Core算法。本論文的主要的工作內(nèi)容如下:1,通過(guò)將K-Core算法和分支限界算法結(jié)合,通過(guò)實(shí)驗(yàn)證明了算法具有提升分支限界算法搜索最大團(tuán)的效率。2,將K-Core算法和Spark分布式計(jì)算框架結(jié)合,設(shè)計(jì)和實(shí)現(xiàn)了分布式K-Core算法,并通過(guò)實(shí)驗(yàn)證明了算法的可行性。3,將算法應(yīng)用到真實(shí)的大型金融社交網(wǎng)絡(luò)——BoardEx中。在BoardEx中通過(guò)組合算法挖掘出最大團(tuán),分析其中的職位信息,發(fā)現(xiàn)在這個(gè)縮小圖中的職位比例近似于原始社交網(wǎng)絡(luò)的職位比例,說(shuō)明在獲取的最大團(tuán)能夠在一定程度上代表BoardEx社交網(wǎng)絡(luò)進(jìn)行某些特征的數(shù)據(jù)分析。
【學(xué)位單位】：暨南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2018
【中圖分類】：O157.5;TP301.6
【部分圖文】：

2.1 社交網(wǎng)絡(luò)的屬性現(xiàn)階段的社交網(wǎng)絡(luò)具有海量的用戶和錯(cuò)綜復(fù)雜的關(guān)系，和社交網(wǎng)絡(luò)在結(jié)構(gòu)上都存在著相同的屬性，而這些屬性在大型社交網(wǎng)絡(luò)中表現(xiàn)更加明顯。其中最具有代表性的三個(gè)屬性：無(wú)尺度分布（scale-free distribution）[24]、小世界效應(yīng)（thesmall-world effect）[24]和強(qiáng)的社區(qū)結(jié)構(gòu)（strong community structure）[24]。2.1.1 無(wú)尺度分布無(wú)尺度分布（scale-free distribution）在圖論中也被稱為冪率分布（power lawdistribution）[25]，如圖 2-1 所描述的是擁有 1138499 個(gè)頂點(diǎn) YouTube 和擁有17115255 條邊 Wiki[26]這兩個(gè)社交網(wǎng)絡(luò)中頂點(diǎn)的度分布情況，從圖中可以看出，這兩個(gè)社交網(wǎng)絡(luò)中大多數(shù)的頂點(diǎn)的度都是比較低的，而只有少數(shù)頂點(diǎn)擁有較高的度，如度值大于 103。并且在圖中頂點(diǎn)的度分布可以用近似線性模式表達(dá)出來(lái)，所以就將符合這種模式特征的分布稱為冪率分布，即無(wú)尺度分布。

分布式 K-Core 算法加速求解最大團(tuán)問(wèn)題及在金融社交網(wǎng)絡(luò)中應(yīng)用.2.1 最大團(tuán)問(wèn)題的定義團(tuán)在圖論中的定義是：在圖 G（V，E），其中 V 表示圖 G 中的頂點(diǎn)，E 表 G 中的邊，存在著任意兩個(gè)頂點(diǎn)都有邊相互連接的子圖結(jié)構(gòu)，就將該子圖稱為團(tuán)。如果存在著這樣的團(tuán)，并且該團(tuán)不是其他團(tuán)的真子集，符合這種條團(tuán)被稱為極大團(tuán)（maximal clique）[36]。若在極大團(tuán)中，某個(gè)極大團(tuán)的頂點(diǎn)最多，則將這個(gè)極大團(tuán)稱為最大團(tuán)（maximum clique）[36]。團(tuán)的大小指的是所包含的頂點(diǎn)個(gè)數(shù)，即如果團(tuán)中包含的頂點(diǎn)個(gè)數(shù)為 k，則稱為 k 團(tuán)，如圖示，描述的是 3 團(tuán)，4 團(tuán)和 5 團(tuán)三個(gè)團(tuán)結(jié)構(gòu)。

圖 2-3 最大團(tuán)的問(wèn)題描述觀察如圖 2-3，可知無(wú)向圖 G（V，E）是由 10 個(gè)頂和 24 條邊構(gòu)成的，通過(guò)枚舉出這個(gè)無(wú)向圖 G 中的團(tuán)結(jié)構(gòu)，可以分解出 6 個(gè)團(tuán)結(jié)構(gòu)，很顯然這六個(gè)團(tuán)結(jié)構(gòu)都滿足屬性2和屬性4，而在這6個(gè)團(tuán)中，頂點(diǎn)數(shù)目最多的是最后一個(gè)團(tuán)Clique它包含有 5 個(gè)頂點(diǎn)，并且 Clique6 滿足團(tuán)的四個(gè)屬性，所以 Clique6 被認(rèn)為是圖G 中的最大團(tuán)。最大團(tuán)問(wèn)題就是通過(guò)最大團(tuán)搜索算法在圖 G 中找出和 Clique6 一樣的結(jié)構(gòu)的子圖問(wèn)題。最大團(tuán)問(wèn)題如果通過(guò)數(shù)學(xué)模型進(jìn)行描述的話，可以通過(guò)整型規(guī)劃的方式進(jìn)行描述，具體推導(dǎo)過(guò)程如下：設(shè) , t(x)={i ∈ } , ∈ , ∈ , 則t 其中∈, n 為圖的頂點(diǎn)數(shù)。tt（2.1）
【參考文獻(xiàn)】

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

1 謝平;鄒傳偉;;互聯(lián)網(wǎng)金融模式研究[J];金融研究;2012年12期

2 王青松;范鐵生;;低度圖的最大團(tuán)求解算法[J];計(jì)算機(jī)工程;2010年06期

3 王麗愛(ài);周旭東;陳崚;;最大團(tuán)問(wèn)題研究進(jìn)展及算法測(cè)試標(biāo)準(zhǔn)[J];計(jì)算機(jī)應(yīng)用研究;2007年07期

4 郭長(zhǎng)庚;潘曉偉;;對(duì)最大團(tuán)問(wèn)題的HEWN算法分析[J];河南科學(xué);2006年05期

本文編號(hào)：2884724