【作者】 王勇；

【导师】 杨静；

【作者基本信息】 哈尔滨工程大学 ， 计算机科学与技术， 2018， 博士

【摘要】 21世纪是人类高度依赖社会网络、深度融入信息社会的世纪。社会网络正在不断地改变着人类的行为模式和社会形态,影响着社会经济的发展以及人们的生活方式。结构特征是社会网络的本质特征,社会网络结构分析是社会网络理论研究和实践应用的重要基础,已成为当前学术界的研究热点和前沿课题。对社会网络的研究能够使人们更加深入地理解社会网络的结构特性,有助于人们认知社会和解释社会现象,适应社会网络给人们工作、学习等带来的变化。同时,进一步揭示社会网络内在的结构功能,理解社会网络个体行为及情感,把握社会网络发展的方向,能够有效地解决社会问题、维护社会稳定和协调社会行为,也能为社会学、管理学等学科的相关研究提供技术支持,因此对社会网络结构及影响力分析的研究具有重要的理论研究价值和广阔的应用前景。本文从宏观、中观和微观三个层面对社会网络结构分析开展研究。一方面,从宏观上研究分析社会网络拓扑结构特性并构建社会网络演化模型,为中观社区识别和微观节点影响力分析提供理论和数据支持;另一方面,从中观和微观角度研究如何设计更加可行、高效和可靠的方法,解决社会网络社区识别和影响力最大化研究中存在的技术难点问题,为开展社会网络分析及其应用提供重要的理论支撑和技术支持。归纳而言,本文的研究内容主要包括以下四个方面:首先,针对现有大多数社会网络演化模型往往从网络全局角度考虑,忽略节点的微观特征和信息传播特性,不能很好地描述真实网络实际演化过程的问题,提出一种基于信息传播特性的社会网络演化模型构建方法。该方法基于节点信息传播特性,综合考虑节点之间的领域相似性、信息传播吸引以及局部传播特性,同时融入节点信息传播活跃程度概念,对节点间信息传播过程进行全面、细腻地模拟,以实现社会网络的演化建模。实验结果表明,该方法能够更加精准地刻画、描述真实网络的拓扑特征和演化特性。其次,针对传统的非重叠社区识别算法存在需要预设社区个数、时间复杂度过高以及社区划分质量较低等问题,提出一种基于标签环形扩散的非重叠社区识别算法。该算法在传统标签传播算法的基础上,采取剪枝策略进行预处理,引入节点影响力对节点进行度量、排序和分组,有效地解决了标签传播算法结果随机性强、识别质量差的问题。实验结果表明,该算法能够在保留标签传播算法近线性的时间复杂度的基础上,降低标签的迭代次数,增强标签传播的稳定性,有效提高社区划分质量。再次,针对重叠社区识别领域现有研究成果大多需要人工设置社区重叠度,不适用于现实世界的真实网络,同时在算法效率、社区划分质量等方面都有待进一步提高的问题,提出一种基于节点隶属度的标签环形传播重叠社区识别算法。该算法首先利用节点间的相似性以及邻居节点结构定义了节点的社区隶属度;同时,引入节点的拓扑势函数度量节点影响力并通过与节点隶属度的对比进行标签截断;然后,采用标签环状扩散策略改进传统标签重叠社区识别算法完成重叠社区的识别。实验结果表明,该算法具有较高的有效性和稳定性,在不需要人工设置参数的情况下也能够有效提高社区识别结果的稳定性和质量。最后,针对已有的研究工作大多忽略网络的局部结构特性且节点影响范围重叠,导致传播效果不理想,无法适应大规模网络等问题,提出一种基于社区识别的社会网络影响力最大化算法。该算法引入拓扑势度量节点的影响力,采用局部化社区识别思想进行候选节点集合的动态选取,利用社区识别与局部边缘去重方法,有效地求解社会网络中的影响力最大化问题。真实数据集上的实验结果表明,相比当前主要的影响力最大化算法,该算法具有更高的可行性和有效性,在相同条件下能够获得更好的传播效果。更多还原

