在線社會網(wǎng)絡(luò)的形成機制
——基于跨學科的視角

衛(wèi)健炯，胡海波

(華東理工大學管理科學與工程系，上海 200237)

在線社會網(wǎng)絡(luò)的形成機制
——基于跨學科的視角

衛(wèi)健炯，胡海波

(華東理工大學管理科學與工程系，上海 200237)

從多學科角度綜述了驅(qū)動在線社會網(wǎng)絡(luò)形成和演化的機制，重點是趨同性和擇優(yōu)連接這兩類較重要的機制。闡述了這些機制最近的研究進展，揭示了各種機制背后的原因及對網(wǎng)絡(luò)演化的影響，指出了這些機制潛在的應(yīng)用，澄清了對在線社會網(wǎng)絡(luò)形成機制的常見誤解。最后總結(jié)了在線社會網(wǎng)絡(luò)形成機制的研究意義，包括理論和應(yīng)用價值，以及未來的研究方向。

在線社會網(wǎng)絡(luò)；復(fù)雜網(wǎng)絡(luò)；趨同性；擇優(yōu)連接；機制

0 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展，特別是以社會協(xié)作技術(shù)為特征的Web 2.0的迅速興起使得各種在線社會網(wǎng)絡(luò)大量涌現(xiàn)，如Facebook、人人網(wǎng)、Twitter、新浪微博和豆瓣網(wǎng)等。這些網(wǎng)絡(luò)由于其潛在的研究價值已吸引了來自社會學、傳播學、計算機科學、物理學和管理學等眾多學科研究人員的關(guān)注[1]。

對于社會學家而言，在線社會網(wǎng)絡(luò)為他們研究大尺度社會網(wǎng)提供了前所未有的機會，有助于他們在這些網(wǎng)絡(luò)中尋找新形式的個人或集體行為；對于傳播學學者而言在線社會網(wǎng)絡(luò)尤其微博為他們研究新聞、內(nèi)容或思想的擴散提供了良好的平臺；對于計算機學者而言在線社會網(wǎng)絡(luò)有助于他們在推薦系統(tǒng)和鏈路預(yù)測方面的研究，有利于提出并測試更好的應(yīng)用于社會網(wǎng)絡(luò)的算法，如影響最大化算法等；對于物理學家，在線社會網(wǎng)絡(luò)有助于他們應(yīng)用統(tǒng)計物理方法研究微觀個體與宏觀群體之間的關(guān)系，大量的網(wǎng)絡(luò)生成和演化模型出自他們的研究；而對于管理學學者而言在線社會網(wǎng)絡(luò)的研究有助于構(gòu)建更好的信息系統(tǒng)平臺，在這些網(wǎng)絡(luò)上更有效地從事商品的口碑營銷或病毒式營銷，在線社會網(wǎng)絡(luò)在應(yīng)急管理和公共管理方面也發(fā)揮了重要作用。

在在線社會網(wǎng)絡(luò)中，最主要的用戶行為之一是用戶跟其他用戶之間建立好友關(guān)系，這導(dǎo)致了網(wǎng)絡(luò)的增長。由于在線社會網(wǎng)絡(luò)規(guī)模非常龐大且時刻處于變化之中，因此需要將傳統(tǒng)的社會網(wǎng)絡(luò)分析方法和現(xiàn)代的復(fù)雜網(wǎng)絡(luò)理論以及數(shù)據(jù)挖掘方法結(jié)合起來才能更好地理解人與人之間相互作用的模式。在線社會網(wǎng)絡(luò)的增長主要體現(xiàn)在其結(jié)構(gòu)參數(shù)會隨時間發(fā)生變化，比如以往的研究表明Pussokram[2]、Facebook[3]、Flickr[4]等很多拓撲參量隨時間的增長表現(xiàn)出非單調(diào)的變化趨勢，路經(jīng)長度會發(fā)生收縮，甚至網(wǎng)絡(luò)的同配系數(shù)也可能從正值變?yōu)樨撝礫5]。這些變化趨勢是傳統(tǒng)的網(wǎng)絡(luò)模型無法再現(xiàn)的。

在在線社會網(wǎng)絡(luò)的演化領(lǐng)域，雖然很多工作揭示了網(wǎng)絡(luò)拓撲參量的演化規(guī)律，但卻很難解釋結(jié)構(gòu)變化背后的內(nèi)在機制。眾所周知用戶建立網(wǎng)絡(luò)連接的行為導(dǎo)致了網(wǎng)絡(luò)結(jié)構(gòu)的變化，而僅針對網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)的研究框架往往不能很好地揭示網(wǎng)絡(luò)演化的個人層面的動因。因此要對在線社會網(wǎng)絡(luò)的演化有更深刻和全面的理解，構(gòu)建更好的網(wǎng)絡(luò)模型、推薦系統(tǒng)和鏈路預(yù)測算法，必須要深入研究這些網(wǎng)絡(luò)形成的驅(qū)動力。

多種機制驅(qū)動了在線社會網(wǎng)絡(luò)中好友關(guān)系的形成，如趨同性、擇優(yōu)連接、近鄰機制、關(guān)系機制等。趨同性關(guān)注個體的屬性在好友關(guān)系形成中起的作用，強調(diào)好友關(guān)系形成中個體屬性之間的兼容性；擇優(yōu)連接表明用戶傾向于與度值大的其他用戶建立好友關(guān)系；近鄰機制聚焦于個體的地理位置或所處的社會組織在時空的鄰近性；關(guān)系機制則強調(diào)用戶已有的社會關(guān)系和在網(wǎng)絡(luò)中的位置的影響。這幾種機制交織在一起，共同驅(qū)動了在線社會網(wǎng)絡(luò)的演化[6]。

在線社會網(wǎng)絡(luò)的形成機制與現(xiàn)實社會網(wǎng)絡(luò)存在很多相似之處，不同之處可能僅在于每種機制的權(quán)重存在差異。現(xiàn)實社會網(wǎng)絡(luò)的形成多基于特定的社交圈，如親屬圈、同學圈、同事圈等，而在線社會網(wǎng)絡(luò)雖然也包含了這些關(guān)系，但更多的則可能是與現(xiàn)實中不易遇到但卻有共同愛好的人建立在線聯(lián)系。相對于現(xiàn)實社會網(wǎng)絡(luò)，維持在線關(guān)系不需要付出大量的時間成本，且出于網(wǎng)絡(luò)友好的原則，在網(wǎng)絡(luò)社區(qū)中發(fā)出的好友關(guān)系請求往往不會被拒絕，這使得首先在線社會網(wǎng)絡(luò)的度分布往往更為異質(zhì)，其次相對于度同配現(xiàn)實社會網(wǎng)絡(luò)，在線社會網(wǎng)絡(luò)的度混合模式更為復(fù)雜。在本文中，我們將焦點放在在線社會網(wǎng)絡(luò)，而不是現(xiàn)實中的社會網(wǎng)絡(luò)以及很大程度上通過現(xiàn)實社會網(wǎng)絡(luò)構(gòu)建起來的電子郵件網(wǎng)或移動電話網(wǎng)，雖然它們的形成機制在很大程度上是相通的。

1 在線社會網(wǎng)絡(luò)的形成機制及原因

1.1 趨同性

趨同性即“物以類聚，人以群分”，是指人們傾向于跟與自己相似的人建立好友關(guān)系[7]。在很多情形下趨同性是顯著的，在諸如信仰、態(tài)度和價值觀方面的相似性能促進友誼形成，而不相似的個體間形成的好友關(guān)系則很容易瓦解，因為從社會心理學的角度講與你類似的人能夠給你一種個人獲得證實的感覺。人與人之間的很多關(guān)系，如朋友、同事、團體成員、訂婚的情侶以及夫妻，會比那些隨機配對的人更可能擁有相同的態(tài)度和價值觀。此外一般來講夫妻間的相似性越大，他們就越幸福。趨同性可用來解釋一些社會心理學現(xiàn)象，如種族分離、社區(qū)發(fā)展和社會流動性等。

趨同性導(dǎo)致個人的好友圈在人口統(tǒng)計學特征、行為特征和心理特質(zhì)方面具有同質(zhì)性，并約束了個人所能收到的信息的類型、他們的態(tài)度以及所經(jīng)歷的人際互動，地理上的鄰近、家庭、組織機構(gòu)和個人在社會網(wǎng)絡(luò)中位置的同構(gòu)性均為趨同機制創(chuàng)造了條件。

1.1.1 測試方法

1.1.2 實證研究

