基於人群模擬與影響力擴散之社群網路探勘

Mining Social Networks from the Perspectives of Crowd Simulation and Influence Propagation

李政德(Cheng-Te Li)

指導教授 ： 林守德

國立臺灣大學/電機資訊學院/資訊網路與多媒體研究所/博士(2013年)

https://doi.org/10.6342/NTU.2013.02306

摘要

社群網路（Social Network）描述真實世界中人與人之間各種社交關係，隨著社群網路服務的崛起，如Facebook、Twitter與Foursquare，社交資料已變得容易取得，傳統社群網路分析之問題，如分析重要節點、偵測網路社群（Network Community）與社群網路生成模型，已逐漸被徹底探討與研究。本論文試圖從兩個嶄新的角度來進行社群網路探勘。(a)社群結構在時間空間下之動態變化：人和人之間的社交連結與人們在地理空間上群聚移動之行為，這二者之間是否存在關聯性？(b)資訊於社交個體間之傳播動態：對於不同情境的影響力擴散，哪些個體對於資訊的流通扮演最關鍵的角色？

人類學家、生物學家與社會學家之研究已指出社群網路之形成乃是人們在地理空間上實際交流與互動之結果，地理位置相距較近之個體能擁有較多的機會彼此物理聯繫，進而發展社交關係。本論文的第一部分在於結合人群模擬之技術（Crowd Simulation）與社群網路分析，試圖從電腦模擬計算之角度來捕捉並分析個體間的社交連結與他們在空間中群聚移動此二者間之關係，以驗證該科學假說。我們設計了一個社交人群模擬之架構Social Flocks，其核心概念在於將人群模擬地理空間中的每個代理人對應至社群網路中的一個社交個體，並透過代理人彼此間的物理交互作用力來實現社交群聚移動之效果。在Social Flocks架構下，我們完成了四個任務，其中前二者之目的在於完成該科學驗證，後二者則為基於社交人群模擬之應用。(1)我們透過社交人群模擬來自動生成具備真實世界社群網路之特性（如：個體間之高群聚性、低平均路徑距離、與具冪次法則之分支度）之合成網路；(2)給定一社群網路，我們利用個體代理人於地理空間中移動之軌跡來偵測網路社群。此二任務之實驗結果驗證了該科學假說：個體於空間中之物理互動與群體移動能夠形成真實社群網路並自然產生社群。(3)我們將社群網路引進人群模擬，藉以產生真實世界社交互動之各種人群集體移動行為。(4)我們結合社群網路與人群逃生，模擬出更為真實的社交逃生行為，並自動規劃出口以及逃生號誌之位置，以改進災難發生時，個體逃生之最終存活率。

在社群網路上，個體彼此間最普遍的互動行為即是資訊的交流與傳遞，任何資訊皆有機會透過社交連結在社群網路中廣為傳播，而病毒式行銷正是這種社群網路上個體間影響力擴散（Influence Propagation）的最佳應用。基於影響力擴散之設定，本論文之第二部分試圖針對真實世界五種不同的應用情境，透過影響力擴散機制之模擬，找出社群網路上，對影響力最大化扮演各種最關鍵角色之個體：(1)哪些個體掌握著資訊擴散之瓶頸？(2)哪些個體可使得目標市場行銷獲得最大效益？(3)當社群網路隨著時間而成長變動時，哪些個體對於影響力最大化最為有效？(4)如何整合直銷與病毒式行銷，以獲得更大行銷效益？(5)在考慮個體間各種異質性關係的狀況下，如何設計影響力傳播之機制並達到影響力最大化？針對這五個問題，我們設計對應的演算法，並實驗於真實社群網路資料，結果顯示對於各種影響力擴散之情境，在影響力最大化之設定下，我們所提出之方法皆能有不錯的效能表現。

關鍵字

社群網路 ； 資料探勘 ； 人群模擬 ； 影響力擴散 ； 資訊擴散 ； 社群網路生成 ； 網路社群偵測 ； 逃生規劃 ； 病毒式行銷 ； 影響力最大化

