應用二元累加窮舉法與網頁排名於社群網路傳播機率預測與建模

Applying Binary-Addition-Tree and PageRank for Predicting and Modeling Propagation Probability in Social Network

徐紫芸(Tzu-Yun Hsu)

指導教授 ： 葉維彰

國立清華大學/工學院/工業工程與工程管理學系/碩士(2021年)

摘要

由於現今智能設備的發展使得社群網絡越來越普及，人們利用社群網路學習新的點子、分享想法，並與志同道合的人或者組織互動。社群網路的影響力沒有國家、種族和宗教的限制，除了幫助企業輕鬆觸及到潛在客戶有著至關重要作用，也打破傳統媒體的壁壘，幫助訊息傳遞者能更快速散播訊息。透過增加預測社群網絡傳播機率的準確性會間接影響資訊傳播需要投入的金錢、人力和時間成本。
本研究提出了一種新方法來預測社群網路傳播的機率。首先我們證明了社群網路屬於一種無尺度網路，並使用Barabási- Albert 模型建構預測模型，透過二元累加窮舉法窮舉出所有可能傳播狀態後，利用PageRank 演算法計算每個社群網路節點出現的機率以及傳播機率，並利用個性化 PageRank 演算法來符合使用者偏好之設定；最後，利用新型二元累加窮舉法計算出所有節點至不同傳播範圍之機率預測值。
此外，我們證明了此方法中所提出的最大傳播狀態 PageRank 值可以作為識別傳播機率的有效工具，以及說明了使用者偏好主題性於傳播機率的影響。總體而言，此預測模型的貢獻為提供一個新的預測社群網路傳播之方法，協助社群網路創造有效的訊息傳播效果，實現了利用最小的投放成本達到最大傳播效率，使網路節點影響力增加。

關鍵字

社群網路 ； 無尺度網路 ； Barabás-Albert模型 ； 二元累加窮舉法 ； PageRank ； 個性化PageRank

並列摘要

The social network is now as smart devices become more and more prevalent. Users use the social network to learn new spots, share opinions, and interact with like-minded people and organizations. The influences of social networks have no limited national, ethnic, and religious. The social network not only plays an important role to help businesses reach their potential customers easily but also breaks the barriers of traditional media and helps the message sender to spread the message faster. The accuracy of predicting the probability of social network propagation will affect the cost of resource input including money, manpower, and time.
This study proposes a novel methodology to predict the probability of social network propagation. We firstly prove that the social network propagation can be represented as a scale-free network and construct a prediction model using the Barabási-Albert model. After enumerating all possible propagation states through the Binary-Addition-Tree, we use the PageRank algorithm calculates the probability of each social network nodes appearing and the probability of spreading, and using the Personalized PageRank algorithm to achieve the user preference settings. Finally, a new Binary-Addition-Tree algorithm is used to calculate the predicted probability of all nodes to different number of propagation areas.
Additionally, we demonstrate that the proposed maximum-state PageRank used in this methodology can be implemented separately as an effective tool to identify the propagation’s probability. Otherwise, the effect of user preference on propagation rates is also illustrated. Overall, the contribution of this predictive model is to provide a new method for predicting social network propagation’s probability, helping social networks create effective information dissemination effects, achieving the maximum transmission efficiency with the smallest delivery cost, and increase the influence of network nodes.

並列關鍵字

social networks ； scale-free network ； Barabás-Albert model ； Binary-Addition-Tree ； PageRank ； Personalized PageRank

參考文獻

[1] Kimura, M., et al., Extracting influential nodes on a social network for information diffusion. Data Mining and Knowledge Discovery, 2010. 20(1): p. 70-97.

[2] Kimura, M., K. Saito, and H. Motoda, Blocking links to minimize contamination spread in a social network. ACM Transactions on Knowledge Discovery from Data (TKDD), 2009. 3(2): p. 1-23.

[3] Gruhl, D., et al. Information diffusion through blogspace. in Proceedings of the 13th international conference on World Wide Web. 2004.

[4] Domingos, P., Mining social networks for viral marketing. IEEE Intelligent Systems, 2005. 20(1): p. 80-82.

[5] Domingos, P. and M. Richardson. Mining the network value of customers. in Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. 2001.