1、<p>　　畢業(yè)論文：在線社交網(wǎng)絡(luò)</p><p><b>　　一、引言</b></p><p>　　在實(shí)際社會(huì)生活中，每個(gè)人都有各自的人際關(guān)系。這樣人與人之間存在的人際關(guān)系就共同構(gòu)成了現(xiàn)實(shí)生活中的社交網(wǎng)絡(luò)(Social Network)，其中人是網(wǎng)絡(luò)中的節(jié)點(diǎn)，人際關(guān)系是網(wǎng)絡(luò)中的邊。由于人際關(guān)系與人們生活息息相關(guān)，且對(duì)人們的工作和學(xué)習(xí)有著顯著影響，因此研究和

2、分析社交網(wǎng)絡(luò)有著重要的意義。</p><p><b>　　二、社交網(wǎng)絡(luò)概念</b></p><p>　　1967 年，哈佛大學(xué)的心理學(xué)教授Stanley Milgram 創(chuàng)立的六度分割理論被認(rèn)為是社交網(wǎng)絡(luò)的理論基礎(chǔ)。按照六度分隔理論，網(wǎng)絡(luò)上每個(gè)用戶的社交圈都不斷放大，最后就可構(gòu)成一個(gè)大型的社交網(wǎng)絡(luò)。然而，什么是社交網(wǎng)絡(luò)？目前還沒(méi)有統(tǒng)一的定義。為便于理解社交網(wǎng)絡(luò)的概念，

3、本文給出一種供參考和商榷的描述性定義?！　∩缃痪W(wǎng)絡(luò)是一個(gè)系統(tǒng)：其中1)系統(tǒng)中的主體是用戶(User)，用戶可以公開(kāi)或半公開(kāi)個(gè)人信息；2)用戶能創(chuàng)建和維護(hù)與其他用戶之間的連接(或朋友)關(guān)系及個(gè)人預(yù)分享的內(nèi)容信息(如日志或照片等)；3)用戶通過(guò)連接(或朋友)關(guān)系能瀏覽和評(píng)價(jià)朋友分享的信息。　　社交網(wǎng)絡(luò)與傳統(tǒng)的Web 網(wǎng)絡(luò)最大不同之處在于：傳統(tǒng)的Web 網(wǎng)絡(luò)的主體是內(nèi)容信息，依靠?jī)?nèi)容信息組織在一起，呈現(xiàn)給用戶；而社交網(wǎng)絡(luò)的主體是人，依靠人

4、與人之間的朋友關(guān)系組織在一起。社交網(wǎng)絡(luò)必須具備三項(xiàng)基本功能，即允許用戶1)創(chuàng)建和維護(hù)朋友關(guān)系；2)上傳自己預(yù)分享的內(nèi)容信息；3)瀏覽其他用戶分享的內(nèi)容信息。但這三項(xiàng)功能在不同的社交網(wǎng)站上的體現(xiàn)形式可能存在較大差異，如Facebook 只允許用戶遍歷三層朋友關(guān)系，而人人網(wǎng)則沒(méi)有這個(gè)限制.　　近</p><p>　　除了上述網(wǎng)絡(luò)以外，某些BBS(如天涯社區(qū))和協(xié)同編輯站點(diǎn)(如百度百科)等也增加了關(guān)注或好友功能，這些

5、站點(diǎn)上的用戶之間也可組成社交網(wǎng)絡(luò)?！　∩鲜稣军c(diǎn)所提供的服務(wù)之間有互補(bǔ)和重疊之處，如視頻分享網(wǎng)絡(luò)優(yōu)酷上的用戶也可以指定自己的好友；Facebook 和人人網(wǎng)上的用戶也可以發(fā)布自己的微博客，這使得我們很難在社交網(wǎng)絡(luò)的分類上給出嚴(yán)格的劃分。 　　三、社交網(wǎng)絡(luò)歷史</p><p>　　1995 年出現(xiàn)的網(wǎng)站Classmates.com 可以幫助用戶保持與他人的聯(lián)系，被認(rèn)為是社交網(wǎng)絡(luò)的雛形，但該網(wǎng)站不允許用戶之間直接建

6、立聯(lián)系，而是依靠就讀的學(xué)校間接地與他人建立聯(lián)系。從這點(diǎn)上說(shuō)，Classmates并不符合本文關(guān)于社交網(wǎng)絡(luò)的定義。1997 年出現(xiàn)SixDegrees允許朋友之間直接建立聯(lián)系，是第一個(gè)符合本文定義的社交網(wǎng)絡(luò)。進(jìn)入21世紀(jì)，隨著互聯(lián)網(wǎng)的普及，出現(xiàn)了一些單純以交友為目的的社交網(wǎng)絡(luò)，其中具有代表性的是Friendster，同時(shí)間段的其他社交網(wǎng)絡(luò)還有Cyworld、Ryze 和LinkedIn 等。2003 年出現(xiàn)的MySpace 提供的功能迎合

