劉尹平，王篤會，任朝陽

　　（南京郵電大學 通信與信息工程學院，江蘇 南京 210003）

　　摘要：在線社交網絡是伴隨著互聯網技術發(fā)展產生的，它屬于眾多復雜網絡中的一種。近年來，對于在線社交網絡的研究不斷深入，研究方向可以細分為網絡拓撲特征的分析、虛擬社區(qū)劃分算法的研究、傳播動力學研究、網絡采樣與重構、網絡拓撲識別等。大數據研究的興起使得在線社交網絡的研究更加受到人們的關注。當前，人們的日常生活幾乎離不開在線社交網絡，也因此每天都會有大量的用戶數據產生，分析、利用這些數據可以幫助人們了解自己并創(chuàng)造更多的價值。

　　關鍵詞：在線社交網絡；拓撲特征；虛擬社區(qū)劃分算法；采樣;重構；大數據

0引言

　　BOCCALETTI S等人［1］2006年發(fā)表的文章中，從復雜網絡結構特征、動力學兩個角度對復雜網絡進行了理論研究及具體應用分析。在國內，方錦清等人將復雜網絡的相關研究定義為一門新的交叉科學——網絡科學［2］，其涉及圖論、統(tǒng)計物理學、現代控制理論、非線性科學等諸多領域的研究理論。

　　社交網絡是一種常見的復雜網絡，是指由許多節(jié)點構成的一種社會結構，可以抽象為由多個節(jié)點及節(jié)點之間的鏈路構成的圖，它是伴隨著人類的誕生而產生的，這里的節(jié)點可以是個人也可以是組織，節(jié)點之間的鏈路對應于各種社會關系，比如朋友關系。

　　在線社交網絡是互聯網與傳統(tǒng)社交網絡的結合，是一種在信息網絡上由社會個體集合及個體之間的連接關系構成的社會性結構，它的產生與計算機技術的飛速發(fā)展息息相關。這種社會性結構也可以抽象為由節(jié)點和鏈路構成的圖。節(jié)點可以是個人或者組織，也可以是網絡ID等虛擬個體，鏈路則代表各種社會關系，或者收發(fā)消息等多種動作行為［3］。

　　復雜網絡、社交網絡、在線社交網絡三者的關系可以理解為，社交網絡為復雜網絡的一種，因此具有許多復雜網絡的特征，而在線社交網絡可以理解為一種特殊的社交網絡。因此，在線社交網絡也具有復雜性，其復雜性主要表現在以下三個方面：（1）節(jié)點的復雜性，網絡中每一個節(jié)點都具有不同的屬性、特征，同一個節(jié)點還可能具有復雜的時間演化行為。（2）結構復雜性，具體來說，就是網絡節(jié)點之間關系混亂，連接交錯復雜，且隨時可能發(fā)生動態(tài)變化。比如，你會在不斷改變的生活環(huán)境中不斷地結交一些新朋友，同時也可能失去一些朋友。（3）結構與節(jié)點之間相互影響，比如，朋友圈的組成結構影響你的言行舉止，而你結交新的朋友就會改變你朋友圈的結構。圖1描述了社交網絡的生長過程。

　　近年來，對于在線社交網絡的研究不斷深入，研究方向可以細分為網絡拓撲特征的分析、虛擬社區(qū)劃分算法的研究、傳播動力學研究、網絡采樣與重構、網絡拓撲識別等。

1在線社交網絡的拓撲特性分析

　　在線社交網絡可以是無向網絡也可以是有向網絡，MSN、QQ、微信等在線實時通信平臺需要雙方認證才可以建立朋友關系，基于這種方式形成的在線社交網絡結構中鏈路是無向的，而通過Twitter、微博等可以建立單向的關系，比如在新浪微博中，你可以關注自己喜歡的明星但明星并不一定會關注你，這樣就會形成有向在線社交網絡。

　　1.1無標度特性

　　在無向網絡中節(jié)點的度指網絡中與該節(jié)點直接相連的邊的數目，度分布P（k）定義為一個隨機選擇的節(jié)點度為k的概率，也就是網絡中度為k的節(jié)點數目與網絡節(jié)點總數目的比值。

　　無標度的概念是BARABSI A L和ALBERTT R［4］提出的。經研究發(fā)現，現實生活中的許多復雜網絡的節(jié)點度分布函數服從冪律分布，其表現為，大部分的節(jié)點擁有的鄰居節(jié)點數很少，只有少部分的節(jié)點擁有大量的鄰居節(jié)點。由于冪律分布函數具有無標度性質，因此又稱這種特征為“無標度”特性。在線社交網絡作為復雜網絡中的一種，也具有無標度特性。

