اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDynamic monopolies in directed graphs: the spread of unilateral influence in social networks
171
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $G$ be a directed graph such that the in-degree of any vertex $G$ is at least one. Let also ${mathcal{tau}}: V(G)rightarrow Bbb{N}$ be an assignment of thresholds to the vertices of $G$. A subset $M$ of vertices of $G$ is called a dynamic monopoly for $(G,tau)$ if the vertex set of $G$ can be partitioned into $D_0cup... cup D_t$ such that $D_0=M$ and for any $igeq 1$ and any $vin D_i$, the number of edges from $D_0cup... cup D_{i-1}$ to $v$ is at least $tau(v)$. One of the most applicable and widely studied threshold assignments in directed graphs is strict majority threshold assignment in which for any vertex $v$, $tau(v)=lceil (deg^{in}(v)+1)/2 rceil$, where $deg^{in}(v)$ stands for the in-degree of $v$. By a strict majority dynamic monopoly of a graph $G$ we mean any dynamic monopoly of $G$ with strict majority threshold assignment for the vertices of $G$. In this paper we first discuss some basic upper and lower bounds for the size of dynamic monopolies with general threshold assignments and then obtain some hardness complexity results concerning the smallest size of dynamic monopolies in directed graphs. Next we show that any directed graph on $n$ vertices and with positive minimum in-degree admits a strict majority dynamic monopoly with $n/2$ vertices. We show that this bound is achieved by a polynomial time algorithm. This upper bound improves greatly the best known result. The final note of the paper deals with the possibility of the improvement of the latter $n/2$ bound.
قيم البحث
اقرأ أيضاً
Let $G$ be a graph and ${mathcal{tau}}: V(G)rightarrow Bbb{N}cup {0}$ be an assignment of thresholds to the vertices of $G$. A subset of vertices $D$ is said to be a dynamic monopoly corresponding to $(G, tau)$ if the vertices of $G$ can be partition
ed into subsets $D_0, D_1,..., D_k$ such that $D_0=D$ and for any $iin {0, ..., k-1}$, each vertex $v$ in $D_{i+1}$ has at least $tau(v)$ neighbors in $D_0cup ... cup D_i$. Dynamic monopolies are in fact modeling the irreversible spread of influence in social networks. In this paper we first obtain a lower bound for the smallest size of any dynamic monopoly in terms of the average threshold and the order of graph. Also we obtain an upper bound in terms of the minimum vertex cover of graphs. Then we derive the upper bound $|G|/2$ for the smallest size of any dynamic monopoly when the graph $G$ contains at least one odd vertex, where the threshold of any vertex $v$ is set as $lceil (deg(v)+1)/2 rceil$ (i.e. strict majority threshold). This bound improves the best known bound for strict majority threshold. We show that the latter bound can be achieved by a polynomial time algorithm. We also show that $alpha(G)+1$ is an upper bound for the size of strict majority dynamic monopoly, where $alpha(G)$ stands for the matching number of $G$. Finally, we obtain a basic upper bound for the smallest size of any dynamic monopoly, in terms of the average threshold and vertex degrees. Using this bound we derive some other upper bounds.
In this paper, we study independent domination in directed graphs, which was recently introduced by Cary, Cary, and Prabhu. We provide a short, algorithmic proof that all directed acyclic graphs contain an independent dominating set. Using linear alg
ebraic tools, we prove that any strongly connected graph with even period has at least two independent dominating sets, generalizing several of the results of Cary, Cary, and Prabhu. We prove that determining the period of the graph is not sufficient to determine the existence of an independent dominating set by constructing a few examples of infinite families of graphs. We show that the direct analogue of Vizings Conjecture does not hold for independent domination number in directed graphs by providing two infinite families of graphs. We initialize the study of time complexity for independent domination in directed graphs, proving that the existence of an independent dominating set in directed acyclic graphs and strongly connected graphs with even period are in the time complexity class $P$. We also provide an algorithm for determining existence of an independent dominating set for digraphs with period greater than $1$.
Let $D$ be a strongly connected digraph. The average distance $bar{sigma}(v)$ of a vertex $v$ of $D$ is the arithmetic mean of the distances from $v$ to all other vertices of $D$. The remoteness $rho(D)$ and proximity $pi(D)$ of $D$ are the maximum a
nd the minimum of the average distances of the vertices of $D$, respectively. We obtain sharp upper and lower bounds on $pi(D)$ and $rho(D)$ as a function of the order $n$ of $D$ and describe the extreme digraphs for all the bounds. We also obtain such bounds for strong tournaments. We show that for a strong tournament $T$, we have $pi(T)=rho(T)$ if and only if $T$ is regular. Due to this result, one may conjecture that every strong digraph $D$ with $pi(D)=rho(D)$ is regular. We present an infinite family of non-regular strong digraphs $D$ such that $pi(D)=rho(D).$ We describe such a family for undirected graphs as well.
Let $G$ be a graph and $tau$ be an assignment of nonnegative integer thresholds to the vertices of $G$. A subset of vertices $D$ is said to be a $tau$-dynamic monopoly, if $V(G)$ can be partitioned into subsets $D_0, D_1, ldots, D_k$ such that $D_0=D
$ and for any $iin {0, ldots, k-1}$, each vertex $v$ in $D_{i+1}$ has at least $tau(v)$ neighbors in $D_0cup ldots cup D_i$. Denote the size of smallest $tau$-dynamic monopoly by $dyn_{tau}(G)$ and the average of thresholds in $tau$ by $overline{tau}$. We show that the values of $dyn_{tau}(G)$ over all assignments $tau$ with the same average threshold is a continuous set of integers. For any positive number $t$, denote the maximum $dyn_{tau}(G)$ taken over all threshold assignments $tau$ with $overline{tau}leq t$, by $Ldyn_t(G)$. In fact, $Ldyn_t(G)$ shows the worst-case value of a dynamic monopoly when the average threshold is a given number $t$. We investigate under what conditions on $t$, there exists an upper bound for $Ldyn_{t}(G)$ of the form $c|G|$, where $c<1$. Next, we show that $Ldyn_t(G)$ is coNP-hard for planar graphs but has polynomial-time solution for forests.
Existing socio-psychological studies suggest that users of a social network form their opinions relying on the opinions of their neighbors. According to DeGroot opinion formation model, one value of particular importance is the asymptotic consensus v
alue---the sum of user opinions weighted by the users eigenvector centralities. This value plays the role of an attractor for the opinions in the network and is a lucrative target for external influence. However, since any potentially malicious control of the opinion distribution in a social network is clearly undesirable, it is important to design methods to prevent the external attempts to strategically change the asymptotic consensus value. In this work, we assume that the adversary wants to maximize the asymptotic consensus value by altering the opinions of some users in a network; we, then, state DIVER---an NP-hard problem of disabling such external influence attempts by strategically adding a limited number of edges to the network. Relying on the theory of Markov chains, we provide perturbation analysis that shows how eigenvector centrality and, hence, DIVERs objective function change in response to an edges addition to the network. The latter leads to the design of a pseudo-linear-time heuristic for DIVER, whose computation relies on efficient estimation of mean first passage times in a Markov chain. We confirm our theoretical findings in experiments.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
