社交网络中社区结构与关键节点探测技术研究

发布时间：2020-10-12 23:56

　　 随着Web2.0技术的迅速发展,人们的生活方式发生了很大的变化。现实社会中的人与人之间的关系在互联网上又有了新的延伸,人们通过互联网进行着各种各样的交互,从而促进了社交网络的蓬勃发展。近年来,一些典型的社交网络服务平台,如Facebook,维基百科,新浪微博等,其用户数量得到了较快的增长。在社交网络中,用户是网络的核心和主体,用户之间通过链接关系形成了社交网络的基本结构。通过这种结构,社交网络上的用户在共同目标或兴趣的驱动下,进行着各式各样信息的传递与共享。在现实世界中,人们的活动往往表现出明显的群体特性,如家庭群体,朋友群体等等。在网络社会中,用户之间的交互同样也表现出明显的群体特性,也称为网络的社区结构特性,即一些用户之间的交互较为紧密,另一些用户之间的交互则较为稀疏,这些交互紧密的用户便形成了网络上的社区。同时,网络社会所呈现出的群体聚集效应使得现实社会中的众多事件、活动的产生和发展变得更加容易。比如,恐怖组织和极端组织等通过社交网络进行恐怖活动的组织和发动,从而极大的危害了国家的安全和社会的稳定。另外,群体聚集效应的形成也离不开网络中的一些信息传播关键个体,这些个体在网络群体中往往具有较高的影响力水平,从而促进了群体的形成及其聚集的速度。通过对这些关键个体的识别,可以有效地对信息传播的进程予以控制,避免不良事件的发生。因此,开展社交网络中群体发现技术以及关键个体识别技术的研究,对于维护社会的稳定,抑制不良信息的传播和巩固国家的安全稳定,具有重要的理论意义和现实意义。目前,研究者可以从多个不同角度对社交网络的相关特性进行分析和研究,但对其结构特性的分析是其它分析方法的基础。社交网络中的各个个体都是基于个体间的链接关系进行着信息的交互与传递,其结构关系的变化直接影响着信息传递的广度与深度。因此,本文从社交网络结构特性的角度出发,分别就群体发现技术和信息传播关键节点识别技术进行了相关研究。本文的主要贡献具体可以概括为以下四个方面:(1)在静态网络社区发现方面,针对当前基于优化的社区发现技术所存在的准确性不高的问题,提出了一种基于群体智能策略的果蝇优化社区发现方法。相对于传统的基于生物进化或群体智能策略的社区发现方法,基于果蝇优化的社区发现方法具有人为设置参数较少,计算过程简单,易于理解等优点。然而,单纯的果蝇优化社区发现方法在寻找最优社区划分的过程中,容易陷入局部极值,全局搜索能力偏弱。针对这一不足,本文通过采用局部爬山搜索来增强算法的局部搜索能力,采用多种群策略来增强算法的全局搜索能力。通过在四个真实网络和人工网络上的实验研究和分析,表明了该方法在解空间上具有良好的全局搜索能力和局部搜索能力,从而使得最终的社区划分结果具有较高的准确性。(2)在静态网络社区发现方面,针对当前大多数社区发现方法需要获取网络的全局结构信息,从而具有较高时间复杂度,难以适应较大规模社交网络社区发现的问题,本文在定义了一种新的节点影响力评估方法(LH-index)的基础上,根据网络的核心—边缘结构特性,提出了一种基于节点LH-index影响力传播的社区发现方法。该方法通过节点的LH-index值的大小来判断节点的影响力水平并对其进行排序,然后根据该顺序进行节点影响力的标签传播,从而克服了传统标签传播社区发现算法中的两个随机性问题(初始节点选择的随机性和标签更新策略的随机性)所导致的社区划分结果的不稳定性。通过在真实网络和人工合成网络上的实验研究和分析,表明了该方法不但具有较低的时间复杂度,而且能够较好的发现网络的社区结构特征,并且发现的社区划分结果较为稳定。(3)在动态网络社区发现方面,针对当前大多数动态社区发现方法不能同时发现动态网络中社区结构的层次性和重叠性(层叠性)问题,以及忽略了节点之间交互强度的变化对节点社区归属的影响,本文以网络中的边为研究对象,提出了一种基于动态加权网络的层叠社区发现方法。该方法不仅可以揭示出动态变化网络中的社区结构,而且能够检测出网络中的重叠社区。同时,该方法还能够通过调整一个参数获得边社区的层次结构。该方法的基本思想是基于加权边聚类系数以及加权边分区密度,从而可以确定种子边的选择和初始边社区的构建,扩展以及合并。通过在人工网络和真实世界网络上实验研究和分析,表明了该方法可以有效地检测出动态加权网络中的层叠社区结构。(4)在信息传播关键节点识别方面,针对当前大多数方法在评估节点影响力水平方面,所得的节点理论影响力水平(该评估方法所得的计算值)与其实际影响力水平(该节点作为信息传播源,利用信息传播模型计算其最终所感染网络中节点的实际数目)存在较大差异的问题,提出了一种基于局部h-index(LH-index)的信息传播关键节点识别方法。H-index作为一种新近提出的节点影响力度量方法,在评估节点的实际影响力水平方面,优于传统方法,且具有准确性较高,对节点度数值微小变化不敏感,只需要网络局部信息等优点。然而,h-index方法在识别信息传播关键节点时,存在分辨率限制的问题。针对h-index方法的这一不足,本文在考虑了一个节点h-index值的基础上,同时考虑了与该节点相邻的邻居节点的h-index值的大小,从而提出了一种基于LH-index的信息传播关键节点识别方法。该方法的基本思想在于一个节点的邻居节点中具有较高影响力的节点数目越多,该节点影响力水平就越强。通过在四个真实网络和两种网络模型所生成的人工模拟网络上的实验研究和分析,表明了LH-index方法在识别信息传播关键节点上的有效性。同时,针对网络的社区结构对节点的信息传播能力存在一定影响的特性,在前述LH-index方法的基础上,考虑了网络的社区结构特性对信息传播关键节点识别技术的影响,提出了一种基于网络社区结构的信息传播关键节点识别方法。通过在真实网络上的实验研究与分析,表明了该方法能够对具有社区结构网络上的信息传播关键节点进行有效的识别。
【学位单位】：国防科技大学
【学位级别】：博士
【学位年份】：2018
【中图分类】：TP393.09
【部分图文】：

图 1.1 所示。关系结构是个体之间通过交互关两个要素：个体以及个体之间的交互关系。互关系则称为边。社交网络的关系结构是研，这是因为它是网络群体形成和网络信息传具有相似观点，行为等因素联系在一起的个和群体之间的网络信息传播活动。也就是说。例如，发生在 2016 年 4 月的 魏则西事件及国内主流媒体对该事件的持续报道引发了对医疗乱象这一关系民生问题的持续热议[4]。构的演化[2]。例如，在上述例子中，随着该事户参与进来，导致了有关该话题的微博用户社交网络中，网络信息是个体与个体之间，群互联系与相互作用的一种表现形式[2]。网络信是社交网络的客体，对网络中的个体和群体会导致网络的关系结构发生变化。

图 1.2 2016 年美国总统大选期间 Twitter 上两位候选人的支持者所形成的两大社区[8]在社交网络中，网络信息最先是通过网络群体中的个体进行传播的，进而能够影响网络中其它个体和群体的观点及其行为[11, 12]。例如，Bond 等在《Nature》上发文[13]，对 2010 年美国国会选举的政治动员消息在 6100 万的 Facebook 用户之

具有社区结构特性的不同类型网络的拓扑结构

本文编号：2838460