　　1.2小世界特性

　　在無權網絡中，從一個節(jié)點到另一個節(jié)點的路徑需要經過的邊數稱為兩節(jié)點間的距離。當網絡中兩節(jié)點之間存在不止一條路徑時，其中距離最短的一條稱為連接兩節(jié)點的最短路徑，此距離即為最短路徑長度。N個節(jié)點構成的網絡中任意兩節(jié)點間距離的均值定義為整個網絡的平均路徑長度。

　　“小世界”概念由社會心理學家MILGRAM S提出，來自于其曾進行的一次“郵件傳播”的實驗，也被稱為“六度分割”理論。WATTS D J和STROGATZ S H 1998年第一次提出了小世界模型［5］。在線社交網絡擁有大量的節(jié)點和鏈路，網絡拓撲十分復雜，但令人驚訝的是，任意兩節(jié)點的最短路徑和網絡平均路徑都非常小，這種現象被形象地稱為“小世界”特征。研究表明，2010年人人網的用戶之間的平均距離為5.38［6］，而2011年全球Facebook上兩個用戶之間的平均距離僅為4.74。然而，對于網絡“小世界”特性的研究均基于無權網絡，并沒有考慮網絡中節(jié)點連接的強弱不同。

　　真實的在線社交網絡的特性不僅局限于無標度特性與小世界特性，有些在線社交網絡還具有聚類特性、社區(qū)結構特性等。因此，建立真實社交網絡的模型仍存在挑戰(zhàn)。

2在線社交網絡虛擬社區(qū)劃分

　　在線社交網絡由若干“群”或“簇”構成。這些群或簇的內部節(jié)點連接緊密，而群或簇間的連接則相對比較稀疏。也就是說，在線社交網絡與諸多復雜網絡一樣，具有“社區(qū)結構”的特征［7］。

　　目前，對于社區(qū)結構的定義有許多不同的方法，比如：如果圖G內所有節(jié)點間連接的度的總和大于其與其他部分圖相連的度的總和，則圖G為一個社區(qū)結構［1］。不同的定義方法對應著不同的虛擬社區(qū)劃分算法，具體來說，虛擬社區(qū)劃分算法有兩類，一類是靜態(tài)虛擬社區(qū)劃分算法，另一類是動態(tài)虛擬社區(qū)劃分算法。

　　經典的靜態(tài)虛擬社區(qū)劃分算法包括Kmeans算法、分裂算法、凝聚算法、譜分析算法等［8］。其中，Kmeans算法是最知名的聚類算法，該算法給出一組歐幾里得節(jié)點并根據節(jié)點數目給出一個正整數k，將數據集劃分為k個不相交的子集。計算機根據k值隨機選擇k個點作為初始中心點，計算所有節(jié)點到k個中心點的平方歐式距離并將節(jié)點歸于距離最短的那個集群。重新計算k個集群的中心點并進行迭代，使得所有點到中心點的平方歐式距離之和最短，同時不同集群中心點的距離最長。這種算法可以實現較好的劃分效果，但k值需要人為估計。

　　對于動態(tài)虛擬社區(qū)的劃分，當前的一個普遍方法是將連續(xù)時間分割成一些離散的時間步，分別抽取社區(qū)結構，然后引入演化特征來解釋隨時間的變化這些劃分之間的差異，從而得到網絡和其中社區(qū)的發(fā)展趨勢。

　　在線社交網絡的虛擬社區(qū)劃分可以應用于廣告的精準投放，將相似的人群劃分在同一社區(qū)，針對不同社區(qū)投放不同的廣告，以減少成本增加商業(yè)利潤。此外，虛擬社區(qū)劃分也可用于在線社交網絡的推薦系統(tǒng)，同一社區(qū)的節(jié)點屬性更具有相似性，因此也更有可能成為朋友。

3在線社交網絡上的傳播動力學

　　復雜網絡的動力學定義為，網絡在“外部刺激”的推動下，或者“內部消息”的觸發(fā)下，節(jié)點自身信息狀態(tài)改變或者節(jié)點間連接關系發(fā)生變化，從而導致整個網絡發(fā)生明顯的或者不明顯的“質變”，這種改變可以是在某種規(guī)則約束下執(zhí)行的，也可能是隨機的。

