利用社群特性於於社區網路影響力最大化之研究

Abstract

近幾年來，因為很多大型社群網站的興起，在社群網路中影響力最大化問題已經引起了很多關注。 影響力最大化問題是在社群網路中找尋一群節點，使得影響力的散播最大化。雖然近幾年已有很多研究在解決影響力最大化的問題，但是用以模擬社群網路的模型不能真實反映現實、網路情境，且效率不佳。然而因為大規模社群網路不斷的增加，效率和實際可行性已經是重要的課題。在此篇論文中，我們使用熱流模模擬切實際的網路，並在此模型下提出兩種解決影響力最大化的演算法。我們利用社群結構來避免影響力重疊，再從所找出來的社群結構中找出最具有影響力的關鍵性節點。藉由社群結構的特性可以大量的減少需要考慮的節點數目。我們使用合成和真實的資料實驗的結果顯示我們所提出的演算法在效能上有很大的改善。

In recent years, considerable concern has arisen over the influence maximization in social network, due to the surge of social network web sites. Influence maximization is the problem of finding a small subset of nodes in a social network that could maximize the spread of influence. Although many recent studies are focused on influence maximization, these works in general are not realistic nor efficient. Nevertheless, with the increasing number of large-scale social networks, efficiency and practicability requirement for influence maximization have become more critical. In this thesis, we propose two novel algorithms, CDH-Kcut and CDH-Shrink, to solve the influence maximization problem in the realistic model, i.e., heat diffusion model. Our algorithms use the community structure, which could significantly decrease the number of candidates of influential nodes, to avoid information overlapping and to find the influential nodes according to the community structure. The experimental results on synthetic and real datasets show our algorithm significantly outperforms in efficiency.