超級乾貨 :一文讀懂社交網絡分析(附應用、前沿、學習資源)

原標題：超級乾貨 ：一文讀懂社交網絡分析（附應用、前沿、學習資源）

本文主要闡述：

• 社交網絡的結構特性與演化機理

• 社交網絡群體行為形成與互動規律

• 社交網絡信息傳播與演化機理

• 社交網絡分析的應用

• 社交網絡前沿研究

• 學習資料

• 參考資料

01 前言

社交網絡在維基百科的定義是「由許多節點構成的一種社會結構。節點通常是指個人或組織，而社交網絡代表著各種社會關係。」在網際網路誕生前，社交網絡分析是社會學和人類學重要的研究分支。早期的社交網絡的主要指通過合作關係建立起來的職業網絡，如科研合作網絡、演員合作網絡等。

本文所指的社交網絡分析專指在線社交網絡分析（Online Social Network Analysis），該門科學的發展是隨著在線社交服務（Social Network Service, SNS）的出現而誕生。在線社交服務的種類大致可分為四種：即時消息類應用（QQ、微信、WhatsApp、Skype 等），在線社交類應用（QQ空間、人人網、Facebook、Google+ 等），微博類應用（新浪微博、騰訊微博、Twitter 等），共享空間類應用（論壇、博客、視頻分享、評價分享等）。

在線社交網絡（下文統稱社交網絡）有著迅捷性、蔓延性、平等性與自組織性等四大特點。正因為這些特性，其在網際網路出現的短短數十年內已經擁有數十億用戶並對現實社會的方方面面產生著影響。在2016年的美國總統大選中，當選總統川普就很好地利用了推特作為宣傳工具；而在國內，從魏則西事件到和頤酒店事­­­件再到最近的「刺死辱母者」事件，無一不是在社交網絡上迅速發酵，並最終對現實社會產生影響。而且這種線上影響線下的趨勢越來越明顯。

除了社交網絡給社會和經濟帶來許多正面影響之外，也帶來了不少負面影響。從Facebook 和 YouTube上的暴力恐怖信息傳播到微博微信上大量謠言和假新聞，這些有害信息藉助社交網絡的特點迅速傳播並且往往產生不可控的後果。

為了利用好社交網絡的特性，產生價值，消除危害，所以產生了社交網絡分析這門科學。它是一種基於信息學、數學、社會學、管理學和心理學等科學的交叉科學。根據社交網絡的特性，其主要研究三大內容：結構與演化，群體與互動，信息與傳播。

本文簡要概述了社交網絡分析領域各個研究方向，對於細節性的內容我只列出參考文獻，在文章最後提供了一些學習資源。 希望通過閱讀本文，對這個領域感興趣的讀者可以對社交網絡分析有一個宏觀理解並且找到學習的方向。筆者作為社交網絡分析的初學者，對某些概念和事實的解釋和陳述不免有錯誤之處，還望各位讀者能及時指正，大家共同交流進步。

02 社交網絡的結構特性與演化機理

1. 社交網絡結構分析與建模

1.1 統計特性

社交網絡模型許多概念來自於圖論，因為社交網絡模型本質上是一個由節點（人）和邊（社交關係）組成的圖。筆者將簡要介紹社交網絡模型中常用的統計概念。

1.2 網絡特性

• 小世界現象：小世界現象是指地理位置相距遙遠的人可能具有較短的社會關係間隔。早在1967年，哈佛大學心理學教授 Stanley Milgram 通過一個信件投遞實驗，歸納並提出了「六度分割理論（Six Degrees of Separation）」, 即任意兩個都可通過平均五個人熟人相關聯起來。1998年，Duncan Watts 和 Steven Strogatz 在《自然》雜誌上發表了裡程碑式的文章《Collective Dynamics of 「Small-World」 Networks》，該文章正式提出了小世界網絡的概念並建立了小世界模型。

  小世界現象在在線社交網絡中得到了很好地驗證，根據2011年 Facebook 數據分析小組的報告， Facebook 約7.2億用戶中任意兩個用戶間的平均路徑長度僅為4.74，而這一指標在推特中為4.67。可以說，在五步之內，任何兩個網絡上的個體都可以互相連接。

1.3 網絡模型

2. 虛擬社區（社團）及發現技術

2.1 定義

虛擬社區基於子圖局部性的定義：社區結構是複雜網絡節點集合的若干子集，每個子集內部的節點之間的連接相對非常緊密，而不同子集節點之間的連邊相對稀疏。

在社交網絡中發現虛擬社區有助於理解網絡拓撲結構特點，揭示複雜系統內在功能特性，理解社區內個體關係。為信息檢索、信息推薦、信息傳播控制和公共事件管控提供有力支撐。虛擬社區發現存在著許多經典的算法，這些算法用於挖掘不同規模的虛擬社區，算法在追求高精度的同時力求提高效率（降低時間複雜度）。

2.2 社區發現算法評價指標

以下評價指標可通過搜尋引擎獲得詳細的介紹：

2.3 社區靜態發現算法

Mark Newman 提出了針對模塊度的最大化的貪心算法FN。可參考文獻：Newman,Mark EJ. "Fast algorithm for detecting community structure innetworks." Physical review E 69.6 (2004): 066133.

Zhao, Yuxin, et al. "Acellular learning automata based algorithm for detecting community structure incomplex networks." Neurocomputing 151 (2015): 1216-1226.

Du, Jingfei, Jianyang Lai,and Chuan Shi. "Multi-Objective Optimization for Overlapping CommunityDetection." International Conference on Advanced Data Mining andApplications. Springer, Berlin, Heidelberg, 2013.

