本文關鍵詞： 在線社會網(wǎng)絡 網(wǎng)絡演化模型 關鍵用戶識別 鏈路預測　出處：《北京交通大學》2016年博士論文　論文類型：學位論文

【摘要】：隨著各種在線社會網(wǎng)絡的飛速發(fā)展,社會網(wǎng)絡研究的節(jié)點規(guī)模上升到了數(shù)百萬甚至是千萬級。在線社會網(wǎng)絡具有規(guī)模巨大,鏈路眾多,關系復雜等特點。網(wǎng)絡演化和結構特征研究是在線社會網(wǎng)絡研究的兩個重要方面,并可進一步擴展成為演化模型、關鍵用戶識別和鏈路預測這三個問題。其中,網(wǎng)絡演化研究的實質是網(wǎng)絡的生成機制,具體包括網(wǎng)絡中各組成部分之間的關系及其整體特征,是從局部對網(wǎng)絡的宏觀整體研究。中心性和用戶行為是刻畫網(wǎng)絡演化的兩個重要指標,其中,中心性既對社會網(wǎng)絡的演化有著重要的影響,也是衡量用戶重要性的關鍵指標之一,用戶行為則是另一個評估用戶重要性的關鍵指標,也是鏈路預測的關鍵依賴條件之一。在此基礎上,網(wǎng)絡演化、關鍵用戶識別和鏈路預測這三個問題形成了一個有機的整體。本文主要針對網(wǎng)絡演化和結構特征兩個方面所涉及的上述三個問題進行深入研究,提出一系列模型與算法。本文的主要創(chuàng)新點工作和成果包括：網(wǎng)絡演化方面(1)針對現(xiàn)有網(wǎng)絡演化模型難以準確刻畫在線社會網(wǎng)絡加速增長過程中老用戶對新用戶產(chǎn)生關注關系這一問題,依次提出了概率復制增長模型、加速復制增長模型和帶更新過程的加速概率復制增長模型,通過解析計算、模擬仿真和實際網(wǎng)絡測量,結果均顯示了上述模型與真實在線社會網(wǎng)絡拓撲特征的一致性,能夠很好的刻畫真實網(wǎng)絡的演化進程。(2)針對當前尚缺乏網(wǎng)絡拓撲特性數(shù)學刻畫方法這一問題,給出了針對前面所提出的三個網(wǎng)絡演化模型的度分布、平均最短路徑和簇聚集系數(shù)的解析方法,通過理論分析得出上述三個拓撲特征增長規(guī)律的同時,也對基于加速增長機制的演化模型網(wǎng)絡特征的理論分析提供了借鑒和參考。網(wǎng)絡結構特征方面(3)針對目前在線社會網(wǎng)絡關鍵用戶識別算法識別率低、排序片面等問題,考慮用戶間動態(tài)“提及”關系及其頻率的相對重要性,通過迭代方式量化了在線社會網(wǎng)絡用戶的關鍵性,在此基礎上,提出了一種基于用戶關系的關鍵用戶識別算法,并給出了算法收斂性和時間復雜度分析。和主流算法對比,該算法可以避免僵尸粉欺騙、名人的普通朋友重要性偏高、排序片面等問題,能夠更好地識別出在線社會網(wǎng)絡中的關鍵用戶。(4)針對現(xiàn)有在線社會網(wǎng)絡鏈路預測準確度和精確度較低的問題,提出了一個基于用戶行為特征的稀疏學習算法。該算法以用戶關注關系作為分類特征基礎,考慮用戶間的“提及”關系,引入用戶行為特征矩陣作為約束條件,利用核投影機(KPM)算法實現(xiàn)從高維Hilbert空間到最佳D維空間的選取,在此基礎上實現(xiàn)用戶間的有效鏈路預測。我們給出了該算法的表示定理并證明了算法的收斂性。實驗結果表明,該算法鏈路預測準確度、精確度優(yōu)于通用的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

【相似文獻】

相關期刊論文 前10條

1 于振江;傅凝;羅批;張斌;;戰(zhàn)爭危機下經(jīng)濟演化模型的經(jīng)濟信心建模研究[J];系統(tǒng)仿真學報;2006年12期

2 何玉梅;齊佳音;劉慧麗;;微博局部世界演化模型探究[J];現(xiàn)代圖書情報技術;2014年05期

3 王行靳,吳孫華,周世祥;技術主體系統(tǒng)的演化過程及演化模型[J];科技進步與對策;2005年01期

4 于振江,張斌,傅凝,羅批;戰(zhàn)爭危機下一種經(jīng)濟演化模型研究[J];系統(tǒng)仿真學報;2005年11期

5 吳海濱,李垣,謝恩;基于組織互動和個人關系的聯(lián)盟演化模型[J];科研管理;2004年01期

6 高俊山;吳遠巍;王磊;;企業(yè)慣例網(wǎng)絡演化模型[J];情報雜志;2011年11期

7 陶少華;楊春;李慧娜;張勇;;基于節(jié)點吸引力的復雜網(wǎng)絡演化模型研究[J];計算機工程;2009年01期

