基于K-Shell算法的社交网络影响力主体识别方法研究

发布时间：2018-03-09 07:54

本文选题：K-Shell　切入点：社交网络　出处：《北京交通大学》2017年硕士论文　论文类型：学位论文

【摘要】：随着拥有大量用户群体的社交网络不断兴起,人们信息交流的方式也正悄悄改变。社交网络这种方便、灵活的交互方式,使得信息的产生、发酵更为快捷,信息的扩散时间也大大缩短,信息演化、传递的复杂程度与不确定性也随之大大增加,这对于信息传播的监控、舆论舆情的引导构成了严峻的挑战。因此,如何识别出社交网络中具有较大影响力的用户主体,进而掌握社交网络中信息的传递导向以及舆论的演化趋势,成为了现在阶段亟待解决的问题。本文结合复杂网络理论、传染病动力学等学科的思想与方法,对影响力主体识别算法K-Shell算法进行了深入的研究与探讨,并在此基础上提出了一种新的算法。论文的研究工作得到了国家自然科学基金项目(No.61271308、61172072、61401015)和北京市教育委员会研究生学科建设项目的支持。论文主要工作如下:首先,本文详细分析了 K-Shell算法的分解原理与计算步骤,发现K-Shell算法在计算网络中节点的影响力大小时,虽然考虑了节点的自身属性与位置属性,却忽略了节点的局域属性,这导致K-Shell算法将网络按照不同的k-shell值划分为若干层后,每一层所包含的节点数量较多,使得网络的划分结果变得粗粒化,而且无法横向比较相同k-shell层中节点之间的影响力大小。本文在此基础上提出了基于权重的 K-Shell 改进算法(Weighted K-Shell Algorithm),简称 WKS 算法。WKS算法综合考虑了节点的自身属性、位置属性和局域属性,用边的潜在影响力来度量节点的局域属性,从而将无权网络问题转化为加权网络问题。随后,本文使用Python语言编程实现了 K-Shell算法与WKS算法对网络的分解步骤,并在真实社交网络——新浪微博用户关系网络中进行了模拟仿真,然后将两种算法的仿真结果进行了详细对比分析,最终的结果表明用户节点的Wk-shell值越大,其影响力越大,而且WKS算法对网络节点影响力大小的划分结果比K-Shell算法粒度更加细腻,实用性更高。最后本文借助SIR信息传播模型对WKS算法的有效性与准确性进行验证,在真实社交网络中的仿真结果表明,WKS算法识别社交网络影响力主体的结果准确性高。该方法能够为社交网络中的舆情控制、广告营销等应用领域提供理论支持。
[Abstract]:With the rise of social networks with a large number of users, the way people communicate information is changing quietly. The convenient and flexible way of interacting with social networks makes the production of information faster. The diffusion time of information is shortened greatly, the information evolves, the complexity and uncertainty of transmission increase greatly, which poses a severe challenge to the monitoring of information dissemination and the guidance of public opinion. How to identify the user who has great influence in social network and how to master the direction of information transmission and the evolution trend of public opinion in social network has become a problem to be solved in the present stage. This paper combines the theory of complex network. Based on the ideas and methods of infectious disease dynamics and other subjects, the K-Shell algorithm for the identification of influential agents is deeply studied and discussed. On the basis of this, a new algorithm is proposed. The research work of this paper is supported by the National Natural Science Foundation Project No. 61271308 (61172072) and the postgraduate subject construction project of Beijing Municipal Commission of Education. The main work of this paper is as follows: first of all, In this paper, the decomposition principle and calculation steps of K-Shell algorithm are analyzed in detail. It is found that in calculating the influence of nodes in the network, K-Shell algorithm takes into account the attributes of nodes themselves and location, but neglects the local attributes of nodes. This result in K-Shell algorithm divides the network into several layers according to different k-shell values, each layer contains a large number of nodes, which makes the network partition results become coarse grained. Moreover, the influence between nodes in the same k-shell layer can not be compared horizontally. Based on this, an improved K-shell algorithm based on weight is proposed in this paper, which is called WKS algorithm. WKS algorithm takes into account the attributes of nodes. The location attribute and the local attribute measure the local property of the node with the potential influence of the edge, thus transforming the unauthorized network problem into the weighted network problem. In this paper, the decomposing steps of K-Shell algorithm and WKS algorithm to the network are realized by using Python language, and the simulation is carried out in the real social network-Sina Weibo user relationship network. Then the simulation results of the two algorithms are compared and analyzed in detail. The final results show that the greater the Wk-shell value of the user node, the greater its influence, and the finer the granularity of the WKS algorithm is compared with the K-shell algorithm. Finally, this paper verifies the validity and accuracy of WKS algorithm with the help of SIR information transmission model. The simulation results in real social networks show that the WKS algorithm has high accuracy in identifying the influential agents of social networks, and this method can provide theoretical support for the applications of public opinion control and advertising marketing in social networks.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP393.09;O157.5

【相似文献】