趨同性不僅在現(xiàn)實社會網(wǎng)絡(luò)的形成中發(fā)揮重要作用[9]，對于在線社會網(wǎng)絡(luò)中好友關(guān)系的形成，它也擔當了不容忽視的角色。Leskovec和Horvitz[10]研究了實時通信系統(tǒng)MicrosoftMessenger的全球通信網(wǎng)絡(luò)，發(fā)現(xiàn)相似的用戶間交流的頻率較高，交流時間較長。用戶傾向于跟與他們講相同語言、地理位置鄰近、具有相似年齡的其他用戶交流，但趨同性對于性別不成立，用戶更傾向于跟異性而非同性交流。

圖1 不同年齡的用戶對的數(shù)量[10]

圖1顯示了用戶年齡的趨同性，大部分用戶來自于10～30歲年齡段，圖1a表明隨機選擇的用戶對年齡之間沒有相關(guān)性，圖1b給出了交流過的用戶對之間年齡的相關(guān)性，圖中的對角線趨勢表明用戶傾向于跟與他們具有相似年齡的其他用戶交流。

在面向婚戀的在線社會網(wǎng)絡(luò)研究方面，Skopek等[11]研究了德國一家婚戀網(wǎng)站，評估了教育程度對發(fā)起或回復(fù)在線聯(lián)系邀請的重要性，發(fā)現(xiàn)教育程度上的趨同性是配偶選擇的最重要的機制，對于女用戶更是如此。教育層次上的相似性將顯著增加發(fā)出或回復(fù)初次聯(lián)系邀請的概率，且趨同性隨著教育層次的提高而增加，這與交換理論思想一致。絕大多數(shù)女用戶不愿與比自己學歷低的男用戶聯(lián)系，而男用戶則不介意女用戶的學歷比自己低。除了學歷用戶在很多屬性方面都表現(xiàn)出趨同性，比如Fiore和Donath[12]研究了美國一家婚戀網(wǎng)站中約65 000位用戶之間的互動情況，發(fā)現(xiàn)與現(xiàn)實世界中的情形一致，用戶更傾向于尋找那些與自己相似的異性用戶。在眾多因素中，趨同性最強的是個人的成長史、婚史和是否想要孩子，其他的因素如體型、相貌和抽煙習慣也表現(xiàn)出顯著的趨同性。當然不同性別的用戶所表現(xiàn)出的趨同性也存在差異，Hitsch等[13]利用一家婚戀網(wǎng)站的數(shù)據(jù)集，評估了用戶在選擇配偶時的傾向性。男人和女人在很多(但不是全部)方面對于相似性有很強的偏好性。特別地，該網(wǎng)站的用戶呈現(xiàn)出明顯的對相同種族(白人、黑人、亞裔等)的偏好性，女性同種族偏好相對于男性更為明顯。對于女性同一種族偏好不因年齡、教育、收入而變化。對于男性，研究發(fā)現(xiàn)不同的人口統(tǒng)計學特征會導(dǎo)致同種族偏好性存在差異，但定量上這些影響很小。對婚戀網(wǎng)站的研究結(jié)論總體上與以往心理學[14-16]和經(jīng)濟學[17]的研究結(jié)果是一致的。在用戶偏好性上有性別差異，特別地，相對于物理特征，如面部吸引力、身高、身體質(zhì)量指數(shù)(BMI)，女性更關(guān)注男性的收入，男性則恰恰相反。這些結(jié)果與進化心理學的預(yù)測[15]和競爭社會結(jié)構(gòu)理論[18]一致，從而表明雖然嚴肅的婚戀交友活動轉(zhuǎn)移到了網(wǎng)絡(luò)空間，但個體對對方的基本要求與現(xiàn)實中的并無顯著差異。

趨同性也存在于其他類型的社交網(wǎng)站中。對于生活日記網(wǎng)站LiveJournal，Lauw等的研究發(fā)現(xiàn)具有共同興趣的兩個用戶之間更易形成好友關(guān)系[19]。圖2a表明隨著共享的最小興趣數(shù)的增大，用戶對之間成為好友的概率逐漸增大，且用戶的活躍度能顯著增加成為好友的概率。同樣圖2b顯示隨著共享的最小社團數(shù)的增大，成為好友的概率也逐漸增大。LiveJournal網(wǎng)站自身的一些特點可能增強了用戶間的趨同性，每個興趣都提供了一個指向具有該興趣的用戶的列表的鏈接，從而使得用戶可以找到具有某種興趣的其他用戶并與之建立連接，此外博客和評論也有助于用戶發(fā)現(xiàn)與之具有類似興趣的其他用戶。

MySpace是Facebook之前最流行的社交網(wǎng)站，其突出特征是以音樂為一個重要的社交對象。Mazur和Richards[20]研究了129位年齡在16～19歲的美國青少年在MySpace上的個人資料，發(fā)現(xiàn)大部分的互動發(fā)生在具有相同種族、年齡和州的用戶間，盡管也會出現(xiàn)跨種族的交流。青春期少年相對于即將成年的表現(xiàn)出更強的年齡上的趨同性。Thelwall[21]研究了MySpace中2 567位用戶以及在他們主頁上發(fā)表評論的好友的個人資料，發(fā)現(xiàn)沒有證據(jù)表明存在性別上的趨同性，這跟Microsoft Messenger中的情形一致，但在種族、宗教信仰、年齡、國家、婚姻狀態(tài)、對孩子的態(tài)度、性取向和加入MySpace的原因方面用戶之間則表現(xiàn)出顯著的趨同性。

圖2 用戶之間共享的屬性與成為好友的概率之間的關(guān)系[19]

Facebook是目前全球最大的社交網(wǎng)站，其網(wǎng)絡(luò)流量也名列前茅。Mayer[22]研究了美國10所高校的Facebook網(wǎng)絡(luò)，發(fā)現(xiàn)用戶在種族、專業(yè)、年級以及政治傾向(自由派、保守派)方面具有趨同性。Mislove等[23]研究了美國Rice大學和New Orleans地區(qū)的Facebook網(wǎng)絡(luò)，發(fā)現(xiàn)具有相同屬性(學院、系、年級、專業(yè)、中學、家鄉(xiāng)、政治觀點)的用戶之間更易形成好友關(guān)系和緊密的社團。Wimmer和Lewis[24]研究了一群大學生的Facebook個人主頁，發(fā)現(xiàn)好友關(guān)系中種族的同質(zhì)性不僅源于種族上的趨同性，也源于相同種族背景下不同人種之間的趨同性以及一些平衡機制，如傾向于接受好友邀請或成為好友的好友，這些都放大了趨同性導(dǎo)致的同質(zhì)效應(yīng)。他們也比較了種族趨同性與驅(qū)動連接形成的其他機制在網(wǎng)絡(luò)演化中所發(fā)揮的作用，發(fā)現(xiàn)相對于種族趨同性，平衡機制、基于共同居住地的近鄰機制以及非種族方面的趨同性(家庭背景或來自特定的州)在影響好友關(guān)系形成方面所發(fā)揮的作用更強。

對于一些社會化書簽系統(tǒng)，用戶之間也表現(xiàn)出顯著的趨同性。Aiello等[25-26]研究了一個在線社會化書簽系統(tǒng)aNobii，探討了用戶個人資料之間的相似性與他們的網(wǎng)絡(luò)距離之間的關(guān)系，發(fā)現(xiàn)隨著用戶之間網(wǎng)絡(luò)距離的增大，他們在閱讀的書、所在的群組和所處的地理位置方面的相似性迅速降低。如圖3所示，〈ncb〉和〈ncg〉分別表示共同的書和群組的平均數(shù)，〈σb〉和〈σg〉分別表示書列表和群組列表的余弦相似性的均值，psc和pst則分別表示居住在相同國家和城鎮(zhèn)的用戶對的比例。作為對比圖3也給出了零模型得到的結(jié)果。aNobii中的趨同性部分原因是由于用戶活動性之間的同配行為，活躍用戶傾向于跟其他的活躍用戶建立聯(lián)系，因而更可能在用戶之間找到相似性，比如共同閱讀的書。雖然如此，趨同性仍在該網(wǎng)絡(luò)增長中發(fā)揮作用，好友之間的相似性相對于隨機選擇的或網(wǎng)絡(luò)距離較遠的要更大。此外，Aiello等[27]對Flickr和Last.fm的研究也發(fā)現(xiàn)，隨著用戶之間網(wǎng)絡(luò)距離的增大，他們所參與的群組或所使用標簽的相似性迅速減小。

