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

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

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

【參考文獻(xiàn)】

相關(guān)期刊論文 前8條

1 張基恒;魏進(jìn)武;張?jiān)朴?石祥路;;大數(shù)據(jù)時(shí)代的社交網(wǎng)絡(luò)分析[J];郵電設(shè)計(jì)技術(shù);2014年07期

2 吳信東;李毅;李磊;;在線(xiàn)社交網(wǎng)絡(luò)影響力分析[J];計(jì)算機(jī)學(xué)報(bào);2014年04期

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

4 陳克寒;韓盼盼;吳健;;基于用戶(hù)聚類(lèi)的異構(gòu)社交網(wǎng)絡(luò)推薦算法[J];計(jì)算機(jī)學(xué)報(bào);2013年02期

5 李勇軍;;在線(xiàn)社交網(wǎng)絡(luò)的拓?fù)涮匦苑治鯷J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2012年03期

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

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

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

相關(guān)碩士學(xué)位論文 前2條

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

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

本文編號(hào)：2602623