在線社會網絡的研究綜述

摘 要 本文綜述了一些大規模在線社會網絡表現出來的無標度和小世界特性、高聚類系數及社團結構等性質，闡明了在線社會網絡結構的一些方法。

關鍵詞 在線社會網絡 拓撲結構

中圖分類號：TP393 文獻標識碼：A

一、引言

社會網絡是一群人或團體按某種關系連接在一起而構成的一個系統，如個人之間的朋友關系、同事之間的合作關系、家庭之間的聯姻關系和公司之間的商業關系等等。Milgram小世界實驗研究了人際關系在某種程度上反映出的小世界特征，得出了著名的六度分離推斷。隨著互聯網的快速發展，各種在線社會網絡如雨后春筍般涌現，最具代表性的平臺包括在線交友網絡（如facebook、MSN、微信）、社交網（如人人網）、BBS和論壇、博客、Wik等等。在線社會網絡是指人們通過以計算機為中介的交際活動，相互聯系和協作，并組成在線社區的網絡。在線社會網絡是圍繞用戶來組織的，用戶參與到一個網絡或社區中，發布文本、圖片等形式的信息，也可建立與他人的鏈接。

二、在線社會網絡中的拓撲結構

自從Watts和Strogatz教授發表“‘小世界’網絡的集體動力學”，揭示了復雜網絡的小世界特征，以及Barabasi和Albert建立無標度模型以來，人們對網絡拓撲結構模型進行了研究。本文所關注的社會網絡是各種基于因特網的在線網絡。哈佛大學的Adamic等人較早開始研究在線社會網絡，發現了在線社會網絡的小世界特性以及團結構。Liben，Nowell等人通過分析Live30umal的數據得出用戶之間的連接和地理位置的關系。Fu等把人人網看作無向網絡。整個網絡的度分布指數為2.12，其中一個連同子圖中節點平均路徑長度為3.48，直徑為9，聚類系數為0.20，人人網具有小世界特性。

互聯網的產生與發展在很大程度上改變了人與人的交流方式，在線社會網絡映射與擴展了現實社會網絡。胡海波在《在線社會網絡的結構、演化及動力學研究》研究了大型在線社會網絡Wealink的結構，該網站是國內最早的商務社交網站之一。并得出該網絡除了具有小世界特性、高聚類系數、社團性等與一般的現實社會網絡相似的共性。Wang等研究了基于P2P通信的Gnutella構建的在線社會網絡結構特性，若用戶B回答了用戶A的提問，則A到B可建立一條有向邊，整個網絡是有向無權圖。

三、在線社會網絡結構的發現方法

尋找大規模復雜網絡中的社團結構，較典型的算法有計算機科學中最有名的譜平分法和Kernighan-Lin算法，社會學中的GN算法和凝聚算法。近年來，研究者對如何在大規模的在線社會網絡中挖掘出社區結構進行了探索。燕飛、張銘等提出了綜合行動者興趣及網絡拓撲結構的社區發現方法，即使用興趣聚類的方法來發現用戶的興趣社區后，再考慮行動者的社會網絡結構特征，主要運用社會網絡權值計算、行動者間相關度計算和社區擴展，對興趣社區進行擴展。Clauset、Newman等提出了一種基于貪婪算法思想的社團結構檢測算法，CNM算法。該算法的計算采用堆數據結構計算和更新模塊度。關于社區結構的檢測算法其中有一種是標簽傳播算法（LPA），其基本思想是在算法開始時，給每個節點初始化一個不同的標簽值，給每個節點指定一個標簽，在算法進行中，節點將選擇與最多鄰居的所在社區改變標簽。因此隨著算法的進行，節點標簽也不斷變化，直到標簽不再改變，則算法結束。

（作者單位：河北大學管理學院）

參考文獻：

[1]Barabasi A-L，Albert R.Emergence of scaling in random networks[J].Science，1999.

[2]Adamic et al..A social network caught in the web[J]，First Monday，2003，8（6）：1-22.

[3]Liben-Nowell， D.， Novak， J.， Kumar， R.， Raghavan， P.， Tomkins， A. （2005） Geographic routing in social networks. Proceedings of National Academy of Sciences， 102 （33） 11，623-11，628.

[4]Fu F， Chen X， Liu L， et a.l Socialdilemmas in an online socialnetwork： the structure and evolution of cooperation[J]. Phys-ics LettersA， 2007， 371（1-2）： 58-64.

[5]胡海波，汪小帆.在線社會網絡的結構、演化及動力學研究[D].上海：上海交通大學，2010.

[6]F. Wang， Y. Moreno， Y. Sun， The structure of peer-to-peer social networks， Phys. Rev. E 73 （2006） 036123.

[7]燕飛，張銘，譚裕韋，唐建，鄧志鴻.綜合社會行動者興趣和網絡拓撲的社區發現方法[J].計算機研究與發展，2010（6）.