即便是像Twitter這類以信息共享為主要目的的微博網(wǎng)站，其用戶間也表現(xiàn)出趨同性。Kang和Lerman[28]利用Twitter列表研究了Twitter上的主題趨同性，Twitter列表由用戶創(chuàng)建，用來組織其他用戶并對用戶進行分類。他們發(fā)現(xiàn)主題上相似的用戶之間建立連接的可能性較大，表明趨同性機制也驅(qū)動了Twitter的演化。當然在一些在線社會網(wǎng)絡(luò)中也發(fā)現(xiàn)了趨同性較弱的情形。Bisgin等[29]研究了在線社會媒體網(wǎng)站BlogCatalog和Last.fm，發(fā)現(xiàn)基于興趣的趨同性并不是一個很強的影響連接形成的因素。對于BlogCatalog超過84%的連接沒有共享一個興趣，表明用戶在形成連接之前沒有考慮興趣。而在Last.fm中超過76%的連接至少共享了一個興趣。BlogCatalog中所有連接的Jaccard相似性系數(shù)為0.04，而Last.fm則為5×10-7，表明Last.fm中的用戶有大量不同的興趣?；谮呁缘奈⒂^的創(chuàng)建連接的過程可導(dǎo)致網(wǎng)絡(luò)中某些宏觀模式如社團結(jié)構(gòu)的形成，他們發(fā)現(xiàn)網(wǎng)絡(luò)不同社團之間，社團與整個網(wǎng)絡(luò)之間興趣類似，這表明同一社團的用戶并未表現(xiàn)出興趣上的相似性，這些網(wǎng)絡(luò)的連接形成中興趣上的趨同性并非主要因素。

除了年齡、宗教信仰和種族等人口統(tǒng)計學特征外，即使是“孤獨感”這類的心理狀態(tài)，在在線社會網(wǎng)絡(luò)中都可能會產(chǎn)生趨同效應(yīng)。Bollen等[30]記錄了Twitter用戶在6個月的時間段內(nèi)的使用情況，發(fā)現(xiàn)主觀幸福感確實在Twitter社會網(wǎng)絡(luò)中存在趨同性。幸福的用戶更傾向于與幸福的用戶建立連接而不幸福的用戶則傾向于和不幸福的用戶建立連接。因而在線社會網(wǎng)絡(luò)可能也受制于導(dǎo)致現(xiàn)實社會網(wǎng)絡(luò)中趨同性發(fā)生的社會機制，這種趨同性是發(fā)生在主觀幸福感層面上的。隨著邊的權(quán)重的增大，主觀幸福感的趨同性增強?？紤]到在線社會網(wǎng)絡(luò)越來越流行，Twitter用戶偏向于與擁有相似主觀幸福感的用戶建立連接的現(xiàn)象可能是幫助我們更好地理解積極和消極情緒是如何在在線網(wǎng)絡(luò)節(jié)點間傳播的一個重要手段。

圖3 用戶之間的網(wǎng)絡(luò)距離與他們的相似性之間的關(guān)系[26]

1.2 擇優(yōu)連接

擇優(yōu)連接，或稱“馬太效應(yīng)”、“富者愈富”現(xiàn)象，在網(wǎng)絡(luò)科學背景下一般是指在網(wǎng)絡(luò)中新的連邊會優(yōu)先地連向度值大的節(jié)點，其本質(zhì)是一種正反饋機制[31]。雖然擇優(yōu)連接中度值可以是其他的中心性指標，如介數(shù)[32]，且不僅在節(jié)點層面，在社團或群組層面也存在擇優(yōu)連接現(xiàn)象[33-34]，但在這部分的討論中，我們將焦點限定在在線社會網(wǎng)絡(luò)中的度擇優(yōu)連接。在在線社會網(wǎng)絡(luò)中，新用戶傾向于跟度值較大的老用戶建立連接，一般認為新用戶和度值為k的老用戶連接的概率與kβ成正比，其中β≥0為擇優(yōu)性指數(shù)。線性擇優(yōu)連接(β=1)也是產(chǎn)生無標度網(wǎng)絡(luò)的一種重要機制。

1.2.1 測試方法

有多種方法可以測試演化網(wǎng)絡(luò)中的擇優(yōu)連接，一種常用的方法[35]是令ki為用戶i的度值，該用戶被選擇作為新的連邊的一個端點的概率為

(1)

可以計算度值為k的老用戶被選擇的概率П(k)，它可利用選擇之前網(wǎng)絡(luò)中存在的度值為k的用戶的數(shù)量歸一化得到

(2)

其中,kv(s-1)=k表示用戶v在時間s-1時度值為k，es=v表示在時間s用戶v被選中作為連邊的一個端點，∧為邏輯與操作，因此es=v∧kv(s-1)=k表示在時間s-1時度值為k的用戶在接下來的s時被選中。[·]表示一個謂項命題，如果表達式為真則取值為1，反之取值為0。|{u:ku(s-1)=k}|表示在時間s-1時度值為k的用戶的數(shù)量。Π(k)通常有大的漲落，尤其在k較大時。為了減少噪聲階，可以研究累積函數(shù)(3)。

(3)

擇優(yōu)連接現(xiàn)象可以發(fā)生在不同的情況下。在網(wǎng)絡(luò)增長過程中，當新用戶與老用戶之間建立連接，或者老用戶之間建立連接的時候，度值大的老用戶都有可能被擇優(yōu)選擇。

1.2.2 實證研究

最近幾年，由于可以獲得演化的在線社會網(wǎng)絡(luò)的數(shù)據(jù)(盡管這些數(shù)據(jù)分辨率很低或僅僅是某一段時間內(nèi)的一個采樣)，擇優(yōu)連接機制得到了證實，盡管在極少數(shù)網(wǎng)絡(luò)中，如Buzznet，表現(xiàn)出相反的特征[36]。指數(shù)β(盡管計算方法不盡相同)也得到了測算，在一些網(wǎng)絡(luò)中β非常接近1，而其他一些網(wǎng)絡(luò)則表現(xiàn)出亞線性或超線性擇優(yōu)連接。

擇優(yōu)連接的實證研究方面比較有代表性的工作有：Mislove等[37]研究了Flickr的演化，發(fā)現(xiàn)線性擇優(yōu)選擇對于出度和入度均成立，一位用戶的出度越大，則她/他發(fā)出連接請求的可能性也就越大；入度越大，則她/他收到新的連接請求的概率也越大。Zhao等[38]研究了豆瓣網(wǎng)的演化，也發(fā)現(xiàn)線性擇優(yōu)選擇對于出度和入度均成立。Leskovec等[35]研究了Flickr、del.icio.us, Yahoo!Answers和LinkedIn的演化,測試了擇優(yōu)連接機制在網(wǎng)絡(luò)的演化中是否發(fā)揮作用，發(fā)現(xiàn)Flickr和del.icio.us表現(xiàn)出線性擇優(yōu)連接，對于Yahoo!Answers則表現(xiàn)出輕微的亞線性擇優(yōu)連接β=0.9。對于LinkedIn當度值較小時β=0.6，而當度值較大時β=1.2，表現(xiàn)出超線性擇優(yōu)連接。Garg等[39]研究了在線社會化聚合器網(wǎng)站FriendFeed，發(fā)現(xiàn)對于源節(jié)點選擇β=0.8，而對于目標節(jié)點選擇β=0.9。Szell和Thurner[40]研究了在線游戲網(wǎng)站Pardus，他們得到了被新來者標記為朋友(或敵人)的用戶的入度值，發(fā)現(xiàn)對于標記為朋友的當kin<30時β=0.62，而對于標記為敵人的β=0.62。Aiello等[25]研究了一個在線社會化書簽系統(tǒng)aNobii的演化，并測試了擇優(yōu)連接機制，發(fā)現(xiàn)對于入度和出度，線性擇優(yōu)性均成立。Hu和Wang[41]研究了在線社會網(wǎng)絡(luò)Wealink和Facebook中存在的擇優(yōu)連接現(xiàn)象，發(fā)現(xiàn)前者表現(xiàn)出顯著的線性擇優(yōu)性，而后者則表現(xiàn)出亞線性擇優(yōu)連接。Rocha等[42]研究了通過因特網(wǎng)賣淫的性關(guān)系網(wǎng)絡(luò)，發(fā)現(xiàn)對于短的和長的時間間隔，嫖客均表現(xiàn)出亞線性擇優(yōu)連接。對于短的時間間隔，對于賣淫者他們發(fā)現(xiàn)了接近線性的擇優(yōu)連接，而對于較長的時間間隔則表現(xiàn)出亞線性擇優(yōu)連接，從而表明對于短的時間尺度反饋過程更強。