Newman, Mark EJ, andElizabeth A. Leicht. "Mixture models and exploratory analysis innetworks." Proceedings of the National Academy of Sciences104.23(2007): 9564-9569.

Ren,Wei, et al. "Simple probabilistic algorithm for detecting communitystructure." Physical Review E 79.3 (2009): 036111.

Rosvall, Martin, and Carl T.Bergstrom. "Maps of random walks on complex networks reveal communitystructure." Proceedings of the National Academy of Sciences 105.4(2008): 1118-1123.

Kim, Youngdo, and HawoongJeong. "Map equation for link communities." Physical Review E 84.2(2011): 026110.

2.4 社區動態發現算法

Palla, Gergely, et al."Uncovering the overlapping community structure of complex networks innature and society." arXiv preprint physics/0506133(2005).

Kumpula,Jussi M., et al. "Sequential algorithm for fast cliquepercolation." Physical Review E 78.2 (2008): 026109.

Shen, Huawei, et al."Detect overlapping and hierarchical community structure innetworks." Physica A: Statistical Mechanics and its Applications388.8(2009): 1706-1712.

Huang,Jianbin, et al. "Density-based shrinkage for revealing hierarchical andoverlapping community structure in networks." Physica A:Statistical Mechanics and its Applications 390.11 (2011): 2160-2171.

Raghavan, Usha Nandini, RékaAlbert, and Soundar Kumara. "Near linear time algorithm to detectcommunity structures in large-scale networks." Physical review E 76.3(2007): 036106.

Gregory, Steve. "Finding overlapping communitiesin networks by label propagation." New Journal of Physics 12.10(2010): 103018.

Lancichinetti, Andrea, andSanto Fortunato. "Benchmarks for testing community detection algorithms ondirected and weighted graphs with overlapping communities." PhysicalReview E 80.1 (2009): 016118.

Lee,Conrad, et al. "Detecting highly overlapping community structure by greedyclique expansion." arXiv preprint arXiv:1002.1827 (2010).

3. 虛擬社區演化分析

在線社交網絡中存在著大量顯性或者隱性的虛擬社區結構，這些虛擬社區結構並不是永恆不變的，隨著事件變化，社區結構也在不斷演變。分析動態的虛擬社區結構演化有助於理解整個社交網絡的演化過程，所以有著重要的研究價值。

3.1 虛擬社區的湧現

虛擬社區湧現即在社交網絡中虛擬社區從無到有的過程，其最重要的特徵是網絡聚集現象。

3.2 虛擬社區的演化

在線社交網絡虛擬社區演化過程非常複雜，影響因素很多。如何挖掘虛擬社區演化中的關鍵性因素成為社交網絡研究中一個重要而有挑戰性的課題， 用戶個體的累積效應、結構多樣性和結構平衡性三個基本因素對虛擬社區演化都存在影響。

3.3 演化虛擬社區的發現

演化虛擬社區發現目前已有大量的研究資料，以下五種是比較成熟的算法模型，具體細節和根據參考文獻進一步了解。

Hopcroft, John, et al."Tracking evolving communities in large linked networks." Proceedingsof the National Academy of Sciences 101.suppl 1 (2004): 5249-5253.

Greene, Derek, Donal Doyle, and PadraigCunningham. "Tracking the evolution of communities in dynamic socialnetworks." Advances in social networks analysis and mining (ASONAM), 2010international conference on. IEEE, 2010.

Chakrabarti, Deepayan, Ravi Kumar,and Andrew Tomkins. "Evolutionary clustering." Proceedings ofthe 12th ACM SIGKDD international conference on Knowledge discovery and datamining. ACM, 2006.

Lin, Yu-Ru, et al."Facetnet: a framework for analyzing communities and their evolutions indynamic networks." Proceedings of the 17th international conference onWorld Wide Web. ACM, 2008.

Lambiotte, Renaud, J-C.Delvenne, and Mauricio Barahona. "Laplacian dynamics and multiscalemodular structure in networks." arXiv preprint arXiv:0812.1770 (2008).

Palla, Gergely, Albert-LaszloBarabasi, and Tamas Vicsek. "Quantifying social groupevolution." Nature 446.arXiv: 0704.0744 (2007): 664.

Hopcroft, John, et al."Tracking evolving communities in large linked networks." Proceedingsof the National Academy of Sciences 101.suppl 1 (2004): 5249-5253.

03 社交網絡群體行為形成與互動規律

1. 用戶行為分析

社交網絡用戶行為是用戶對自身需求，社會影響和社交網絡技術進行綜合評估的基礎上做出的使用社交網絡服務的意願，以及由此引起的各種使用活動的總和。用戶行為是在線社交網絡研究的重要內容。現有研究主要基於如下兩種思路展開，一是將在線社交網絡作為一種特定的信息技術，研究用戶對在線社交網絡技術的採納行為、拒絕行為和用戶忠誠；二是將在線社交網絡視為提供各種服務和應用的平臺，研究用戶使用各種服務和應用所表現出的特徵與規律。

1.1 用戶採納與忠誠

在線社交網絡用戶採納是指用戶在對自身需求、社會影響和在線社交網絡技術進行綜合評估的基礎上做出的使用在線社交網絡服務的意願或行為，在線社交網絡再出現初期能否被儘可能多的用戶採納和試用對於其後續的擴散至關重要。目前已有多種理論被用於揭示在線社交網絡用戶採納行為機理。其中，技術接受模型和計劃行為理論是研究者們應用最多的兩種理論。

在線社交網絡用戶忠誠是指用戶在使用社交網絡服務之後，能夠繼續保持使用的習慣。各種層出不窮的新型網絡服務所帶來的競爭壓力讓保持在線社交網絡用戶忠誠度愈發困難。目前為止，已經有多種理論被用於在線社交網絡的用戶忠誠研究。其中，期望確認理論和心流體驗理論受到較多研究者青睞。

