# The Structure of Optimal and Near Optimal Target Sets in Consensus Models

Fern Y. Hunt
Applied and Computational Mathematics Division
National Institute of Standards and Technology
Gaithersburg,Maryland 20899

###### Abstract

We consider the problem of identifying a subset of nodes in a network that
will enable the fastest spread of information in a decentralized
environment.In a model of communication based on a random walk on an
undirected graph, the optimal set over all sets of the same or smaller
cardinality minimizes the sum of the mean first arrival times to the set by
walkers starting at nodes outside the set. The problem originates from the
study of the spread of information or consensus in a network and was
introduced in this form by V.Borkar et al. in 2010. More generally, the work
of A. Clark et al. in 2012 showed that estimating the fastest rate of
convergence to consensus of so-called leader follower systems leads to a
consideration of the same optimization problem.

The set function $F$ to be minimized is supermodular and therefore the greedy
algorithm is commonly used to construct optimal sets or their approximations.
In this paper, the problem is reformulated so that the search for solutions is
restricted to optimal and near optimal subsets of the graph. We prove
sufficient conditions for the existence of a greedoid structure that contains
feasible optimal and near optimal sets. It is therefore possible we
conjecture, to search for optimal or near optimal sets by local moves in a
stepwise manner to obtain near optimal sets that are better approximations
than the factor $(1-1/e)$ degree of optimality guaranteed by the use of the
greedy algorithm. A simple example illustrates aspects of the method.

##  1 Random Walk Consensus Model

Given a connected graph $G=(V,E)$, with vertices or nodes $V$ and edges $E$,
we imagine a random walker situated at a node $i\in V$, moving to another node
$j\in V$ in a single discrete time step. The choice of $j$ is random and has
probability,

$Prob\\{i\rightarrow j\\}=\begin{cases}p_{ij}>0,&\text{if }(i,j)\in E\\\
p_{ij}=0&\text{otherwise.}\end{cases}$ (1)

The matrix $\mathbb{P}=(p_{ij})_{i,j=1\cdots N}$ is the transition matrix of a
Markov chain which in this paper, is assumed to be irreducible and aperiodic
([7]). $N$ is the number of nodes and as in [1] the spread of information is
described in terms of a process that is dual to the movement from informed to
uninformed nodes. A random walk begins outside a pre-determined set $A$ of
informed target nodes and ends at $A$. Starting at node $i\notin A$, a random
walker first reaches the set $A$ at a hitting time $T_{A}=\min\\{n>0:X_{n}\in
A\\}$, where $X_{n}$ is the node occupied by the walker at time $n$. The
hitting time is closely related to the rate of convergence in a leader-
follower model of Clark et al., as well as other consensus models [3, 10],
[1]. The effectiveness of a set A in the spread of information by random walks
can then be measured by,

$F(A)=\left({\sum}_{i\notin A}h(i,A)\right),$ (2)

where $h(i,A)=\mathbf{E_{i}}[T_{A}]$, is the expected number of steps to $A$
starting at node $i$. When $F(A)$ is small, $A$ is a desirable choice of
informed nodes, but is a poor choice if $F(A)$ is large. A standard result in
Markov chain theory tells us that $h(i,A)$ is the ith component of the vector
$\mathsf{H}$, which solves the linear equation.

${\LARGE\mathsf{H}}=\bf{1}+\mathbb{P}_{A}{\LARGE\mathsf{H}}$ (3)

where $\mathbf{1}$ is a column vector of $N-|A|$ ones and $\mathbb{P}_{A}$ is
the matrix that results from crossing out the rows and columns of $\mathbb{P}$
corresponding to the nodes of $A$ [7]. Limited resources can constrain the
maximum size of the subset to be selected so it makes sense then to ask for
the most effective spreader subject to a cardinality constraint, i.e.

$\min_{A\subset V,\\\ \ |A|\leq M}F(A)$ (4)

Borkar et al. [1] showed that for arbitrary subsets $A,\ B\subseteq V\,$,
$F(A\cap B)+F(A\cup B)\geq F(A)+F(B)$, that is, $F$ is a supermodular
function. Clark et al. in [3] discussed a continuous time leader-follower
problem where a set $A$ of leader nodes are assigned fixed function values and
the remaining follower nodes update their function values by weighted exchange
with their neighbors with weights defined by equation (1). If $G$ is strongly
connected, the node function values converge to a consensus value (vector)
determined by the leader nodes and the rate of convergence has a connection to
precisely the random walk problem we are describing. In [3], two optimization
problems are posed. The first, is to select up to $M$ leaders in order to
minimize the convergence error. Given the random walk connection the problem
in Clark is equivalent to the the problem posed in equation (4).

Since $F$ is supermodular, both references [1],[3] make use of the work of
[11] to devise a greedy algorithm that builds an approximate solution to the
optimization problem (4) in a stepwise fashion until a set of cardinality $M$
is reached. Recall that at the first stage of construction, the node with the
smallest value of $F$ among the nodes is selected. At the $p$th stage the node
is added to the set that results in a set of cardinality $p+1$ with the
smallest value of $F$. Using the results of [11], Borkar et al. were able to
give some guarantee of the quality of the approximation of a weaker version of
the optimization problem with the additional constraint that the set contain
an element $\\{a\\}$. If $F_{a}^{*}$ is the optimal value of this weaker
optimization problem and $A_{M}(a)$ is the greedy approximation obtained by
starting the algorithm with the set $\\{a\\}$, then

$F(\\{a\\})-F(A_{M}(a))\geq(1-\frac{1}{e})(F(\\{a\\})-F_{a}^{*})$ (5)

In the continuous time setting, Clark et al. obtained a similar inequality but
it is independent of the choice of a required initial element.

It will be instructive in what follows to see the results of applying the
greedy algorithm to a specific graph. In all the examples discussed in this
paper we assume that for every neighbor $j$ of node $i$,
$p(i,j)=\frac{1}{deg(i)}$.

EXAMPLE 1 Figures 1-5 show the picture of a graph $G$ with $9$ nodes including
the nodes of the optimal set of cardinality $K$ for $K=1$ through $5$. In this
example the optimal set of a given cardinality does not contain an optimal
subset that is one element smaller. Thus, for example the optimal $3$ element
set cannot be obtained from the (unique) $2$ element set. In turn the $2$
element set does not contain the $1$ element optimal set. Therefore the greedy
algorithm does not produce optimal sets.

In this paper,the optimization problem is reformulated with a view towards
improving the guarantees of the greedy algorithm proved in [1], [3]. We seek
solutions or approximations of the problem for some cardinality $M$ where
$M<K$ where $K$ fixed, is the cardinality of a vertex cover of the graph. A
vertex cover is an optimal set for its cardinality, so we first seek solutions
of problem (4) that are subsets of the cover. This is done in section 2 in
order to provide motivation for our method. Since (as we show) it is not
always possible to find optimal subsets in an arbitrary vertex cover, the
search space is enlarged to a class of optimal and near optimal sets of a
specified degree of optimality relative to the vertex cover (see the
definition in (9)). These sets are introduced in section 2.2. Our main result
is a sufficient condition for the existence of a gredoid structure containing
optimal and near optimal sets (see Theorem 1 and Corollaries 1 and 2). The
properties of the greedoid enable one to make local moves (for example by
adding or deleting certain elements of a set) that preserve the optimality or
near optimality of feasible sets. We have observed that solutions of the
original optimization problem are well approximated by high ranking near
optimal sets and the quality of the approximations can exceed the $(1-1/e)$
factor guaranteed by the greedy algorithm. In section 2.3 we show an
illustrative example. The key is the ability to improve the approximations by
searching the greedoid structure. This is formalized in section 3.1, where we
briefly introduce the greedoid graph whose nodes are feasible sets. Properties
of adjacent nodes in this graph enable local moves among sets that can be used
to improve approximations and thus lay the groundwork for deterministic local
search methods such as branch and bound on the one hand or stochastic search
on the other. The paper concludes in section 4 with a summary of the results
and questions for further research.

##  2 Finding and Approximating Optimal Sets

###  2.1 Maximal Matches

The optimization problem as posed in equation(4) assumes no advance knowledge
about the optimal set or other possibly related subsets of $G$. In this
section we seek to explore alternative formulations of the problem that could
lead to better approximations of the optimal set. The next definition will be
helpful in the discussion that follows:

###### Definition 1

A vertex cover of a graph $G=(V,E)$ is a set of vertices that are incident to
every edge in $E$.

###### Lemma 1

Let $A$ be a vertex cover of the graph $G$, with $K=|A|$. Then $A$ solves the
optimization problem (4) for $M=K$.

Proof: Since every edge of $G$ is incident to an element of $A$, a random
walker starting at a vertex $i$ outside of $A$ must hit $A$ at the first step.
That is $h(i,A)=1$. Now equation (3) implies that $h(i,A)\geq 1$ so it follows
that $A$ must be an optimal set for its own cardinality. $\Box$

Thus the problem of finding an optimal subset is partially resolved if one can
construct a vertex cover. Fortunately, there is a simple greedy algorithm
(sometimes called the Two Opt algorithm) for constructing a maximal match,
whose vertices are a vertex cover.