在線社會網(wǎng)絡(luò)的擇優(yōu)性指數(shù)β并不是普適的，對于不同的網(wǎng)絡(luò)該參數(shù)存在較大的差異。Kunegis等[43]廣泛研究了7類共47個在線社會化系統(tǒng)的擇優(yōu)性指數(shù)β，發(fā)現(xiàn)絕大多數(shù)網(wǎng)絡(luò)表現(xiàn)出非線性擇優(yōu)連接，且該指數(shù)跟網(wǎng)絡(luò)類型密切相關(guān)[43]。某些類型的網(wǎng)絡(luò)表現(xiàn)出明顯的超線性擇優(yōu)連接，而其他類型的網(wǎng)絡(luò)則表現(xiàn)出亞線性擇優(yōu)連接。特別地他們發(fā)現(xiàn)70%的網(wǎng)絡(luò)在亞線性目錄中，包括在線打分網(wǎng)絡(luò)、交流網(wǎng)絡(luò)、大眾分類網(wǎng)絡(luò)和社交網(wǎng)絡(luò)，其他的30%的網(wǎng)絡(luò)落在超線性目錄中，包括顯式的和隱式的相互作用網(wǎng)絡(luò)。

事實上，不僅對于不同的網(wǎng)絡(luò)，擇優(yōu)性指數(shù)β存在較大的差異，即使對于同一網(wǎng)絡(luò)，它也不是穩(wěn)定的，而是會隨著網(wǎng)絡(luò)的增長發(fā)生變化。Zhao等[44]研究了中國最大的在線社會網(wǎng)絡(luò)人人網(wǎng)的演化，發(fā)現(xiàn)雖然好友關(guān)系的建立具有擇優(yōu)連接特性，但強度隨著網(wǎng)絡(luò)的擴張和成熟逐漸減弱，即β并非一常數(shù)，隨著網(wǎng)絡(luò)的增長，β逐漸減小，從網(wǎng)站創(chuàng)建之初的1.25減小到兩年后的0.65(此時人人網(wǎng)中的連邊數(shù)已達1.99億)。這表明當網(wǎng)絡(luò)尚年輕時，它的增長表現(xiàn)出較強的擇優(yōu)連接特征，而當網(wǎng)絡(luò)規(guī)模逐漸增大時，新的連邊的建立不再由擇優(yōu)連接主導(dǎo)。一個可能的解釋是當該社交網(wǎng)站剛剛開始運作時，與度值大的超級用戶建立連接是驅(qū)動好友關(guān)系請求的關(guān)鍵因素，但是隨著網(wǎng)絡(luò)的成長，在如此大的社會網(wǎng)絡(luò)中定位超級用戶變得越來越困難，他們的影響力開始減弱?；蛘弋斁W(wǎng)站較年輕時，新的用戶可在上面找到的線下好友屈指可數(shù)，于是那些人氣很高的超級用戶便抓住了他們的吸引力，隨著網(wǎng)絡(luò)的增長，用戶在網(wǎng)站上找到了他們越來越多的線下好友，于是用戶開始將更多的注意力放在這些他們在線下可能認識的用戶上，而不是那些擁有很多好友的超級用戶上。

1.2.3 機制背后的原因

擇優(yōu)連接是驅(qū)動網(wǎng)絡(luò)增長和演化的重要機制，但為什么會存在該種機制？傳統(tǒng)社會學對它的一種解釋是擁有社會資本的個體能利用這些資本獲得更多的社會資本。此外一些其他的結(jié)構(gòu)化機制也能導(dǎo)致?lián)駜?yōu)連接現(xiàn)象，比如Li等[45]發(fā)現(xiàn)節(jié)點間局部的相互作用可導(dǎo)致全局性的擇優(yōu)連接,如與網(wǎng)絡(luò)距離最近的節(jié)點建立連接。

值得注意的是，擇優(yōu)連接機制看起來非常合理，但卻施加了過強的假設(shè)。因為它認為一個節(jié)點的流行度(人氣)越大，它的吸引力就越大，流行度跟吸引力之間存在強的正相關(guān)性。而Utz[46]對荷蘭在線社會網(wǎng)絡(luò)Hyves的研究則發(fā)現(xiàn)，相對于那些好友較少的用戶，人們往往認為好友多的用戶更流行但并非更有社交方面的吸引力。事實上還可以提出一種完全不同的非結(jié)構(gòu)化的機制，同樣可以解釋擇優(yōu)連接現(xiàn)象，這種機制可稱之為優(yōu)點機制，即個體由于具有某些優(yōu)點從而吸引了大量的連接。該機制認為，網(wǎng)絡(luò)中每個節(jié)點的質(zhì)量是不一樣的，質(zhì)量高的節(jié)點將獲得更多的連接，在網(wǎng)絡(luò)增長過程中，這些節(jié)點由于質(zhì)量高具有某些優(yōu)點將持續(xù)吸引新的連接，從而同樣可以導(dǎo)致?lián)駜?yōu)連接現(xiàn)象。但這種擇優(yōu)連接過程不是依靠網(wǎng)絡(luò)結(jié)構(gòu)層面的屬性，如節(jié)點度值，而是完全依靠節(jié)點內(nèi)在的特性，如它的質(zhì)量。在這種情況下，仍然能發(fā)現(xiàn)度值為k的節(jié)點獲得新連接的概率П(k)將隨k的增加而增大，盡管這種情況下的增長機制完全不同于擇優(yōu)連接。

比如在文獻引用網(wǎng)絡(luò)中，引用率高的論文可能具有某些優(yōu)點，由于它們質(zhì)量較高將會再次獲得引用，并不是僅僅因為它們以前很流行。當然引用率高的論文更有可能被一位潛在的引用者在文獻搜索中找到并且因為這個原因更可能被引用。同樣地，在社會網(wǎng)絡(luò)中，高質(zhì)量的用戶更容易獲得新的連接或在線好友，同樣好友多的用戶也更容易被搜索發(fā)現(xiàn)從而進一步導(dǎo)致好友數(shù)的增加。Lu等[47]研究了在線商品點評網(wǎng)站Epinions中由用戶之間的信任關(guān)系所構(gòu)成的有向社會網(wǎng)絡(luò)，并探討了在該網(wǎng)絡(luò)中意見領(lǐng)袖是如何涌現(xiàn)的。該網(wǎng)絡(luò)中入度大的用戶可被視為意見領(lǐng)袖，他們發(fā)現(xiàn)擇優(yōu)連接并不能解釋為什么隨著時間的推移某用戶的意見領(lǐng)袖地位會被另外的用戶取代。因為如果擇優(yōu)連接是唯一的機制，具有大量入度的用戶將收到按同等比例的大量的新的指向他們的入連接，也就是說，如果沒有施加本質(zhì)性的影響，意見領(lǐng)袖將永遠是意見領(lǐng)袖，他們的地位不會被剝奪(盡管新的意見領(lǐng)袖會出現(xiàn))。但是對Epinions的研究并未發(fā)現(xiàn)該特性。特別地一位很熱門的評論者在某段時間內(nèi)不活躍之后，她/他收到的額外的入連接在之后的每個階段都將顯著減少。

實際上很難相信在在線社會網(wǎng)絡(luò)中用戶傾向于跟度值大的其他用戶建立好友關(guān)系僅僅因為這些用戶有很多的在線好友，一個可能的原因是這些用戶擁有某些我們喜歡或期望的特質(zhì)，對現(xiàn)實中社會網(wǎng)絡(luò)的研究確實已發(fā)現(xiàn)在個人好友數(shù)與個人的某些優(yōu)良品質(zhì)，比如創(chuàng)造力、工作能力、個人發(fā)展空間、影響力和威望之間存在正相關(guān)性[6]。Kim和Jo[48]認為，擇優(yōu)連接從經(jīng)濟學角度講可被看作是一種理性平衡行為，個體的好友數(shù)是表征該個體價值的一種信號，即可以觀測的度值包含了個體不可觀測的價值的某些信息。Lu等[47]對Epinions的研究發(fā)現(xiàn)，雖然基于網(wǎng)絡(luò)結(jié)構(gòu)的因素如擇優(yōu)連接和互惠性是網(wǎng)絡(luò)增長的顯著驅(qū)動力，用戶內(nèi)在的特性，如發(fā)布評論的數(shù)量和文本特性如全面性、客觀性和可讀性，也是網(wǎng)絡(luò)增長的驅(qū)動力。實際上，網(wǎng)上評論者可能收到指向他們的信任連接或入連接，也可以為網(wǎng)絡(luò)社區(qū)貢獻新的評論，這兩個因素都將增加他們相對于網(wǎng)絡(luò)社區(qū)中其他成員的吸引力。

1.3 關(guān)系機制