　　傳播是一種常見的網絡動力學行為［9］。目前，關于在線社交網絡上傳播動力學研究的文章有許多，比如對于微博中的謠言傳播的研究。在線社交網絡上傳播的不僅只有謠言，也可以是口碑、情緒等。研究傳播動力學的前提是對在線網絡進行建模，基于代理的建模是其中一種常見的方法，即利用現有的計算機技術建立基于代理的網絡模型，該模型由許多自治的、相互交互的“代理”組成。代理具有自身的行為，也可與其他代理進行交互，這種交互會影響代理自身的行為。根據模型應用環(huán)境的不同，模型中的代理可以代表個人、家庭、公司甚至是國家。基于代理的建模采用“自底向上”的建模思想，通過對一個個代理的建模，就可以將不同代理的屬性和行為的多樣性從整個系統(tǒng)的行為中表現出來。

　　研究在線社交網絡上的傳播動力學有著重要的實際意義，例如，研究謠言在在線社交網絡中的傳播過程、傳播規(guī)律可以為政府及有關部門的征兆預警、判斷分析及公共宣傳工作提供保障。因此，研究不同類型的信息在在線社交網絡中的傳播過程，揭示信息傳播的一般規(guī)律與特性，提出科學有效的控制策略，是傳播研究領域的重要課題。

4在線社交網絡采樣與重構

　　參考文獻［10］中指出，網絡采樣與網絡重構與網絡構建的發(fā)展趨勢密切相關。一方面，由于受到現有技術的限制，對于許多網絡只能通過采樣的方法獲得數據；另一方面，即使能夠獲得完整的數據，有些網絡問題的研究也需要對網絡進行采樣。例如，研究在線社交網絡上的傳播動力學問題時，一般只在部分子網絡進行研究。此外，在處理大規(guī)模數據可視化的問題時也需要有效的采樣。

　　目前被廣泛應用的采樣算法有廣度優(yōu)先采樣、Frontier采樣、Forest Fire采樣等。每種采樣算法都有其優(yōu)缺點，以FF(Forest Fire)采樣算法為例，FF采樣算法基于隨機游走思想，它首先隨機地選取一個節(jié)點作為森林火災的發(fā)源地，然后選取與該節(jié)點的鄰居節(jié)點作為下一步有可能被燒到的樹木，每一個節(jié)點（樹木）被燒到的概率為P，P的大小決定了抽樣效果的好壞，文獻［11］指出P=0.8時抽樣的效果最好。FF算法采集的子網雖然連通性較好，且具有小世界特性，但由于更傾向于獲取度值較大的節(jié)點，因此樣本節(jié)點之間的連接將逐漸具有超線性關系，所以無法實現對原始網絡的真實采樣。

　　與網絡采樣相對應的一個問題是網絡重構(Network Reconstruction)，即能否以及如何從部分網絡數據推測得到整個網絡的數據。這一問題也被稱為網絡完整性(Network Completion)、網絡推斷(Network inference)或逆向工程網絡(Reverse Engineering Network)。

　　網絡重構的問題最早由GUIMER R和SALESPARDO M提出［12］，他們基于隨機分塊模型來進行網絡重構，隨機分塊模型的基本思想是將節(jié)點分為相互獨立的組，兩個節(jié)點之間存在鏈路的概率只與節(jié)點所在的組有關，文獻［12］中指出，不僅可以預測兩個未連接的節(jié)點之間是否存在鏈路，同時也可以判斷網絡中存在的虛假邊。鏈路預測也是網絡重構相關的研究之一，鏈路預測的主要思想是利用節(jié)點之間屬性相似性或者網絡結構的相關性等來恢復丟失連邊［13］，例如基于共同鄰居指標的鏈路預測，即兩個節(jié)點擁有的共同鄰居越多，它們之間存在鏈路的可能性就越大。鏈路預測技術可用于在線社交網絡的推薦系統(tǒng)，兩個陌生人有很多的共同朋友或者擁有許多的共同愛好，那么他們能夠成為朋友的概率就很大。

5在線社交網絡拓撲識別

　　近年來，無論是對復雜網絡還是對具體的在線社交網絡的研究，大多是研究網絡拓撲結構在已知條件下的網絡動力學問題，或者是研究網絡結構的各種特征參數，如平均距離、度分布等對網絡動力學的影響［14］。然而實際的網絡存在各種不確定性的信息，網絡的節(jié)點數目、拓撲連接等往往只有部分已知，并且還可能不斷地變化。假設網絡動力學演化是可以測量獲取的，那么能否根據網絡動力學演化來估計網絡的拓撲結構，是一個極具挑戰(zhàn)性的問題。如果說在已知網絡拓撲結構條件下研究網絡動力學問題是正問題的話，那么對于網絡拓撲結構的識別則屬于反演問題（或者反問題）。顯然，反問題比正問題困難，而且一般來說反問題的解是不唯一的，解反問題是需要附加補充條件的。

