本文選題：復雜網(wǎng)絡 + 社區(qū)發(fā)現(xiàn)　； 參考：《重慶大學》2016年碩士論文

【摘要】：隨著互聯(lián)網(wǎng)的蓬勃發(fā)展,社交網(wǎng)絡變得日益龐大和復雜。社交網(wǎng)絡是指人與人之間關系而組成的復雜網(wǎng)絡。復雜的社交網(wǎng)絡存在著一個共同的特性——社團結構,即社團內(nèi)部的節(jié)點聯(lián)系緊湊,而社團之間的節(jié)點聯(lián)系稀疏。在整個網(wǎng)絡中,我們根據(jù)節(jié)點之間關聯(lián)關系,尋找聯(lián)系緊密小型子網(wǎng)絡結構的過程稱為社團劃分或社區(qū)發(fā)現(xiàn)。網(wǎng)絡中的類型社團根據(jù)所有節(jié)點是否所屬于多個社團情況分為非重疊社團和重疊社團。社交網(wǎng)絡的社團劃分可以應用于多個場景:在同一個社團中推薦好友、對同一個社團中用戶進行商品推薦等。由于社交網(wǎng)絡具有復雜網(wǎng)絡的一般特性,人們常常使用復雜網(wǎng)絡對社交網(wǎng)絡建立模型進行研究。獲得復雜的社交網(wǎng)絡中高效而又準確的社團劃分,這是研究復雜網(wǎng)絡中社團劃分問題的出發(fā)點和落腳點。在此研究領域中,眾多學者提出許多經(jīng)典的算法:GN算法、譜平分算法、隨機游走算法、標簽傳播算法、CPM算法和EAGLE算法等。然而,近年來,社交網(wǎng)絡呈指數(shù)式發(fā)展,許多經(jīng)典的算法面臨了更多的挑戰(zhàn)。本論文著力于無向網(wǎng)絡的非重疊社團劃分的研究問題,根據(jù)不同的社交網(wǎng)絡特性提出了三種社團劃分算法。(1)面對規(guī)模較小已知社團個數(shù)網(wǎng)絡時,本論文針對非重疊社團劃分問題,提出了ECFM算法(Easy Community Finding based on Matrix Algorithm)。該算法劃分后的準確率較高,但是該算法存在著不足:需要指定網(wǎng)絡中的社團個數(shù),否則無法判斷算法終止條件。(2)針對ECFM算法的缺陷,本論文利用遺傳算法和聚類算法的思想,提出了GKNM算法(Genetic K-Means based on Normal Matrix Algorithm)。該算法較以前的經(jīng)典算法在劃分準確率上得到明顯地提升。該算法由于采用了遺傳算法的架構,該算法的運行時間耗費較長。同時,該算法選取了Normal矩陣作為聚類模型,不適用于規(guī)模較大的網(wǎng)絡。(3)針對復雜的網(wǎng)絡模型,本論文利用了LPA算法具有超低時間復雜度的特性,采用了多重標簽傳播模型,提出了CMLPA算法(Multiple Label Propagation based on Clique Algorithm)。該算法不僅在時間復雜度上與LPA算法一樣近乎線性,而且在結果準確率上高于其它一些算法。在設計算法時,CMLPA算法遵循了Pregel計算框架,該算法是可以運行在Spark大數(shù)據(jù)框架下。
[Abstract]:With the vigorous development of the Internet, social networks have become increasingly large and complex. Social network is a complex network formed by the relationship between people. A common feature of complex social networks is the community structure, in which the nodes within the community are closely connected and the connections between the communities are sparse. In the whole network, the process of searching for a compact sub-network is called community division or community discovery according to the relationship between nodes. The types of societies in the network are divided into non-overlapping associations and overlapping societies according to whether all nodes belong to more than one community. Social network community division can be used in many scenarios: recommend friends in the same community, recommend goods to users in the same community, etc. Because social networks have the general characteristics of complex networks, people often use complex networks to model social networks. It is the starting point and end point of studying the problem of community division in complex social networks to obtain efficient and accurate community partition in complex social networks. In this field, many scholars have proposed many classical algorithms, such as: GN algorithm, spectral partition algorithm, random walk algorithm, label propagation algorithm, EAGLE algorithm and so on. However, with the exponential development of social networks in recent years, many classical algorithms face more challenges. In this paper, we focus on the study of the non-overlapping community partitioning of undirected networks. According to different characteristics of social networks, we propose three community partitioning algorithms. In this paper, ECFM algorithm is proposed to solve the problem of nonoverlapping community division. The accuracy of the algorithm after partition is high, but the algorithm has some shortcomings: we need to specify the number of communities in the network, otherwise we can not judge the termination condition of the algorithm. (2) aiming at the defects of the ECFM algorithm, this paper uses the idea of genetic algorithm and clustering algorithm. The genetic K-Means based on Normal Matrix algorithm (GKNM) is proposed. Compared with the previous classical algorithm, this algorithm can improve the partition accuracy obviously. Because of the structure of genetic algorithm, the running time of the algorithm is very long. At the same time, the algorithm selects Normal matrix as the clustering model, which is not suitable for large-scale network. Aiming at the complex network model, this paper makes use of the characteristic of LPA algorithm with ultra-low time complexity and adopts the multi-label propagation model. In this paper, CMLPA algorithm is proposed. The algorithm is not only as linear as the LPA algorithm in time complexity, but also more accurate than some other algorithms. When designing the algorithm, the CMLPA algorithm follows the Pregel computing framework, and the algorithm can run under the framework of Spark big data.
【學位授予單位】：重慶大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O157.5

【參考文獻】

相關期刊論文 前4條

1 武志昊;林友芳;Steve Gregory;萬懷宇School of Computer and Information Technology,Beijing Jiaotong University;田盛豐;;Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks[J];Journal of Computer Science & Technology;2012年03期

2 ;Group decision-making method based on entropy and experts cluster analysis[J];Journal of Systems Engineering and Electronics;2011年03期

3 向玨良;在并行分布式圖匹配方案中的分割算法實現(xiàn)[J];上海工程技術大學學報;1998年03期

4 向玨良;一個有效的圖匹配并行分布式算法[J];上海工程技術大學學報;1995年04期

相關碩士學位論文 前1條

1 戴文華;基于混合并行遺傳算法的文本分類及聚類研究[D];華中師范大學;2007年

，

本文編號：1977670