除了趨同性和擇優(yōu)連接，還有其他的機制驅(qū)動了在線社會網(wǎng)絡(luò)的演化。在現(xiàn)實生活中我們都有這樣的體會，通過朋友的引薦結(jié)識新的好友，這個過程就是所謂的關(guān)系機制，即一般而言人們易于跟自己好友的好友建立連接，從而使得社會網(wǎng)絡(luò)具有較高的聚類系數(shù)和顯著的社團結(jié)構(gòu)。在線社會網(wǎng)絡(luò)中關(guān)系機制同樣發(fā)揮作用，在Flickr[27],Last.fm[27],Douban[38],aNobii[25]和Gowalla[49]的演化中都已發(fā)現(xiàn)了證據(jù)。

在線社會網(wǎng)絡(luò)的形成中通常存在3類標度關(guān)系，一是擇優(yōu)連接機制中一位用戶獲得一條新的連接的概率與她/他的度值之間的標度關(guān)系，二是冪律度分布中的標度關(guān)系，三是網(wǎng)絡(luò)層次化結(jié)構(gòu)中聚類系數(shù)與度值之間的標度關(guān)系。近來的研究表明關(guān)系機制或所謂的三元閉合可在一定程度上再現(xiàn)所有這3類標度關(guān)系[50]，從而表明關(guān)系機制是在線社會網(wǎng)絡(luò)形成的重要機制之一。

1.4 近鄰機制

我們也都有這樣的生活體驗，居住位置相近的人也更易形成好友關(guān)系，這就是近鄰機制，這種機制將社會網(wǎng)絡(luò)的形成放在了更寬廣的個體的社會和文化環(huán)境中。在現(xiàn)實生活中近鄰意味著個體有更多的機會遇見并相互作用，進而導(dǎo)致新的好友關(guān)系的形成和舊的好友關(guān)系的維持。近鄰機制之所以能夠發(fā)揮作用是因為熟悉度或曝光效應(yīng)，我們暴露在某一刺激下越多也就越可能對其產(chǎn)生好感。我們經(jīng)?？吹揭恍┨囟ǖ娜耍敱舜俗兊迷絹碓绞煜?，友誼也就越來越容易形成。盡管互聯(lián)網(wǎng)使人與人之間的交流跨越了空間的限制，使整個世界變得更加扁平，但近來大量的實證研究表明，對于在線社會網(wǎng)絡(luò)，近鄰機制在好友關(guān)系的形成中仍擔當重要角色，個人的好友圈在地理位置上具有相似性。在基于位置的在線社會網(wǎng)絡(luò)，如Gowalla[51-53]，BrightKite[52-54]，F(xiàn)ourSquare[53-54]，以及Microsoft Messenger[10]，LiveJournal[54]，Twitter[54-55]和Facebook[56]中都發(fā)現(xiàn)了空間距離所起的作用。

社會網(wǎng)絡(luò)中個體間的地理距離與他們成為好友的概率間存在特定的標度關(guān)系P(r)∝r-α。Kleinberg[57]指出在二維空間中的小世界網(wǎng)絡(luò)中只有當α=2時網(wǎng)絡(luò)才具有最佳的可搜索性，Liben-Nowell等[58]對LiveJournal的研究則發(fā)現(xiàn)α≈1。事實上Kleinberg的結(jié)論是在人口均勻分布的情況下得到的，而實際上現(xiàn)實中的人口密度很少是均勻的，大城市人口密度大而鄉(xiāng)村則人口密度小。如果考慮到人口密度因素，這兩個指數(shù)其實是等價的，也就是說LiveJournal自發(fā)形成了一個具有最優(yōu)可搜索性的在線社會網(wǎng)絡(luò)，在Facebook中也有類似的發(fā)現(xiàn)[56]。Hu等[59]研究認為社會網(wǎng)絡(luò)中的空間標度關(guān)系P(r)∝r-1可能是對個體搜集信息進行優(yōu)化的結(jié)果，大部分的個體傾向于最大化他們的好友關(guān)系的多樣性，因而可視為最大化信息熵的過程。當然并不是對所有的在線社會網(wǎng)絡(luò)α=1，對Gowalla、BrightKite和FourSquare的研究表明[53]，它們的指數(shù)更接近于0.5，這可能是因為這些網(wǎng)站相對較新，主要吸引了早期的采納者。值得一提的是早在六十多年前，Zipf[60]就已在實證數(shù)據(jù)中發(fā)現(xiàn)了該標度關(guān)系。Zipf分析了1930年代美國Philadelphia州5 000對夫妻的居住地，發(fā)現(xiàn)夫妻之間在他們結(jié)婚之前的空間距離分布滿足P(r)∝r-0.842 5。

2 應(yīng)用及有關(guān)問題的澄清

2.1 應(yīng)用

對各種機制的深入理解有助于構(gòu)建更好的網(wǎng)絡(luò)模型并對網(wǎng)絡(luò)結(jié)構(gòu)和用戶屬性進行預(yù)測。在復(fù)雜網(wǎng)絡(luò)領(lǐng)域已有大量的文獻探討了擇優(yōu)連接和關(guān)系機制在網(wǎng)絡(luò)建模、鏈路預(yù)測和推薦系統(tǒng)中的應(yīng)用[41,61-64]，限于篇幅本文不再討論。在本部分中我們將焦點放在趨同性機制的應(yīng)用上。

既然趨同性可以導(dǎo)致社會網(wǎng)絡(luò)中好友關(guān)系的形成，因此學者們也提出了各種基于趨同性的網(wǎng)絡(luò)生成模型。在社會網(wǎng)絡(luò)中，每一個節(jié)點都有豐富的屬性與特征，比如在線社會網(wǎng)絡(luò)包含用戶簡介信息。然而大部分現(xiàn)有的網(wǎng)絡(luò)模型，如很多基于擇優(yōu)連接和關(guān)系機制的模型，都聚焦于網(wǎng)絡(luò)結(jié)構(gòu)，忽略了節(jié)點的內(nèi)在特征和屬性。Kim和Leskovec[65]構(gòu)建了一個多屬性圖模型，該模型可以自動捕獲網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點屬性間的交互作用。在模型中每個節(jié)點都與一個分類屬性向量相關(guān)聯(lián)，連接親和性矩陣模擬了某個屬性值和節(jié)點間建立連接的可能性之間的關(guān)系。在對度分布進行分析之后發(fā)現(xiàn)多屬性圖模型具有很好的靈活性，可以生成具有對數(shù)正態(tài)或冪律度分布的網(wǎng)絡(luò)。

社會網(wǎng)絡(luò)通常具有較高的聚類系數(shù)、某些觀測屬性上的趨同性、社團結(jié)構(gòu)以及個體度值的異質(zhì)性。Krivitsky等[66]提出一個隱聚類隨機效應(yīng)模型來表示所有的這些特征，并用貝葉斯推斷來估計模型參數(shù)。該模型適用于二元與非二元網(wǎng)絡(luò)數(shù)據(jù)，可再現(xiàn)網(wǎng)絡(luò)的聚類系數(shù)、趨同性、社團結(jié)構(gòu)和無標度特性等重要性質(zhì)。

在基于趨同性的網(wǎng)絡(luò)模型的解析研究方面，Tarbush和Teytelboym[67]提出了一個精簡的，易處理的動態(tài)社會網(wǎng)絡(luò)生成模型，模型中用戶在重疊的社交群中相互作用，從而可以同時分析網(wǎng)絡(luò)屬性和趨同性模式。他們使用平均場近似方法解析得到了度分布和趨同性指數(shù)的表達式，并利用2005年10所美國大學的Facebook學生關(guān)系網(wǎng)絡(luò)來測試模型，發(fā)現(xiàn)解析表達式和模擬結(jié)果與實際數(shù)據(jù)的趨同性模式、度分布和個體聚類系數(shù)取得了很好的一致。

此外理解趨同性有助于為個性化推薦系統(tǒng)構(gòu)建更好的用戶模型，也有助于提出更好的鏈路預(yù)測算法。比如對在線社會網(wǎng)絡(luò)Flickr，Last.fm和aNobii的研究發(fā)現(xiàn)擁有相同興趣的用戶更可能成為朋友[27]，因此僅僅基于用戶生成的元數(shù)據(jù)(描述數(shù)據(jù)的數(shù)據(jù)，如標簽)注解的主題相似性就可以預(yù)測用戶間的社會連接。通過在不同的數(shù)據(jù)集上做實驗，證實由主題相似性構(gòu)成的社會網(wǎng)絡(luò)能夠精確描述真實的友誼關(guān)系，當和拓撲特性結(jié)合在一起后，主題相似性能達到92%的預(yù)測準確率。

