劉尹平，王篤會，任朝陽
?。暇┼]電大學 通信與信息工程學院，江蘇 南京 210003）
摘要：在線社交網(wǎng)絡是伴隨著互聯(lián)網(wǎng)技術發(fā)展產(chǎn)生的，它屬于眾多復雜網(wǎng)絡中的一種。近年來，對于在線社交網(wǎng)絡的研究不斷深入，研究方向可以細分為網(wǎng)絡拓撲特征的分析、虛擬社區(qū)劃分算法的研究、傳播動力學研究、網(wǎng)絡采樣與重構、網(wǎng)絡拓撲識別等。大數(shù)據(jù)研究的興起使得在線社交網(wǎng)絡的研究更加受到人們的關注。當前，人們的日常生活幾乎離不開在線社交網(wǎng)絡，也因此每天都會有大量的用戶數(shù)據(jù)產(chǎn)生，分析、利用這些數(shù)據(jù)可以幫助人們了解自己并創(chuàng)造更多的價值。
關鍵詞：在線社交網(wǎng)絡；拓撲特征；虛擬社區(qū)劃分算法；采樣;重構；大數(shù)據(jù)
0引言
BOCCALETTI S等人［1］2006年發(fā)表的文章中，從復雜網(wǎng)絡結構特征、動力學兩個角度對復雜網(wǎng)絡進行了理論研究及具體應用分析。在國內(nèi)，方錦清等人將復雜網(wǎng)絡的相關研究定義為一門新的交叉科學——網(wǎng)絡科學［2］，其涉及圖論、統(tǒng)計物理學、現(xiàn)代控制理論、非線性科學等諸多領域的研究理論。
社交網(wǎng)絡是一種常見的復雜網(wǎng)絡，是指由許多節(jié)點構成的一種社會結構，可以抽象為由多個節(jié)點及節(jié)點之間的鏈路構成的圖，它是伴隨著人類的誕生而產(chǎn)生的，這里的節(jié)點可以是個人也可以是組織，節(jié)點之間的鏈路對應于各種社會關系，比如朋友關系。
在線社交網(wǎng)絡是互聯(lián)網(wǎng)與傳統(tǒng)社交網(wǎng)絡的結合，是一種在信息網(wǎng)絡上由社會個體集合及個體之間的連接關系構成的社會性結構，它的產(chǎn)生與計算機技術的飛速發(fā)展息息相關。這種社會性結構也可以抽象為由節(jié)點和鏈路構成的圖。節(jié)點可以是個人或者組織，也可以是網(wǎng)絡ID等虛擬個體，鏈路則代表各種社會關系，或者收發(fā)消息等多種動作行為［3］。
復雜網(wǎng)絡、社交網(wǎng)絡、在線社交網(wǎng)絡三者的關系可以理解為，社交網(wǎng)絡為復雜網(wǎng)絡的一種，因此具有許多復雜網(wǎng)絡的特征，而在線社交網(wǎng)絡可以理解為一種特殊的社交網(wǎng)絡。因此，在線社交網(wǎng)絡也具有復雜性，其復雜性主要表現(xiàn)在以下三個方面：（1）節(jié)點的復雜性，網(wǎng)絡中每一個節(jié)點都具有不同的屬性、特征，同一個節(jié)點還可能具有復雜的時間演化行為。（2）結構復雜性，具體來說，就是網(wǎng)絡節(jié)點之間關系混亂，連接交錯復雜，且隨時可能發(fā)生動態(tài)變化。比如，你會在不斷改變的生活環(huán)境中不斷地結交一些新朋友，同時也可能失去一些朋友。（3）結構與節(jié)點之間相互影響，比如，朋友圈的組成結構影響你的言行舉止，而你結交新的朋友就會改變你朋友圈的結構。圖1描述了社交網(wǎng)絡的生長過程。
近年來，對于在線社交網(wǎng)絡的研究不斷深入，研究方向可以細分為網(wǎng)絡拓撲特征的分析、虛擬社區(qū)劃分算法的研究、傳播動力學研究、網(wǎng)絡采樣與重構、網(wǎng)絡拓撲識別等。
1在線社交網(wǎng)絡的拓撲特性分析
在線社交網(wǎng)絡可以是無向網(wǎng)絡也可以是有向網(wǎng)絡，MSN、QQ、微信等在線實時通信平臺需要雙方認證才可以建立朋友關系，基于這種方式形成的在線社交網(wǎng)絡結構中鏈路是無向的，而通過Twitter、微博等可以建立單向的關系，比如在新浪微博中，你可以關注自己喜歡的明星但明星并不一定會關注你，這樣就會形成有向在線社交網(wǎng)絡。
1.1無標度特性
在無向網(wǎng)絡中節(jié)點的度指網(wǎng)絡中與該節(jié)點直接相連的邊的數(shù)目，度分布P（k）定義為一個隨機選擇的節(jié)點度為k的概率，也就是網(wǎng)絡中度為k的節(jié)點數(shù)目與網(wǎng)絡節(jié)點總數(shù)目的比值。
無標度的概念是BARABSI A L和ALBERTT R［4］提出的。經(jīng)研究發(fā)現(xiàn)，現(xiàn)實生活中的許多復雜網(wǎng)絡的節(jié)點度分布函數(shù)服從冪律分布，其表現(xiàn)為，大部分的節(jié)點擁有的鄰居節(jié)點數(shù)很少，只有少部分的節(jié)點擁有大量的鄰居節(jié)點。由于冪律分布函數(shù)具有無標度性質(zhì)，因此又稱這種特征為“無標度”特性。在線社交網(wǎng)絡作為復雜網(wǎng)絡中的一種，也具有無標度特性。
1.2小世界特性
在無權網(wǎng)絡中，從一個節(jié)點到另一個節(jié)點的路徑需要經(jīng)過的邊數(shù)稱為兩節(jié)點間的距離。當網(wǎng)絡中兩節(jié)點之間存在不止一條路徑時，其中距離最短的一條稱為連接兩節(jié)點的最短路徑，此距離即為最短路徑長度。N個節(jié)點構成的網(wǎng)絡中任意兩節(jié)點間距離的均值定義為整個網(wǎng)絡的平均路徑長度。
“小世界”概念由社會心理學家MILGRAM S提出，來自于其曾進行的一次“郵件傳播”的實驗，也被稱為“六度分割”理論。WATTS D J和STROGATZ S H 1998年第一次提出了小世界模型［5］。在線社交網(wǎng)絡擁有大量的節(jié)點和鏈路，網(wǎng)絡拓撲十分復雜，但令人驚訝的是，任意兩節(jié)點的最短路徑和網(wǎng)絡平均路徑都非常小，這種現(xiàn)象被形象地稱為“小世界”特征。研究表明，2010年人人網(wǎng)的用戶之間的平均距離為5.38［6］，而2011年全球Facebook上兩個用戶之間的平均距離僅為4.74。然而，對于網(wǎng)絡“小世界”特性的研究均基于無權網(wǎng)絡，并沒有考慮網(wǎng)絡中節(jié)點連接的強弱不同。
真實的在線社交網(wǎng)絡的特性不僅局限于無標度特性與小世界特性，有些在線社交網(wǎng)絡還具有聚類特性、社區(qū)結構特性等。因此，建立真實社交網(wǎng)絡的模型仍存在挑戰(zhàn)。
2在線社交網(wǎng)絡虛擬社區(qū)劃分
在線社交網(wǎng)絡由若干“群”或“簇”構成。這些群或簇的內(nèi)部節(jié)點連接緊密，而群或簇間的連接則相對比較稀疏。也就是說，在線社交網(wǎng)絡與諸多復雜網(wǎng)絡一樣，具有“社區(qū)結構”的特征［7］。
目前，對于社區(qū)結構的定義有許多不同的方法，比如：如果圖G內(nèi)所有節(jié)點間連接的度的總和大于其與其他部分圖相連的度的總和，則圖G為一個社區(qū)結構［1］。不同的定義方法對應著不同的虛擬社區(qū)劃分算法，具體來說，虛擬社區(qū)劃分算法有兩類，一類是靜態(tài)虛擬社區(qū)劃分算法，另一類是動態(tài)虛擬社區(qū)劃分算法。
經(jīng)典的靜態(tài)虛擬社區(qū)劃分算法包括Kmeans算法、分裂算法、凝聚算法、譜分析算法等［8］。其中，Kmeans算法是最知名的聚類算法，該算法給出一組歐幾里得節(jié)點并根據(jù)節(jié)點數(shù)目給出一個正整數(shù)k，將數(shù)據(jù)集劃分為k個不相交的子集。計算機根據(jù)k值隨機選擇k個點作為初始中心點，計算所有節(jié)點到k個中心點的平方歐式距離并將節(jié)點歸于距離最短的那個集群。重新計算k個集群的中心點并進行迭代，使得所有點到中心點的平方歐式距離之和最短，同時不同集群中心點的距離最長。這種算法可以實現(xiàn)較好的劃分效果，但k值需要人為估計。
對于動態(tài)虛擬社區(qū)的劃分，當前的一個普遍方法是將連續(xù)時間分割成一些離散的時間步，分別抽取社區(qū)結構，然后引入演化特征來解釋隨時間的變化這些劃分之間的差異，從而得到網(wǎng)絡和其中社區(qū)的發(fā)展趨勢。
在線社交網(wǎng)絡的虛擬社區(qū)劃分可以應用于廣告的精準投放，將相似的人群劃分在同一社區(qū)，針對不同社區(qū)投放不同的廣告，以減少成本增加商業(yè)利潤。此外，虛擬社區(qū)劃分也可用于在線社交網(wǎng)絡的推薦系統(tǒng)，同一社區(qū)的節(jié)點屬性更具有相似性，因此也更有可能成為朋友。
3在線社交網(wǎng)絡上的傳播動力學
復雜網(wǎng)絡的動力學定義為，網(wǎng)絡在“外部刺激”的推動下，或者“內(nèi)部消息”的觸發(fā)下，節(jié)點自身信息狀態(tài)改變或者節(jié)點間連接關系發(fā)生變化，從而導致整個網(wǎng)絡發(fā)生明顯的或者不明顯的“質(zhì)變”，這種改變可以是在某種規(guī)則約束下執(zhí)行的，也可能是隨機的。
傳播是一種常見的網(wǎng)絡動力學行為［9］。目前，關于在線社交網(wǎng)絡上傳播動力學研究的文章有許多，比如對于微博中的謠言傳播的研究。在線社交網(wǎng)絡上傳播的不僅只有謠言，也可以是口碑、情緒等。研究傳播動力學的前提是對在線網(wǎng)絡進行建模，基于代理的建模是其中一種常見的方法，即利用現(xiàn)有的計算機技術建立基于代理的網(wǎng)絡模型，該模型由許多自治的、相互交互的“代理”組成。代理具有自身的行為，也可與其他代理進行交互，這種交互會影響代理自身的行為。根據(jù)模型應用環(huán)境的不同，模型中的代理可以代表個人、家庭、公司甚至是國家。基于代理的建模采用“自底向上”的建模思想，通過對一個個代理的建模，就可以將不同代理的屬性和行為的多樣性從整個系統(tǒng)的行為中表現(xiàn)出來。
研究在線社交網(wǎng)絡上的傳播動力學有著重要的實際意義，例如，研究謠言在在線社交網(wǎng)絡中的傳播過程、傳播規(guī)律可以為政府及有關部門的征兆預警、判斷分析及公共宣傳工作提供保障。因此，研究不同類型的信息在在線社交網(wǎng)絡中的傳播過程，揭示信息傳播的一般規(guī)律與特性，提出科學有效的控制策略，是傳播研究領域的重要課題。
4在線社交網(wǎng)絡采樣與重構
參考文獻［10］中指出，網(wǎng)絡采樣與網(wǎng)絡重構與網(wǎng)絡構建的發(fā)展趨勢密切相關。一方面，由于受到現(xiàn)有技術的限制，對于許多網(wǎng)絡只能通過采樣的方法獲得數(shù)據(jù)；另一方面，即使能夠獲得完整的數(shù)據(jù)，有些網(wǎng)絡問題的研究也需要對網(wǎng)絡進行采樣。例如，研究在線社交網(wǎng)絡上的傳播動力學問題時，一般只在部分子網(wǎng)絡進行研究。此外，在處理大規(guī)模數(shù)據(jù)可視化的問題時也需要有效的采樣。
目前被廣泛應用的采樣算法有廣度優(yōu)先采樣、Frontier采樣、Forest Fire采樣等。每種采樣算法都有其優(yōu)缺點，以FF(Forest Fire)采樣算法為例，F(xiàn)F采樣算法基于隨機游走思想，它首先隨機地選取一個節(jié)點作為森林火災的發(fā)源地，然后選取與該節(jié)點的鄰居節(jié)點作為下一步有可能被燒到的樹木，每一個節(jié)點（樹木）被燒到的概率為P，P的大小決定了抽樣效果的好壞，文獻［11］指出P=0.8時抽樣的效果最好。FF算法采集的子網(wǎng)雖然連通性較好，且具有小世界特性，但由于更傾向于獲取度值較大的節(jié)點，因此樣本節(jié)點之間的連接將逐漸具有超線性關系，所以無法實現(xiàn)對原始網(wǎng)絡的真實采樣。
與網(wǎng)絡采樣相對應的一個問題是網(wǎng)絡重構(Network Reconstruction)，即能否以及如何從部分網(wǎng)絡數(shù)據(jù)推測得到整個網(wǎng)絡的數(shù)據(jù)。這一問題也被稱為網(wǎng)絡完整性(Network Completion)、網(wǎng)絡推斷(Network inference)或逆向工程網(wǎng)絡(Reverse Engineering Network)。
網(wǎng)絡重構的問題最早由GUIMER R和SALESPARDO M提出［12］，他們基于隨機分塊模型來進行網(wǎng)絡重構，隨機分塊模型的基本思想是將節(jié)點分為相互獨立的組，兩個節(jié)點之間存在鏈路的概率只與節(jié)點所在的組有關，文獻［12］中指出，不僅可以預測兩個未連接的節(jié)點之間是否存在鏈路，同時也可以判斷網(wǎng)絡中存在的虛假邊。鏈路預測也是網(wǎng)絡重構相關的研究之一，鏈路預測的主要思想是利用節(jié)點之間屬性相似性或者網(wǎng)絡結構的相關性等來恢復丟失連邊［13］，例如基于共同鄰居指標的鏈路預測，即兩個節(jié)點擁有的共同鄰居越多，它們之間存在鏈路的可能性就越大。鏈路預測技術可用于在線社交網(wǎng)絡的推薦系統(tǒng)，兩個陌生人有很多的共同朋友或者擁有許多的共同愛好，那么他們能夠成為朋友的概率就很大。
5在線社交網(wǎng)絡拓撲識別
近年來，無論是對復雜網(wǎng)絡還是對具體的在線社交網(wǎng)絡的研究，大多是研究網(wǎng)絡拓撲結構在已知條件下的網(wǎng)絡動力學問題，或者是研究網(wǎng)絡結構的各種特征參數(shù)，如平均距離、度分布等對網(wǎng)絡動力學的影響［14］。然而實際的網(wǎng)絡存在各種不確定性的信息，網(wǎng)絡的節(jié)點數(shù)目、拓撲連接等往往只有部分已知，并且還可能不斷地變化。假設網(wǎng)絡動力學演化是可以測量獲取的，那么能否根據(jù)網(wǎng)絡動力學演化來估計網(wǎng)絡的拓撲結構，是一個極具挑戰(zhàn)性的問題。如果說在已知網(wǎng)絡拓撲結構條件下研究網(wǎng)絡動力學問題是正問題的話，那么對于網(wǎng)絡拓撲結構的識別則屬于反演問題（或者反問題）。顯然，反問題比正問題困難，而且一般來說反問題的解是不唯一的，解反問題是需要附加補充條件的。
對于網(wǎng)絡的拓撲結構識別問題，目前國內(nèi)已經(jīng)取得一些重要進展。陸君安等人提出基于自適應同步的網(wǎng)絡動力學參數(shù)和拓撲識別方法［15］，指出動力學信息對于拓撲識別并非是充分的，為了識別網(wǎng)絡拓撲結構，需要滿足經(jīng)內(nèi)連耦合動力學映射后的一簇函數(shù)組在同步流形上線性無關的條件。如果需要同時識別網(wǎng)絡拓撲結構和動力學參數(shù)，則需要滿足經(jīng)內(nèi)連耦合動力學和節(jié)點動力學映射后的兩簇函數(shù)組在同步流形上線性無關的條件。對于具體的在線社交網(wǎng)絡，可以考慮利用其上的傳播等動力學行為推測其具體結構，進一步研究動力學行為與網(wǎng)絡結構之間的相互影響。
6結論
在線社交網(wǎng)絡各方面的研究目前已經(jīng)取得了相當多的研究成果，同時也受到了越來越多人的關注與投入，在線社交網(wǎng)絡研究與大數(shù)據(jù)研究的結合是當前的一個研究熱點，未來將會有更好的發(fā)展與應用。
大數(shù)據(jù)是指無法在一定時間內(nèi)用常用軟件工具對其內(nèi)容進行抓取、管理和處理的數(shù)據(jù)集合［16］。2013年新浪公司全年財報中指出，截至2013年12月份，新浪微博注冊用戶數(shù)達2.81億，微博活躍用戶數(shù)達1.67億，每天產(chǎn)生約2億條微博數(shù)據(jù)。2012年3月美國政府發(fā)布《大數(shù)據(jù)研究和發(fā)展倡議》，時至今日，大數(shù)據(jù)顯然已成為一種競爭資源。在線社交網(wǎng)絡每天都有大量數(shù)據(jù)產(chǎn)生，如何利用這些數(shù)據(jù)，結合已有的在線社交網(wǎng)絡理論研究成果，分析人們的生活和行為，挖掘政治、社會、文化、商業(yè)、健康等領域的信息，以便于更好地服務于用戶并從中獲利，將具有廣闊發(fā)展前景。
參考文獻
?。?］ BOCCALETTI S, .LATORA V, MORENO Y, et al．Complex network:structure and dynamics ［J/OL］．Physics Reports,2006,424:17530.［20160320］.http://www.sciencedirect.com/science/article/pii/S037015730500462X.
［2］ 方錦清，汪小帆，鄭志剛，等．一門嶄新的交叉科學：網(wǎng)絡科學（上）［J］．物理學進展，2007，27（3）：239343．
?。?］ 方濱興，許進，李建華，等．在線社交網(wǎng)絡分析［M］．北京：電子工業(yè)出版社，2014．
?。?］ BARABáSI A L, ALBERT R. Emergence of scaling in random networks［J/OL］.Science ,1999,286(5439):50912.［20160320］.http://science.sciencemag.org/content/286/5439/509.
?。?］ WATTS D J, STROGATZ S H. Collective dynamics of smallworld networks［J/OL］. Nature, 1998,393(6684):440442. ［20160320］.http://apps.webofknowledge.com/full_record.do?product=UA&search_mode=GeneralSearch&qid=9&SID=N2CCOYPK3reQ14t9giD&page=1&doc=3.
?。?］ Jiang Jing，WILSON C，Wang Xiao，et al．Understanding latent interactions in online social networks ［J/OL］.ACM Transactions on the Web，2010,7(4):369382.［20160320］.http://apps.webofknowledge.com/full_record.do?product=UA&search_mode=GeneralSearch&qid=6&SID=N2CCOYPK3reQ14t9giD&page=1&doc=1.
?。?］ 鄭浩原，黃戰(zhàn)．復雜網(wǎng)絡社區(qū)挖掘———改進的層次聚類算法［J ］．微型機與應用，2011，30（16）：8588．
［8］ 顧宏博，奚杰杰，吳晶．基于關聯(lián)系數(shù)的社區(qū)劃分算法［J］．微型機與應用，2015，34（18）：1719．
?。?］ MORENO Y, NEKOVEE M, PACHECO A F. Dynamics of rumor spreading in complex networks［J/OL］. Physical Review E, 2004, 69(6 Pt 2):066130. ［20160320］.http://journals.aps.org/pre/abstract/10.1103/PhysRevE.69.066130.
［10］ 汪小帆．網(wǎng)絡科學發(fā)展研究［J］．學科發(fā)展報告，2013，36（4）：111119．
［11］ LESKOVEC J，F(xiàn)ALOUTSOS C．Sampling from large graphs［C］．The Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2006：2023.
［12］ GUIMERà R，SALESPARDO M．Missing and spurious interactions and reconstruction of complex network［C］．Proceeding of National Academy of Science of the United States of America，2009：2207322078.
?。?3］ 呂琳媛，周濤．鏈路預測［M］.北京：高等教育出版社，2013．