David Fred 提出技術接受模型是目前信息系統研究領域最經典的模型之一。對模型詳細了解可參考：

Davis, Fred D. "Perceived usefulness, perceived ease of use, and user acceptance of information technology." MIS quarterly (1989): 319-340.

Icek Ajzen 提出的計劃行為理論已經被廣泛用於人類行為研究。對理論詳細了解可參考：

Ajzen, Icek. "From intentions to actions: A theory of planned behavior." Action control. Springer Berlin Heidelberg, 1985. 11-39.

由 Oliver 提出的期望確認理論是研究消費者滿意度的基本理論。 Anol Bhattacherjee 再該理論的基礎上結合信息系統的特點提出了信息系統持續使用的期望確認模型（ECM-ISC）。對模型詳細了解可參考：

Bhattacherjee, Anol. "Understanding information systems continuance: an expectation-confirmation model." MIS quarterly (2001): 351-370.

Mihaly Csikszentmihalyi等提出的心流體驗理論是目前關於用戶體驗研究的重要理論。對理論詳細了解可參考:Csikszentmihalyi, Mihaly. Beyond boredom and anxiety. Jossey-Bass, 2000.

1.2 用戶個體使用行為

• 一般使用行為：用戶可以在社交網絡上執行各種各樣的行為，例如瀏覽，點擊，分享，點讚，收藏等等。具體的分類可參考：Benevenuto F, Rodrigues T, Cha M, Almeida V. Characterizing User Behavior in Online Social Networks. New York, New York, USA: ACM; 2009:49-62. doi:10.1145/1644893.1644900.

1.3 用戶群體互動行為

• 群體互動關係選擇：對群體互動關係的研究主要是識別用戶之間的關係，通過制定不同的衡量指標，研究用戶之間的關係強弱。

• 群體互動的內容選擇：社交網絡中用戶對內容選擇與其社交關係密不可分。例如有研究表明兩位維基百科編輯在互動前後產生的編輯內容的相似性有所不同。

• 群體互動的時間規律：在線社交網絡中人類行為的時間特徵研究主要集中於分析行為發生的時間間隔分布。研究發現在線社交網絡中用戶行為時間間隔分布不同於傳統的負指數分布，而是呈現冪律分布，即具有「長尾效應」。對群體互動時間規律的研究可以應用到公共管理和決策等場景中。

2. 社交網絡情感分析

隨著網際網路技術的迅速發展，網絡已經成為人們獲取信息，發表意見的主要途徑，根據文本內容，我們可以將網絡中的文本分為兩種，一種是客觀描述信息，主要針對事件、產品等進行客觀描述，另一種是主觀性信息，主要產生與用戶對人物、事件、產品進行客觀性描述；另一種是主觀性信息，主要產生於用戶對人物、事件、產品等的評價信息。主觀性信息表達了人們的各種情感色彩和情感傾向，如「支持」、「反對」、「中立」等。

情感分析，在此等同於意見挖掘，是針對主觀性信息進行分析、處理和歸納過程。情感分析最初起源於自然語言處理領域，主要從語法語義規則方面對文本的情感傾向性進行研判。隨著社交網絡的興起與發展，情感分析逐漸涉及多個研究領域，如文本挖掘、Web 數據挖掘等，並延伸至管理學及社會科學等學科，並在產品評論、輿情監控、信息預測等多個領域發揮著重要的作用。

2.1 文本情感分析技術

2.2 社交網絡情感分析技術

3. 個體影響力分析

發現社交網絡中的有影響力的個體是社交網絡研究中非常重要的研究分支，而且其有著重要的應用價值。例如微博營銷，謠言檢測，輿情管理等等。

1.1 基於網絡結構的個體影響力計算

基於社交網絡的圖結構特性，有幾個指標用來衡量網絡中節點的中心度，即節點的影響力。除了以下三種外還有 PageRank 中心度等度量方法。

1.2 基於行為的個體影響力計算

社交網絡中用戶的行為決定用戶的影響力，以微博為例，用戶主要表現的行為是評論、轉發、回復、點讚、複製、閱讀等等，基於這些行為特徵構建多種網絡關係圖，可通過隨機遊走等方法發現網絡中的影響力個體。

1.3 基於話題的個體影響力計算

在社交網絡中用戶在不同話題下的影響力不同，可以根據用戶的關注網絡和用戶興趣相似性來計算用戶在每個話題上的影響力。

4. 群體聚集及影響機制分析

本部分主要介紹群體極化的概念。群體極化是指在群體決策的情境中，個體意見或決定往往會受到群體間的彼此討論的影響，而產生一個群體性的結果。群體極化往往表現為群體內的個體不經過個人思考而同意大多數人的觀點。群體極化是一個社會心理學概念，在社會學名著《烏合之眾》中提到的大眾心理狀態就是群體極化的體現。

群體極化產生的條件可概括為四點：第一，必須有激發事件出現；第二，群體內的個人能看到前人的選擇；第三，群體信息缺乏；第四，群體有一定的同質性。

在在線社交網絡分析中，人們通過建立分析模型和仿真來研究在線社交網絡中的群體極化現象。主要的分析模型有基於博弈論和委託—代理理論的從眾行為模型，基於信息瀑的群體一致性模型和基於元胞自動機群決策和行為仿真。

Twitter 中政治觀點的極化[4]

04 社交網絡信息傳播與演化機理

1. 在線社交網絡信息檢索

信息檢索(Information Retrieval) 是從大規模非結構化數據中獲取信息的過程，例如搜尋引擎就是典型的信息檢索技術的應用。在線社交網絡數據結構有其特殊性，以微博的「話題」（#話題名稱#）為例，這種新型的信息組織方式是傳統信息檢索研究沒有涉及的，所以對社交網絡信息的檢索成為了一門研究課題。

