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

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

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

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

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

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

2 王青松;范鐵生;;低度圖的最大團求解算法[J];計算機工程;2010年06期

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

4 郭長庚;潘曉偉;;對最大團問題的HEWN算法分析[J];河南科學(xué);2006年05期

本文編號：2884724