在線社會網絡的形成機制
——基于跨學科的視角

衛健炯，胡海波

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

在線社會網絡的形成機制
——基于跨學科的視角

衛健炯，胡海波

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

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

在線社會網絡；復雜網絡；趨同性；擇優連接；機制

0 引言

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

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

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

在在線社會網絡的演化領域，雖然很多工作揭示了網絡拓撲參量的演化規律，但卻很難解釋結構變化背后的內在機制。眾所周知用戶建立網絡連接的行為導致了網絡結構的變化，而僅針對網絡結構參數的研究框架往往不能很好地揭示網絡演化的個人層面的動因。因此要對在線社會網絡的演化有更深刻和全面的理解，構建更好的網絡模型、推薦系統和鏈路預測算法，必須要深入研究這些網絡形成的驅動力。

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

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

1 在線社會網絡的形成機制及原因

1.1 趨同性

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

趨同性導致個人的好友圈在人口統計學特征、行為特征和心理特質方面具有同質性，并約束了個人所能收到的信息的類型、他們的態度以及所經歷的人際互動，地理上的鄰近、家庭、組織機構和個人在社會網絡中位置的同構性均為趨同機制創造了條件。

1.1.1 測試方法

1.1.2 實證研究

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

圖1 不同年齡的用戶對的數量[10]

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

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

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

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

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

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

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

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

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

圖3 用戶之間的網絡距離與他們的相似性之間的關系[26]

1.2 擇優連接

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

1.2.1 測試方法

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

(1)

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

(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的用戶的數量。Π(k)通常有大的漲落，尤其在k較大時。為了減少噪聲階，可以研究累積函數(3)。

(3)

擇優連接現象可以發生在不同的情況下。在網絡增長過程中，當新用戶與老用戶之間建立連接，或者老用戶之間建立連接的時候，度值大的老用戶都有可能被擇優選擇。

1.2.2 實證研究

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

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

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

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

1.2.3 機制背后的原因

擇優連接是驅動網絡增長和演化的重要機制，但為什么會存在該種機制？傳統社會學對它的一種解釋是擁有社會資本的個體能利用這些資本獲得更多的社會資本。此外一些其他的結構化機制也能導致擇優連接現象，比如Li等[45]發現節點間局部的相互作用可導致全局性的擇優連接,如與網絡距離最近的節點建立連接。

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

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

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

1.3 關系機制

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

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

1.4 近鄰機制

我們也都有這樣的生活體驗，居住位置相近的人也更易形成好友關系，這就是近鄰機制，這種機制將社會網絡的形成放在了更寬廣的個體的社會和文化環境中。在現實生活中近鄰意味著個體有更多的機會遇見并相互作用，進而導致新的好友關系的形成和舊的好友關系的維持。近鄰機制之所以能夠發揮作用是因為熟悉度或曝光效應，我們暴露在某一刺激下越多也就越可能對其產生好感。我們經常看到一些特定的人，當彼此變得越來越熟悉，友誼也就越來越容易形成。盡管互聯網使人與人之間的交流跨越了空間的限制，使整個世界變得更加扁平，但近來大量的實證研究表明，對于在線社會網絡，近鄰機制在好友關系的形成中仍擔當重要角色，個人的好友圈在地理位置上具有相似性。在基于位置的在線社會網絡，如Gowalla[51-53]，BrightKite[52-54]，FourSquare[53-54]，以及Microsoft Messenger[10]，LiveJournal[54]，Twitter[54-55]和Facebook[56]中都發現了空間距離所起的作用。

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

2 應用及有關問題的澄清

2.1 應用

對各種機制的深入理解有助于構建更好的網絡模型并對網絡結構和用戶屬性進行預測。在復雜網絡領域已有大量的文獻探討了擇優連接和關系機制在網絡建模、鏈路預測和推薦系統中的應用[41,61-64]，限于篇幅本文不再討論。在本部分中我們將焦點放在趨同性機制的應用上。

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

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

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

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

在同一網絡中用戶不同屬性的趨同性強弱存在差異，對于不同的網絡同一屬性的趨同性也存在差異。Traud等[68]研究了美國100所大學的Facebook好友網絡的社會結構，考察了用戶的屬性如性別、年級、專業、畢業高中以及居住地在這些機構好友關系形成中擔當的角色。他們測試了不同的用戶特性在不同機構好友關系形成中的相對重要性，發現對于規模較大的機構中的社會網絡，共同的高中重要性較高，而共同專業的重要性隨著機構的不同而變化。對于幾乎所有的機構，所在年級相對于其他人口統計學特性趨同性更強。此外女生相對于男生更傾向于跟與自己居住地相同的人建立好友關系。

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

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

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

2.2 有關問題的澄清

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

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

圖4 兩種機制中變量之間的關系[71]

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

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

(4)

在網絡演化中這兩種機制的權重并非一成不變，Lu等[47]對Epinions的研究發現，時間是這兩個影響因素的重要調節器。內在的用戶特性對于短期內獲得更多的入連接是一種比較強的驅動力，而擇優連接雖然影響力較弱，但卻可以持續很長時間。

3 總結與展望

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

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

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

[1]胡海波, 王科, 徐玲, 等. 基于復雜網絡理論的在線社會網絡分析[J]. 復雜系統與復雜性科學, 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)；中央高校基本科研業務費專項資金(WN1524301)

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

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

N94

A