1.1 社交網絡內容搜索

內容搜索是指給定查詢，從大量信息中返回相關信息的過程。例如在微博上搜索相關熱點事件名稱，能夠返回關於熱點事件的微博。內容搜索是信息檢索最經典的應用形式。經典的信息檢索模型有向量空間模型（VSM），概率模型及 BM25檢索公式，基於統計建模檢索模型及查詢擬然模型，基於統計語言建模的檢索模型等。

針對微博的內容檢索建模，目前有兩種主要的方法:

• 時間先驗方法：時間先驗是由於語料庫中的文檔具有不同的重要性，考慮語料庫背景定義不同的計算公式，再將計算結果用於檢索模型以期得到更好的檢索效果的一種檢索方法。目前考慮時間信息計算文檔先驗的研究工作可分為兩種：一種定義文檔的時間變化關係；另一種為修改 PageRank 的方法，在其中加入時間關係。具體細節可參考：

  Li, Xiaoyan, and W. Bruce Croft. "Time-based language models." Proceedings of the twelfth international conference on Information and knowledge management. ACM, 2003.

  Yu, Philip S., Xin Li, and Bing Liu. "On the temporal dimension of search." Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters. ACM, 2004.

• 多特徵組合的方法：多特徵組合方法是通過組合多個微博特性來檢索微博內容。下面的參考文獻中提到的微博特性有：微博個數，關注數，粉絲數，微博長度，微博是否含有外鏈。具體細節可參考：

  Li, Nagmoti, Rinkesh, Ankur Teredesai, and Martine De Cock. "Ranking approaches for microblog search." Web Intelligence and Intelligent Agent Technology (WI-IAT), 2010 IEEE/WIC/ACM International Conference on. Vol. 1. IEEE, 2010.

1.2 社交網絡內容分類

面向文本的分類稱為文本分類。分類包括訓練和測試兩階段，簡單地說，訓練是根據已標註類別的語料來學習分類規則或規律的過程。而測試是將已訓練好的分類器用於新文本的過程。不管是訓練還是測試，都需要將分類對象進行特徵表示，然後利用分類算法進行學習或者分類。以下社交網絡中內容主題分類的相關參考文獻，讀者可自行查閱。

Liu, Zitao, et al. "Short text feature selection for micro-blog mining." Computational Intelligence and Software Engineering (CiSE), 2010 International Conference on. IEEE, 2010.

Yuan, Quan, Gao Cong, and Nadia Magnenat Thalmann. "Enhancing naive bayes with various smoothing methods for short text classification." Proceedings of the 21st International Conference on World Wide Web. ACM, 2012.

Ling, Xiao, et al. "Can chinese web pages be classified with english data source?." Proceedings of the 17th international conference on World Wide Web. ACM, 2008.

Zhang, Dan, et al. "Transfer Latent Semantic Learning: Microblog Mining with Less Supervision." AAAI. 2011.

1.3 社交網絡推薦

Ma, Hao, et al. "Sorec: social recommendation using probabilistic matrix factorization." Proceedings of the 17th ACM conference on Information and knowledge management. ACM, 2008.

Funk, Simon. "Netflix update: Try this at home." (2006).

Jamali, Mohsen, and Martin Ester. "A matrix factorization technique with trust propagation for recommendation in social networks." Proceedings of the fourth ACM conference on Recommender systems. ACM, 2010.

2. 社交網絡信息傳播規律

信息傳播是人們通過符號、信號、傳遞、接收與反饋信息的活動，是人們彼此交換意見、思想、情感，已達到互相了解和影響的過程。社交網絡信息傳播是指以社交網絡為媒介進行信息傳播的過程。研究社交網絡信息傳播的規律，有助於我們加深對社交系統的認識，理解社交現象。也有助於模式發現，大影響力節點識別和個性化推薦。下面主要介紹幾種社交網絡信息傳播模型。

2.1 基於網絡結構的傳播模型

Granovetter, Mark. "Threshold models of collective behavior." American journal of sociology 83.6 (1978): 1420-1443.

Goldenberg, Jacob, Barak Libai, and Eitan Muller. "Talk of the network: A complex systems look at the underlying process of word-of-mouth." Marketing letters 12.3 (2001): 211-223.

2.2 基於群體狀態的傳播模型

傳染病模型（SI, SIS, SIR）, 傳染病模型是經典的信息傳播模型，網上有豐富的參考資料。

Yang, Jaewon, and Jure Leskovec. "Modeling information diffusion in implicit networks." Data Mining (ICDM), 2010 IEEE 10th International Conference on. IEEE, 2010.

2.3 基於信息特性的傳播模型

在線社交網絡中的信息承載著用戶網上活動的所有記錄，在信息傳播分析時起著不可或缺的重要作用。信息本身也具有一些特性，例如時效性，主體多樣性，多源觸發，信息合作與競爭等。依據這些特徵，可建立不同的模型。

Myers, Seth A., Chenguang Zhu, and Jure Leskovec. "Information diffusion and external influence in networks." Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2012.

Beutel, Alex, et al. "Interacting viruses in networks: can both survive?." Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2012.

此外，對社交網絡信息傳播規律的研究還包括熱度預測和信息溯源。感興趣的讀者可自行查閱了解。

3. 話題發現與演化

在話題發現和演化的大部分研究中，話題是指一個引起關注的事件或活動，及其所有相關事件和活動。其中，事件或者活動是指在一個特定的時間和地點，發生的一些事情。社交網絡語料庫中的數據和傳統話題發現語料庫的數據區別較大，所以我們必須使用新的方法或對傳統方法進行改進來適應社交網絡數據特點。

