電機資訊學院: 資訊工程學研究所指導教授: 郭大維; 李政德曾建智Tseng, Chien-ChihChien-ChihTseng2017-03-032018-07-052017-03-032018-07-052016http://ntur.lib.ntu.edu.tw//handle/246246/275370影響力最大化演算法是一個在社群網路中尋找一組高影響力的個體，使得在特定的訊息傳播模型下能夠讓總體影響力達到最大化的NP難度的問題，雖然基於蒙地卡羅模擬的演算法能夠有理論上的保證來產生近似於最佳解的結果，時間上的高複雜度使得此種方法難以應用到巨量社群網路。因此一些基於經驗法則的演算法為了解決蒙地卡羅模擬演算法的高耗時問題，犧牲了答案的精確度理論保證來大幅提升時間效率。另一方面，隨著GPU開始被大量使用於加速一般應用程式，一些研究也顯示了GPU在應用於圖論演算法的加速潛力，此外隨著近年來異質運算平台像是OpenCL以及HSA的發展，CPU與GPU之間的共同運算也變得較以往容易許多。因此我們提出了一個在GPU-CPU異質多核心平台上的高效率影響力最大化演算法，基於蒙地卡羅模擬的方法且利用GPU的平行運算處理能力來加速影響力值模擬計算，此外也提出了一些技巧來進一步加速我們的演算法。實驗結果顯示和現有獨立使用CPU以及GPU運算的蒙地卡羅模擬演算法相比，我們的演算法能夠有數百倍的加速卻仍然能保持相同的答案精確度。Influence maximization is an NP-hard problem to find a small set of highly influential individuals in a social network to maximize the influence spread under a specific information propagation model. While the Monte-Carlo-simulation-based algorithms produce near-optimal solutions with a theoretical guarantee, these algorithms run extremely slow for large-scale networks. Therefore, many heuristic algorithms have been proposed without theoretical guarantee, compromising the quality of solution with time efficiency. On the other hand, graphics processing unit (GPU) has recently been widely used as a popular general-purpose computing device and shown promising potential in accelerating the computation of some graph algorithms. In addition, the development of heterogeneous computing frameworks such as OpenCL and HSA makes the collaboration of CPU and GPU much more easily than before. As a result, we propose an efficient GPU-CPU algorithm for influence maximization problem on heterogeneous platform, which is based on the Monte-Carlo-simulation-based approach, where we leverage the parallel processing capability of GPU for large number of independent influence spread calculations. Moreover, several techniques are presented in this paper to accelerate the algorithm. The experimental results show the speedup over the state-of-the-art Monte-Carlo-simulation-based algorithms for CPU and GPU respectively with up to two orders of magnitude while maintaining the quality of solution.論文使用權限: 不同意授權影響力最大化異質運算蒙地卡羅模擬巨量社群網路influence maximizationheterogeneous computingMonte-Carlo simulationlarge-scale social networksthesis10.6342/NTU201600155