基于空间活跃度的时变网络建模及其搜索

发布时间：2018-01-02 01:08

本文关键词：基于空间活跃度的时变网络建模及其搜索　出处：《华东师范大学》2016年硕士论文　论文类型：学位论文

【摘要】：很多实际的网络都具有时变特性,时变网络的建模研究可以帮助人们更好地理解真实网络的结构与功能。当网络拓扑演化的时间尺度与传播动力学的时间尺度相当时,基于静态或准静态模型所理解的动力学过程会存在一定的偏差。作为一种基本的动力学过程,复杂网络的搜索具有广泛的应用,例如因特网中网页的搜索等。经典搜索策略通常基于静态网络,在时变网络中的有效性有待验证,因此时变网络上的搜索策略研究可以为解决社交网络中消息的快速传递等实际问题提供参考。针对以上问题,本文基于在线社交网络的特征,提出了活跃度驱动的时变空间网络模型,即空间活跃度网络模型,讨论了时变网络上的搜索过程。本文的主要贡献如下：1.利用Twitter数据集构建具有时变特性的在线社交网络,结合实证分析提出了空间活跃度网络模型。利用Twitter数据集构建了在线社交时变网络,得到了一定时间间隔内的网络拓扑。通过分析网络聚合拓扑特性后发现,网络中用户的活跃度分布独立于时间尺度,并且网络的度值分布和边长分布均具有异质性。结合实证网络的分析结果,考虑到现实网络中存在的时变性与空间性,提出了由节点活跃度和地理偏好连接共同驱动的空间活跃度网络模型。对网络模型的统计特性进行分析,发现与实证结果相符,从而验证了模型构建机制的准确性。2.在空间活跃度网络上进行网络搜索,提出了三种搜索策略的衡量指标,比较了随机游走、最大活跃度搜索、贪婪搜索等策略的搜索效率。为了研究空间活跃度网络上的搜索过程,首先,详细介绍了搜索时间、搜索路径长度、等待时间三种搜索策略的评价指标；其次,结合节点的活跃度特性提出了最大活跃度搜索策略,通过算法实现了随机游走、最大活跃度搜索和贪婪搜索三种策略；最后,在空间活跃度网络上运用这些搜索策略进行网络搜索,计算了各自的效率指标,发现贪婪搜索策略的效率最高,随机游走的效率最低。3.改进了经典的贪婪搜索策略,并结合节点的活跃度特性和地理空间特性提出了最大活跃度最小距离搜索策略。为了保证搜索时信息的传递方向始终不偏离目标节点,改进经典的贪婪搜索策略,每次在计算邻居节点到目标节点距离的同时,计算当前节点到目标节点的距离并进行比较,选择其中离目标节点最近的节点作为下一步信息传递的地址。如果当前节点距离目标节点最近,则不进行信息的传递而是等待一个时间步长。仿真结果表明改进的搜索策略比经典的贪婪搜索策略效率更高。此外,提出了最大活跃度最小距离搜索策略,在搜索过程中,同时考虑邻居节点的活跃度以及邻居节点与目标节点的地理距离。实验结果表明,在空间活跃度网络上进行搜索时,最大活跃度最小距离搜索策略比随机游走搜索策略、最大活跃度搜索策略和改进的贪婪搜索策略的搜索效率都高,从而优化了目标搜索的过程。
[Abstract]:Many real networks have time-varying characteristics, modeling of time-varying networks can help people better understand the structure and function of the real network. When the network topology evolution time scales and dynamic propagation time scale, dynamic process of static or quasi-static model understanding, there will be some deviation based on as. A basic dynamical process, the complex network search is widely used in the Internet, such as web search. The classical search strategy is usually based on static network, the time-varying effectiveness in the network to be verified, so the study on time-varying search strategy on the network can provide a reference for the rapid transmission to solve practical problems in social news in the network. To solve the above problems, the characteristics of online social network based on the proposed activity driven by time-varying spatial network model, namely space activity The network model, discusses the time-varying search process on the network. The main contributions of this paper are as follows: 1. using Twitter data set with online social network time-varying characteristics, combined with the empirical analysis puts forward the space activity network model. By using the Twitter data set constructed online social time-varying network, the network topology for a certain time interval the topological characteristics. Through the analysis of network aggregation and found that the degree distribution of active users in the network is independent of time scale, and the network degree distribution and length distribution have the heterogeneity. Combined with the empirical analysis results of the network, considering the time-varying and space of reality in the network, proposed the active network model a node is active and connected to a common geographic preference driven space. Statistical characteristics of network model analysis, found that the results are consistent with the empirical analysis, which verifies the model The mechanism of the accuracy of.2. in the space of active network to search the Internet, has been proposed to measure the indexes of three kinds of search strategy, the random walk, the maximum activity of the search, the search efficiency of greedy search strategies. In order to study the space active search process of the network first, details of the search time, search path the length of the waiting time, the evaluation index of three kinds of search strategies; secondly, combining the characteristics of active nodes is presented. Active search strategy, through the algorithm of random walk, the three largest active search strategy and greedy search; finally, in the space of active network using the search strategy for network search efficiency index the calculated that greedy search strategy has the highest efficiency and the lowest efficiency of random walk.3. improved the classical greedy search strategy, combined with the active node The characteristics and geographical space presents the maximum activity of the minimum distance search strategy. In order to ensure the transmission direction of search information does not deviate from the target node, improving the classical greedy search strategy, in the calculation of each neighbor node to a target distance at the same time, the computing node to a target distance and compare them from the node nearest to the destination node as the next message transfer address. If the current node from the target node recently, transferring information but not wait for a time step. The simulation results show that the improved search strategy than the classical greedy search strategy is more efficient. In addition, the maximum activity of the minimum distance search strategy in the search process, at the same time, consider the neighbor node active and neighbor node and the target node's geographical distance. Experimental results show that in the space of living When searching on jump network, the maximum activity minimum distance search strategy has higher search efficiency than random walk search strategy, maximum activity search strategy and improved greedy search strategy, thus optimizing the process of target search.

【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5;TP391.3

【相似文献】