一般社交網絡例如 Twitter 的數據有以下特點：數據規模大、內容簡短、噪聲多、數據特徵豐富等。下面介紹幾種主要的話題發現和演化模型。

3.1 基於主題模型的話題發現

Blei, David M., Andrew Y. Ng, and Michael I. Jordan. "Latent dirichlet allocation." Journal of machine Learning research 3.Jan (2003): 993-1022.

3.2 基於向量空間模型的話題發現

Salton, Gerard, Anita Wong, and Chung-Shu Yang. "A vector space model for automatic indexing." Communications of the ACM 18.11 (1975): 613-620.

Becker, Hila, Mor Naaman, and Luis Gravano. "Beyond Trending Topics: Real-World Event Identification on Twitter." ICWSM 11.2011 (2011): 438-441.

3.3 基於詞項關係圖的話題發現

詞項共現是自然語言處理技術在信息檢索中的成功應用之一。它的核心思想是詞項之間的共現頻率在某種程度上反映了詞項的語義關聯。最初學者們利用詞項共現來計算文檔的相似性，隨後學者們利用該方法來完成話題詞提取，話題句提取和摘要生成任務。

Sayyadi, Hassan, Matthew Hurst, and Alexey Maykov. "Event detection and tracking in social streams." Icwsm. 2009.

3.4 基於主題模型的話題演化

Yin, Zhijun, et al. "LPTA: A probabilistic model for latent periodic topic analysis." Data Mining (ICDM), 2011 IEEE 11th International Conference on. IEEE, 2011.

Wang, Xiaolong, Chengxiang Zhai, and Dan Roth. "Understanding evolution of research themes: a probabilistic generative model for citations." Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013.

3.5 基於相鄰時間片關聯的話題演化

Lin, Cindy Xide, et al. "The joint inference of topic diffusion and evolution in social communities." Data Mining (ICDM), 2011 IEEE 11th International Conference on. IEEE, 2011.

Saha, Ankan, and Vikas Sindhwani. "Learning evolving and emerging topics in social media: a dynamic nmf approach with temporal regularization." Proceedings of the fifth ACM international conference on Web search and data mining. ACM, 2012.

4. 影響力最大化

影響力最大化是在社交網絡中選定信息初始傳播用戶，使得信息的傳播範圍能達到最大，即影響力最大。影響力最大化算法的目的就是找出一定數量的用戶作為影響力傳播的初始節點。對影響力最大化的問題的建模是基於社交網絡信息傳播模型的。其中最經典的模型是線性閾值和獨立級聯模型。

影響力最大化算法被證明為 NP-hard問題，下面主要介紹兩種典型的影響力最大化算法。

4.1 貪心算法

貪心算法從單個節點開始，計算每選一個新節點作為初始節點對每個節點帶來的邊際收益，取能造成邊際收益最大的點加入初始節點集合。貪心算法的缺點是計算時間成本較大，但是計算精度較高。

Kempe, David, Jon Kleinberg, and Éva Tardos. "Maximizing the spread of influence through a social network." Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2003.

Chen, Wei, Yajun Wang, and Siyu Yang. "Efficient influence maximization in social networks." Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2009.

4.2 啟發式算法

不同於貪心算法選擇任何一個點作為初始節點開始計算，啟發式算法先通過一定策略選取一定數量的初始節點，然後計算其影響力傳播。其優點是速度快，缺點是精度低。

Chen, Wei, Yajun Wang, and Siyu Yang. "Efficient influence maximization in social networks." Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2009.

Chen, Wei, Yifei Yuan, and Li Zhang. "Scalable influence maximization in social networks under the linear threshold model." Data Mining (ICDM), 2010 IEEE 10th International Conference on. IEEE, 2010.

05 社交網絡分析的應用

1. 社交推薦

社交推薦顧名思義是利用社交網絡或者結合社交行為的推薦，具體表現為推薦 QQ 好友，微博根據好友關係推薦內容等。在線推薦系統最早被亞馬遜用來推薦商品，如今，推薦系統在網際網路已無處不在，目前大熱的概念「流量分發是網際網路第一入口」，支撐這個概念有兩點核心，其一是內容，另外就是推薦，今日頭條在短短幾年間的迅速崛起便是最好的證明。

根據推薦系統推薦原理，社交推薦可定義為一種「協同過濾」推薦，即不依賴於用戶的個人行為，而是結合用戶的好友關係進行推薦。對於網際網路上的每一個用戶，通過其社交帳戶能很快定義這個用戶眾多特點，再加之社交網絡用戶數之多，使得利用社交關係的推薦近些年備受關注。

人們更願意接受來自朋友的推薦，來源：尼爾森

筆者所了解到的研究有，根據不同社交網絡之間進行信息信息匹配進而進行推薦，有根據社交關係解決新註冊用戶的冷啟動問題等。總之社交推薦在內容分發、廣告宣傳等領域有著十分重要的地位。具體應用細節大家可以關注筆者的一篇介紹騰訊社交廣告的文章（http://mp.weixin.qq.com/s/ mLpNoMdBpDAEb5IZB_A3Rg），如果想了解這方面更多信息還可以關注推薦系統領域頂級會議 ACM RecSys。

2. 輿情分析

輿情分析在網際網路出現之前就被廣泛應用在政府公共管理，商業競爭情報搜集等領域。在社交媒體出現之前，輿情分析主要是線下的報紙，還有線上門戶網站的新聞稿件，這些信息的特點是相對專業準確，而且易於分析和管理；但隨著社交媒體出現，輿情事件第一策源地已經不是人民日報新華社這樣的大媒體，而是某一個名不見經傳的微博用戶，一個個人微信公眾號。他們的特點是信息非常新鮮，缺點是真實度較低且傳播十分迅速，難以控制。所以在社交網絡下的輿情分析是一門新的學問。

