網路拓樸的遞移性:以流行性傳染病的潛在感染風險為例

The Transitivity of Network Topology: Example of Epidemic Spreading Risk

陳璽文(Hsi-Wen Chen)

指導教授 ： 孫春在

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2011年)

https://doi.org/10.6842/NCTU.2011.00540

摘要

分析網路拓樸動態產生的遞移性現象，儼然已成為研究網路拓樸亟需解決也不可或缺的需求。經由分析遞移性現象找出網路各節點在動態傳播過程中的影響力及重要性，就能控制核心節點來達到影響群體、主宰網路訊息傳遞的效果，對於網路拓樸所反映的現實實體層面即可提供有價值的參考資訊。本研究中，將過往探討遞移性現象的理論模型延伸擴充，依據網路拓樸架構及連結所呈現的權重值，分析動態傳播過程中每個節點的重要性。透過重要性的排序比較，得以找出關鍵的核心節點，解決現今研究網路拓樸的需求。
在本文以實際流行病傳播動態為案例研究來驗證演算法的正確性，並使用基因演算法優選在流行病傳播現象中，最貼近實際傳播動態的網路拓樸結構。實驗結果顯示經本模型分析，病原體遞移傳播對各節點的重要性造成的影響與案例研究比對呈現正相關性，證實本研究方法能夠有效處理遞移概念並分析各節點重要性。此外透過基因演算法搜尋結果也可顯示出實際流行病的傳播動態以及造成傳播的影響因素。

關鍵字

網路拓樸 ； 遞移性 ； 馬可夫鏈模型 ； 網頁等級排序演算法 ； 基因演算法

並列摘要

Analyzing the transitivity phenomenon influencing by network topology is among the requirements in studying network topology. Influenced by the transitive spreading, every node has different impacts in varied kinds of network topology. We can offer valuable information for the physical layer reflected by the network topology if the importance of every node can be analyzed.
In this research we propose an algorithm, based on the Markov Chain Model and the PageRank algorithm, for computing the spreading of the transitivity phenomenon of network topology and the importance of nodes. The importance of nodes in every network is determined only by considering the structure of the network topology and edge weights without taking complex dynamics of spreading into account, so the computation is rapid and easily analyzed.
We take epidemiological data as a case study to verify the correctness of our algorithm. Furthermore, a genetic algorithm can optimize the parameters to simulate an actual dynamic structure of network topology in the real epidemic spreading. Our experimental results show that the importance of nodes in network topology is correlated with epidemiological data. The algorithm can deal with the phenomenon of transitivity and analyze the importance of nodes efficiently. Besides, the solution searched by genetic algorithm can reflect the spreading dynamics of the real epidemics and the causes of spreading components.

並列關鍵字

Network Topology ； Transitivity ； Markov Chain Model ； PageRank Algorithm ； Genetic Algorithm

參考文獻

Andersen, R., Chung, F., & Lang, K. (2006). Local graph partitioning using pagerank vectors.

Back, T., & Schwefel, H. (1993). An overview of evolutionary algorithms for parameter optimization. Evolutionary computation, 1(1), 1-23.

Centola, D. (2010). The spread of behavior in an online social network experiment. Science, 329(5996), 1194.

Goldberg, D. (1989). Genetic algorithms in search, optimization, and machine learning: Addison-wesley.

Grais, R., Hugh Ellis, J., & Glass, G. (2003). Assessing the impact of airline travel on the geographic spread of pandemic influenza. European Journal of Epidemiology, 18(11), 1065-1072.