本文選題：社會網(wǎng)絡(luò)　切入點：標簽傳播　出處：《西南大學》2015年碩士論文

【摘要】：現(xiàn)實世界中的很多網(wǎng)絡(luò)系統(tǒng)都可以抽象成社會網(wǎng)絡(luò),在這些網(wǎng)絡(luò)中,節(jié)點表示個體,節(jié)點之間的邊表示個體之間的相互聯(lián)系。隨著對社會網(wǎng)絡(luò)研究的不斷深入,人們發(fā)現(xiàn)網(wǎng)絡(luò)具有社團結(jié)構(gòu)的特性,在社團結(jié)構(gòu)內(nèi)部,節(jié)點之間的連接比較緊密,而社團與社團之間的節(jié)點連接較為稀疏。社團結(jié)構(gòu)往往代表了網(wǎng)絡(luò)中具有某一相同屬性特征的節(jié)點集合,挖掘網(wǎng)絡(luò)中這種社團結(jié)構(gòu)對研究社會網(wǎng)絡(luò)的演化過程、分析網(wǎng)絡(luò)的拓撲結(jié)構(gòu)以及了解網(wǎng)絡(luò)潛在的功能都具有非常重要的意義。本文圍繞著如何快速且有效地對網(wǎng)絡(luò)中的社團結(jié)構(gòu)進行聚類這一問題進行了相關(guān)研究。本文首先分析總結(jié)了社團聚類的相關(guān)背景與研究現(xiàn)狀,研究了有關(guān)社會網(wǎng)絡(luò)的重要理論,為后續(xù)研究奠定了理論基礎(chǔ)。對基于局部信息的標簽傳播算法(LPA算法)進行了深入研究與分析,發(fā)現(xiàn)LPA算法在算法迭代過程中會出現(xiàn)“標簽?zāi)媪鳌爆F(xiàn)象,同時初始化標簽數(shù)目過多,標簽更新條件單一、不全面,標簽更新策略具有隨機性等問題,針對這些問題給出了總體的解決方案。在具體實現(xiàn)這個解決方案的基礎(chǔ)上,本文提出了一種帶有適合度的標簽傳播算法,記為LPA-FA算法。LPA-FA算法首先將網(wǎng)絡(luò)中所有的節(jié)點按照其度的大小進行排序,組成了一個有序的節(jié)點序列,在每次算法迭代過程中,都按照這個節(jié)點序列依次進行節(jié)點標簽更新,避免了LPA算法由于采用隨機節(jié)點序列而造成的“標簽?zāi)媪鳌爆F(xiàn)象,提高了算法效率。在節(jié)點標簽初始化過程中,在LPA-FA算法中設(shè)計了一種簡單線性初始化方法,減少了網(wǎng)絡(luò)中初始標簽的個數(shù),從而降低算法的運行時間。然后在節(jié)點標簽傳播過程中,當節(jié)點的更新標簽出現(xiàn)不唯一時,LPA-FA算法引入了鄰接子系統(tǒng)聚集系數(shù)、鄰接邊權(quán)重、節(jié)點屬性相似度三個參數(shù),進而通過Topsis方法得到三者的綜合評價值標簽適合度,最終選擇使標簽適合度最大的鄰接子系統(tǒng)內(nèi)的標簽作為更新標簽,不僅解決了LPA算法節(jié)點標簽更新條件單一、不全面的缺陷,也克服了LPA算法的隨機性,從而降低算法的時間開銷,提高了聚類社團的質(zhì)量。最后,將LPA-FA算法與LPA算法分別在Zachary空手道俱樂部網(wǎng)絡(luò)和科學家合著網(wǎng)絡(luò)兩個數(shù)據(jù)集上進行了實驗,并對實驗結(jié)果與實驗數(shù)據(jù)進行比對分析。最終,實驗表明本文提出的LPA-FA算法無論在運行時間,還是聚類社團的質(zhì)量上都要優(yōu)于LPA算法,從而驗證了LPA-FA算法的有效性。
[Abstract]:Many network systems in the real world can be abstracted into social networks in which nodes represent individuals and edges between nodes represent individual relationships.With the development of the research on social network, it is found that the network has the characteristics of community structure. Within the community structure, the connections between nodes are relatively close, and the connections between communities and communities are sparse.The community structure often represents a set of nodes with the same attribute in the network, mining this kind of community structure in the network to study the evolution process of the social network.It is very important to analyze the topological structure of the network and to understand the potential functions of the network.This paper focuses on how to quickly and effectively cluster the community structure in the network.Firstly, this paper analyzes and summarizes the relevant background and research status of community clustering, and studies the important theory of social network, which lays a theoretical foundation for further research.In this paper, the label propagation algorithm based on local information is deeply studied and analyzed. It is found that the LPA algorithm will appear the phenomenon of "label countercurrent" in the iterative process of the algorithm, at the same time, the number of initialized tags is too many, and the condition of tag updating is single.In view of these problems, the overall solution is given.Based on the implementation of this solution, this paper proposes a label propagation algorithm with degree of fitness, which is called LPA-FA algorithm. LPA-FA algorithm first sorts all nodes in the network according to their degree.An ordered node sequence is formed. In each iteration process, the node label is updated according to the node sequence in turn, which avoids the "label countercurrent" phenomenon caused by the adoption of random node sequences in the LPA algorithm.The algorithm efficiency is improved.In the process of node label initialization, a simple linear initialization method is designed in the LPA-FA algorithm, which reduces the number of initial tags in the network and thus reduces the running time of the algorithm.Then, in the process of node label propagation, the LPA-FA algorithm introduces three parameters, such as the clustering coefficient of adjacent subsystem, the weight of adjacent edge, and the similarity of node attribute, when the updated label of nodes is not unique.Then through the Topsis method to get the three comprehensive evaluation value label fitness, finally select the label in the adjacent subsystem with the greatest label fitness as the update label, not only solve the LPA algorithm node label update condition is single.The defect of incompleteness also overcomes the randomness of LPA algorithm, which reduces the time cost of the algorithm and improves the quality of clustering community.Finally, the LPA-FA algorithm and the LPA algorithm are experimented on the Zachary karate club network and the scientist coauthor network, respectively, and the experimental results are compared with the experimental data.Finally, the experimental results show that the proposed LPA-FA algorithm is superior to the LPA algorithm in terms of running time and clustering community quality, thus validating the effectiveness of the LPA-FA algorithm.
【學位授予單位】：西南大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5;TP311.13

【參考文獻】

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

1 李曉佳;張鵬;狄增如;樊瑛;;復雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)[J];復雜系統(tǒng)與復雜性科學;2008年03期

2 李軍利;趙紅領(lǐng);范明;;郵件社區(qū)劃分和小世界網(wǎng)絡(luò)[J];計算機應(yīng)用;2008年S1期

3 沙愛暉;黃樹成;李甜;;一種基于網(wǎng)絡(luò)社團結(jié)構(gòu)和模塊化函數(shù)的聚類算法[J];計算機應(yīng)用與軟件;2014年04期

4 金弟;楊博;劉杰;劉大有;何東曉;;復雜網(wǎng)絡(luò)簇結(jié)構(gòu)探測——基于隨機游走的蟻群算法[J];軟件學報;2012年03期

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

1 汪大明;復雜網(wǎng)絡(luò)社團模型與結(jié)構(gòu)研究[D];國防科學技術(shù)大學;2010年

2 李明濤;結(jié)合話題的社會網(wǎng)絡(luò)社團發(fā)現(xiàn)技術(shù)研究[D];解放軍信息工程大學;2012年

，

本文編號：1700323