發(fā)布時(shí)間：2018-04-02 12:10

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

【摘要】：現(xiàn)實(shí)世界中的很多網(wǎng)絡(luò)系統(tǒng)都可以抽象成社會(huì)網(wǎng)絡(luò),在這些網(wǎng)絡(luò)中,節(jié)點(diǎn)表示個(gè)體,節(jié)點(diǎn)之間的邊表示個(gè)體之間的相互聯(lián)系。隨著對(duì)社會(huì)網(wǎng)絡(luò)研究的不斷深入,人們發(fā)現(xiàn)網(wǎng)絡(luò)具有社團(tuán)結(jié)構(gòu)的特性,在社團(tuán)結(jié)構(gòu)內(nèi)部,節(jié)點(diǎn)之間的連接比較緊密,而社團(tuán)與社團(tuán)之間的節(jié)點(diǎn)連接較為稀疏。社團(tuán)結(jié)構(gòu)往往代表了網(wǎng)絡(luò)中具有某一相同屬性特征的節(jié)點(diǎn)集合,挖掘網(wǎng)絡(luò)中這種社團(tuán)結(jié)構(gòu)對(duì)研究社會(huì)網(wǎng)絡(luò)的演化過(guò)程、分析網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)以及了解網(wǎng)絡(luò)潛在的功能都具有非常重要的意義。本文圍繞著如何快速且有效地對(duì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)進(jìn)行聚類(lèi)這一問(wèn)題進(jìn)行了相關(guān)研究。本文首先分析總結(jié)了社團(tuán)聚類(lèi)的相關(guān)背景與研究現(xiàn)狀,研究了有關(guān)社會(huì)網(wǎng)絡(luò)的重要理論,為后續(xù)研究奠定了理論基礎(chǔ)。對(duì)基于局部信息的標(biāo)簽傳播算法(LPA算法)進(jìn)行了深入研究與分析,發(fā)現(xiàn)LPA算法在算法迭代過(guò)程中會(huì)出現(xiàn)“標(biāo)簽?zāi)媪鳌爆F(xiàn)象,同時(shí)初始化標(biāo)簽數(shù)目過(guò)多,標(biāo)簽更新條件單一、不全面,標(biāo)簽更新策略具有隨機(jī)性等問(wèn)題,針對(duì)這些問(wèn)題給出了總體的解決方案。在具體實(shí)現(xiàn)這個(gè)解決方案的基礎(chǔ)上,本文提出了一種帶有適合度的標(biāo)簽傳播算法,記為L(zhǎng)PA-FA算法。LPA-FA算法首先將網(wǎng)絡(luò)中所有的節(jié)點(diǎn)按照其度的大小進(jìn)行排序,組成了一個(gè)有序的節(jié)點(diǎn)序列,在每次算法迭代過(guò)程中,都按照這個(gè)節(jié)點(diǎn)序列依次進(jìn)行節(jié)點(diǎn)標(biāo)簽更新,避免了LPA算法由于采用隨機(jī)節(jié)點(diǎn)序列而造成的“標(biāo)簽?zāi)媪鳌爆F(xiàn)象,提高了算法效率。在節(jié)點(diǎn)標(biāo)簽初始化過(guò)程中,在LPA-FA算法中設(shè)計(jì)了一種簡(jiǎn)單線(xiàn)性初始化方法,減少了網(wǎng)絡(luò)中初始標(biāo)簽的個(gè)數(shù),從而降低算法的運(yùn)行時(shí)間。然后在節(jié)點(diǎn)標(biāo)簽傳播過(guò)程中,當(dāng)節(jié)點(diǎn)的更新標(biāo)簽出現(xiàn)不唯一時(shí),LPA-FA算法引入了鄰接子系統(tǒng)聚集系數(shù)、鄰接邊權(quán)重、節(jié)點(diǎn)屬性相似度三個(gè)參數(shù),進(jìn)而通過(guò)Topsis方法得到三者的綜合評(píng)價(jià)值標(biāo)簽適合度,最終選擇使標(biāo)簽適合度最大的鄰接子系統(tǒng)內(nèi)的標(biāo)簽作為更新標(biāo)簽,不僅解決了LPA算法節(jié)點(diǎn)標(biāo)簽更新條件單一、不全面的缺陷,也克服了LPA算法的隨機(jī)性,從而降低算法的時(shí)間開(kāi)銷(xiāo),提高了聚類(lèi)社團(tuán)的質(zhì)量。最后,將LPA-FA算法與LPA算法分別在Zachary空手道俱樂(lè)部網(wǎng)絡(luò)和科學(xué)家合著網(wǎng)絡(luò)兩個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn),并對(duì)實(shí)驗(yàn)結(jié)果與實(shí)驗(yàn)數(shù)據(jù)進(jìn)行比對(duì)分析。最終,實(shí)驗(yàn)表明本文提出的LPA-FA算法無(wú)論在運(yùn)行時(shí)間,還是聚類(lèi)社團(tuán)的質(zhì)量上都要優(yōu)于LPA算法,從而驗(yàn)證了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.
【學(xué)位授予單位】：西南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：O157.5;TP311.13

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

，

本文編號(hào)：1700323