「刺死辱母者」微博轉發趨勢，來源見水印

舉幾個例子，去年的和頤酒店，今年的北京地鐵罵人事件這類急性輿情事件最早就是在微博上爆出，而且在短時間內迅速傳播。還有去年的關於快手的「中國農村殘酷底層物語」，今年的「北京房價」等這類民生話題，也是在微信公眾號逐漸發酵。

當然，在新形勢下的輿情應對，也已經有新的工具，大家百度「輿情分析平臺」或者「輿情分析軟體」可以找出一大堆。比較有名的有蟻坊、紅麥、清博、知微、新榜等等。一些傳統的輿情分析機構開始轉型做「大數據」的輿情分析，也有近年來完全基於社交媒體的輿情平臺，比如基於微信的新榜和基於微博的知微 。除此之外，BAT 等大型平臺有自己輿情分析工具，可以私人訂製，也有開放的指數（百度指數、微信指數）。

3. 隱私保護

隱私問題在網際網路時代已經是老生常談的問題了。在社交網絡中，作為用戶，我們可能會留下大量痕跡，這些痕跡有隱性的，也有顯性的，好不誇張地，社交服務提供商可以根據你的少量痕跡，挖掘到大量你的個人信息，有些信息是你不願意別人知道的。

這其中存在一個矛盾，即社交服務提供商處於商業目的想儘可能獲取你的個人信息，但是你又擔心自己的個人信息被洩露。所以在隱私保護領域，一方面要設計足夠安全的機制，技術層面的，法律層面的，在保護個人隱私的前提下最大化商業利益和用戶的體驗。

「雲端」的隱私，來源：http://s9.sinaimg.cn

舉一個大家比較熟悉的例子，即許多網站註冊帳戶的時候使用微信、支付寶帳戶驗證，即免去了大家填寫個人信息的煩惱，又保護了大家的隱私。同理，螞蟻金服提供的芝麻信用功能也有隱私保護的功能。

目前學界對隱私保護的研究主要還是從技術層面設計完善的隱私保護機制。

4. 用戶畫像

一種用戶畫像流程，來源：http://www.51callcenter.com

用戶畫像，這是個營銷術語，即通過研究用戶的資料和行為，將其劃分為不同的類型，進而採取不同的營銷策略。傳統的用戶畫像最常用的手段就是調查問卷，訂閱過雜誌和報紙的讀者都知道，會有各種各樣的有獎問卷，一方面用來獲得對於產品的反饋，另一方面就是對你進行畫像，這些畫像資料甚至廣泛在黑市流通，這就是你為什麼有時候會接到莫名其妙的電話的原因（又扯到了隱私保護問題）。

在社交網絡，用戶畫像方式變得更多了，除了傳統的線下問卷變成在線問卷。我們通過用戶的行為，一方面通過統計學方法獲得一些用戶特徵（經典的例子是沃爾瑪的「啤酒和尿布」，另一方面通過機器學習進行建模和驗證獲得意外的收穫（參見上面提到的騰訊社交廣告文章）。

接觸過微信公眾號後臺的讀者都知道，公眾號後臺對微信公眾號文章的讀者還有公眾號粉絲的畫像已經做得非常充足了，好像微博會員也有粉絲畫像的功能。這些便捷的功能對於媒體運營者和廣告投放者都有非常重要的作用。

5. 謠言檢測

謠言檢測算是輿情分析的一部分，之所以單獨提出來是因為這部分非常重要，而且謠言的確定對於輿情管理非常重要。早起微博因為充斥著大量謠言，使得新浪微博不得不推出「微博闢謠」官方帳號，到如今微博以及有許多自發和官方的闢謠帳號，微信公眾號也是如此。

「六小齡童春晚被拒」謠言傳播走勢，來源見水印

傳統闢謠方法無非是進行試試檢驗，用證據說話，隨著現在機器學習技術的迅速發展，我們也可以通過信息傳播的軌跡，信息內容等維度自動判斷消息是否屬於謠言，而且判斷地越迅速，對於輿情管理的意義就越大。同理，這種技術也被應用在社交網絡有害信息識別。

在國外，有關 Facebook 假新聞的新聞被炒得火熱，有興趣的讀者可以關注一下。

6. 可視化

可視化是隨著大數據一起成為熱門話題的。因為人類對於圖像信息的理解速度要大於文字信息數百倍，所以講一些數據可視化有助於人們更生動地理解某一結論或現象。當然不是所有數據都適合可視化，在社交網絡中，我們最常見的有信息傳播軌跡還有詞雲圖等。有關這方面的內容可以參考微博帳號「社交網絡與數據挖掘」。

微博明星好友關係可視化，來源見水印

除了專門可視化的機構，網上也有許多開源的可視化庫，百度的 Echarts 就很有名。 對於社交網絡信息傳播以及好友關係等的可視化，使得我們能直觀看到一些事實，這對於輿情報告製作以及新聞報導都有很好的輔助作用。

06 社交網絡前沿研究

我在本部分搜集了幾篇近兩年來在社交網絡頂級會議上比較受關注的文章，將文章的摘要翻譯並陳列，以供各位讀者參考。

1. Negative Link Prediction in Social Media

Tang, Jiliang, et al. "Negative link prediction in social media." Proceedings of the Eighth ACM International Conference on Web Search and Data Mining. ACM, 2015

