發(fā)布時間：2018-01-02 01:08

  本文關鍵詞：基于空間活躍度的時變網絡建模及其搜索　出處：《華東師范大學》2016年碩士論文　論文類型：學位論文

  更多相關文章： 時變網絡 活躍度驅動 空間性 搜索策略 最優(yōu)搜索

【摘要】：很多實際的網絡都具有時變特性,時變網絡的建模研究可以幫助人們更好地理解真實網絡的結構與功能。當網絡拓撲演化的時間尺度與傳播動力學的時間尺度相當時,基于靜態(tài)或準靜態(tài)模型所理解的動力學過程會存在一定的偏差。作為一種基本的動力學過程,復雜網絡的搜索具有廣泛的應用,例如因特網中網頁的搜索等。經典搜索策略通常基于靜態(tài)網絡,在時變網絡中的有效性有待驗證,因此時變網絡上的搜索策略研究可以為解決社交網絡中消息的快速傳遞等實際問題提供參考。針對以上問題,本文基于在線社交網絡的特征,提出了活躍度驅動的時變空間網絡模型,即空間活躍度網絡模型,討論了時變網絡上的搜索過程。本文的主要貢獻如下：1.利用Twitter數據集構建具有時變特性的在線社交網絡,結合實證分析提出了空間活躍度網絡模型。利用Twitter數據集構建了在線社交時變網絡,得到了一定時間間隔內的網絡拓撲。通過分析網絡聚合拓撲特性后發(fā)現,網絡中用戶的活躍度分布獨立于時間尺度,并且網絡的度值分布和邊長分布均具有異質性。結合實證網絡的分析結果,考慮到現實網絡中存在的時變性與空間性,提出了由節(jié)點活躍度和地理偏好連接共同驅動的空間活躍度網絡模型。對網絡模型的統(tǒng)計特性進行分析,發(fā)現與實證結果相符,從而驗證了模型構建機制的準確性。2.在空間活躍度網絡上進行網絡搜索,提出了三種搜索策略的衡量指標,比較了隨機游走、最大活躍度搜索、貪婪搜索等策略的搜索效率。為了研究空間活躍度網絡上的搜索過程,首先,詳細介紹了搜索時間、搜索路徑長度、等待時間三種搜索策略的評價指標；其次,結合節(jié)點的活躍度特性提出了最大活躍度搜索策略,通過算法實現了隨機游走、最大活躍度搜索和貪婪搜索三種策略；最后,在空間活躍度網絡上運用這些搜索策略進行網絡搜索,計算了各自的效率指標,發(fā)現貪婪搜索策略的效率最高,隨機游走的效率最低。3.改進了經典的貪婪搜索策略,并結合節(jié)點的活躍度特性和地理空間特性提出了最大活躍度最小距離搜索策略。為了保證搜索時信息的傳遞方向始終不偏離目標節(jié)點,改進經典的貪婪搜索策略,每次在計算鄰居節(jié)點到目標節(jié)點距離的同時,計算當前節(jié)點到目標節(jié)點的距離并進行比較,選擇其中離目標節(jié)點最近的節(jié)點作為下一步信息傳遞的地址。如果當前節(jié)點距離目標節(jié)點最近,則不進行信息的傳遞而是等待一個時間步長。仿真結果表明改進的搜索策略比經典的貪婪搜索策略效率更高。此外,提出了最大活躍度最小距離搜索策略,在搜索過程中,同時考慮鄰居節(jié)點的活躍度以及鄰居節(jié)點與目標節(jié)點的地理距離。實驗結果表明,在空間活躍度網絡上進行搜索時,最大活躍度最小距離搜索策略比隨機游走搜索策略、最大活躍度搜索策略和改進的貪婪搜索策略的搜索效率都高,從而優(yōu)化了目標搜索的過程。
[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

【相似文獻】

相關期刊論文 前1條

1 ;英科學家研究發(fā)現人腦在45歲時已開始衰老[J];瀘州科技;2014年01期

相關重要報紙文章 前10條

1 記者 李榮;國內鋼市漲跌無力 礦市活躍度未升反降[N];經濟參考報;2014年

2 記者 潘圣韜;A股賬戶活躍度創(chuàng)10個月新高[N];上海證券報;2014年

3 北京商報記者 魏蔚;拼車功能成易信用戶活躍度突破點[N];北京商報;2014年

4 本報記者 趙學毅;震蕩市勤倒騰 股基投資活躍度達4.17倍[N];證券日報;2014年

5 記者 潘圣韜;A股交易活躍度持續(xù)降溫 逾六成賬戶一年內無買賣[N];上海證券報;2012年

6 記者 王曉宇;上市公司重要股東10月減持驟緩 大宗交易活躍度下降[N];上海證券報;2012年

7 記者 潘圣韜;A股賬戶活躍度創(chuàng)一年新高[N];上海證券報;2013年

8 本報記者 齊潔;活躍度下降 微博需要“擠泡沫”[N];中國經營報;2013年

9 商報記者 敖祥菲　實習生 李璐;活躍度下滑三成 新浪微博改版阻擊微信?[N];重慶商報;2013年

10 見習記者 朱傳岐;新品種密集上市 期貨公司擔憂市場活躍度[N];21世紀經濟報道;2013年

相關碩士學位論文 前2條

1 申明明;網絡獵頭行為的分析[D];首都經濟貿易大學;2015年

2 陳超;基于空間活躍度的時變網絡建模及其搜索[D];華東師范大學;2016年

，

本文編號：1367000