社会网络中关键节点的发现算法研究

发布时间：2017-11-24 08:15

  本文关键词：社会网络中关键节点的发现算法研究

  更多相关文章： 关键节点挖掘 社会网络 DS证据理论 集聚系数

【摘要】：在我们的生活中网络无处不在，典型的人类社会网、生活中的朋友圈、微博圈、各种社交网站如脸谱（Facebook）等这些都属于社会网络的范畴。社会网络并不是一个新的研究领域，早在十九世纪就已经有学者开始针对社会网络进行研究，而今随着社会与科技的发展，现代科学研究的进一步加深，也促进了对复杂网络和社会网络的研究。 研究社会网络就离不开研究网络中的关键节点这一基本内容，关键节点挖掘是以寻找网络中的关键节点为目的的，关键节点在衡量网络的抗毁性、网络效率、鲁棒性等方面具有重大意义。在挖掘出网络的关键节点后，就可以有针对性的制定相应策略，以达到对网络的有效控制，从而使网络能更好的服务于人类。 现在的很多研究者提出了各种关键节点挖掘算法，依据这些算法的基本思想进行划分，可以分为基于网络全局信息和基于网络局部信息的算法。基于网络全局信息的算法特点是挖掘结果的精准度较高，但是算法的复杂度也高，通常都高于O(N3)，这类算法在选取节点重要性评价指标时通常以节点的全局信息为考量，如节点在网络中的位置是不是更接近整个网络的中心，该类算法由于计算复杂度过高，因此不适用于大型网络，尤其是海量数据处理，如处理节点数量过亿，且网络整体集聚系数较高的网络；而基于网络局部信息的算法，其特点是只选取节点的局部信息作为其重要性的衡量指标，例如最简单的以节点的度值作为其重要性评价指标，稍微复杂一些的如考量节点的度以及其邻居节点的度值总和为评价指标，该类算法在计算节点的重要性评价指标时仅选取了节点自身的固有信息或节点及其有限层邻居节点的信息，故其计算复杂度低，但在挖掘结果的精准度上不高。 基于以上问题，本文通过对近年来关键节点挖掘算法代表性文献的研究，分析了目前一些具有代表性的关键节点挖掘算法，在此基础上，基于网络局部半局部信息，提出了一种新的社会网络中关键节点挖掘算法。节点的重要性是一个相对的概念，可以用“高”和“低”来表达其重要的程度，故可以构建一个用于表达节点重要性程度的识别框架 (high,low)，分别定义两个指标f i和g i，其中表示节点v i及其邻居节点的度之和，表示节点的集聚系数，并对该指标进行了归一化处理，基于这两个指标，依据D-S证据理论，可以分别构建各自的基本概率分配函数(BPA)m fi和m pi，其含义是在识别框架 下，这两个指标对于节点重要性“高”和“低”支持的程度，最后通过D-S证据理论合成公式，对和进行合并，，得到一个新的节点重要性的评价指标DSC(D-Sclustering centrality)中心性指标，该指标对节点重要性的“高”和“低”以概率的形式进行了量化，以得到关键节点重要性的排序结果。 由于该算法只考虑了网络的局部信息，因此算法的时间复杂度较低。在仿真实验和实证网络上的测试结果表明，该算法在时间复杂度上明显优于一些代表性的挖掘算法，如基于节点介数中心性指标的挖掘算法、基于节点接近中心性指标的挖掘算法等。与其它基于网络局部或半局部信息的挖掘算法相比，该算法在挖掘的精准度也有显著的提高。 本文对社会网络中的节点重要性排序算法进行了细致的研究，以构建新的节点重要性评价指标为出发点，分析总结了目前的主流挖掘算法，对网络中关键节点挖掘这一网络科学中的基本问题进行了研究。
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【参考文献】

中国期刊全文数据库 前9条

1 孙全,叶秀清,顾伟康;一种新的基于证据理论的合成公式[J];电子学报;2000年08期

2 赫南;李德毅;淦文燕;朱熙;;复杂网络中重要性节点发掘综述[J];计算机科学;2007年12期

3 于俊清;刘青;何云峰;;基于感兴趣区域的H.264视频加密算法[J];计算机学报;2010年05期

4 任晓龙;吕琳媛;;网络重要节点排序方法综述[J];科学通报;2014年13期

5 王冰,修志龙,唐焕文;基于复杂网络理论的代谢网络结构研究进展[J];中国生物工程杂志;2005年06期

6 陈勇,胡爱群,胡啸;通信网中节点重要性的评价方法[J];通信学报;2004年08期

7 陈静;孙林夫;;复杂网络中节点重要度评估[J];西南交通大学学报;2009年03期

8 章忠志,荣莉莉,周涛;一类无标度合作网络的演化模型[J];系统工程理论与实践;2005年11期

9 任卓明;邵凤;刘建国;郭强;汪秉宏;;基于度与集聚系数的网络节点重要性度量方法研究[J];物理学报;2013年12期

本文编号：1221584