近年來，符號網絡（signed network）越來越受到關注。對於符號網絡的研究表明，負關係（negative link）對分析過程有幫助。由於許多網絡中用戶無法指定這種負關係，這是其被有效利用的主要障礙。話句話說，負關係的重要性與其在真實數據集之間的應用存在著差距。因此，我們自然而然會探討是否能通過公開的社交網絡數據自動預測用戶的負關係。在本文中，我們研究了在社交媒體中僅僅用正關係和內容為中心的交互行為（content-centric interactions）來預測負關係的問題。我們對負關係做了一些列觀測並且提出了一個原則性框架 NeLP，該框架可以利用正關係和以內容為中心的交互來預測負關係。我們對在現實社交網絡的實驗結果表明，NeLP框架可以準確地預測具有正關係和以內容為中心的交互關係的負關係。 我們的詳細實驗還說明了各種因素對NeLP框架有效性的重要性。

2. Twitter Sentiment Analysis with Deep Convolutional Neural Networks

Severyn, Aliaksei, and Alessandro Moschitti. "Twitter sentiment analysis with deep convolutional neural networks." Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 2015

本文介紹了我們用於推特輿情分析的深度學習系統。我們工作主要的貢獻是提出了一個初始化卷積神經網絡參數權重的模型，這對於準確訓練模型至關重要，同時避免增加新的特徵。簡而言之，我們用無監督神經語言模型來訓練初始的詞嵌入（initial word embeddings），這個詞嵌入將被通過我們的基於遠程監督語料庫（distant supervised corpus）的深度學習模型進一步調整。在最後階段，預先訓練的參數將被用於初始化我們的模型，然後我們通過由Semeval-2015組織的Twitter情緒分析官方系統評價競賽最近提供的監督訓練集對後者進行培訓。我們的方法得到的結果和參與競賽的系統的結果之間的比較表明，我們的模型可以分別排在短語級別子任務A（11個團隊）和消息級子任務B（40個團隊）前兩位。這證明了我們解決方案的實際價值。

3. Social Recommendation with Strong and Weak Ties

Wang, Xin, et al. "Social Recommendation with Strong and Weak Ties." Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. ACM, 2016

隨著在線社交網絡的爆炸式增長，現在人們普遍了解，社會信息對推薦系統非常有幫助。社會推薦方法能夠應對關鍵的冷啟動問題，從而可以大大提高預測精度。主要的原因是，基於信任和影響，人們對其朋友購買過的產品表現出更多的興趣。儘管在社交推薦領域已經有大量工作，但是很少有人關注社交強關係和弱關係這兩個重要的社會學概念之間的區別。在這篇文章中，我們使用鄰域重疊來逼近關係強度，並擴展受歡迎的貝葉斯個性化排名（BPR）模型並將其用於區別強弱關係。我們提出了一種基於 EM （EM-based）的算法，它可以根據最優推薦準確度（optimal recommendation accuracy）對強弱關係進行分類並學習所有用戶和所有商品的潛在特徵向量（latent feature vectors）。我們對四個現實世界數據集進行廣泛的實驗，並證明我們提出的方法在各種精度指標中顯著優於目前最好的成對排名（pairwise ranking）方法。

4. Online Actions with Offline Impact: How Online Social Networks Influence Online and Offline User Behavior

Althoff, Tim, P. Jindal, and J. Leskovec. "Online Actions with Offline Impact: How Online Social Networks Influence Online and Offline User Behavior." Tenth ACM International Conference on Web Search and Data Mining ACM, 2016:537-546

如今許多應用軟體都廣泛地利用了社交網絡功能並允許用戶互相連接、互相關注、分享內容和評價動態。儘管這些功能已經被廣泛應用，對於用戶在線時和離線後參與還是保留的行為卻很少有人理解。本文中，我們通過一個運動記錄 APP研究了社交網絡是如何影響用戶線下行為的。

我們分析了600萬用戶五年間的七億九千一百萬條線上和線下活動記錄，結果表明社交網絡對用戶線上和線下的行為有著巨大的影響。具體來講，我們提出了社交網絡影響用戶行為的因果關係。我們發現新社交關係的建立能將用戶在 APP 中的活躍度提高30%，用戶保留率提高17%，線下活躍率提高7%（大約每天多走400步）。通過開展自然實驗，我們將新社交關係對用戶的影響和用戶因為對 APP 的興趣而走更多步數作了區分。

我們發現社交影響佔所有對用戶行為影響因素的55%，剩下的45%可以用用戶對 APP 本身的興趣來解釋。此外我們還發現一連串的個人用戶之間的社交關係建立對每日步數的增加有顯著影響，用戶之間每增加一條邊都對會減弱這種影響，並且這些變化是基於邊屬性和用戶自己的資料屬性。最後我們用這些現象設計了一個模型，模型用來判斷哪些用戶最容易被新建立的社交網絡關係影響。

5. Intertwined Viral Marketing in Social Networks

Zhang, Jiawei, et al. "Intertwined viral marketing in social networks." Advances in Social Networks Analysis and Mining (ASONAM), 2016 IEEE/ACM International Conference on. IEEE, 2016

傳統的病毒式營銷問題旨在為一個單一產品選擇一個種子用戶的子集，以最大限度地提高其在社交網絡中的知名度。而然在實際情況下，許多產品可以同時在社交網絡中進行推廣。從產品層面來看，這些產品之間的關係是互相纏繞的，舉個例子，就是競爭、互補且獨立的關係。

在這篇文章中，我們將研究「糾纏影響力最大化」問題，它是基於一個目標產品需要在社交網絡上進行宣傳，而同時有多個競爭/互補/獨立的產品在推廣這樣的場景。糾纏影響力最大化是一個非常具有挑戰性的問題，首先是因為很少有模型能模擬多種產品同時宣傳時的信息擴散形式；第二是對於目標產品最優種子集的選擇可能很大程度上取決於其它產品的營銷策略。為了解決此問題，我們提出了一種統一貪心算法框架（interTwined Influence EstimatoR， TIER），在四種不同類型現實社交網絡數據集的實驗表明TIER 優於所有的比較方法，在解決糾纏影響力最大化問題上有著顯著優勢。

