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

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

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

1.1 趨同性

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

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

1.1.1 測試方法

1.1.2 實(shí)證研究

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

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

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

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

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

MySpace是Facebook之前最流行的社交網(wǎng)站，其突出特征是以音樂為一個(gè)重要的社交對(duì)象。Mazur和Richards[20]研究了129位年齡在16～19歲的美國青少年在MySpace上的個(gè)人資料，發(fā)現(xiàn)大部分的互動(dòng)發(fā)生在具有相同種族、年齡和州的用戶間，盡管也會(huì)出現(xiàn)跨種族的交流。青春期少年相對(duì)于即將成年的表現(xiàn)出更強(qiáng)的年齡上的趨同性。Thelwall[21]研究了MySpace中2 567位用戶以及在他們主頁上發(fā)表評(píng)論的好友的個(gè)人資料，發(fā)現(xiàn)沒有證據(jù)表明存在性別上的趨同性，這跟Microsoft Messenger中的情形一致，但在種族、宗教信仰、年齡、國家、婚姻狀態(tài)、對(duì)孩子的態(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è)、年級(jí)以及政治傾向(自由派、保守派)方面具有趨同性。Mislove等[23]研究了美國Rice大學(xué)和New Orleans地區(qū)的Facebook網(wǎng)絡(luò)，發(fā)現(xiàn)具有相同屬性(學(xué)院、系、年級(jí)、專業(yè)、中學(xué)、家鄉(xiāng)、政治觀點(diǎn))的用戶之間更易形成好友關(guān)系和緊密的社團(tuán)。Wimmer和Lewis[24]研究了一群大學(xué)生的Facebook個(gè)人主頁，發(fā)現(xiàn)好友關(guān)系中種族的同質(zhì)性不僅源于種族上的趨同性，也源于相同種族背景下不同人種之間的趨同性以及一些平衡機(jī)制，如傾向于接受好友邀請(qǐng)或成為好友的好友，這些都放大了趨同性導(dǎo)致的同質(zhì)效應(yīng)。他們也比較了種族趨同性與驅(qū)動(dòng)連接形成的其他機(jī)制在網(wǎng)絡(luò)演化中所發(fā)揮的作用，發(fā)現(xiàn)相對(duì)于種族趨同性，平衡機(jī)制、基于共同居住地的近鄰機(jī)制以及非種族方面的趨同性(家庭背景或來自特定的州)在影響好友關(guān)系形成方面所發(fā)揮的作用更強(qiáng)。

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

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

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

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

1.2 擇優(yōu)連接

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

1.2.1 測試方法

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

(1)

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

(2)

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

(3)

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

1.2.2 實(shí)證研究

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

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

在線社會(huì)網(wǎng)絡(luò)的擇優(yōu)性指數(shù)β并不是普適的，對(duì)于不同的網(wǎng)絡(luò)該參數(shù)存在較大的差異。Kunegis等[43]廣泛研究了7類共47個(gè)在線社會(huì)化系統(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ò)。

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

1.2.3 機(jī)制背后的原因

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

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

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

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

1.3 關(guān)系機(jī)制

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

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

1.4 近鄰機(jī)制

我們也都有這樣的生活體驗(yàn)，居住位置相近的人也更易形成好友關(guān)系，這就是近鄰機(jī)制，這種機(jī)制將社會(huì)網(wǎng)絡(luò)的形成放在了更寬廣的個(gè)體的社會(huì)和文化環(huán)境中。在現(xiàn)實(shí)生活中近鄰意味著個(gè)體有更多的機(jī)會(huì)遇見并相互作用，進(jìn)而導(dǎo)致新的好友關(guān)系的形成和舊的好友關(guān)系的維持。近鄰機(jī)制之所以能夠發(fā)揮作用是因?yàn)槭煜ざ然蚱毓庑?yīng)，我們暴露在某一刺激下越多也就越可能對(duì)其產(chǎn)生好感。我們經(jīng)常看到一些特定的人，當(dāng)彼此變得越來越熟悉，友誼也就越來越容易形成。盡管互聯(lián)網(wǎng)使人與人之間的交流跨越了空間的限制，使整個(gè)世界變得更加扁平，但近來大量的實(shí)證研究表明，對(duì)于在線社會(huì)網(wǎng)絡(luò)，近鄰機(jī)制在好友關(guān)系的形成中仍擔(dān)當(dāng)重要角色，個(gè)人的好友圈在地理位置上具有相似性。在基于位置的在線社會(huì)網(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)了空間距離所起的作用。

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

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

2.1 應(yīng)用

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(4)

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

3 總結(jié)與展望

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

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

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

[1]胡海波, 王科, 徐玲, 等. 基于復(fù)雜網(wǎng)絡(luò)理論的在線社會(huì)網(wǎng)絡(luò)分析[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 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.

(責(zé)任編輯 李進(jìn))

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

國家自然科學(xué)基金(61104139，61473119)；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金(WN1524301)

衛(wèi)健炯(1992-)，男，江蘇無錫人，博士研究生，主要研究方向?yàn)樾畔⑾到y(tǒng)。

胡海波(1980-)，男，山東萊西人，博士，副教授，主要研究方向?yàn)樵诰€社會(huì)網(wǎng)絡(luò)。

N94

A