7、了用戶的需求，迅速發(fā)長(zhǎng)為最大的社交網(wǎng)絡(luò)。在隨后幾年，許多類似MySpace 的社交網(wǎng)絡(luò)不斷涌現(xiàn)，進(jìn)入社交網(wǎng)絡(luò)的快速發(fā)展階段?！　≡趪?guó)內(nèi)，創(chuàng)建于1998 年5 月的中國(guó)同學(xué)錄(5460.net)和Classmates類似，都是以同學(xué)數(shù)據(jù)為基礎(chǔ)的校友錄網(wǎng)站。2003 年開(kāi)通的UUZone被認(rèn)為是國(guó)內(nèi)最早的社交網(wǎng)站。2005 年12 月，校內(nèi)網(wǎng)（現(xiàn)改名人人網(wǎng)）在清華、北大、人大三所學(xué)校開(kāi)通服務(wù)，這是國(guó)內(nèi)首個(gè)實(shí)名制且具備一定影響</p&

8、gt;<p>　　近幾年，社交網(wǎng)絡(luò)的研究越來(lái)越多地引起學(xué)術(shù)界的關(guān)注，研究?jī)?nèi)容包括社交網(wǎng)絡(luò)的拓?fù)浞治?、社?huì)化推薦(social recommendation)、網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)、社交網(wǎng)絡(luò)中的信息傳播等，也取得了一些成果。</p><p>　　1、社交網(wǎng)絡(luò)拓?fù)涮匦苑治觥　‘?dāng)社會(huì)網(wǎng)絡(luò)剛開(kāi)始進(jìn)入研究者的視線的時(shí)候，人們希望通過(guò)了解社會(huì)網(wǎng)絡(luò)的拓?fù)涮匦?，和已知的一些網(wǎng)絡(luò)，例如WWW， Internet 的拓?fù)浣Y(jié)構(gòu)

9、進(jìn)行比較。這些比較主要是基于節(jié)點(diǎn)度分布，社交網(wǎng)絡(luò)的網(wǎng)絡(luò)半徑、平均路徑長(zhǎng)度和聚集系數(shù)等 ，來(lái)看看社交網(wǎng)絡(luò)的圖結(jié)構(gòu)和非社交網(wǎng)絡(luò)的圖結(jié)構(gòu)有什么不同。有些研究希望通過(guò)這些特性分析判斷某些應(yīng)用的性能。例如：有些應(yīng)用只有在具有很強(qiáng)的局部連通的社交結(jié)構(gòu)的條件才能有效的工作。這就意味著，社交圖必須有大量的聯(lián)系緊密的簇。　　分析Facebook 的節(jié)點(diǎn)度分布，其分布符合冪律分布。為研究社交網(wǎng)絡(luò)的網(wǎng)絡(luò)半徑、平均路徑長(zhǎng)度和聚集系數(shù)等特性，依據(jù)每個(gè)區(qū)域net

10、work 構(gòu)建了社交網(wǎng)絡(luò)圖，所有區(qū)域network 的平均路徑長(zhǎng)度都小于6，網(wǎng)絡(luò)半徑或直徑相對(duì)較低。聚集系數(shù)相對(duì)于同規(guī)模的隨機(jī)圖或隨機(jī)冪律圖具有較高的聚集性。Facebook 中所有network 的同配系數(shù)均大于0，說(shuō)明度值較高的節(jié)點(diǎn)之間的互聯(lián)的概率較大，這些度值較高的、相互連接的節(jié)點(diǎn)就形成了小世界網(wǎng)絡(luò)的骨干網(wǎng)，這使得處于網(wǎng)絡(luò)邊緣的那些高聚集的節(jié)點(diǎn)與其它節(jié)點(diǎn)之間具有較小的平均路徑長(zhǎng)度。</p><p>　　2、

11、用戶行為分析　　主要分析了用戶訪問(wèn)社交網(wǎng)絡(luò)過(guò)程中的行為，數(shù)據(jù)來(lái)源是用戶訪問(wèn)社交網(wǎng)絡(luò)的HTTP 會(huì)話過(guò)程數(shù)據(jù)。文中分析并比較了四種不同社交網(wǎng)絡(luò)（Facebook, LinkedIn, Hi5,和StudiVZ）的用戶訪問(wèn)行為特征。結(jié)果表明訪問(wèn)社交網(wǎng)站與其他網(wǎng)站存在不同之處：a)用戶容易重復(fù)同一個(gè)行為；b)用戶每次會(huì)話過(guò)程時(shí)間比較長(zhǎng)；c）圖片目錄最受歡迎。除了研究用戶訪問(wèn)社交網(wǎng)絡(luò)的行為外，還研究了各種行為之間轉(zhuǎn)移概率。為驗(yàn)證社交網(wǎng)絡(luò)拓?fù)涮?/p>

