請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/44907
標題: | 基於門檻值之連鎖啟動程序分析 Analysis of Threshold-Based Processes of Cascading Activation in Graphs |
作者: | Ching-Lueh Chang 張經略 |
指導教授: | 呂育道(Yuh-Dauh Lyuu) |
關鍵字: | 不可逆性動態寡佔,全域傾瀉,不可逆性轉換集,無序二元雪崩,社群影響,傳染性,集體行為, Irreversible dynamic monopoly,Global cascade,Irreversible conversion set,Unordered binary avalanche,Social influence,Contagion,Collective behavior, |
出版年 : | 2010 |
學位: | 博士 |
摘要: | 假設G(V,E)為一簡單的有向或無向圖,且每個v∈V都被賦予一值φ(v)≥1。許多文獻不斷探討如下的過程及其變形:一開始,我們啟動若干個被稱為種子的節點,之後,每當指向一節點v之已啟動節點達到φ(v)個或更多時,v就會跟著被啟動,整個過程將一直持續到沒有更多節點能被啟動為止。在下列的幾種情形中,我們探討了啟動δ∈[0,1]比例或更多的節點所需之最少種子數:
˙G為一艾狄胥-倫依隨機圖(Erdos-Renyi random graph)且任何一節點皆會在其有ρ∈(0,1]比例或更多的鄰居被啟動時,也跟著被啟動。 ˙G為一無向連通圖且任何一節點皆會在其有嚴格超過一半的鄰居被啟動時,也跟著被啟動。 ˙G為一節點入度(indegree)皆非零之有向圖,且對任何一節點而言,當指向該節點之其他所有節點有至少一半被啟動時,該節點也會跟著被啟動。 ˙G為一節點入度皆非零之有向圖,且對任何一節點而言,當指向該節點之其他所有節點有嚴格超過一半被啟動時,該節點也會跟著被啟動。 ˙G為一有向圖,每個點v被賦予的φ(v)值皆非零且δ=1。 我們也探究了找尋最少種子以啟動所有的節點,究竟需耗費多少計算資源。 Let $G(V,E)$ be a simple directed or undirected graph and $phi(v)geq 1$ for each $vin V$. The following process and its variants have been studied extensively in the literature. Initially, only a set of vertices, called the seeds, are active. Thereafter, an inactive vertex $v$ is activated when at least $phi(v)$ of its in-neighbors are active. The process ends when no additional vertices can be activated. We derive bounds on the minimum number of seeds needed to activate at least a $deltain [0,1]$ fraction of the vertices at the end, for the following cases: egin{itemize} item $G$ is an Erd{H{o}}s-R{'e}nyi random graph. An inactive vertex is activated when at least a $ hoin [0,1]$ fraction of its neighbors are active. item $G$ is a connected undirected graph. An inactive vertex is activated when more than half of its neighbors are active. item $G$ is a directed graph with positive indegrees. An inactive vertex is activated when at least half of its in-neighbors are active. item $G$ is a directed graph with positive indegrees. An inactive vertex is activated when more than half of its in-neighbors are active. item $G$ is a directed graph, $phi(v)geq 1$ for all $vin V$ and $delta=1$. end{itemize} We also investigate the computational hardness of finding a minimum set of seeds activating all vertices at the end. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/44907 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 645.44 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。