本文選題：社會網(wǎng)絡(luò)　切入點：社區(qū)發(fā)現(xiàn)　出處：《吉林大學(xué)》2014年碩士論文　論文類型：學(xué)位論文

【摘要】：隨著互聯(lián)網(wǎng)的發(fā)展和普及，在線社會網(wǎng)絡(luò)已經(jīng)滲透到人們生活中的每個角落，拉近了人們彼此之間的距離，對社會網(wǎng)絡(luò)的研究能夠讓我們了解社會網(wǎng)絡(luò)的結(jié)構(gòu)特征以及演化規(guī)律讓其更好地為人類服務(wù)。在網(wǎng)絡(luò)研究方面有兩個熱點問題：社區(qū)發(fā)現(xiàn)和節(jié)點的重要性評估，這兩個問題的研究對于我們認(rèn)識復(fù)雜社會網(wǎng)絡(luò)的結(jié)構(gòu)以及特征具有非常重要的意義。社會網(wǎng)絡(luò)研究中的社區(qū)發(fā)現(xiàn)工作可以把大的網(wǎng)絡(luò)分成粒度更小的社區(qū)，讓我們發(fā)現(xiàn)內(nèi)部個體聯(lián)系緊密的團(tuán)體，節(jié)點評估可以對網(wǎng)絡(luò)中的節(jié)點以不同的角度進(jìn)行重要性評估，發(fā)現(xiàn)重要節(jié)點。 目前的社區(qū)發(fā)現(xiàn)算法大部分基于圖形分割和層次聚類思想，雖然這些算法大部分情況下能夠有效地對社區(qū)進(jìn)行識別，但都必須指定社區(qū)的數(shù)量或社區(qū)的規(guī)模，顯然這是不合理的。遺傳算法作為一種搜索最優(yōu)解的方法能夠在沒有先驗信息的情況下自動識別社區(qū)的數(shù)量，高效準(zhǔn)確的對社區(qū)進(jìn)行發(fā)現(xiàn)，但是傳統(tǒng)的種群的初始化方法僅僅考慮到鄰接信息，沒有充分考慮網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，因此得到的種群的質(zhì)量比較差，影響算法的收斂速度。節(jié)點的評估算法也存在許多，有的依據(jù)節(jié)點的局部特征，有的依據(jù)整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，作為用在搜索引擎中評估網(wǎng)頁重要程度的PageRank算法，在社會節(jié)點評估中也有很廣泛的應(yīng)用，但傳統(tǒng)的PageRank算法在權(quán)值分配的時候都是均勻分配，這種分配方式在社會網(wǎng)絡(luò)中是不合理的，因為社會網(wǎng)絡(luò)反映的是用戶與用戶之間的關(guān)系，，這種關(guān)系是有親疏之分的，不能同等對待。針對上面的分析，本文主要對社區(qū)發(fā)現(xiàn)的遺傳算法和節(jié)點評估的PageRank算法存在的不足進(jìn)行改進(jìn)，主要的工作如下： 首先，對用于社區(qū)發(fā)現(xiàn)的遺傳算法的種群初始化方法進(jìn)行了改進(jìn)，根據(jù)社會網(wǎng)絡(luò)的特性，給出了信息在網(wǎng)絡(luò)中傳播的特征定義，然后根據(jù)社會網(wǎng)絡(luò)的自身特征和信息在網(wǎng)絡(luò)中傳播的特性提出了能夠充分應(yīng)用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的初始化方法k-path方法,并且給出了基于k-path初始化的遺傳算法的計算過程。 然后，依據(jù)節(jié)點之間的親密程度，提出了節(jié)點間的認(rèn)可度概念，針對用于節(jié)點評估的PageRank算法權(quán)值均勻分配的不合理性問題，提出以節(jié)點間的認(rèn)可度為依據(jù)來分配權(quán)值，最后給了改進(jìn)的節(jié)點評估算法ARank算法。 最后，在數(shù)據(jù)集上驗證了改進(jìn)的遺傳算法和PageRank算法，實驗結(jié)果表明改進(jìn)的遺傳算法在收斂速度要比傳統(tǒng)的算法快，改進(jìn)的PageRank算法對節(jié)點的評估比傳統(tǒng)的評估方式得到結(jié)果合理。
[Abstract]:With the development and popularity of the Internet, the online social network has penetrated into every corner of people's lives, drawing closer the distance between people. The study of social networks allows us to understand the structural characteristics and evolutionary laws of social networks so that they can better serve humanity. There are two hot issues in network research: community discovery and the importance of nodes. The study of these two issues is of great significance for us to understand the structure and characteristics of complex social networks. Community discovery in social network studies can divide large networks into smaller ones. Let us find the group which is closely connected with each other. The node evaluation can evaluate the importance of the nodes in the network from different angles and find the important nodes. Most of the current community discovery algorithms are based on the idea of graph segmentation and hierarchical clustering. Although these algorithms can effectively identify communities in most cases, they must specify the number of communities or the size of communities. Obviously, this is not reasonable. Genetic algorithm, as a method of searching the optimal solution, can automatically identify the number of communities without prior information, and efficiently and accurately find the communities. However, the traditional initialization method only considers the adjacent information and does not fully consider the topology of the network, so the quality of the population is poor, which affects the convergence speed of the algorithm, and there are many evaluation algorithms for nodes. Some are based on the local characteristics of nodes, some are based on the topology of the entire network, as a PageRank algorithm used to evaluate the importance of web pages in search engines, and they are also widely used in social node evaluation. However, the traditional PageRank algorithm is distributed evenly when the weights are allocated, which is unreasonable in the social network, because the social network reflects the relationship between the user and the user. In view of the above analysis, this paper mainly improves the genetic algorithm found in the community and the PageRank algorithm based on node evaluation. The main work is as follows:. Firstly, the population initialization method of genetic algorithm for community discovery is improved. According to the characteristics of social network, the characteristic definition of information transmission in the network is given. Then, according to the characteristics of social network and the characteristics of information spreading in the network, an initialization method, k-path method, which can make full use of the network topology, is proposed, and the calculation process of genetic algorithm based on k-path initialization is given. Then, according to the degree of intimacy between nodes, the concept of recognition degree between nodes is proposed. In view of the unreasonable distribution of weight values of PageRank algorithm used for node evaluation, it is proposed that the weights should be assigned according to the recognition degree between nodes. Finally, an improved node evaluation algorithm, ARank algorithm, is presented. Finally, the improved genetic algorithm and PageRank algorithm are verified on the data set. The experimental results show that the improved genetic algorithm converges faster than the traditional algorithm. The result of the improved PageRank algorithm is more reasonable than that of the traditional method.
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP301.6

【參考文獻(xiàn)】

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

1 王林;張婧婧;;復(fù)雜網(wǎng)絡(luò)的中心化[J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2006年01期

2 蔡曉妍;戴冠中;楊黎斌;;基于譜聚類的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法[J];計算機(jī)科學(xué);2009年09期

3 劉旭;易東云;;基于局部相似性的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J];自動化學(xué)報;2011年12期

4 楊博;劉大有;金弟;馬海賓;;復(fù)雜網(wǎng)絡(luò)聚類方法[J];軟件學(xué)報;2009年01期

5 周濤,柏文潔,汪秉宏,劉之景,嚴(yán)鋼;復(fù)雜網(wǎng)絡(luò)研究概述[J];物理;2005年01期

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

1 韓毅;社會網(wǎng)絡(luò)分析與挖掘的若干關(guān)鍵問題研究[D];國防科學(xué)技術(shù)大學(xué);2011年

本文編號：1574351