在同一網(wǎng)絡(luò)中用戶不同屬性的趨同性強弱存在差異，對于不同的網(wǎng)絡(luò)同一屬性的趨同性也存在差異。Traud等[68]研究了美國100所大學的Facebook好友網(wǎng)絡(luò)的社會結(jié)構(gòu)，考察了用戶的屬性如性別、年級、專業(yè)、畢業(yè)高中以及居住地在這些機構(gòu)好友關(guān)系形成中擔當?shù)慕巧?。他們測試了不同的用戶特性在不同機構(gòu)好友關(guān)系形成中的相對重要性，發(fā)現(xiàn)對于規(guī)模較大的機構(gòu)中的社會網(wǎng)絡(luò)，共同的高中重要性較高，而共同專業(yè)的重要性隨著機構(gòu)的不同而變化。對于幾乎所有的機構(gòu)，所在年級相對于其他人口統(tǒng)計學特性趨同性更強。此外女生相對于男生更傾向于跟與自己居住地相同的人建立好友關(guān)系。

趨同性也可用來預(yù)測用戶屬性，Agarwal等[69]研究了一個在線旅游社區(qū)TravelSite，該社區(qū)同時包含了個人的好友網(wǎng)絡(luò)以及從限定列表中填寫的個人屬性和愛好。他們提出了用高斯場諧函數(shù)——一種圖轉(zhuǎn)換算法——作為測量友誼網(wǎng)絡(luò)關(guān)聯(lián)性的方法。研究發(fā)現(xiàn)個人好友網(wǎng)絡(luò)能夠預(yù)測用戶的一些(但不是所有的)屬性。利用支持矢量機方法并結(jié)合高斯場諧函數(shù)發(fā)現(xiàn)其他一些屬性，比如年齡和語言對于預(yù)測也很重要。

對于Facebook網(wǎng)絡(luò)Mislove等[23]研究了Rice大學和新奧爾良地區(qū)的子網(wǎng)，發(fā)現(xiàn)學院、系、年級、專業(yè)、畢業(yè)中學、家鄉(xiāng)、政治觀點等屬性相同的用戶更可能結(jié)為好友而且更可能形成高密度的社團，根據(jù)這兩個發(fā)現(xiàn)并基于已有的社會網(wǎng)絡(luò)中的社團檢測算法他們提出了一種可推測用戶屬性的方法。結(jié)果表明即使只知道提供了屬性信息的20%的用戶，仍然可以以超過80%的準確率推測剩下的用戶的屬性。

既然相似的用戶更易形成好友關(guān)系，因此可以利用用戶屬性來預(yù)測用戶之間的相互作用。對虛擬世界SecondLife的研究表明[70]，地點信息是預(yù)測在線社會網(wǎng)絡(luò)中用戶之間交互(聊天或消息交流)行為的一個重要參考，其性能超過社會網(wǎng)絡(luò)特征，這些特征既包括拓撲特征，如共同好友、Jaccard相似系數(shù)、擇優(yōu)連接，也包括趨同特征，如共同小組、共同愛好、共同區(qū)域。然而如果要預(yù)測用戶間的互惠消息交流，社會網(wǎng)絡(luò)特征更為重要。

2.2 有關(guān)問題的澄清

我們在1.2.3節(jié)已經(jīng)知道，在很多在線社會網(wǎng)絡(luò)的演化中存在兩種混合機制，即擇優(yōu)連接和優(yōu)點機制，節(jié)點的吸引力隨著他們流行度的增加而增大，同時不同節(jié)點某些特性之間存在異質(zhì)性，這些特性并不與他們的度值直接相關(guān)。這兩種機制都會使節(jié)點獲得新連接的概率隨著它的度值的增加而增大，因此有必要將這兩種機制區(qū)分開。

deBlasio等[71]提出了一種統(tǒng)計方法來區(qū)分網(wǎng)絡(luò)演化中的擇優(yōu)連接和優(yōu)點機制。假定有網(wǎng)絡(luò)在3個不同時間點ti(i=1,2,3)的快照Gti，某節(jié)點在Gti中的度值為Di，并設(shè)度值增量為X1=D2-D1，X2=D3-D2。利用Pearl提出的因果關(guān)系有向圖分析方法[72]，圖4給出了擇優(yōu)連接機制和優(yōu)點機制中變量之間的關(guān)系，可發(fā)現(xiàn)在兩種情況下度值增量X1均會影響t2時的節(jié)點度值D2。在擇優(yōu)連接機制中D2又會影響第2個時間間隔內(nèi)的度值增量X2，但是除了依靠D2將二者聯(lián)系起來，在X1和X2之間并無因果關(guān)系。而在優(yōu)點機制中，D2和X2之間沒有直接的關(guān)系，而X1和X2均被一個共同的原因Z影響，Z是節(jié)點的優(yōu)點或質(zhì)量，每個節(jié)點在其首次出現(xiàn)時都可根據(jù)特定的概率分布被賦予優(yōu)點值Z。

圖4 兩種機制中變量之間的關(guān)系[71]

從圖4可見，在擇優(yōu)連接機制中控制D2可以阻斷X1和X2之間唯一的路徑，因此將移除兩個變量之間的相關(guān)性。而在優(yōu)點機制中在控制D2之后X1和X2之間的路徑仍未受影響，二者之間的相關(guān)性仍然存在。因此控制變量D2后研究X1和X2之間的相關(guān)性將區(qū)分擇優(yōu)連接機制和優(yōu)點機制。一種方法是依靠線性回歸即

E[γ(X2)|X1,D2]=β0+β1X1+β2D2

(4)

在網(wǎng)絡(luò)演化中這兩種機制的權(quán)重并非一成不變，Lu等[47]對Epinions的研究發(fā)現(xiàn)，時間是這兩個影響因素的重要調(diào)節(jié)器。內(nèi)在的用戶特性對于短期內(nèi)獲得更多的入連接是一種比較強的驅(qū)動力，而擇優(yōu)連接雖然影響力較弱，但卻可以持續(xù)很長時間。

3 總結(jié)與展望

本文從多學科角度探討了在線社會網(wǎng)絡(luò)的形成機制最新的進展，尤其是趨同性和擇優(yōu)連接這兩方面的進展。在線社會網(wǎng)絡(luò)形成機制的研究具有重要的理論和應(yīng)用價值，通過對用戶建立網(wǎng)絡(luò)連接的機制的分析，可以揭示網(wǎng)絡(luò)演化的驅(qū)動力，進而構(gòu)建更符合實際情況的網(wǎng)絡(luò)模型，為網(wǎng)絡(luò)上的動力學研究奠定基礎(chǔ)。此外通過對網(wǎng)絡(luò)形成機制的研究，可以發(fā)現(xiàn)用戶的偏好性及其個性品位，從而預(yù)測網(wǎng)絡(luò)未來的發(fā)展。實際上現(xiàn)有的鏈路預(yù)測算法幾乎都基于網(wǎng)絡(luò)形成機制，如趨同性、擇優(yōu)連接、關(guān)系機制等[63]，深入理解這些機制有助于提出更好的鏈路預(yù)測算法。此外研究網(wǎng)絡(luò)的形成機制對社交網(wǎng)站本身也具有重要的現(xiàn)實意義。理解用戶在建立好友關(guān)系時的偏好性，可以構(gòu)建更好的好友推薦系統(tǒng)[64]，既能吸引新用戶加入其中，增長網(wǎng)站的人氣，又能留住當前用戶，增加用戶的活躍度，從而提高了網(wǎng)站的吸引力和用戶的粘附力。

雖然目前在線社會網(wǎng)絡(luò)的形成機制方面已取得了一定的進展[73]，但對這些機制仍缺乏深入理解，一方面是因為包含用戶屬性的網(wǎng)絡(luò)演化數(shù)據(jù)難以獲取，另一方面是缺乏適當?shù)难芯抗ぞ呖梢酝茰y每條連接的形成原因或動機。對于利用這些機制進行鏈路預(yù)測或構(gòu)建推薦系統(tǒng)，目前的研究也仍缺乏將各種影響因素有效融合在一起的方法。此外，雖然不同的機制都可驅(qū)動在線社會網(wǎng)絡(luò)中好友關(guān)系的形成，但它們的權(quán)重或所發(fā)揮的作用的強弱在網(wǎng)絡(luò)不同的演化階段可能會存在差異[74]。從更微觀的角度講即使對同一用戶而言，她/他從加入在線社會網(wǎng)絡(luò)開始在不同階段建立網(wǎng)絡(luò)連接的機制也可能存在差異，在有些階段趨同性占主導(dǎo)地位而在另一些階段擇優(yōu)連接或關(guān)系機制擔當主要角色，現(xiàn)有研究不論是理論研究還是應(yīng)用研究都很少考慮到這種時變性。