12、性與用戶交互網(wǎng)絡(luò)拓?fù)涮匦灾g的差異，利用facebook 中的數(shù)據(jù)分別對(duì)這兩種網(wǎng)絡(luò)的拓?fù)涮匦赃M(jìn)行統(tǒng)計(jì)分析，結(jié)果表明二者之間存在較大的差異，用戶交互網(wǎng)絡(luò)的網(wǎng)絡(luò)直徑顯著變大。</p><p>　　3、社會(huì)化推薦　　傳統(tǒng)的推薦技術(shù)主要利用了user 對(duì)item 評(píng)價(jià)矩陣，但在社交網(wǎng)絡(luò)中用戶對(duì)某item 的評(píng)價(jià)往往極大影響其朋友的選擇。綜合了user 對(duì)item 評(píng)價(jià)以及user 之間的信任關(guān)系（構(gòu)成Social Tr

13、ust Ensemble）進(jìn)行推薦，使得推薦結(jié)果更精確，并具有現(xiàn)實(shí)意義。研究基于協(xié)同過(guò)濾的社會(huì)化推薦問(wèn)題，針對(duì)傳統(tǒng)協(xié)同過(guò)濾法存在的兩個(gè)問(wèn)題：a）因計(jì)算復(fù)雜度而引起的特征信息融合困難；b）各種特征信息之間的依賴關(guān)系不能有效地利用，提出了多層次的連續(xù)隨機(jī)場(chǎng)模型，用于社會(huì)化推薦。</p><p>　　4、社區(qū)關(guān)系挖掘　　網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法有很多種，但有些算法的可擴(kuò)展性較差，適合于大規(guī)模網(wǎng)絡(luò)的卻為數(shù)不多，CNM、Waki

14、ta和Louvain是三種擴(kuò)展性較好算法。然而這三種算法都存在：　　當(dāng)輸入數(shù)據(jù)順序不同時(shí)，得到的結(jié)果也不相同的問(wèn)題。提出兩個(gè)定量指標(biāo)成員成對(duì)概率(pairwise membership probability)和一致性(consistency)，并依據(jù)這兩個(gè)指標(biāo)提出新的挖掘算法解決挖掘結(jié)果一致性的問(wèn)題。利用Filckr 中的圖片和標(biāo)簽描述信息推測(cè)圖片的拍攝位置，并基于位置進(jìn)行新型的關(guān)系挖掘，表明時(shí)序信息和可視內(nèi)容有助于推測(cè)圖片呈現(xiàn)的位

15、置。結(jié)合位置和時(shí)序信息可以還原圖片的拍攝路線，啟示了信息的變遷。</p><p>　　5、社交網(wǎng)絡(luò)中的信息傳播　　目前社交網(wǎng)絡(luò)信息傳播模型大都是基于獨(dú)立級(jí)聯(lián)模型(Independent Cascade Model , ICM)的，但I(xiàn)CM 的計(jì)算量較大，用最短路徑模型（Shortest-Path Model, SPM）來(lái)近似求解信息的傳播范圍以降低計(jì)算量，SPM 的主要思想是信息沿著從已受影響節(jié)點(diǎn)集合到將要受影

16、響節(jié)點(diǎn)的最短路徑進(jìn)行傳播，其速度是最快的，SPM 是ICM 的一個(gè)特例。實(shí)驗(yàn)結(jié)果表明最短路徑模型（SPM）具有獨(dú)立級(jí)聯(lián)模型(ICM)的相同效果，但運(yùn)行效率更高。利用因子圖建模，提出三種不同的學(xué)習(xí)算法，對(duì)社會(huì)影響力進(jìn)行了定量分析。從兩個(gè)方面研究了信息傳播最大化的問(wèn)題：a）改進(jìn)貪婪算法，降低運(yùn)行時(shí)間；b）通過(guò)舍棄某些度值，提出新的啟發(fā)式算法，以改進(jìn)信息的傳播速度。基于實(shí)驗(yàn)結(jié)果，作者認(rèn)為在解決信息傳播的可擴(kuò)展性方面，啟發(fā)式算法應(yīng)優(yōu)于貪婪算法。

17、很多研究者關(guān)心，在社交網(wǎng)絡(luò)的活動(dòng)中，哪些用戶行為會(huì)影響信息傳播，因此，在在社會(huì)網(wǎng)絡(luò)之上，有人又提出了interactive network，visit network 等表現(xiàn)用戶交互行為的關(guān)系網(wǎng)。</p><p>　　6、其它基于社會(huì)網(wǎng)絡(luò)的應(yīng)用　　除了針對(duì)社會(huì)網(wǎng)絡(luò)本身特性的研究，越來(lái)越多的研究開(kāi)始關(guān)注基于社會(huì)網(wǎng)絡(luò)的其它應(yīng)用問(wèn)題。例如利用社會(huì)網(wǎng)絡(luò)中朋友關(guān)系疏密程度，來(lái)防止Sybil attacks。還有利用朋友關(guān)