　　對于網絡的拓撲結構識別問題，目前國內已經取得一些重要進展。陸君安等人提出基于自適應同步的網絡動力學參數和拓撲識別方法［15］，指出動力學信息對于拓撲識別并非是充分的，為了識別網絡拓撲結構，需要滿足經內連耦合動力學映射后的一簇函數組在同步流形上線性無關的條件。如果需要同時識別網絡拓撲結構和動力學參數，則需要滿足經內連耦合動力學和節(jié)點動力學映射后的兩簇函數組在同步流形上線性無關的條件。對于具體的在線社交網絡，可以考慮利用其上的傳播等動力學行為推測其具體結構，進一步研究動力學行為與網絡結構之間的相互影響。

　　6結論

　　在線社交網絡各方面的研究目前已經取得了相當多的研究成果，同時也受到了越來越多人的關注與投入，在線社交網絡研究與大數據研究的結合是當前的一個研究熱點，未來將會有更好的發(fā)展與應用。

　　大數據是指無法在一定時間內用常用軟件工具對其內容進行抓取、管理和處理的數據集合［16］。2013年新浪公司全年財報中指出，截至2013年12月份，新浪微博注冊用戶數達2.81億，微博活躍用戶數達1.67億，每天產生約2億條微博數據。2012年3月美國政府發(fā)布《大數據研究和發(fā)展倡議》，時至今日，大數據顯然已成為一種競爭資源。在線社交網絡每天都有大量數據產生，如何利用這些數據，結合已有的在線社交網絡理論研究成果，分析人們的生活和行為，挖掘政治、社會、文化、商業(yè)、健康等領域的信息，以便于更好地服務于用戶并從中獲利，將具有廣闊發(fā)展前景。

參考文獻

　　［1］ BOCCALETTI S, .LATORA V, MORENO Y, et al．Complex network:structure and dynamics ［J/OL］．Physics Reports,2006,424:17530.［20160320］.http://www.sciencedirect.com/science/article/pii/S037015730500462X.

　　［2］ 方錦清，汪小帆，鄭志剛，等．一門嶄新的交叉科學：網絡科學（上）［J］．物理學進展，2007，27（3）：239343．

　　［3］ 方濱興，許進，李建華，等．在線社交網絡分析［M］．北京：電子工業(yè)出版社，2014．

　　［4］ BARABáSI A L, ALBERT R. Emergence of scaling in random networks［J/OL］.Science ,1999,286(5439):50912.［20160320］.http://science.sciencemag.org/content/286/5439/509.

　　［5］ WATTS D J, STROGATZ S H. Collective dynamics of smallworld networks［J/OL］. Nature, 1998,393(6684):440442. ［20160320］.http://apps.webofknowledge.com/full_record.do?product=UA&search_mode=GeneralSearch&qid=9&SID=N2CCOYPK3reQ14t9giD&page=1&doc=3.

　　［6］ 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):369382.［20160320］.http://apps.webofknowledge.com/full_record.do?product=UA&search_mode=GeneralSearch&qid=6&SID=N2CCOYPK3reQ14t9giD&page=1&doc=1.

　　［7］ 鄭浩原，黃戰(zhàn)．復雜網絡社區(qū)挖掘———改進的層次聚類算法［J ］．微型機與應用，2011，30（16）：8588．

　　［8］ 顧宏博，奚杰杰，吳晶．基于關聯系數的社區(qū)劃分算法［J］．微型機與應用，2015，34（18）：1719．

　　［9］ 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. ［20160320］.http://journals.aps.org/pre/abstract/10.1103/PhysRevE.69.066130.

　　［10］ 汪小帆．網絡科學發(fā)展研究［J］．學科發(fā)展報告，2013，36（4）：111119．

　　［11］ LESKOVEC J，FALOUTSOS C．Sampling from large graphs［C］．The Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2006：2023.

　　［12］ GUIMERà R，SALESPARDO M．Missing and spurious interactions and reconstruction of complex network［C］．Proceeding of National Academy of Science of the United States of America，2009：2207322078.

　　［13］ 呂琳媛，周濤．鏈路預測［M］.北京：高等教育出版社，2013．