【Abstract】 In the 21 st century,humans become highly dependent on social networks and deeply integrated into the information society.Social networks are constantly changing human behavior patterns and social patterns,and influencing the socioeconomic development and people’s lifestyle.Structural characteristics are the essential characteristics of social networks,and the analysis of social networks structure is an important basis of the theoretical research and practical application of social networks,which has become a research hotspot and frontier topics in the current academic community.Research on social networks can make people further understand the structural characteristics of social networks,help people to recognize and explain social phenomena,adapt to the changes brought about by social networks to people’s work,study,etc.Meanwhile,it can help further reveal the internal structural functions of social networks,understand individual behaviors and emotions of social networks,grasp the direction of social network development,effectively solve social problems,maintain social stability and coordinate social behavior,and provide technical support for sociology,management science and other disciplines.Therefore,the research on social networks structure and influence analysis has important theoretical research value and broad application prospects.The social networks structure analysis is studied from the macro,meso,and micro perspectives in this dissertation.On the one hand,it studies macroscopically the characteristics of social network topology and constructs a social network evolution model,which can provide theoretical and data support for the meso community identification and micro-nodal influence analysis.On the other hand,it studies how to design more feasible,efficient,and reliable methods to solve technical difficulties in social network community identification and influence maximization from the perspective of meso and micro perspectives,which can provide important theoretical support and technical support for conducting social network analysis and its application.In summary,the research content of this dissertation mainly includes the following four aspects:Firstly,as most of the existing social network evolution models often consider from the perspective of the overall network,but ignore the microscopic characteristics and information dissemination characteristics of the nodes and fail to describe the actual evolutionary process of the real network,a new method of constructing social network evolutionary model based on information communication characteristics is proposed in this dissertation.This method isbased on the information propagation characteristics of nodes,which comprehensively considers the similarity of domains between the nodes,the information dissemination attraction and the local dissemination characteristics.It also integrates the concept of the activity level of node information dissemination,which completes social networks model building by comprehensively and exquisitely simulating the information dissemination process between nodes.The results of experiments show that this method can portray and describe the topological characteristics and evolutionary characteristics of real networks more accurately.Secondly,considering that traditional non-overlapping community identification algorithms suffer from the problems such as the need for a preset number of communities,high time complexity,and low quality of community classification,this dissertation proposes a non-overlapping community identification algorithm based on circular spread label propagation.Based on the traditional label propagation algorithm,it adopts the pruning strategy to preprocess,introduces the node influence to measure,sort and group the nodes,and effectively solves the problems of strong randomness and poor recognition quality of the label propagation algorithm.The results of experiments demonstrate that the iterations of tags are reduced,and the stability of the propagation is enhanced and community classification is effectively improved by the new algorithm,while the near-linear linearity of tag propagation is retained.Thirdly,most of the existing research results in the field of overlapping community identification require manually setting the community overlap,which does not apply to the real networks,and the problems such as algorithm efficiency and community division quality need to be further improved,so this dissertation proposes a label propagation overlapping community identification algorithm based on membership degree.The algorithm first uses the similarity between nodes and the neighboring node structure to define the community membership grade of the node.At the same time,the topological potential of the node is introduced to measure the node influence and the tag is truncated by comparing with the node membership degree;Then,the circular spread strategy is used to improve the traditional label overlapping community identification algorithms and complete the overlapping community identification.The results of experiments show that this algorithm has high efficiency and stability,and can effectively improve the stability and quality of community identification results without setting parameters manually.Finally,most of the existing research work ignores the local structural characteristics of the network and the node influence range overlapping,resulting in unsatisfactory propagation effects and the inability to adapt to large-scale network problems.To solve the problem,analgorithm for maximizing social network influence based on community identification is proposed.The method of measuring node influence with topological potential is introduced in the algorithm.The candidate nodes are selected dynamically by localized community partitioning,and then,the problem of maximizing the influence in the social network is settled by community identification and the local edge deduplication.The experiments on real data sets demonstrate that compared with the major algorithms,the new one is more feasible and effective,and the propagation effects are better under the same conditions.更多还原