6. Who to Invite Next? Predicting Invitees ofSocial Groups

Yu Han, and Jie Tang. "Who to Invite Next?Predicting Invitees of Social Groups " Proceedings of theTwenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17).2017.

WhatsApp、Snapchat 和微信等社交即時通訊工具很大程度上改變了人們工作生活和交流的方式，也受到了多個領域例如計算機科學、心理學、社會學和物理學的關注。在社交即時消息工具中，社交群組在多用戶交流中扮演著重要的角色。一個有趣的問題是，社交群組動態演變的機制是什麼？更具體來說，在一個群組中，誰將會被邀請加入？這篇文章中，我們研究社交群組潛在加入者這樣一個新穎的問題。我們採用微信這個中國最大的社交軟體作為實驗數據的來源。我們提出了一個概率圖模型用來計算影響用戶被邀請加入群組概率的因子。我們的實驗預測結果表明我們的模型相比目前的其他模型有顯著的提高。

7. The Co-Evolution Model for Social NetworkEvolving and Opinion Migration

Gu,Yupeng, Yizhou Sun, and Jianxi Gao. "The Co-Evolution Model for SocialNetwork Evolving and Opinion Migration." Proceedings of the 23rd ACMSIGKDD International Conference on Knowledge Discovery and Data Mining.ACM, 2017.

幾乎所有的真實社交網絡都是動態且隨著時間演化的。新的鏈路的形成和舊的鏈路的消失很大程度上取決於社交網絡用戶的同質性。同時，一些社交網絡用戶的隱性性質例如用戶的觀點也隨著時間而變化。其中一部分原因是用戶從社交網絡中接收到影響力，這些改變進而會影響社交網絡的結構。社交網絡的演化和節點性質的遷移通常被認為是兩個獨立正交的問題。

在這篇文章中，我們提出一種協演化模型，通過對兩種現象的建模形成閉環。模型有兩個主要部分：

• 一個已知節點性質的網絡生成模型；

• 一個已知社交網絡結構的節點性質遷移模型。

通過模擬發現我們的模型有一些不錯的特性：

最後，我們模型的有效性通過在對議會立法議案支持者的預測中得到了驗證，並且我們的模型優於一些目前的方法。

07 學習資料

1. 圖書

2. 網站

• 大數據導航（此網站包含很多資源）

  http://hao.199it.com/

• 斯坦福數據集網站（Jure 男神）

  http://memetracker.org/data/index.html

• 加州大學歐文分校數據集網站

  http://archive.ics.uci.edu/ml/datasets.html

• 國內社交網絡數據集共享網站

  http://www.socialysis.org/data/project/project

• 清華大學搭建的學術資料庫

  https://cn.aminer.org/

• 亞馬遜商品流行趨勢分析平臺

  http://132.239.95.211:8080/demowww/index.jsp#

• 明尼蘇達雙城分校社會計算實驗室

  https://grouplens.org/

• 新華網信息傳播影響力評估

  http://www.xinhuanet.com/xuanzhi/zt/xzyxl/index.html

• 新榜，微信公眾號數據檢測平臺

  http://www.newrank.cn/

• 清博新媒體大數據平臺

  http://www.gsdata.cn/

• 百度Echarts數據可視化庫

  http://echarts.baidu.com/

• 阿里雲 DataV 數據可視化庫

  https://yq.aliyun.com/teams/8

3. 工具

4. 會議

筆者僅列出與社交網絡相關的部分國際會議，排名不分先後，加粗的會議為專門討論社交網絡話題的會議。

KDD, WWW, ICDM, CIKM, AAAI, SDM, IEEE BigData, ASONAM, WSDM, ICWSM, ACL, IJCAI, NIPS, ICML, ECML-PKDD, VLDB, SIGIR, PAKDD, RecSys, ACM HT, SBP, ICWE, PyData

筆者在這裡推薦兩個國內的社交網絡分析會議，一個是全國社會媒體處理大會（SMP），由中國中文信息學會主辦，會議論文 EI 檢索。第二個是國際網絡空間數據科學會（IEEE ICDSC），會議由中科院，北大，中國網絡空間安全協會等機構籌辦。

5. 課程

筆者在上一部分提到的國際會議，例如 WWW、KDD 等，每年都有關於社交網絡分析方向的 tutorial，其視頻和 PTT 都是在網上可獲取的，通過 tutorial 能對相關領域有一個宏觀了解並且能了解領域前沿動態。

除此之外，在 Coursera 上面密西根大學安娜堡分校開設的一系列 Python 學習課程也值得一看。在網易公開課上面也有中文的 Python 數據挖掘課程可供學習。

萬能的淘寶也提供大量廉價的視頻和電子學習資料。

最後，利用好科學上網工具和搜尋引擎（不是百度）才是王道。

08 參考資料

[1] 方濱興, 許進, 李建華. 在線社交網絡分析[M]. 電子工業出版社, 2014.

[2] Reza Zafarani, Mohammad Ali Abbasi, Huan Liu. 社會媒體挖掘[M]. 人民郵電出版社, 2015.

[3] Carlos Castillo, Wei Chen, Laks V.S. Lakshmanan, Information and Influence Spread in Social Networks，KDD 2012 Tutorial

來源：數據派THU

END

投稿和反饋請發郵件至[e-mail]。轉載大數據公眾號文章，請向原文作者申請授權，否則產生的任何版權糾紛與大數據無關。

大數據

返回搜狐，查看更多

責任編輯：