文件導向社群網路影響力最大化之研究

Abstract

影響力最大化問題是在社群網路中找尋一群節點，使得影響力的散播最大化。大部分影響力最大化這方面的研究都只針對在同質的社群網路上，且他們忽略了相聯性影響力的作用。在此篇論文中，我們介紹一種新型態的社群網路－文件導向社群網路，文件導向社群網路不但包含了由使用者間社交關係所組成的一般社群網路，也包含了使用者所擁有的文件所組成的文件相似度網路。使用者可能會被不認識的其他使用者影響僅僅因為他們興趣相同，在文件導向社群網路我們可以利用文件相似度網路來模擬相聯性影響力的作用。有了文件相似度網路，使用者就能夠被興趣相同的人影響。在此篇論文中，我們提出了解決在文件導向社群網路中影響力最大化的問題，首先提出一個有效率的解決影響最大化的演算法，並且介紹如何使用這演算法於文件導向社群網路中。真實的資料實驗的結果顯示出我們的方法有效性，並且相對於貪婪演算法有不錯的影響力擴散。

Influence maximization is the problem of selecting top k seed nodes in a social network to maximize their influence coverage under certain influence diffusion models. Majority of the literature on this topic have focused only on homogeneous social networks and they ignore the effect of correlational influence. In this thesis, we introduce a new type of social network – document-based social network (DBSN). A DBSN not only contains the social relations between the users in conventional social networks, but also includes the similarity relations between the documents (such as images and videos) owned by users in similarity networks. The users may be activated by someone just because they have same interests even if they do not know each other. In DBSN, we can utilize the document similarity networks to model the diffusion of correlational influence. In this thesis, we tackle the influence maximization problem in DBSN. We first propose an efficient algorithm, CDGA, to solve the influence maximization problem. And then we introduce the framework of how to use CDGA in DBSN. The experimental results on real datasets show that the proposed CDGA algorithm significantly outperforms the state-of-the-art algorithms in efficiency but also have a good influence spread compared with Greedy algorithm.