###### Definition 2

A maximal match of a graph is a set of edges that are non-adjacent (i.e. they
do not share a common vertex). The set is maximal in the sense that there is
no larger set with this property.

As is well known [6], the vertices of a maximal match form a vertex cover. To
see why note that every edge $e$ in $E$ is either an edge of a maximal match
or is adjacent to such an edge. Thus $e$ contains a vertex in the match. That
is, $e$ is incident to some vertex in the match so the definition of vertex
cover is satsified. Now let $\mathscr{M}$ be the set of vertices of the
maximal match that was constructed using the Two Opt algorithm. It can be
shown ([4]) that,

$OPT\leq|\mathscr{M}|\leq 2\cdot OPT,$ (6)

where $OPT$ is the cardinality of the minimal vertex cover. The run time of
Two Opt is $\Large{O}(|E|)$ [4]. Because supersets of a vertex cover are
optimal sets and since we observe that optimal sets are often subsets of a
vertex cover, it is natural to seek solutions of the optimization problem
among the subsets of $\mathscr{M}$:

$\min_{A\subset\mathscr{M},\\\ |A|\leq M}F(A).$ (7)

Recall that the graph in EXAMPLE 1 has optimal sets which cannot be found by
application of the greedy algorithm. However when the Two Opt algorithm is
used to obtain edges of a maximal match $(1,3),(5,6),(7,8)$, the vertices
$\mathscr{M}$, contain optimal subsets for $M=1,2,3,4,6$. In contrast to the
greedy approach of building up to an optimal set, we start with a maximal
match and obtain optimal sets of smaller cardinality as subsets. Unfortunately
as the next example illustrates, this approach is not always successful.

EXAMPLE 2:
The vertices of two maximal matches for a graph are shown in Figure 6. The
figure on the left shows a maximal match whose vertex set $\mathscr{M}$
contains no optimal subsets except itself while the match shown on the right
contains subsets that are optimal sets for $M=1$ through $4$. Both maximal
matches were obtained using the Two Opt algorithm.

Do we have a way to predict when optimal sets of predetermined cardinality are
contained in a maximal match? Presently we do not. The reason is that
optimality is not always preserved by adding or removing elements from a
single optimal set. However as discussed in the next section and 3.1 there is
a greedoid containing optimal and near optimal sets (see the definition in 9)
with a structure that is preserved under such operations. Moreover in section
3 we prove sufficient conditions for a vertex cover to contain optimal and
near optimal subsets (Proposition 4).

###  2.2 Optimal and Near Optimal Sets

In section 1 a measure of the spread effectiveness of sets was introduced in
(2). It will be convenient to convert this to a rank defined on subsets of
$V$. In particular, suppose there exists a maximal match with $K$ vertices. We
will order all non-empty subsets $A\subseteq V$ such that $|A|\leq K$ with a
ranking function $\rho(A)$ defined as,

$\rho(A)=\frac{F_{max}-F(A)}{F_{max}-F_{min}}$ (8)

where $F_{max}=\max_{\emptyset\neq A\subseteq V|A|\leq K}\large F(A)$, and
$F_{min}$ is the corresponding minimum. $F_{min}$ can be calculated by
computing $F$ for a maximal match of cardinality $K$, while $F_{max}$ is the
maximal value of $F$ among all one element subsets. We assume that
$F_{max}\neq F_{min}$. If this were not the case, $F(A)$ would have the same
value for any non-empty subset $A$ with $|A|\leq K$. Thus any $A$ would be a
solution of the problem.

If $A$ is optimal set of cardinality $K$, then $\rho(A)=1$, the maximum value
of $\rho$, conversely the worst performing set has value $0$. An optimal set
of size $M<K$, has the largest $\rho$ value among sets of size $M$. For a
constant $c,\,0<c\leq 1$ and $K$, the non-empty set

$\large{\mathnormal{L}_{c,K}}=\\{A:A\subseteq V,|A|\leq K,\rho(A)\geq c\\}$
(9)

defines a set of optimal and near optimal subsets, with the degree of near
optimality depending of course on $c$. The structure of optimal and near
optimal sets is conveniently described in terms of a concept in combinatorial
optimization known as a greedoid [9, 2].

###### Definition 3

Let $\mathbf{E}$ be a set and let $\mathscr{F}$ be a collection of subsets of
$\mathbf{E}$. The pair $(\mathbf{E},\mathscr{F})$ is called a greedoid if
$\mathscr{F}$ satisfies

  * •

$\mathbf{G1}:$ $\emptyset\in\mathscr{F}$

  * •

$\mathbf{G2}:$ For $A\in\mathscr{F}$ non-empty, there exists an $a\in A$ such
that $A\setminus\\{a\\}\in\mathscr{F}$

  * •

$\mathbf{G3}:$ Given $X$, $Y$ $\in\mathscr{F}$ with $|X|>|Y|$, there exists an
$x\in X\setminus Y$, such that $Y\cup\\{x\\}\in\mathscr{F}$

A set in $\mathscr{F}$ is called feasible. Note that $\mathbf{G2}$ implies
that a single element can be removed from a feasible set $X$ so that the
reduced set is still feasible. By repeating this process the empty set
eventually is reached. Conversely starting from the empty set, $X$ can be
built up in steps using the $\mathbf{G3}$ property.
Our first step is to show that $\mathnormal{L_{c,K}}$ satisfies condition
$\mathbf{G3}$ of the definition for $0<c\leq 1$, $0\leq K\leq N$ (Proposition
1). The proof depends on several short lemmas. The first uses an adaptation of
an argument in Clark et al.

###### Lemma 2

Let $S\subseteq V$, $u\in V\setminus S$. Then $F(S)\geq F(S\cup\\{u\\})$.

Proof: Suppose $S$, a set of nodes is a target set for the random walk. Let
$E_{ij}^{l}(S)$ be the event, $E_{ij}^{l}(S)=\\{X_{0}=i\in V,\ X_{l}=j\in
V\setminus S,\ X_{r}\notin S,\ 0\leq r\leq l\\}$. Thus paths of the random
walk start at $i$ and arrive at $j$ without visiting $S$ during the interval
$[0,l]$. Also define the event
$F_{ij}^{l}(S,u)=E_{ij}^{l}(S)\cap\bigcup_{m=0}^{l}\\{X(m)=u\\}$ where
$u\notin S$. Paths in this event also start at $i$ and arrive at $j$ without
visiting $S$, but must visit the element $u$ at some time during the interval
$[0,l]$. Since a path either visits $u$ in the time interval $[0,l]$ or it
does not, it follows that:

$E_{ij}^{l}(S)=E_{ij}^{l}(S\cup\\{u\\})\cup F_{ij}^{l}(S,u)$ (10)

We have $E_{ij}^{l}(S\cup\\{u\\})\bigcap F_{ij}^{l}(S,u)=\emptyset$. This
implies that,

$\chi(E_{ij}^{l}(S))=\chi(E_{ij}^{l}(S\cup\\{u\\}))+\chi(F_{ij}^{l}(S,u))$
(11)

and therefore:

