基於門檻值之連鎖啟動程序分析

Abstract

假設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.