8 裴偉東;夏瑋;王全來;趙子平;馬希榮;;多三角形結構動態(tài)復雜網(wǎng)絡演化模型及其穩(wěn)定性分析[J];計算機工程與應用;2011年23期

9 王林;戴冠中;覃森;;Internet的一種新的動態(tài)演化模型[J];系統(tǒng)工程理論與實踐;2006年10期

10 王楊;張林靜;黃亞坤;趙傳信;陳付龍;;基于博弈論的物聯(lián)網(wǎng)語義社區(qū)演化模型[J];計算機工程與科學;2012年09期

相關會議論文 前10條

1 章忠志;周水庚;;集團演化生成的無尺度網(wǎng)絡[A];2006全國復雜網(wǎng)絡學術會議論文集[C];2006年

2 ;Nonlinear Dynamical Behavior in BS Evolution Model Based on Small-World Network Added with Mechanism of Preferential Connection[A];全國復雜系統(tǒng)研究論壇論文集（二）[C];2005年

3 秦瓊;劉海英;許鵬遠;王志平;張放;;無標度演化模型的研究[A];2006全國復雜網(wǎng)絡學術會議論文集[C];2006年

4 孫祥安;周健;;基于距離的復雜網(wǎng)絡演化模型[A];2011中國儀器儀表與測控技術大會論文集[C];2011年

5 雷國雄;陳恩;;制度變遷:一個擬生物演化模型[A];2008年度（第六屆）中國法經(jīng)濟學論壇論文集（下）[C];2008年

6 郭曉;楊乃定;;聯(lián)盟環(huán)境下基于復雜網(wǎng)絡的項目風險演化模型構建及仿真研究[A];中國系統(tǒng)工程學會第十八屆學術年會論文集——A12系統(tǒng)科學與系統(tǒng)工程理論在各個領域中的應用研究[C];2014年

7 溫睿;程波;馬亞平;;基于邊權演化模型的心理傳播研究[A];第五屆全國復雜網(wǎng)絡學術會議論文（摘要）匯集[C];2009年

8 于同奎;;“柔性”執(zhí)法與普遍性違法——基于演化模型的經(jīng)濟學分析[A];中國系統(tǒng)工程學會第十八屆學術年會論文集——A07社會發(fā)展過程中的復雜系統(tǒng)問題[C];2014年

9 李夢輝;狄增如;;一個基于集團增長的無標度網(wǎng)絡演化模型[A];管理科學與系統(tǒng)科學研究新進展——第8屆全國青年管理科學與系統(tǒng)科學學術會議論文集[C];2005年

10 趙廷寧;祁有祥;史辰曦;陳志泊;;基于GIS和CA的荒漠化動態(tài)演化模型研究——以鹽池縣為例[A];中國首屆沙產(chǎn)業(yè)高峰論壇文集[C];2008年

相關博士學位論文 前9條

1 卜湛;在線網(wǎng)絡社會行為特征研究及其應用[D];南京航空航天大學;2014年

2 吳哲;在線社會網(wǎng)絡的演化模型及關鍵技術研究[D];北京交通大學;2016年

3 章忠志;復雜網(wǎng)絡的演化模型研究[D];大連理工大學;2006年

4 趙暉;一般輸運網(wǎng)絡演化模型及動力學特征的相關研究[D];北京交通大學;2007年

5 孫更新;基于多子網(wǎng)復合復雜網(wǎng)絡模型的互聯(lián)網(wǎng)拓撲演化模型及相關性質研究[D];青島大學;2013年

6 晉建志;復雜網(wǎng)絡基于節(jié)點重要性的社團探測及社團演化模型研究[D];華中師范大學;2014年

7 王學文;復雜網(wǎng)絡的演化模型研究[D];上海大學;2013年

8 齊翔;互惠利他行為的演化模型與仿真[D];華中科技大學;2008年

9 張彪;創(chuàng)新技術采納決策與擴散問題研究及應用[D];華中科技大學;2008年

相關碩士學位論文 前10條

1 鮑媛媛;復雜網(wǎng)絡中重要節(jié)點挖掘及演化模型分析[D];安徽大學;2016年

2 李夢婷;一類基于經(jīng)典博弈的隨機演化模型[D];南京航空航天大學;2015年

3 侯麗芳;無標度網(wǎng)絡的演化模型研究及應用[D];燕山大學;2016年

4 戈文豹;大型活動影響下的交通流演化模型研究[D];內蒙古大學;2016年

5 馬棟才;常規(guī)公交競合網(wǎng)絡復雜性及演化模型研究[D];哈爾濱工業(yè)大學;2016年

6 楊經(jīng)明;基于復雜網(wǎng)絡的無線傳感器網(wǎng)絡演化模型研究[D];南京郵電大學;2016年

7 徐俊;復雜網(wǎng)絡重要節(jié)點排序及其演化模型研究[D];電子科技大學;2015年

8 秦瓊;復雜網(wǎng)絡演化模型的研究[D];大連海事大學;2007年

9 潘家鑫;加權復雜網(wǎng)絡的演化模型及其同步的研究[D];合肥工業(yè)大學;2010年

10 喬瑩;微博用戶粉絲演化模型的構建與實證[D];河北大學;2012年

，

本文編號：1523738