在线社会网络的演化模型及关键技术研究

发布时间：2018-02-22 05:27

本文关键词： 在线社会网络网络演化模型关键用户识别链路预测　出处：《北京交通大学》2016年博士论文　论文类型：学位论文

【摘要】：随着各种在线社会网络的飞速发展,社会网络研究的节点规模上升到了数百万甚至是千万级。在线社会网络具有规模巨大,链路众多,关系复杂等特点。网络演化和结构特征研究是在线社会网络研究的两个重要方面,并可进一步扩展成为演化模型、关键用户识别和链路预测这三个问题。其中,网络演化研究的实质是网络的生成机制,具体包括网络中各组成部分之间的关系及其整体特征,是从局部对网络的宏观整体研究。中心性和用户行为是刻画网络演化的两个重要指标,其中,中心性既对社会网络的演化有着重要的影响,也是衡量用户重要性的关键指标之一,用户行为则是另一个评估用户重要性的关键指标,也是链路预测的关键依赖条件之一。在此基础上,网络演化、关键用户识别和链路预测这三个问题形成了一个有机的整体。本文主要针对网络演化和结构特征两个方面所涉及的上述三个问题进行深入研究,提出一系列模型与算法。本文的主要创新点工作和成果包括：网络演化方面(1)针对现有网络演化模型难以准确刻画在线社会网络加速增长过程中老用户对新用户产生关注关系这一问题,依次提出了概率复制增长模型、加速复制增长模型和带更新过程的加速概率复制增长模型,通过解析计算、模拟仿真和实际网络测量,结果均显示了上述模型与真实在线社会网络拓扑特征的一致性,能够很好的刻画真实网络的演化进程。(2)针对当前尚缺乏网络拓扑特性数学刻画方法这一问题,给出了针对前面所提出的三个网络演化模型的度分布、平均最短路径和簇聚集系数的解析方法,通过理论分析得出上述三个拓扑特征增长规律的同时,也对基于加速增长机制的演化模型网络特征的理论分析提供了借鉴和参考。网络结构特征方面(3)针对目前在线社会网络关键用户识别算法识别率低、排序片面等问题,考虑用户间动态“提及”关系及其频率的相对重要性,通过迭代方式量化了在线社会网络用户的关键性,在此基础上,提出了一种基于用户关系的关键用户识别算法,并给出了算法收敛性和时间复杂度分析。和主流算法对比,该算法可以避免僵尸粉欺骗、名人的普通朋友重要性偏高、排序片面等问题,能够更好地识别出在线社会网络中的关键用户。(4)针对现有在线社会网络链路预测准确度和精确度较低的问题,提出了一个基于用户行为特征的稀疏学习算法。该算法以用户关注关系作为分类特征基础,考虑用户间的“提及”关系,引入用户行为特征矩阵作为约束条件,利用核投影机(KPM)算法实现从高维Hilbert空间到最佳D维空间的选取,在此基础上实现用户间的有效链路预测。我们给出了该算法的表示定理并证明了算法的收敛性。实验结果表明,该算法链路预测准确度、精确度优于通用的SVM算法和TKPM算法。
[Abstract]:With the rapid development of various online social networks, the scale of social network research nodes has increased to millions or even tens of millions. Network evolution and structural characteristics are two important aspects of online social network research, and can be further expanded into three problems: evolution model, key user identification and link prediction. The essence of the network evolution research is the generation mechanism of the network, including the relationship between the components of the network and its overall characteristics. Centrality and user behavior are two important indicators to characterize the evolution of networks, in which centrality has an important impact on the evolution of social networks. It is also one of the key indicators to measure the importance of users, and user behavior is another key indicator to evaluate the importance of users, and it is also one of the key dependency conditions for link prediction. On this basis, the network evolves. The three problems of critical user identification and link prediction form an organic whole. A series of models and algorithms are proposed. The main innovations and achievements of this paper include: network evolution. 1) it is difficult to accurately depict old users to new users in the process of accelerating the growth of online social networks. The issue of relationships of concern, The probabilistic replicative growth model, accelerated replication-growth model and accelerated probabilistic replication-growth model with updating process are put forward in turn. The results show that the above models are consistent with the topological features of real online social networks, and can well describe the evolution process of real networks. An analytical method for the degree distribution, average shortest path and cluster aggregation coefficient of the three network evolution models proposed in this paper is given. By theoretical analysis, the growth laws of the above three topological characteristics are obtained. It also provides a reference for the theoretical analysis of the network characteristics of the evolution model based on the accelerated growth mechanism. In terms of network structure features, the paper aims at the problems of low recognition rate and one-sided ranking of key users in online social networks. Considering the relative importance of the dynamic "mention" relationship among users and its frequency, this paper quantifies the key of online social network users by iterative method. On this basis, a key user identification algorithm based on user relationship is proposed. The convergence and time complexity analysis of the algorithm are given. Compared with the mainstream algorithms, the algorithm can avoid zombie spoofing, the importance of ordinary friends of celebrities is on the high side, and the ranking is one-sided, and so on. Be able to better identify key users in online social networks. In this paper, a sparse learning algorithm based on user behavior feature is proposed, which takes user concern relation as the basis of classification feature, considers the "mention" relation among users, and introduces user behavior feature matrix as constraint condition. The kernel projector KPM) algorithm is used to select the best D-dimensional space from high-dimensional Hilbert space, and on this basis, the effective link prediction between users is realized. We give the representation theorem of the algorithm and prove the convergence of the algorithm. The link prediction accuracy and accuracy of this algorithm is better than that of SVM algorithm and TKPM algorithm.
【学位授予单位】：北京交通大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP393.09

【相似文献】