未來的工作有幾個潛在的研究方向。首先在線社會網(wǎng)絡(luò)的演化中各種機制往往交織在一起，因此有必要提出一套理論或方法來有效識別每個連接的形成動因。其次在同一網(wǎng)絡(luò)中不同屬性的趨同性強弱存在差異，在不同網(wǎng)絡(luò)中同一屬性的趨同性也不盡相同，如何將各種屬性融合起來構(gòu)建網(wǎng)絡(luò)模型或進行鏈路預(yù)測是值得研究的問題。最后，為了刻畫不同機制在網(wǎng)絡(luò)演化不同階段所發(fā)揮作用的不同，必須構(gòu)建自適應(yīng)的鏈路預(yù)測或推薦算法，這也是今后一個重要的研究方向。

[1]胡海波, 王科, 徐玲, 等. 基于復(fù)雜網(wǎng)絡(luò)理論的在線社會網(wǎng)絡(luò)分析[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學, 2008, 5(2): 1-14.

HuHaibo,WangKe,XuLing,etal.Analysisofonlinesocialnetworksbasedoncomplexnetworktheory[J].ComplexSystemsandComplexityScience, 2008, 5(2): 1-14.

[2]HolmeP,EdlingCR,LiljerosF.StructureandtimeevolutionofanInternetdatingcommunity[J].SocialNetworks, 2004, 26: 155-174.

[3]ViswanathB,MisloveA,ChaM,etal.OntheevolutionofuserinteractioninFacebook[C]//Proceedingsofthe2ndACMWorkshoponOnlineSocialNetworks.NewYork:ACMPress, 2009: 37-42.

[4]KumarR,NovakJ,TomkinsA.Structureandevolutionofonlinesocialnetworks[C]//Proceedingsofthe12thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACMPress, 2006: 611-617.

[5]HuH,WangX.Evolutionofalargeonlinesocialnetwork[J].PhysicsLettersA, 2009, 373: 1105-1110.

[6]RiveraMT,SoderstromSB,UzziB.Dynamicsofdyadsinsocialnetworks:assortative,relational,andproximitymechanisms[J].AnnuRevSociol, 2010, 36(1): 91-115.

[7]McPhersonM,Smith-LovinL,CookJM.Birdsofafeather:homophilyinsocialnetworks[J].AnnuRevSociol, 2001, 27: 415-444.

[8]CurrariniS,JacksonMO,PinP.aneconomicmodeloffriendship:homophily,minoritiesandsegregation[J].Econometrica, 2009, 77: 1003-1045.

[9]BurgessS,SandersonE,Umaa-AponteM.Schoolties:ananalysisofhomophilyinanadolescentfriendshipnetwork[DB/OL]. [2014-04-01].www.bris.ac.uk/cmpo/publications/papers/2011/wp267.pdf.

[10]LeskovecJ,HorvitzE.Planetary-scaleviewsonalargeinstant-messagingnetwork[C]//Proceedingsofthe17thInternationalConferenceonWorldWideWeb.NewYork:ACMPress, 2008: 915-924.

[11]SkopekJ,SchulzF,BlossfeldHP.Whocontactswhom?educationalhomophilyinonlinemateselection[J].EurSociolRev, 2011, 27(2): 180-195.

[12]FioreAT,DonathJS.Homophilyinonlinedating:whendoyoulikesomeonelikeyourself[C]//CHI’05ExtendedAbstractsonHumanFactorsinComputingSystems.NewYork:ACMPress, 2005: 1371-1374.

[13]HitschGJ,HortasuA,ArielyD.Whatmakesyouclick?-matepreferencesinonlinedating[J].QuantitativeMarketingandEconomics, 2010, 8(4): 393-427.

[14]BussDM.Sexdifferencesinhumanmatepreferences:evolutionaryhypothesestestedin37cultures[J].BehavioralandBrainSciences, 1989, 12: 1-49.

[15]BussDM.TheEvolutionofDesire:StrategiesofHumanMating[M].NewYork:BasicBooks, 1995.

[16]EastwickPW,FinkelEJ.Sexdifferencesinmatepreferencesrevisited:dopeopleknowwhattheyinitiallydesireinaromanticpartner?[J].JournalofPersonalityandSocialPsychology, 2008, 94(2): 245-264.

[17]FismanR,IyengarSS,KamenicaE,etal.Genderdifferencesinmateselection:evidencefromaspeeddatingexperiment[J].QuarterlyJournalofEconomics, 2006, 2: 673-697.

[18]EaglyAH,WoodW.Theoriginsofsexdifferencesinhumanbehavior[J].AmericanPsychologist, 1999, 54(6): 408-423.

[19]LauwH,ShaferJC,AgrawalR,etal.Homophilyinthedigitalworld:aliveJournalcasestudy[J].IEEEInternetComputing, 2010, 14(2): 15-23.

[20]MazurE,RichardsL.Adolescents’andemergingadults’socialnetworkingonline:homophilyordiversity[J].JournalofAppliedDevelopmentalPsychology, 2011, 32: 180-188.

[21]ThelwallM.HomophilyinMySpace[J].JournaloftheAmericanSocietyforInformationScience&Technology, 2009, 60(2): 219-231.

[22]MayerA.Onlinesocialnetworksineconomics[J].DecisionSupportSystems, 2009, 47: 169-184.

[23]MisloveA,ViswanathB,GummadiKP,etal.Youarewhoyouknow:inferringuserprofilesinonlinesocialnetworks[C]//ProceedingsoftheThirdACMInternationalConferenceonWebSearchandDataMining.NewYork:ACMPress, 2010: 251-260.

[24]WimmerA,LewisK.Beyondandbelowracialhomophily:ERGmodelsofafriendshipnetworkdocumentedonFacebook[J].AmericanJournalofSociology, 2010, 116(2): 583-642.

[25]AielloLM,BarratA,CattutoC,etal.LinkcreationandprofilealignmentintheaNobiisocialnetwork[C]//Proceedingsofthe2010IEEESecondInternationalConferenceonSocialComputing.Washington,DC:IEEEComputerSociety, 2010: 249-256.

[26]AielloLM,BarratA,CattutoC,etal.Linkcreationandinformationspreadingoversocialandcommunicationtiesinaninterest-basedonlinesocialnetwork[J].EPJDataScience, 2012, 1: 12.

[27]AielloLM,BarratA,SchifanellaR,etal.Friendshippredictionandhomophilyinsocialmedia[J].ACMTransWeb, 2012, 6(2): 373-382.

[28]KangJH,LermanK.Usingliststomeasurehomophilyontwitter[C]//WorkshopsattheTwenty-SixthAAAIConferenceonArtificialIntelligence. 2012: 26-32.

[29]BisginH,AgarwalN,XuX.Astudyofhomophilyonsocialmedia[J].WorldWideWeb, 2012, 15: 213-232.

[30]BollenJ,GonalvesB,RuanG,etal.Happinessisassortativeinonlinesocialnetworks[J].ArtificialLife, 2011, 17(3): 237-251.

[31]DiPreteTA,EirichGM.Cumulativeadvantageasamechanismforinequality:areviewoftheoreticalandempiricaldevelopments[J].AnnuRevSociol, 2006, 32(1): 271-297.

[32]AbbasiA,HossainL,LeydesdorffL.Betweennesscentralityasadriverofpreferentialattachmentintheevolutionofresearchcollaborationnetworks[J].JournalofInformetrics, 2012, 6(3): 403-412.

[33]Hébert-DufresneL,AllardA,MarceauV,etal.Structuralpreferentialattachment:stochasticprocessforthegrowthofscale-free,modular,andself-similarsystems[J].PhysRevE, 2012, 85(2): 026108.

[34]GrabowiczPA,RamascoJJ,EguiluzVM.Dynamicsinonlinesocialnetworks[DB/OL]. [2014-04-01].http://arxiv.org/abs/1210.0808.

[35]LeskovecJ,BackstromL,KumarR,etal.Microscopicevolutionofsocialnetworks[C]//Proceedingsofthe14thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACMPress, 2008: 462-470.

[36]LangJ,WuSF.Anti-preferentialattachment:ifIfollowyou,willyoufollowme?[C] //IEEEThirdInternationalConferenceonPrivacy,Security,RiskandTrust(PASSAT)andIEEEThirdInternationalConferenceonSocialComputing.Washington,DC:IEEEComputerSociety, 2011: 339-346.

[37]MisloveA,KoppulaHS,GummadiKP,etal.Growthoftheflickrsocialnetwork[C]//ProceedingsoftheFirstWorkshoponOnlineSocialNetworks.NewYork:ACMPress, 2008: 25-30.

[38]ZhaoJ,LuiJCS,TowsleyD,etal.Empiricalanalysisoftheevolutionoffollowernetwork:acasestudyonDouban[C]//IEEEConferenceonComputerCommunicationsWorkshops(INFOCOMWKSHPS).Washington,DC:IEEEComputerSociety, 2011: 924-929.

[39]GargS,GuptaT,CarlssonN,etal.Evolutionofanonlinesocialaggregationnetwork:anempiricalstudy[C]//Proceedingsofthe9thACMSIGCOMMConferenceonInternetMeasurementConference.NewYork:ACMPress, 2009: 315-321.

[40]SzellM,ThurnerS.Measuringsocialdynamicsinamassivemultiplayeronlinegame[J].SocialNetworks, 2010, 32(4): 313-329.

[41]HuH,WangX.Howpeoplemakefriendsinsocialnetworkingsites-amicroscopicperspective[J].PhysicaA, 2012, 391: 1877-1886.

[42]RochaLEC,LiljerosF,HolmeP.Informationdynamicsshapethesexualnetworksofinternet-mediatedprostitution[J].ProcNatlAcadSciUSA, 2010, 107(13): 5706-5711.

[43]KunegisJ,BlattnerM,MoserC.Preferentialattachmentinonlinenetworks:measurementandexplanations[DB/OL]. [2014-04-01].http://arxiv.org/abs/1303.6271.

[44]ZhaoX,SalaA,WilsonC,etal.Multi-scaledynamicsinamassiveonlinesocialnetwork[C]//Proceedingsofthe2012ACMConferenceonInternetMeasurement.NewYork:ACMPress, 2012: 171-184.

[45]LiM,GaoL,FanY,etal.Emergenceofglobalpreferentialattachmentfromlocalinteraction[J].NewJournalofPhysics, 2010, 12(4): 043029.

[46]UtzS.ShowmeyourfriendsandIwilltellyouwhattypeofpersonyouare:howone’sprofile,numberoffriends,andtypeoffriendsinfluenceimpressionformationonsocialnetworksites[J].JournalofComputer-MediatedCommunication, 2010, 15 (2): 314-335.

[47]LuY,JerathK,SinghPV.TheEmergenceofopinionleadersinanetworkedonlinecommunity:adyadicmodelwithtimedynamicsandaheuristicforfastestimation[J].ManagementScience, 2013, 59(8): 1783-1799.

[48]KimJY,JoHH.Asignallingexplanationforpreferentialattachmentintheevolutionofsocialnetworks[J].JournalofEvolutionaryEconomics, 2010, 20: 375-393.

[49]AllamanisM,ScellatoS,MascoloC.Evolutionofalocation-basedonlinesocialnetwork:analysisandmodels[C]//Proceedingsofthe2012ACMConferenceonInternetMeasurement.NewYork:ACMPress, 2012: 145-158.

[50]KlimekP,ThurnerS.Triadicclosuredynamicsdrivesscalinglawsinsocialmultiplexnetworks[J].NewJournalofPhysics, 2013, 15: 063008.

[51]ScellatoS,NoulasA,MascoloC.Exploitingplacefeaturesinlinkpredictiononlocation-basedsocialnetworks[C]//Proceedingsofthe17thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACMPress, 2011: 1046-1054.

[52]ChoE,MyersSA,LeskovecJ.Friendshipandmobility:usermovementinlocation-basedsocialnetworks[C]//Proceedingsofthe17thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACMPress, 2011: 1082-1090.

[53]ScellatoS,NoulasA,LambiotteR,etal.Socio-spatialpropertiesofonlinelocation-basedsocialnetworks[C]//ProceedingsoftheFifthInternationalAAAIConferenceonWeblogsandSocialMedia.PaloAlto,CA:TheAAAIPress, 2011: 329-336.

[54]ScellatoS,MascoloC,MusolesiM,etal.Distancematters:geo-socialmetricsforonlinesocialnetworks[DB/OL][2014-02-20].http://www.usenix.org/legacy/events/wosn10/tech/slides/scellato.pdf.

[55]TakhteyevY,GruzdA,WellmanB.Geographyoftwitternetworks[J].SocialNetworks, 2012, 34: 73-81.

[56]LevyM,GoldenbergJ.Thegravitationallawofsocialinteraction[J].PhysicaA, 2014, 393: 418-426.

[57]KleinbergJM.Navigationinasmallworld[J].Nature, 2000, 406: 845.

[58]Liben-NowellD,NowakJ,KumarR,etal.Geographicroutinginsocialnetworks[J].ProcNatlAcadSciUSA, 2005, 102: 11623-11628.

[59]HuY,WangY,LiD,etal.Possibleoriginofefficientnavigationinsmallworlds[J].PhysRevLett, 2011, 106: 108701.

[60]ZipfGK.HumanBehaviorandthePrincipleofLeastEffort[M].Cambridge,MA:Addison-WesleyPress, 1949.

[61]VázquezA.Growingnetworkwithlocalrules:preferentialattachment,clusteringhierarchy,anddegreecorrelations[J].PhysRevE, 2003, 67(5): 056104.

[62]GhoshalG,ChiL,BarabásiAL.Uncoveringtheroleofelementaryprocessesinnetworkevolution[J].SciRep, 2013, 3: 2920.

[63] Lü L, Zhou T. Link prediction in complex networks: a survey[J]. Physica A, 2011, 390: 1150-1170.

[64] Lü L, Medo M, Yeung C H, et al. Recommender systems[J]. Physics Reports, 2012, 519: 1-49.

[65] Kim M, Leskovec J. Multiplicative attribute graph model of real-world networks[J]. Internet Mathematics, 2012, 8(1/2): 113-160.

[66] Krivitsky P N, Handcock M S, Raftery A E, et al. Representing degree distributions, clustering, and homophily in social networks with latent cluster random effects models[J]. Social Networks, 2009, 31(3): 204-213.

[67] Tarbush B, Teytelboym A. Homophily in online social networks[J]. Lecture Notes in Computer Science, 2012, 7695: 512-518.

[68] Traud A L, Mucha P J, Porter M A. Social structure of Facebook networks[J]. Physica A, 2012, 391: 4165-4180.

[69] Agarwal A, Rambow O, Bhardwaj N. Predicting interests of people on online social network[C]// Proceedings of the 2009 International Conference on Computational Science and Engineering-Volume 04. Washington, DC: IEEE Computer Society, 2009: 735-740.

[70] Steurer M, Trattner C. Predicting interactions in online social networks: an experiment in second life[DB/OL].[2014-02-20]. http://www.christophtrattner. info/pubs/msn 2013_CR.pdf.

[71] de Blasio B F, Seierstad T G, Aalen O O. Frailty effects in networks: comparison and identification of individual heterogeneity versus preferential attachment in evolving networks[J]. J R Stat Soc Ser C Appl Stat, 2011, 60: 239-259.

[72] Pearl J. Causality: Models, Reasoning and Inference[M]. New York: Cambridge University Press, 2009.

[73] Gallos L K, Rybski D, Liljeros F, et al. How people interact in evolving online affiliation networks[J]. Phys Rev X, 2012, 2(3): 031014.

[74] Wang Z Z, Zhu J J H. Homophily versus preferential attachment: evolutionary mechanisms of scientific collaboration networks[J]. Int J Mod Phys C, 2014, 25: 1440014.

(責任編輯 李進)

The Underlying Mechanisms Driving the Formation of Online Social Networks—Interdisciplinary Perspective

WEI Jianjiong， HU Haibo

(Department of Management Science & Engineering， East China University of Science & Technology， Shanghai 200237， China)

This survey summarizes the mechanisms driving the formation and evolution of online social networks from the multidisciplinary perspective, with emphasis on homophily and preferential linking. The survey elaborates the advances made recently in the research of these mechanisms, reveals the reasons behind various mechanisms and the impact of these mechanisms on network evolution, points out the potential application of these mechanisms, and clarifies the common misunderstanding for the formation mechanisms of online social networks. Finally this survey summarizes the research significance, including theoretical and application value, and future research directions on the formation mechanisms of online social networks.

online social network; complex network; homophily; preferential linking; mechanism

1672-3813(2015)04-0014-11;

10.13306/j.1672-3813.2015.04.002

2014-04-08；

2014-06-20

國家自然科學基金(61104139，61473119)；中央高?；究蒲袠I(yè)務(wù)費專項資金(WN1524301)

衛(wèi)健炯(1992-)，男，江蘇無錫人，博士研究生，主要研究方向為信息系統(tǒng)。

胡海波(1980-)，男，山東萊西人，博士，副教授，主要研究方向為在線社會網(wǎng)絡(luò)。

N94

A