並列摘要

Social networks depict the interactions between people in the real world. With the bloom of social networking services, such as Facebook, Twitter, and Foursquare, social topology has been investigated every hole and corner, ranging from entity resolution to group identification and social network generation modeling in either static or dynamic points of view. In this thesis, we propose to study the social interactions between people from two novel perspectives: (a) the spatial-temporal dynamics of social structures: what is the potential relationship between social connections and collective moving behaviors of crowds in the geographical space? (b) The influence dynamics over social actors: which nodes are the most critical ones under different scenarios of influence propagation?

Scientific studies from anthropologists, biologists, and sociologists have hypothesized that the formation of social structures usually resulted from the spatial-temporal interactions between individuals, as people who live in the geospatial neighborhood have more chances to physically contact with each other and construct the social relationships. The first part of this thesis brings a marriage of crowd simulation and social network analysis to verify such scientific hypothesis by unveiling the connection between the spatial-temporal movements of people and their social relationships. We exploit the crowd simulation to accomplish the spatial-temporal dynamics of social elements by associating each node in the social network with one agent in the space. A social simulation framework, Social Flocks, is developed to deal with four tasks. The first two tasks are designed to verify the scientific hypothesis while the last two are application based on social crowd simulation. (1) We aim to generate realistic social networks that satisfy network properties (e.g. high clustering coefficient, low average path length, and power-law degree distribution). (2) Given a social network, we aim at detecting network communities based on the social moving trajectories of nodes. Experimental results on these two tasks verify the scientific hypothesis that the movement and physical interaction among people can indeed lead to the formulation of a social network as well as the communities. (3) We impose the social connections between agents into produce realistic collective social behaviors over crowds. (4) We consider social factors to study the evacuation dynamics and automatically facilitate the spatial deployment of exit determination and sign placement for improving the survival rate.

One of the most common actions between individuals in social networks is information exchange and diffusion. Any digital contents could be propagated around the social network through social connections. Viral marketing is one of the well-known applications of such influence propagation phenomenon. In the second part, we consider the information diffusion over individuals as well as influence maximization in a social network as the fundamental to identify nodes which play crucial roles under diverse kinds of real-world marketing scenarios. Through simulating how influence is propagated over individuals, we propose and tackle five various but novel marketing problems: (1) How to locate those individuals that hold the bottlenecks of influence propagation? (2) Can we discover the effective seed individuals for targeted advertising? (3) Which nodes are the influential seeds for starting the propagation in a dynamic social network? (4) How to integrate the ideas of direct selling and viral marketing? (5) Can we devise the propagation mechanism over heterogeneous social networks for influence maximization? Experiments conducted on real social networks demonstrate the promising performance of the proposed approaches on enhancing the effectiveness of influence propagation.

並列關鍵字

social network ； data mining ； crowd simulation ； influence propagation ； information diffusion ； social network generation ； community detection ； evacuation planning ； viral marketing ； influence maximization

參考文獻

[1] B. Adamcsek, G. Palla, I. J. Farkas, I. Derenyi, and T. Vicsek. CFinder: Locating Cliques and Overlapping Modules in Biological Networks. Bioinformatics, 22(8), 1021-1023, 2006.

[3] L. Akoglu, M. Mcglohon, and C. Faloutsos. RTM: Laws and A Recursive Generator for Weighted Time Evolving Graphs. In Proceedings of IEEE International Conference on Data Mining (ICDM’08), 701-706, 2008.

[4] M. Aoyagi and A. Namatame. Synchronization in Mobile Agents and Effects of Network Topology. Journal of Agent-Based Social Systems, 6(3), 31-42, 2009.

[5] A. L. Barabasi, and R. Albert. Emergence of Scaling in Random Networks. Science 286(5439), 509-512, 1999.

[8] M. E. F. Bloch. How we Think They Think: Anthropological Approaches to Cognition, Memory, and Literacy. Boulder, Colo.: Westview Press, 1998.