【摘要】：使用多種多樣的在線社交網(wǎng)絡進行社交活動已經(jīng)成為當前社交的特色。每個在線社交網(wǎng)絡反映了我們真實社交網(wǎng)絡的一個方面。將多個在線社交網(wǎng)絡連接起來的社交網(wǎng)絡匹配算法對于我們進行全面的社交網(wǎng)絡分析具有重要作用。但是目前的在線社交網(wǎng)絡匹配算法存在時間復雜度高、圖間信息量較少的情況下匹配準確率不高、沒有與其他領域知識很好的結(jié)合以提高實踐應用能力等問題。論文對社交網(wǎng)絡匹配算法的時間復雜度、匹配準確率和在實踐中的應用進行了研究,提出了基于子圖分割的社交網(wǎng)絡匹配算法、基于有向圖的社交網(wǎng)絡匹配算法和基于多重社交網(wǎng)絡匹配的好友推薦算法,并在實驗上取得了很好的效果。主要研究成果如下:1.對于社交網(wǎng)絡匹配算法的時間復雜度較高的問題,考慮到算法時間復雜度較高主要是因為算法中存在大量的冗余計算,我們可以通過分割成多個子圖的方式把問題化整為零,并在分割的過程中引入社群分割算法,使得子圖間的聯(lián)系相對稀疏,子圖內(nèi)的聯(lián)系相對緊密�；谧訄D分割的社交網(wǎng)絡匹配算法通過分割子圖后進行索引搜索的方式可以在社交網(wǎng)絡圖匹配的過程中節(jié)省匹配時間,節(jié)省了 30%時間。2.基于有向圖的社交網(wǎng)絡匹配算法有效的解決了有向圖的匹配準確率不高問題,提出了基于方向的節(jié)點相似度計算方式,通過在計算網(wǎng)絡層中兩個點的節(jié)點相似度時引入方向性,有效的提高了匹配算法的準確性。在一些對方向性變化敏感的社交網(wǎng)絡圖間做社交網(wǎng)絡圖匹配時,算法準確率提升可達到10%。3.基于多重社交網(wǎng)絡匹配的好友推薦算法很好的將傳統(tǒng)好友推薦算法和社交網(wǎng)絡匹配算法結(jié)合起來,提升了推薦的準確率。
【圖文】：

形式進行描述。通過用節(jié)點表示人，邊表示人際交往關系，可將社交網(wǎng)絡形式逡逑化描述為Ｇ＝｛Ｖ，Ｅ｝，其中Ｇ代表社交網(wǎng)絡，，Ｖ代表點的集合，Ｅ代表邊的集合（可逡逑以是有向邊集或無向邊集）［９］。圖２－１選取了新浪微博網(wǎng)絡的一部分節(jié)點和邊逡逑對典型的在線社交網(wǎng)絡結(jié)構(gòu)進行示意。逡逑圖２－１是從新浪微博人氣排名（被關注數(shù)排名）前十的用戶中選取八位用逡逑７逡逑

的最小值即為有效直徑。圖二（ｂ）中網(wǎng)絡的直徑為３，對應的最短路徑為Ｇ－Ｅ－Ｆ－Ｈ逡逑或邋Ｇ－Ｅ－Ｆ－Ｄ。逡逑例２－１計算圖２－１邋（ｂ）所示網(wǎng)絡的平均路徑長度與網(wǎng)絡直徑［１２］。逡逑解：首先計算出網(wǎng)絡所有節(jié)點對間的距離：ｄｃｊＥ＝ｌ；邋ｄＧＢ＝２；邋ｄ0Ａ＝２；邋ｄＧｃ＝２；逡逑ｄＧＦ＝２；邋ｄＧＨ＝３；邋ｄＧＤ＝３；邋ｄＥＢ＝ｌ邋；邋ｄＥＡ＝ｌ邋；邋ｄＥＣ－１邋；邋ｄＥＦ＾ｌ邋；邋ｄＥＨ＝２；邋ｄＥＤ＝２；邋ｄＢＡ＝ｌ邋；逡逑ｄＢＥ＝ｌ邋；邋ｄＢＣ＝２；邋ｄＢＨ＝＝２；邋ｄＢＤ＝２；邋ｄＡＦ＝ｌ；邋ｄＡｃ＝２；邋ｄＡ0＝２；邋ｄＡＨ＝２；邋ｄｃＦ＝ｌ；邋ｄｃＨ＝２；逡逑ｄｃＤ＝２；邋ｄＦＨ＝ｌ；邋ｄＥＤ＝ｌ；邋ｄＤＨ＝ｌ。將以上數(shù)據(jù)代入式（２－２）可得逡逑Ｌ邋＝邋—－—Ｙｄａ＝１．６４邐（２－４）逡逑８（８－１）逡逑根據(jù)式（２－３）可求得直徑逡逑Ｄ邋＝邋ｍａｘ邋ｄｕ邋＝邋ＤＧＨ邋＝邋Ｄｇｄ邋＝邋３邐（２－５）逡逑２．２在線社交網(wǎng)絡一致性匹配算法逡逑在線社交網(wǎng)絡一致性匹配問題是我們在進行跨社交網(wǎng)絡間賬戶識別時最常逡逑遇到的問題，以往的很多一致性匹配算法大多數(shù)基于社交網(wǎng)絡圖中個人的行為逡逑特征來進行在線社交網(wǎng)絡的一致性匹配。但是這種方式需要進行大量的個人行逡逑為分析［１３］。除此之外，在不同類型的社交網(wǎng)絡中人們的行為特征可能出現(xiàn)較大逡逑差異。目前的社交網(wǎng)絡一致性匹配算法從社交網(wǎng)絡圖的角度出發(fā)，利用社交網(wǎng)逡逑絡圖的特點進行圖與圖之間的匹配，而非單個賬戶的識別。這個問題類似于圖逡逑的同構(gòu)問題。但是圖的同構(gòu)問題是一個ＮＰ問題
【學位授予單位】：北京郵電大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP393.09

【參考文獻】

相關期刊論文 前8條

1 張基恒;魏進武;張云勇;石祥路;;大數(shù)據(jù)時代的社交網(wǎng)絡分析[J];郵電設計技術;2014年07期

2 吳信東;李毅;李磊;;在線社交網(wǎng)絡影響力分析[J];計算機學報;2014年04期

3 王昊翔;曾珊;劉揮揚;;虛擬社交網(wǎng)絡中節(jié)點重要度分析[J];上海交通大學學報;2013年07期

4 陳克寒;韓盼盼;吳健;;基于用戶聚類的異構(gòu)社交網(wǎng)絡推薦算法[J];計算機學報;2013年02期

5 李勇軍;;在線社交網(wǎng)絡的拓撲特性分析[J];復雜系統(tǒng)與復雜性科學;2012年03期

6 竇炳琳;李澍淞;張世永;;基于結(jié)構(gòu)的社會網(wǎng)絡分析[J];計算機學報;2012年04期

7 袁園;孫霄凌;朱慶華;;微博用戶關注興趣的社會網(wǎng)絡分析[J];現(xiàn)代圖書情報技術;2012年02期

8 覃學健;李翠白;;虛擬學習社區(qū)的社會網(wǎng)絡分析研究[J];現(xiàn)代教育技術;2009年02期

相關碩士學位論文 前2條

1 郭琛;社交網(wǎng)絡分析與信息傳播研究[D];復旦大學;2012年

2 劉耀庭;社交網(wǎng)絡結(jié)構(gòu)研究[D];浙江大學;2008年

本文編號：2602623