大型社交網路的影響範圍最大化方法

Maximizing the Spread of Influence in Large Social Networks

陳德銘(Te-Ming Chen)

《電腦與通訊》 145期 (2012/06) Pp. 116-122

https://doi.org/10.29917/CCLTJ.201206.0017

摘要

病毒式行銷是一種基於個體間，如家庭、朋友、同事等社交連結的信任關係所形成的一種行銷策略。然而由於有限的廣告預算，通常只能選擇少量使用者進行行銷。這個問題，稱為影響最大化，可描述為在一個社交網路中找到一個具影響力節點的小集合，使得在一個訊息傳播模型下，此小集合的影響範圍可以達到最大。目前已經有許多貪婪演算法被提出來解決這個問題，然而卻仍無法實際運用於大型社交網路。因此如何取得運算時間和影響範圍的平衡是一個重要的課題。在本篇論文中，我們利用了因子圖模型分析社交網路中節點的相互影響關係所推論出的社交影響強度，作為訊息傳播模型的傳播機率。在此傳播模型下，我們利用社交影響強度進行分群，並結合群組間和群組內的分群貪婪演算法，可以有效率地找出種子集合。和CELF++貪婪演算法相比，實驗結果顯示此方法在損失2.49%的影響範圍估算下，可以將運算時間減少了98.99%。

關鍵字

病毒式行銷 ； 社交網路 ； 影響最大化 ； 因子圖 ； 分群貪婪演算法

並列摘要

Viral marketing is a marketing strategy based on trust among individuals' social links of families, friends, and coworkers, etc. Usually, it has a limited budget that it can only select a small number of initial users for advertising. The problem, called influence maximization, is to find a small set of influential nodes in a social network that maximizes the spread of influence under an information diffusion model. Many greedy algorithms have been proposed to solve the influence maximization problem. However, it is not scalable to large social networks. Hence, how to find the balance between the runtime and the influence spread is an important issue.In this paper, a factor graph model is used to analyze the social influence strength between nodes which can be set as the propagation probabilities of the information diffusion model. To efficiently find a small set of influential nodes, i.e., a seed set, the social network is clustered into communities with the social influence strength. Then inter/intra community-based greedy algorithm is proposed to find a seed set under the information diffusion model. The experimental results show that our method can achieve 98.99% of time reduction rate while losing 2.49% of the influence spread compared with the CELF++ greedy algorithm.

並列關鍵字

Viral Marketing ； Social Network ； Influence Maximization ； Factor Graph ； Community-based Greedy Algorithm