$\chi(E_{ij}^{l}(S))\geq\chi(E_{ij}^{l}(S\cup\\{u\\})$ (12)

Here $\chi(A)$ is the indicator function of the set $A$. Recalling that
$T_{S}$ is the hitting time for set $S$, the following relation comes from
taking the expection of $\chi(E_{ij}^{l}(S))$ on the left hand side of (12)
summing over all $j\in V\setminus S$. Here $\mathbb{E}$ denotes expectation.

$\mathbf{Prob}\\{T_{S}>l|X_{0}=i\\}=\mathbb{E}\left(\sum_{j\in V\setminus
S}\chi(E_{ij}^{l}(S))\right)$ (13)

A similar result is obtained for $T_{S\cup\\{u\\}}$ from taking the
expectation of $\chi(E_{ij}^{l}(S\cup\\{u\\}))$ on the right hand side of (12)
and summing over $j\in V\setminus S$. Summing once again over all $l\geq 1$
results in the inequality,

$h(i,S)\geq h(i,S\cup\\{u\\})$ (14)

Finally on summing (14) over all $i$ and recalling the definition of $F$
(equation (2)) one obtains the result to be proved. $\Box$

The following result uses that fact that $F$ is supermodular.

###### Lemma 3

For $\bar{c}>0$, let $\mathscr{P}=\\{X\subseteq V\colon F(X)\geq\bar{c}>0\\}$.
If $A,B\in\mathscr{P}$ where $|A|=|B|$ and $|A\cap B|=|A|-1$, then $A\cap
B\in\mathscr{P}$.

Proof: The hypothesis implies the existence of a set $X$ such that
$A=X\cup\\{a\\}$ and $B=X\cup\\{b\\}$ with $a\neq b,a,b,\in V$. The
supermodular property of $F$ implies that:

$F(X\cup\\{a\\}\cup\\{b\\})+F(X)\geq F(X\cup\\{a\\})+F(X\cup\\{b\\})$ (15)

Rearranging we have,

$F(X)\geq F(X\cup\\{a\\})+[F(X\cup\\{b\\})-F(X\cup\\{a\\}\cup\\{b\\})]$ (16)

Thus on writing $X=A\cap B$, using the hypothesis on $A$, and then applying
Lemma 2 to the bracketed quantity, we have,

$F(A\cap B)\geq F(A)\geq\bar{c}$

$\Box$.
The following lemma is part of a result in [9, 2] on paving greedoids.

###### Lemma 4

If $\mathscr{P}$ is any class of sets satisfying the conclusion of Lemma 3,
$\mathscr{S}=2^{V}\setminus\mathscr{P}$ has property $\mathbf{G3}$. That is,
given any $A,\ B\in\mathscr{S}$, with $|A|>|B|$, there is an $a\in A\setminus
B$ such that $B\cup\\{a\\}\in\mathscr{S}$.

Proof: Suppose the conclusion is false. If $|A\setminus B|=1$, then for $a\in
A\setminus B$, $B\cup\\{a\\}\in\mathscr{P}$. But $A=B\cup\\{a\\}$. To see this
suppose there is some $a^{{}^{\prime}}\neq a$ that is not in $B$. Then
$A\setminus B$ contains $a^{{}^{\prime}}$ so $|A\setminus B|>1$ so this is a
contradiction. Thus $A=B\cup\\{a\\}$, but $A\in\mathscr{S}$, and this is also
a contradiction. Suppose next that $|A\setminus B|>1$. Then there exists $a$,
$a^{{}^{\prime}}$ $\in A\setminus B$. We have $B\cup\\{a\\}$ and
$B\cup\\{a^{{}^{\prime}}\\}\in\mathscr{P}$. Thus the conclusion of Lemma 3
implies that $B\in\mathscr{P}$, which is a contradiction. $\Box$

###### Proposition 1

For $0<c\leq 1$ and $0<K\leq N$, let $\mathnormal{L}_{c,K}$ be the class of
sets defined in equation (9). Then $\mathnormal{L}_{c,K}$ satisfies condition
$\mathbf{G3}$.

Proof: If $\mathscr{P}$ is the set defined in Lemma 4 then
$\mathnormal{L_{c,K}}=\mathscr{S}$ for some $c$. In fact we may set
$c=\frac{F_{max}-\bar{c}}{F_{max}-F_{min}}$. If $F_{min}\leq\bar{c}\leq
F_{max}$ , we have $0\leq c\leq 1$. $\mathnormal{L_{c,K}}$ satisfies the
conclusion of Lemma 4 and therefore it satisfies property $\mathbf{G3}$.
$\Box$

The proposition establishes that $L_{c,K}$ satisfies the $\mathbf{G3}$
property for greedoids. However, $\mathbf{G2}$ does not hold. For example if
the set $A$ has cardinality $m$ where $m$ is the size of the smallest set in
$L_{c,K}$ then $A\setminus\\{a\\}$ cannot be in $\mathnormal{L_{c,K}}$ for any
element $a\in A$. Conversely, let $c_{m}=\max_{|X|\leq m}\rho(X)$. If
$c_{m}\geq c>c_{m-1}$ then $m$ is the size of the smallest set in
$\mathnormal{L_{c,K}}$. To create a class of sets with the $\mathbf{G2}$
property, one constructs subsets of $G_{m}$ of size $n\leq m$ that satisfy
$\mathbf{G3}$, while sets $G_{n}$ for $n>m$ are culled so the remaining sets
satisfy $\mathbf{G2}$. The greedoid will then consist of selected subsets and
supersets of $G_{m}$ This construction is illustrated in the next section
(section 2.3) where an example of a greedoid is presented and our proposed
method for solving problem (4) is demonstrated. It is based on restricting the
search for solutions to feasible optimal and near optimal sets in the
greedoid. Following this, in section 3, sufficient conditions for the
existence of a greedoid are presented as well as proofs.

###  2.3 Greedoid Based Approach to the Optimization Problem

Let $G$ be the graph discussed in EXAMPLE 1 of section 2.1. The smallest sets
in $\mathnormal{L_{7/8,8}}$ have cardinality $m=2$. Any sets in
$\mathnormal{L_{7/8,8}}$ will have guaranteed degree of optimality $7/8$ as
defined by equation (8). Our method is based on searching for optimal and near
optimal sets that are the feasible sets of the greedoid constructed from
$G_{2}$. Values of $F$ for two element sets are computed in advance to start
the procedure. In addition to $G_{2}$ itself, the empty set and selected one
element subsets of $G_{2}$ must also be included. These sets arise from the
pairwise intersection of sets in $G_{2}$ (listed below) and in addition they
must satisfy $\mathbf{G3}$ for every set in $G_{2}$. The two element sets are:

Elements of $G_{2}=\widehat{G}_{2}$

$\displaystyle\\{3,7\\}^{*},\\{2,8\\}$ (17)
$\displaystyle\\{1,7\\}^{*},\\{1,9\\}$ $\displaystyle\\{2,7\\},\\{2,9\\}$
$\displaystyle\\{3,8\\}^{*},\\{5,7\\}^{*}$ $\displaystyle\\{3,9\\},\\{1,4\\}$
$\displaystyle\\{3,4\\},\\{1,6\\}^{*}$ $\displaystyle\\{3,6\\}^{*},\\{2,4\\}$
$\displaystyle\\{1,8\\}^{*},\\{2,6\\}$

The one element sets of the greedoid are therefore
$\widehat{G}_{1}=\\{1,2,3,7\\}$. The two element feasible sets are defined to
be supersets of $\widehat{G}_{1}$. Here that is all of $G_{2}$, no culling is
necessary. Once $n>m$, the feasible sets of the greedoid are subsets of
$G_{n}$ that are supersets of $\widehat{G}_{n-1}$. Thus feasible sets of
cardinality $3$, $\widehat{G}_{3}$ are sets in $G_{3}$ that are supersets of
$\widehat{G}_{2}$. It will be helpful in our discussion of the method to list
some of the elements in the greedoid. It can be checked that the displayed
sets satisfy $\mathbf{G1}$-$\mathbf{G3}$.

$\displaystyle\text{10 elements of }\widehat{G}_{3}$ $\displaystyle\text{10
elements of }\widehat{G}_{4}$ $\displaystyle\text{10 elements of
}\widehat{G}_{5}$ (18) $\displaystyle\\{3,4,9\\}$ $\displaystyle\\{2,5,7,9\\}$
$\displaystyle\\{2,3,4,6,9\\}$ $\displaystyle\\{3,6,8\\}$
$\displaystyle\\{2,5,7,8\\}$ $\displaystyle\\{2,3,4,6,8\\}$
$\displaystyle\\{1,5,7\\}$ $\displaystyle\\{1,5,7,9\\}$
$\displaystyle\\{1,3,4,6,9\\}$ $\displaystyle\\{2,5,7\\}$
$\displaystyle\\{1,5,7,8\\}$ $\displaystyle\\{1,3,4,6,8\\}$
$\displaystyle\\{3,4,7\\}$ $\displaystyle\\{3,4,6,9\\}$
$\displaystyle\\{2,3,6,7,8\\}$ $\displaystyle\\{3,5,7\\}$
$\displaystyle\\{3,4,6,8\\}$ $\displaystyle\\{2,3,5,7,9\\}$
$\displaystyle\\{3,7,9\\}$ $\displaystyle\\{3,6,7,8\\}$
$\displaystyle\\{2,3,5,7,8\\}$ $\displaystyle\\{3,6,7\\}$
$\displaystyle\\{3,5,7,9\\}$ $\displaystyle\\{2,3,4,7,9\\}$
$\displaystyle\\{3,7,8\\}$ $\displaystyle\\{3,5,7,8\\}$
$\displaystyle\\{2,3,4,6,7\\}$ $\displaystyle\\{3,4,6\\}$
$\displaystyle\\{3,4,7,9\\}$ $\displaystyle\\{1,3,6,7,8\\}$

Suppose we try to solve the optimization problem (4) for $M=5$. One could
exhaustively compare the $F$ values for all possible $5$ element subsets.
Alternatively, one could apply the greedy algorithm to the best single
node(s).The thesis of this paper is that one can reduce the number of $5$
element sets to the smaller class of near optimal sets. For any $c>0$ this
class contains optimal $5$ element sets and approximations that are better
than the guarantees of the greedy algorithm approximations. The greedoid
properties enable the near optimal sets to be constructed from one-element
sets in a stepwise manner. Given the vertex cover for our example graph $G$,
$VC=\\{1,3,5,6,7,8\\}$ , a selection of two element sets in $\widehat{G_{2}}$
that are also subsets of $VC$ (indicated in display (17) by stars) was used to
create a sample of $5$ element candidate sets to be compared. Each starred $2$
element set was greedily extended to a $5$ element candidate set, step by
step. The left most column of display (19) shows the $3$ element sets obtained
from a greedy one element extension of the $2$ element sets. The next column
shows the corresponding $F$ values of each set. The third column is a list of
the $4$ element sets obtained by a one element greedy extension of the $3$
element sets. The column of corresonding $F$ values appears next. Finally the
fifth and sixth columns contain the $5$ element sets and the corresponding $F$
values respectively.

Our method is to offer the $5$ element set with smallest $F$ value as the
approximate(or actual) solution of the problem.In this case the set we obtain,
$A=\\{2,3,4,6,8\\}$ is a solution. Note that the same procedure can be used to
obtain the solutions to the problem for $M=3$ ($\\{3,6,8\\}$) and $M=4$
($\\{2,5,7,8\\}$ or $\\{1,5,7,9\\}$). The set $\\{1,5,7,8\\}$ is symmetric to
the latter sets so it is left out.

This example illustrates two more additional advantages of the greedoid
structure of optimal and near optimal sets. Optimal solutions that are not
subsets of the vertex cover but that are in the greedoid can still be found by
these methods. For example, $A$ is not a subset of $VC$. Secondly, an
approximate solution can be improved using greedoid properties $\mathbf{G2}$
and $\mathbf{G3}$. Thus given an approximation $B=\\{2,3,4,6,7\\}$ with
$F(B)=5.00$, the sequence
$\\{2,3,4,6,7\\}\rightarrow\\{3,4,6,7\\}\rightarrow\\{3,4,6\\}\rightarrow\\{3,4,6,8\\}\rightarrow
A=\\{2,3,4,6,8\\}$.Thus swapping the elements $7$ in $B$ with $8$ in $A$
preserves near optimality and in fact improves the value of $F$. Thus we
conjecture that navigation through the greedoid offers a systematic way of
accessing highly optimal solutions. Section 3.1 elaborates on this idea.

$\displaystyle\\{3,4,7\\}$ $\displaystyle 12.4$ $\displaystyle\\{3,4,7,9\\}$
$\displaystyle 8.00$ $\displaystyle\\{1,3,4,7,9\\}$ $\displaystyle 5.00$ (19)
$\displaystyle\\{3,6,7\\}$ $\displaystyle 12.4$ $\displaystyle\\{3,4,6,7\\}$
$\displaystyle 8.00$ $\displaystyle\\{2,3,4,6,7\\}$ $\displaystyle 5.00$
$\displaystyle\\{1,5,7\\}$ $\displaystyle 11.8$ $\displaystyle\\{1,5,7,9\\}$
$\displaystyle 7.40$ $\displaystyle\\{1,2,5,7,9\\}$ $\displaystyle 5.00$
$\displaystyle\\{2,5,7\\}$ $\displaystyle 11.8$ $\displaystyle\\{2,5,7,8\\}$
$\displaystyle 7.40$ $\displaystyle\\{1,2,5,7,8\\}$ $\displaystyle 5.00$
$\displaystyle\\{3,6,8\\}$ $\displaystyle 11.6$ $\displaystyle\\{3,4,6,8\\}$
$\displaystyle 7.82$ $\displaystyle\\{2,3,4,6,8\\}$ $\displaystyle 4.82$
$\displaystyle\\{1,4,6\\}$ $\displaystyle 13.9$ $\displaystyle\\{1,4,6,9\\}$
$\displaystyle 9.04$ $\displaystyle\\{1,4,5,6,9\\}$ $\displaystyle 6.21$

##  3 The Structure of Optimal and Near Optimal Target Sets

In this section we discuss how given a fixed $c$, a measure of near optimality
and $K$ the size of the largest optimal set under consideration, a greedoid
can be constructed from the set $L_{c,K}$ of optimal and near optimal sets.
Two sufficient conditions are presented (see Case I and Case II) for the
construction of a greedoid. Corollaries 1 and 2 describe the feasible sets of
the greedoid for Cases I and II respectively.

In order to construct a greedoid of optimal and near optimal sets one must
construct a class of sets from $L_{c,K}$ that satisfy $\mathbf{G2}$ as well as
$\mathbf{G3}$. The process can proceed along two tracks- one for sets of
cardinality $n\leq m$ and the second for sets of cardinality $n\geq m$. For
the latter, let $G_{n}=\\{A\in L_{c,K},\ |A|=n\\}$ for $n\geq m$. Lemma 4
shows that $\mathnormal{L}_{c,K}$ satisfies $\mathbf{G3}$. We set
$G_{m}=g_{m}$. Suppose $\widehat{G}_{n}$, for $m\leq n\leq K$,( respectively
$\\{\widehat{g}_{n}\\}_{1\leq n\leq m}$ ) is a class of supersets
(respectively subsets) of $\widehat{G}_{m}$ of cardinality $n$, with the
properties:

T1

$\widehat{g}_{m}=\widehat{G}_{m}\subseteq G_{m}$

T2

Every $A\in\widehat{g}_{n}$, contains a subset $B\in\widehat{g}_{n-1}$.

T3

For every $B\in\widehat{g}_{n-1}$, and $A\in\widehat{g}_{n}$, there is $p\in
A\setminus B$ such that $B\cup\\{p\\}\in\widehat{g}_{n}$.

T4

For $n>m$, $\widehat{G}_{n}=\\{A|A\in G_{n}\ A\supset B,\
B\in\widehat{G}_{n-1}\\}$,

then the collection of sets $\mathscr{F}_{c,K}=\\{\,\emptyset,\
(\widehat{g}_{n},\ 1\leq n\leq m),\,(\widehat{G}_{n},m\leq n\leq K),\\}$ are
the feasible sets for a greedoid over ground set $V$. This follows from Lemma
5 and its consequence Theorem 1.

###### Lemma 5

: Suppose $\widehat{G}_{n}$, $n\geq m$,(respectively $\widehat{g}_{n}$ $n<m$ )
are supersets (respectively subsets) of $G_{m}$ that satisfy
$\mathbf{T1}$-$\mathbf{T4}$. Then:

(1)

$f_{m}=\\{\,\emptyset,\ (\widehat{g}_{n},\ 1\leq n\leq m)\ \\}$ satisfies
$\mathbf{G1}$ and $\mathbf{G2}$.

(2)

If $A\in\widehat{G}_{n}$ for $n>m$, there is an $a\in A$ such that
$A\setminus\\{a\\}$ is in $\widehat{G}_{n-1}$.

(3)

If $B\in\widehat{g}_{n},n<m$ and $A\in f_{m}$ or $\in G_{k},k\geq m$, with
$|A|>|B|$, then there is an $a\in A$ such that
$B\cup\\{a\\}\in\widehat{g}_{n+1}$.

Proof: For statement (1) $\mathbf{G1}$ is clear. By $\mathbf{T2}$ for any
$A\in\widehat{g}_{n}$ there is a subset $B\in\widehat{g}_{n-1}$. Since $A$ has
cardinality $n$ and $B$ has cardinality $n-1$ we must have
$B=A\setminus\\{a\\}$ for some $a$. Thus $\mathbf{G2}$ holds. The proof of
statement(2) is the same as the proof of the $\mathbf{G2}$ property for
$f_{m}$ where here $\mathbf{T4}$ is used. To show (3), first suppose
$A\in\widehat{g}_{k},k>n$. By (1) we may apply $\mathbf{G2}$ repeatedly to
reduce $A$ to a set $A^{{}^{\prime}}\in\widehat{g}_{n+1}$. Then by
$\mathbf{T3}$, $B\cup\\{a\\}\in\widehat{g}_{n+1}$ for some $a\in
A^{{}^{\prime}}\setminus B$. Since $A^{{}^{\prime}}\subseteq A$, we have $a\in
A$. Next if $A\in\widehat{G}_{k}$ for $k\geq m$, either $A\in\widehat{G}_{m}$
or (2) can be applied repeatedly to produce a set in $\hat{G}_{m}$. By
$\mathbf{T1}$, $\widehat{G}_{m}=\widehat{g}_{m}$ so $A$ is reduced finally to
a set in $f_{m}$. Thus we obtain the conclusion by repeating the argument used
in the previous case. $\Box$.

###### Theorem 1

The class of sets $\mathscr{F}_{c,K}=\\{\,\emptyset,\ (\widehat{g}_{n},\ 1\leq
n\leq m-1),\,(\widehat{G}_{n},m\leq n\leq K)\\}$ is a class of feasible sets
for a greedoid over $V$.

Proof: By Proposition 1, $\mathbf{G3}$ is satisfied when $A\in\widehat{G_{n}}$
since $\widehat{G_{n}}\subseteq G_{n}$. $\mathbf{G3}$ is established for
$A\in\widehat{g_{k}}$ by Lemma 5 (3). Property $\mathbf{G2}$ for
$A\in\widehat{G}_{n}$ follows from Lemma 5 (2) when $n>m$ and Lemma 5 (1) and
$\mathbf{T1}$ when $A\in\widehat{G}_{m}=\widehat{g}_{m}$. If
$A\in\widehat{g}_{k}$, then $A$ satisfies $\mathbf{G2}$ because of Lemma 5
(1). Finally $\mathscr{F}_{c,K}$ clearly contains $\emptyset$. $\Box$.

Theorem 1 describes the feasible sets of the greedoid formed by sets
$\widehat{g}_{n}$ and $\widehat{G}_{n}$ when $\mathbf{T1-T4}$ are satisfied.
We next present two sufficient conditions for the existence of sets satisfying
$\mathbf{T1}$-$\mathbf{T4}$.

Case I: Suppose $G_{m}$ is a single set $G_{m}=\widehat{G}_{m}=\\{H\\}$. For
$n=m-1$, define $\hat{g}_{m-1}$ to be the class of subsets of $H$ of
cardinality $m-1$. When $n<m-1$, $\widehat{g}_{n-1}=\\{B|B\subset
H,|B|=n-1\\}$. $\widehat{G}_{n}$ is a superset of $G_{m}$ obtained by stepwise
addition of elements as described in $\mathbf{T4}$. If $G_{m}$ has more than
one set an arbitrary $H$ can be selected.

###### Corollary 1

The collection of sets $\\{\widehat{g}_{n}|n\leq m\\}$ and
$\\{\widehat{G}_{n}|n>m\\}$ in Case I, satisfy conditions $\mathbf{T1-T4}$,
therefore $\mathscr{F}(L_{c,K})=\\{\emptyset,\ (B:B\subset H,|B|<m),\ H,\
(A|A\supset H,|A|\leq K)\\}$ are the feasible sets of a greedoid.

Proof: $\mathbf{T1}$ and $\mathbf{T2}$ follow directly from the definitions of
$\widehat{G}_{n}$ and $\widehat{g}_{n}$. The property $\mathbf{T3}$ holds. To
see this suppose $A\in\widehat{g}_{n}$ and $B\in\widehat{g}_{n-1}$. Since $A$
and $B$ are subsets of $H$, $A$ has at least one element $p$ that is not in
$B$. Now $\hat{g}_{n}$ contains all subsets of $H$ of cardinality $n$ it must
have $B\cup\\{p\\}$. $\mathbf{T4}$ follows immediately from the definition of
$\widehat{G}_{n}$. $\Box$.

To describe the second sufficient condition for the existence and construction
of a greedoid we will need a couple of definitions.

Definition: Given subsets $A$ and $B$ of $V$, with an element $p\in V\setminus
B$ such that $A=B\cup\\{p\\}$, $A$ is a parent of $B$ and $p$ is a partner of
$B$.

As before members of $G_{n}$ are elements of $L_{c,K}$ of cardinality $n\geq
m$ and $g_{n}$ are subsets of $G_{m}$ of cardinality $n\leq m$. However in the
present situation, sets in $g_{n}$ will be defined in terms of pairwise
intersections of sets of cardinality $n+1$. Specifically let
$U_{n}=\\{B:B=C\cap A,\,|A|=|C|=n+1\\}$. Then for $n<m$ we define by backward
induction starting from $m$,

$g_{n}=\\{B\in U_{n}|B=E\cap F,\,E,F\in g_{n+1}\\}.\\\ $

Thus elements in $g_{n}$ subsets of size $n$ are pairwise intersections of
adjacent pairs (in the Hamming metric sense) of sets in $g_{n+1}$.

The second sufficient condition is defined in terms of the following sets: let
$X_{p,k}=\\{A|A\in g_{k},A=S\cup\\{p\\},|S|=k-1\\}$ , $Y_{p,k}=\\{W|W\in
g_{k-1},W\cup\\{p\\}\in g_{k}\\}$. The set $A$ is in $X_{p,k}$ if it contains
$p$ and is the parent of an $S$ with cardinality $k-1$. A set $W$ is in
$Y_{p,k}$ if it has a partner $p$.

###### Proposition 2

Suppose $B\in g_{n}$ where $n<m$. Further suppose there is a finite set
$\\{p_{i}\in V:i=1\cdots l_{n}\\}$ (which may depend on $B$), such that
$g_{n+1}=\bigcup_{i=1}^{l_{n}}X_{p_{i},n+1}$ where $p_{i}\notin B,\
i=1\cdots,l_{n}$, and $B\subset\bigcap_{i=1}^{l_{n}}Y_{p,,n+1}\neq\emptyset$.
Then for every $A\in g_{n+1}$, there exists a $p\in A\setminus B$ such that
$B\cup\\{p\\}\in g_{n+1}$.

Proof: The hypothesis states that $B$ has partners, $p_{i}\notin B,i=1,\cdots
l_{n}$. Moreover we also have that each $A\in g_{n+1}$ contains an element,
say $p$ in this set by hypothesis. Thus by the definition of partner, we must
have $B\cup\\{p\\}\in g_{n+1}$. $\Box$
The shorthand notation $B\nearrow g_{n+1}$ used in the sequel means that $B$
satisfies the hypothesis of Proposition 2. Therefore as a consequence of the
conclusion, $B$ satisfies $\mathbf{T3}$.

Case II

  * •

(i) For every $1\leq n\leq m$, $\widehat{g}_{n}=\\{B\in g_{n}\mid B\nearrow
g_{n+1},B\supset C,C\in\widehat{g}_{n}\\}\neq\emptyset$.

  * •

(ii) $\widehat{g}_{m}=\widehat{G}_{m}=\\{A\in G_{m}|A\supset
B,B\in\widehat{g}_{m-1}\\}$.

  * •

(iii) $\widehat{G}_{n}=\\{A\in G_{n}|A\supset B\in G_{n-1}\\}$ , $n>m$.

REMARK: If property (i) is true then for every $n<m$, there are elements in
$g_{n}$ that satisfy the hypotheses of Proposition 2.
Case II is illustrated in the example discussed in section 2.3. Here the one
element feasible sets are are
$\widehat{g_{1}}=\\{\\{1\\},\\{2\\},\\{3\\},\\{7\\}\\}$. The elements
$\\{4\\}$,$\\{5\\}$,$\\{6\\}$,$\\{8\\}$,$\\{9\\}$ are excluded even though
these sets arise from the pairwise intersection of sets in $G_{2}$, because
they fail to satisfy (i) and therefore they do not satisfy $\mathbf{T3}$ (and
thus $\mathbf{G3}$).

###### Proposition 3

If CASE II holds, then $\mathbf{T1}$-$\mathbf{T4}$ is satisfied.

Proof: $\mathbf{T1}$ and $\mathbf{T2}$ follow easily from (i) and (ii). To see
that $\mathbf{T3}$ holds note that it is a consequence of (i) since
$B\nearrow\widehat{g}_{n+1}$ and any $A\in\widehat{g}_{n}$ is in $g_{n}$.
$\mathbf{T4}$ follows from (iii). $\Box$.

###### Corollary 2

Suppose $\\{\widehat{g}_{n}\\}$ $1\leq n\leq m$ and $\\{\widehat{G}_{n}\\}$
$m\leq n\leq K$ satisfy the conditions of Case II.Then the class of sets
$\mathscr{F}(L_{c,K})=\\{\emptyset,\ (\widehat{g}_{n},\ 1\leq n\leq m-1),\
(\widehat{G}_{n},\ m\leq n\leq K)\\}$ are the feasible sets of a greedoid.

Proof: By Proposition 3, the hypotheses of Theorem 1 are satisfied. Thus the
conclusion of this proposition follows from the theorem. $\Box$.

When $\mathscr{M}$ is a vertex cover (e.g. the vertices of a maximal match)
then we can give a partial answer to the question raised in section 2 of when
vertex covers contain optimal sets. If $\mathscr{M}$ is a feasible set with
$|\mathscr{M}|>m$, then it will contain optimal or near optimal sets where the
degree of optimality is defined by $c$ in (9).

###### Proposition 4

: Let $\mathscr{M}$ be the vertices of a vertex cover (maximal match) and
suppose $c$ and $K$ as in (9) are given. Further let $m$ be the minimum
cardinality of sets in $\mathnormal{L}_{c,K}$. If $|\mathscr{M}|>m$, and
$\mathscr{M}$ is a feasible set of the greedoid in Theorem 1, then it and its
subsets with cardinality at least $m$ are in $\mathnormal{L}_{c,K}$.Thus it
has nearly optimal subsets. In particular if there is an $S\in\widehat{G}_{m}$
with $S\subset\mathscr{M}$, then $\mathscr{M}$ has nearly optimal subsets in
the sense of (9).

When are any of the non-optimal sets contained in $\mathscr{M}$ actually
optimal? In general we do not know. Since $c$ effectively measures the quality
of the sets in $L_{c,K}$ the closer $c$ is to $1$, the closer the subsets are
to optimal sets. A step towards answering this question would be to identify a
class of graphs for which a moderate level of $c$ is enough to guarantee that
a large percentage of $L_{c,K}$ consists of optimal and very high quality
sets.

###  3.1 The Graph of Optimal and Near Optimal Sets

We introduce a graph $\mathscr{G}(\mathnormal{L}_{c,K})$ whose nodes are the
feasible sets of the greedoid described in Theorem 1. To simplify the notation
we use $\mathsf{F}=\mathscr{F}(\mathnormal{L_{c,K}})$ to denote the node set
of $\mathscr{G}(\mathnormal{L}_{c,K})$. The local structure of the graph is
defined by adjacent nodes.

###### Definition 4

Two nodes $A$ and $B$$\in\mathsf{F}$ are adjacent in
$\mathscr{G}(\mathnormal{L}_{c,K})$ if one of the following statements is
true.

  * •

$A$, $B$ $\in\mathsf{F}$, $B=A\cup\\{r\\}$, for $r\notin A$

  * •

$B=A\setminus a$ for some element $a\in A$

  * •

$|A|=|B|$ and $|A\setminus B|=1$

Let $A$ and $C$ in $\mathsf{F}\cap\mathnormal{L_{c,K}}$ be two feasible sets
of equal cardinality. We assume the cardinality is greater than $m$,the
smallest set in $L_{c,K}$. For some $a\in V$, the set $D=A\setminus a$ is
$\in\mathnormal{L}_{c,K}$. Indeed, since $A$ is feasible, for some $a$, $D$ is
feasible. Moreover $|D|\geq m$. By Theorem 1, any set of this cardinality is a
member of $\mathnormal{L}_{c,K}$. Feasible sets of cardinality greater than
$m$ that are described in Corollaries 1 and 2 have the property that there is
a $d\in C$, not in $A$, such that $B=D\cup\\{d\\}\in\mathsf{F}$. For such
greedoids, sets $A$ and $B$ and $D$ are adjacent in
$\mathscr{G}(\mathnormal{F}_{c,K})$ where clearly $B$ is the result of
replacing $a$ by $d$ in $A$. By repeated swapping and other local moves, one
can construct a neighborhood of $A$ suitable for local search. When $A$ is a
subset of vertices of a feasible maximal match or vertex cover, navigation to
an enlarged neighborhood can be achieved by a sequence of moves to feasible
adjacent sets. In fact optimal sets that are not subsets of the vertex cover
can be reached. In section 2.3, this is demonstrated using a different type of
path than the one discussed here. A topic for future research is the
development of efficient methods for doing this calculation as well as
navigating $\mathscr{G}(\mathnormal{L_{c,K}})$ so that the number of
evaluations of $F$ is minimized.

##  4 Conclusion

We posed the problem of identifying the subset of nodes in a network that will
enable the fastest spread of information in a decentralized communication
environment. In a model of communication based on a random walk on an
undirected graph $G=(V,E)$, the optimal set of nodes are found by minimizing
the sum of the mean times of first arrival to the set by walkers who start at
nodes outside the set.

Since the objective function for this problem is supermodular, the greedy
algorithm has been a principal method for constructing approximations to
optimal sets. References [3], [1] obtain results guaranteeing that these sets
are in some sense within $(1-1/e)$ of optimality. In this work we took a
different approach. Rather than seek an optimizing set for problem (4) without
any information about $G$ other than its cardinality and objective function
$F$– the problem was reformulated.

We introduced the concept of optimal and near optimal set, ordering the
feasible subsets of problem (4) with a ranking relative to the vertex cover of
the graph with cardinality $K$. A constant $c$ is a lower bound on the rank
that measures the degree of optimality of the sets (see equation (9)). For a
fixed cardinality, higher ranking subsets are close to optimal solutions of
the problem and approximations to the problem can be compared. If we want to
improve an approximation we need a set structure to enable us to make local
moves from one set to another. In particular, it should be possible to add,
delete or swap elements so that the resulting set is still optimal or near
optimal with the specified degree of optimality $c$. Our main result (Theorem
1, section 3), describes sufficient conditions for the construction of a
greedoid based on selected optimal and near optimal subsets of smallest
cardinality. This greedoid provides the desired structure for local search
methods. A greedoid graph formalizes this idea as described in section 3.1. We
believe that a local search method based on branch and bound is a promising
avenue for current and future research ([5]). As seen in section 2.3 there are
graphs where it is possible to improve the bounds guaranteed by the use of the
greedy algorithm. As a corollary of our work we prove a theorem that gives
sufficient conditions for when a vertex cover contains a near optimal subset,
thereby partially confirming empirical observations made in section 2.1.

Other issues for additional future research are characterizing the class of
graphs for which this approach works well, i.e. when can sets with a high
degree of optimality in the sense of problem (4) be achieved when we have a
large $c$ ? Finally the methods of this paper could be used to optimize
submodular, monotone functions that arise in other models of network spread.
For example it would be interesting to consider the independent cascade model
discussed by Kempe et al. ([8]).

Figure 1: graph for EXAMPLE 1 with 9 vertices showing optimal K=1 set Figure
2: graph for EXAMPLE 1 with 9 vertices showing optimal K=2 set Figure 3: graph
for EXAMPLE 1 with 9 vertices showing optimal K=3 set Figure 4: graph for
EXAMPLE 1 with 9 vertices showing optimal K=4 set  Figure 5: graph for EXAMPLE
1 with 9 vertices showing optimal K=5 set Figure 6: graph for EXAMPLE 2 with 6
nodes is shown with two vertex covers. The nodes of the covers are colored. On
the left, the vertex cover contains no optimal subsets except itself, the
vertex cover shown on the right contains optimal subsets for $K=1$ through $4$

## References

  * [1] V.S. Borkar, J. Nair, N. Sanketh, _Manufacturing Consent_ , 48th Annual Allerton Conference, Allerton House, UIUC, Illinois, September 2010, pp. 1550-1555

  * [2] A. Bjorner, G. Ziegler, _Introduction to Greedoids_ , in Matroid Applications (ed. N. White), Encyclopedia of Mathematics, Vol. 40, Cambridge University Press, London, UK, 1992, pp.284-357

  * [3] A. Clark, L. Bushnell, R. Poovendran, _Leader Selection for Minimizing Convergence Error in Leader-Follower Systems:A Supermodular Optimization Approach_ , 10th International Symposium Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks (WiOpt), May 2012, pp. 111-115

  * [4] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein _Introduction to Algorithms_ , third edition, MIT Press, 2009

  * [5] F.Hunt, _Branch and Bound Methods for Calculating Optimal and Near Optimal sets in Consensus Models_ , preprint 2014
  * [6] D. Jungnickel, _Graphs, Networks, and Algorithms_ , Springer Verlag, New York, Berlin, Heidelberg, Tokyo, 1991

  * [7] J. Kemeny, J. Snell, _Finite Markov Chains_ , 2nd edition, Springer-Verlag, New York, Berlin, Heidelberg, Tokyo, 1976

  * [8] D. Kempe, J.. Kleinberg, E. Tardos, _Maximizing the Spread of Influence through a Social Network_ , Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2003

  * [9] B. Korte, L. Lovasz, R. Schrader, _Greedoids_ , Algorithms and Combinatorics Series, Vol. 4, Springer Verlag, Berlin, Germany,1991

  * [10] R. Lambiotte, R. Sinatra, J.C.Delvenne, T.S. Evans, M. Barahona, V.Lattora, _Interweaving dynamics and structure_ , Phys Rev. E 84, 017102, 2011

  * [11] G.L. Nemhauser, L.A. Wolsey, M.L. Fisher, _An analysis of approximations for maximizing submodular set functions-I_ , Mathematical Programming, Vol. 14, pp.553-574, 2003

  * [12] C. Papadimitrioius, D. Steiglitz, _Combinatorial Optimization and Complexity_ , Chapter 17 and p.432, Dover Publications, 1998


# Robust Modulation Technique for Diffusion-based Molecular Communication in
Nanonetworks

Subodh Pudasaini, Seokjooo Shin and Kyung Sup Kwak
S. Pudasaini and K. S. Kwak are with UWB Wireless Communications Research
Center, Inha University, Incheon, Korea.S. Shin is with Department of Computer
Engineering, Chosun University, Gwangju, Korea.This work was supported by the
National Research Foundation of Korea grant funded by the Korean government
(MEST 2010-0018116).

###### Abstract

Diffusion-based molecular communication over nanonetworks is an emerging
communication paradigm that enables nanomachines to communicate by using
molecules as the information carrier. For such a communication paradigm,
Concentration Shift Keying (CSK) has been considered as one of the most
promising techniques for modulating information symbols, owing to its inherent
simplicity and practicality. CSK modulated subsequent information symbols,
however, may interfere with each other due to the random amount of time that
molecules of each modulated symbols take to reach the receiver nanomachine. To
alleviate Inter Symbol Interference (ISI) problem associated with CSK, we
propose a new modulation technique called Zebra-CSK. The proposed Zebra-CSK
adds inhibitor molecules in CSK-modulated molecular signal to selectively
suppress ISI causing molecules. Numerical results from our newly developed
probabilistic analytical model show that Zebra-CSK not only enhances capacity
of the molecular channel but also reduces symbol error probability observed at
the receiver nanomachine.

###### Index Terms:

Diffusion, Inter Symbol Interference, Modulation, Molecular Communications,
Nanonetworks

##  I Introduction

Recent advancements in nanotechnology have offered several practical
approaches for the realization of physical, biological or even hybrid
nanomachines [1]. Typically, such nanomachines are a few tens nanometers in
size and are able to perform simple tasks such as computing, storage, sensing
and actuation. Nanomachines with communication capabilities can be
interconnected to form a nanonetwork through which complex tasks that may be
relevant and necessary for realizing different biomedical, environmental and
industrial applications can be executed in a collaborative manner.

One of the most promising paradigms to interconnect nanomachines, especially
the biological and bio-physical hybrid ones, to set up a nanonetwork is
molecular communication. Molecular communication involves the transmission of
information encoded using molecules that physically travel from a transmitter
nanomachine to a receiver nanomachine. Several types of molecular transport
mechanisms have been studied so far. Broadly, they involve either passive
transport of molecules utilizing free particle diffusion dynamics or active
transport of molecules using bacterial chemotaxis and molecular motors that
generate motion [2]. In this work, we consider the former diffusion-based
passive molecular transport mechanism.

Recently, Kuran et al. proposed two different modulation schemes for realizing
molecular communication via diffusion: Concentration Shift Keying (CSK) and
Molecule Shift Keying (MoSK) [3]. They are analogous to amplitude shift keying
and frequency shift keying, respectively, which have been popularly used in
electromagnetic communication for many decades. CSK uses different
concentrations (or simply number) of molecules to uniquely represent different
information symbols while MoSK uses different types of molecules for such
purpose. For the transmission of $s$ information bits in one MoSK-modulated
symbol, $2^{s}$ different types of molecules are required. Hence, the
complexity of transmitter and receiver nanomachines increases as $s$ increases
and thus MoSK may not be practical.

Consider serial transmission of CSK-modulated information symbols over a time-
slotted diffusion channel as described in Section II. In such a diffusion
channel, for a transmitted information symbol, molecular concentration (or
alternately number of messenger molecules) observed at the receiver
nanomachine is initially (i.e. at the start of a slot) zero and it quickly
increases until reaching its maximum. Then, the molecular concentration slowly
decreases over time resulting in a long-tailed molecular concentration signal
that may stretches over several slot durations. Messenger molecules belonging
to the tail of the molecular concentration signal of previous information
symbols thus act as the source of interference to the molecular concentration
signal of the current information symbol. Such interference is called Inter
Symbol Interference (ISI). In [4] and [5], authors have shown that ISI
significantly deteriorates the decoding performance of the receiver
nanomachine. Motivated with this problem, in this letter, we present a robust
modulation scheme, Zebra-CSK, that attempts to reduce ISI as much as possible.

##  II System Model

We consider a molecular communication system consisting of a pair of
transmitter and receiver nanomachines. The transmitter nanomachine is fixed at
the origin of an unbounded three-dimensional stationary fluidic environment
while the receiver nanomachine is $d$ distance apart from the transmitter
nanomachine.

Furthermore, we consider the molecular communication system is time-slotted
with a slot duration of $T_{s}$, and the transmitter and receiver nanomachines
are perfectly synchronized. At the transmitter nanomachine, a binary CSK
modulation is employed; impulse of $n$ molecules are released at the start of
the slot for binary symbol $1$ while no molecules are released for binary
symbol $0$. The encoded information symbols will be conveyed to the receiver
nanomachine through molecular diffusion. Once a molecule arrives at the
receiver nanomachine, it will be removed from the communication medium. We
assume that all molecules are homogeneous and diffuses independently with
respect to other molecules with a common diffusion coefficient found using the
Einstein relation

$D=\frac{K_{B}T}{6\pi\eta r},$ (1)

where $K_{B}$ is the Boltzmann constant ($K_{B}=1.38\times 10^{-23}$), $T$ is
the temperature in kelvin, $\eta$ is the viscosity of the fluidic medium, and
$r$ is the common radius of the molecules.

The receiver nanomachine counts the total number of received molecules
(denoted by a random variable $N$) at the end of each time slot and applies
the following decision rule to determine the transmitted binary symbol:

$N\mathop{\gtrless}_{0}^{1}\lambda,$ (2)

where $\lambda$ is a pre-specified threshold.

##  III The Proposed Modulation Technique

Following two classes of molecules are used in the proposed Zebra-CSK: (i)
messenger molecules for encoding information symbols, and (ii) inhibitor
molecules for supressing residual messenger molecules from the previous
information symbol.

Figure 1: High-level flowchart of the proposed Zebra-CSK.

Fig. 1 depicts the high-level flowchart of Zebra-CSK. In Zebra-CSK, as the
name suggests, types of messenger molecules in subsequent information symbols
are altered from _type a_ messenger molecules (denoted as Ma) to _type b_
messenger molecules (denoted as Mb), or vice versa, while the information
encoding mechanism is similar with that of the conventional CSK. Furthermore,
each type of messenger molecules are accompanied by inhibitor molecules of the
other type. In other words, Ma molecules are accompanied with the inhibitor of
Mb molecules (denoted as Ib) while Mb molecules are accompanied with the
inhibitor of Ma molecules (denoted as Ib).

Figure 2: Temporal molecular-type alternation of both inhibitor and messenger
molecules in the proposed Zebra-CSK.

Fig. 2 illustrates temporal molecular-type alternation of both messenger and
inhibitor molecules in the proposed Zebra-CSK. In a given slot duration, when
one type of messenger molecules are released along with inhibitor of the other
type messenger molecules, the late-arriving residual messenger molecules from
the previous symbol (which are of the other type) are acted upon by the
inhibitor molecules. As a consequence, ISI is reduced. However, it is
noteworthy to mention that magnitude of the reduction in ISI depends on the
efficiency of the used inhibitor molecules.

##  IV Performance Analysis

###  IV-A Analytical Model

The impulse of messenger molecules released from the transmitter nanomachine
spread out through the fluid medium via diffusion and hence the random motion
of the messenger molecules can be represented as Brownian motion. Following
the well developed literature on analysis of Brownian motion, probability
density function of the time a messenger molecule requires to reach the
receiver nanomachine (referred to as absorbance time of Brownian particle in
the literature) can be written as

$f(t)=\begin{cases}0,&t=0\\\ \frac{d}{\sqrt{4\pi
Dt^{3}}}\cdot\exp(-\frac{d^{2}}{4Dt}),&t>0.\end{cases}$ (3)

Utilizing (3), the probability that a molecule reaches the receiver
nanomachine within a current slot of $T_{s}$ can be obtained as

$p_{c}=\int_{0}^{T_{s}}f(t)dt.$ (4)

Define $Z_{k}$ to be a binary random variable indicating whether a $k$-th
molecule among $n$ molecules released by the transmitter nanomachine at the
beginning of a slot arrives at the receiver nanomachine before the slot ends,
i.e. $Z_{k}=1$ if the molecule arrives within $T_{s}$ and $Z_{k}=0$ otherwise.
Thus, considering $Z_{k}$, we have

$P(N_{c}=m)=P(Z_{1}+Z_{2}+Z_{3}+\cdot\cdot\cdot+Z_{n}=m),$ (5)

where $N_{c}$ is a random variable denoting the total number of molecules
received at the receiver nanomachine within $T_{s}$. Given the number of the
transmitted molecules $n$, from (5) it can be seen that $N_{c}$ follows the
binomial distribution, i.e. $N_{c}\thicksim\text{Bionomial}(n,p_{c})$. For
large $n$, distribution of $N_{c}$ can be approximated as Guassian
distribution with the knowledge of its mean and variance as

$N_{c}\thicksim\mathcal{N}\Big{(}np_{c},np_{c}(1-p_{c})\Big{)}.$ (6)

Note that distribution of $N_{c}$ does not consider the late arriving
messenger molecules from the previous symbols.

Let $N_{cp}$ be a random variable denoting the total number of messenger
molecules received at the receiver nanomachine among the $n$ molecules
released in the previous slot. It is evident that $N_{cp}$ is also binomially
distributed as $N_{c}$, and can be approximated as

$N_{cp}\thicksim\mathcal{N}\Big{(}np_{cp},np_{cp}(1-p_{cp})\Big{)},$ (7)

where

$p_{cp}=p_{c}+(1-\beta)\int_{T_{s}}^{2T_{s}}f(t)dt$ (8)

for a given inhibition efficiency $\beta$ of the inhibitor molecules. Based on
(6) and (7) the distribution of a random variable representing the number of
messenger molecules that may cause inter symbol interference, denoted by
$N_{p}$, thus can be expressed as

$\displaystyle N_{P}$ $\displaystyle\thicksim$
$\displaystyle\mathcal{N}\Big{(}np_{cp},np_{cp}(1-p_{cp})\Big{)}-\mathcal{N}\Big{(}np_{c},np_{c}(1-p_{c})\Big{)}$
(9) $\displaystyle\thicksim$
$\displaystyle\mathcal{N}\Big{(}n(p_{cp}-p_{c}),np_{cp}(1-p_{cp})+np_{c}(1-p_{c})\Big{)}.$

Utilizing distributions of $N_{c}$ and $N_{p}$ in (6) and (9), we next
calculate the channel capacity and also derive the symbol error performance of
the receiver nanomachine for the proposed modulation scheme.

Consider serial transmission of information symbols where binary symbols $1$
and $0$ occur with _a priori_ probabilities equal to $q$ and $1-q$,
respectively. In such a serial transmission, probabilities of correct
detection of a transmitted symbol at the receiver nanomachine (probability
that $0$ is received when $0$ is transmitted and $1$ is received when $1$ is
transmitted), can be expressed as

$\displaystyle P(0,0)$ $\displaystyle=$ $\displaystyle
P(0,0|S_{-1}=0)P(S_{-1}=0)$ (10) $\displaystyle+$ $\displaystyle
P(0,0|S_{-1}=1)P(S_{-1}=1)$ $\displaystyle=$ $\displaystyle(1-q)\cdot
1\cdot(1-q)+(1-q)P(N_{p}<\lambda)q$ $\displaystyle=$
$\displaystyle(1-q)^{2}+q(1-q)\Big{[}1-Q(A_{1})\Big{]},\ \text{and}$
$\displaystyle P(1,1)$ $\displaystyle=$ $\displaystyle
P(1,1|S_{-1}=0)P(S_{-1}=0)$ (11) $\displaystyle+$ $\displaystyle
P(1,1|S_{-1}=1)P(S_{-1}=1)$ $\displaystyle=$ $\displaystyle
qP(N_{c}\geq\lambda)(1-q)+qP(N_{c}+N_{p}\geq\lambda)q$ $\displaystyle=$
$\displaystyle q(1-q)Q(A_{2})+q^{2}Q(A_{3}),$

where $S_{-1}$ is a binary random variable indicating the information symbol
transmitted in the previous slot, $Q(\cdot)$ is the the tail probability of
the Gaussian probability distribution function,
$A_{1}=\frac{\lambda-n(p_{cp}-p_{c})}{[np_{cp}(1-p_{cp})+np_{c}(1-p_{c})]^{1/2}}$,
$A_{2}=\frac{\lambda-np_{c}}{[np_{c}(1-p_{c})]^{1/2}}$ and
$A_{3}=\frac{\lambda-np_{cp}}{[np_{cp}(1-p_{cp})+2np_{c}(1-p_{c})]^{1/2}}$. On
the other hand, probabilities of erroneous detection of a transmitted symbol
at the receiver nanomachine (probability that $1$ is received when $0$ is
transmitted and $0$ is received when $1$ is transmitted), can be expressed as

$\displaystyle P(0,1)$ $\displaystyle=$ $\displaystyle
P(0,1|S_{-1}=0)P(S_{-1}=0)$ (12) $\displaystyle+$ $\displaystyle
P(0,1|S_{-1}=1)P(S_{-1}=1)$ $\displaystyle=$ $\displaystyle(1-q)\cdot
0\cdot(1-q)+(1-q)P(N_{p}\geq\lambda)q$ $\displaystyle=$ $\displaystyle
q(1-q)Q(A_{1}),\ \text{and}$ $\displaystyle P(1,0)$ $\displaystyle=$
$\displaystyle P(1,0|S_{-1}=0)P(S_{-1}=0)$ (13) $\displaystyle+$
$\displaystyle P(1,0|S_{-1}=1)P(S_{-1}=1)$ $\displaystyle=$ $\displaystyle
qP(N_{c}<\lambda)(1-q)+qP(N_{c}+N_{p}<\lambda)q$ $\displaystyle=$
$\displaystyle q(1-q)\Big{[}1-Q(A_{2})\Big{]}+q^{2}\Big{[}1-Q(A_{3})\Big{]}.$

Total probability that a symbol is decoded erroneously at the receiver
nanomachine, denoted as $P_{e}$, is the sum of $P(0,1)$ and $P(1,0)$, Thus,
using (12) and (13),

$P_{e}=q(1-q)Q(A_{1})+q(1-q)\Big{[}1-Q(A_{2})\Big{]}+q^{2}\Big{[}1-Q(A_{3})\Big{]}.$
(14)

Next, we determine capacity $C$ of the considered molecular communication
system, i.e., the maximum rate of transmission between the transmitter
nanomachine and the receiver nanomachine. This can be calculated utilizing the
seminal Shannon’s formula, which defines the capacity as the maximum mutual
information $I(S;R)$ between the transmitted symbol $S$ and the received
symbol $R$ as

$C=\max_{\lambda}I(S;R),$ (15)

where

$I(S;R)=\sum_{S\in{\\{0,1\\}}}\sum_{R\in{\\{0,1\\}}}P(S,R)\log_{2}\frac{P(S,R)}{P(S)P(R)}.$
(16)

Note that $P(S,R)$ can be calculated using (10)-(13) while the marginal
probabilities $P(S)$ and $P(R)$ can be obtained using
$P(S)=\sum_{R\in{\\{0,1\\}}}P(S,R)$ and $P(R)=\sum_{S\in{\\{0,1\\}}}P(S,R)$.

###  IV-B Numerical Results

Fig. 3 shows mutual information between the Zebra-CSK modulated binary symbols
transmitted by the transmitter nanomachine and binary symbols received by the
receiver nanomachine. For all three considered cases of inhibition efficiency
of the inhibitor molecules (viz. $\beta=1,\ \beta=0.5,$ and $\beta=0$), mutual
information increases with increase in the detection threshold value until
reaching its maximum but starts to fall with further increase in the detection
threshold. Note that Zebra-CSK with null inhibition efficiency (i.e.
$\beta=0$) is logically equivalent to the conventional CSK. From the figure it
is evident that higher mutual information can be achieved between Zebra-CSK
modulated transmitted symbols and received symbols by selecting a relatively
smaller detection threshold than the one that maximizes the mutual information
between CSK modulated symbols and the received symbols. The higher mutual
information in Zebra-CSK thus results in higher channel capacity. For
instance, for the considered $n$, $d$, $q$ and $D$ values, channel capacity of
Zebra-CSK is $29.85\%$ and $37.31\%$ higher than that of CSK when $\beta=0.5$
and $\beta=1$, respectively.

Fig. 4 shows symbol error performance of the receiver nanomachine while
demodulating Zebra-CSK modulated binary symbols. The symbol error probability
of Zebra-CSK is significantly lower than that of the conventional CSK for most
of the possible detection threshold values that are smaller than the optimum
detection threshold value for CSK. Interestingly, the higher the inhibition
efficiency of the inhibitor molecules is, the higher will be the reduction in
the symbol error probability. For instance, for the considered $n$, $d$, $q$
and $D$ values, minimum achievable symbol error probability of Zebra-CSK (i.e
at optimum detection threshold) is $0.017$ when $\beta=0.5$ and $0.00993$ when
$\beta=1$. These are clearly $75.36\%$ and $85.61\%$ improvement over the
minimum achievable symbol error probability of $0.069$ in the conventional
CSK.

Figure 3: Mutual information between the transmitted binary symbol $S$ and
received symbol $R$ when $n=100$, $q=0.5$, $d=32\ \mu$m, and $T_{s}=5.9\ $s.
Figure 4: Probability of symbol error at receiver nanomachine when $n=100$,
$q=0.5$, $d=32\ \mu$m, and $T_{s}=5.9\ $s. Figure 5: Effect of distance
between transmitter and receiver nanomachine on symbol error performance when
$n=100$, $q=0.5$, $T_{s}=5.9\ $s, and $\lambda=20$.

Fig. 5 shows symbol error performance of the receiver nanomachine located at
various distance from the transmitter nanomachine. For a given detection
threshold, the symbol error probability increases as the distance between
transmitter and receiver nanomachine increases. Symbol error probability of
Zebra-CSK is always lower than that of the conventional CSK regardless of the
distance between transmitter and receiver nanomachine. It is note worthy to
mention that, except for very higher inhibition efficiencies closer to $1$,
symbol error performance gain of Zebra-CSK over CSK (i.e difference between
the symbol error probabilities of CSK and Zebra-CSK) increases with an
increase in the distance between transmitter and receiver nanomachine.

##  V Conclusion

In this paper, we have proposed a new modulation technique (named as Zebra-
CSK) for transmitting information symbols over diffusive channel in nanoscale
molecular communication networks. The proposed modulation technique is robust
in the sense that it reduces inter symbol interferences among subsequently
transmitted information symbols. Reduction in the inter symbol interference
depends on the efficiency of the molecules used to inhibit the messenger
molecules. Through numerical analysis we have shown that symbol detection
error probability of a receiver nanomachine is lower for demodulating Zebra-
CSK modulated binary information symbols than demodulating the conventional
CSK modulated binary information symbols. As a future work, we plan to analyze
and quantify the performance of the proposed Zebra-CSK for quaternary and even
higher order modulations.

## References

  * [1] I. F. Akyildiz, F. Brunetti, and C. Blazquez, “Nanonetworks: A New Communication Paradigm,” Computer Networks, vol. 52, pp. 2260-2279, 2008.
  * [2] T. Nakano, M. J. Moore, F. Wei, A. V. Vasilakos, and J. Shuai, “Molecular Communication and Networking: Opportunities and Challenges,” IEEE Trans. Nanobiosci., vol. 11, no. 2, pp. 135-148, 2012.
  * [3] M. S. Kuran, H. B. Yilmaz, and T. Tugcu, I. F. Akyildiz, “Modulation Techniques for Communication via Diffusion in Nannonetworks” in _Proc. Int. Conf. on Communications (ICC)_ , pp. 1-5, June 2011.
  * [4] M. Pierobon, and I. F. Akyildiz, “Intersymbol and Co-channel Interference in Diffusion-based Molecular Communication,” in _Proc. Int. Conf. on Communications (ICC)_ , pp. 6126-6131, June 2012.
  * [5] M. S. Kuran, H. B. Yilmaz, T. Tugcu, and I. F. Akyildiz, “Interference Effects on Modulation Techniques in Diffusion based Nanonetworks,” Nano Communication Networks, vol. 3, pp. 65-73, 2012.