# Transformer-Encoder Detector Module: Using Context to Improve Robustness to
Adversarial Attacks on Object Detection

Faisal Alamri  Department of Computer Science
The University of Exeter
Email<EMAIL_ADDRESS>Sinan Kalkan  Department of Computer Engineering
Middle East Technical University
Email<EMAIL_ADDRESS>Nicolas Pugeault  School of Computing Science
University of Glasgow
Email<EMAIL_ADDRESS>
###### Abstract

Deep neural network approaches have demonstrated high performance in object
recognition (CNN) and detection (Faster-RCNN) tasks, but experiments have
shown that such architectures are vulnerable to adversarial attacks (FFF,
UAP): low amplitude perturbations, barely perceptible by the human eye, can
lead to a drastic reduction in labelling performance. This article proposes a
new context module, called Transformer-Encoder Detector Module, that can be
applied to an object detector to (i) improve the labelling of object
instances; and (ii) improve the detector’s robustness to adversarial attacks.
The proposed model achieves higher mAP, F1 scores and AUC average score of up
to 13% compared to the baseline Faster-RCNN detector, and an mAP score 8
points higher on images subjected to FFF or UAP attacks due to the inclusion
of both contextual and visual features extracted from scene and encoded into
the model. The result demonstrates that a simple ad-hoc context module can
improve the reliability of object detectors significantly.

00footnotetext:  This work is accepted for the 25th International Conference
on Pattern Recognition (ICPR’2020).

##  I Introduction

Recognising objects in a visual scene is an effortless task for humans, one
that has challenged computer vision since its inception. The advent of deep
neural network approaches over the last decades has delivered major
improvements on this task on all benchmarks, although some difficulties remain
[39].

One notable weakness of deep neural network approaches to vision, first
demonstrated by Szegedy et al. [34], is that perturbations of very small
amplitude, barely visible to the human eye, can be found that lead to major
decrease in the neural networks’ labelling accuracy—so called adversarial
attacks. This seminal finding was confirmed by following studies, which showed
that such attacks could be designed to be independent on the specific neural
network or even neural architecture employed [23], and that such attack
patterns could be data independent [24].

This apparent weakness is in contrast to how robust human perception of
objects is to a variety of noise and perturbations. One plausible reason for
this difference in robustness between human and artificial perception is
context [3]. Contextual information plays an important role in visual
recognition for both human and computer vision systems [3, 28]. Imagine there
are an office desktop, a chair, a PC, a monitor and a keyboard, then we ask
the question “what is the missing object in this scene?”. Some may say a cup,
or a pen, but when looking deeply and understanding the context, you are
likely to say the missing object is a mouse. Such guesses are made even
without seeing or gazing at the scene due to leveraging contextual
information. This shows how context carries rich information about visual
scenes. In terms of object recognition, the context could be defined as cues
captured from a scene that presents knowledge about objects locations, size
and object-to-object relationships. Due to the importance of contextual
information and how it improves detection, it has been widely studied [7, 40,
14, 11, 25]. Contextual information can be captured from images explicitly as
attempted in [1], or implicitly as proposed in this paper upon the success of
the Transformer model proposed by [35] for Natural Language Processing.

This paper describes a contextual detection module, proposed as an add-on to
classical object detection architectures such as Faster-RCNN, named
Transformer-Encoder Detector Module (TEDM). This model implicitly encodes
contextual statistics of objects and uses attention mechanism to improve the
labelling of image regions. It improves the detection performance of a state-
of-the-art object detector, as evaluated on natural images and perturbed
images. This model does rescore, relabel, and correct detector predictions, in
contrast to [11, 8], which only rescore detected objects’ confidences.

This paper is organised as follows: First, we review the Transformer Model,
and how it works. CNN-based detectors (Section II). In Section III, we explain
how the proposed model is built and how features are encoded in the pipeline.
Finally, the proposed model is examined on MSCOCO2017 dataset in comparison
with Faster RCNN detector and the Relabelling Model proposed by [1] in Section
IV. Natural and perturbed images are both used to evaluate the proposed model.

##  II Related Work

###  II-A Adversarial attacks

The vulnerability of deep neural network architectures to small amplitude
perturbations optimised to damage the networks’ performance has first been
found by Szegedy et al. [34]. They demonstrated that image perturbations of
small amplitude, barely visible to the eye, when optimised to cause the
highest misclassification error, can achieve large decreases in performance.
Moreover, such perturbations can decrease performance across network
architectures and even on different datasets.

Mohsen et al. [23] proposed an approach to find Universal Adversarial
Perturbations (UAP), single patterns of perturbation that lead to large
misclassification across all inputs of the network, and demonstrated its
efficiency on various classifiers (e.g. CaffeNet [18], VGG-16 [32], VGG-19
[33]), claiming that the addition of the perturbations drops the tested
classifiers’ performance by almost 90% as tested on ImageNet validation
dataset. Therefore, this leads to the result that the single universal
perturbation vectors can cause most of the natural images to be misclassified.
Therefore, it can be concluded that using UAP perturbations optimised on a
network architecture X (e.g., VGG-F) will also lead to misclassification when
applied to images classified with another network architecture Y (e.g.,
CaffeNet).

Moreover, Reddy et al. [24] claim that their proposed model, named Fast
Feature Fool (FFF), is transferable to various different models (i.e. they use
the same models examined in [23]). The main and important difference between
UAP and FFF is that FFF is data-independent. In other words, it can be applied
on any model even if the trained and tested models are trained on different
datasets (i.e., no prior knowledge about the target CNNs is needed). It is
also reported that when FFF is trained on X dataset and evaluated on Y
dataset, it can still impact the CNN models, leading to an increase in the
fooling rate compared to UAP, which is a data-dependent method.

###  II-B Visual context for object detection

Contextual information can help improve detection performance due to the
knowledge it provides from scenes [20, 14]. It is defined in [2] as any data
obtained from an object’s own statistical property and/or from its vicinity,
including intra-class and inter-class details. Such a definition is claimed
due to the information observed while studying the importance of context in
digital images.

It is said that contextual information is a tool used more with multiple
objects so that relationships among objects can be deeply understood [12].
Roozbeh et al. [25] also state that in digital images, objects with clear
appearance (e.g. large objects) are easy to detect, whereas some small objects
are harder. Lubor et al. [27] also claim that contextual information,
therefore, can be a solution here as it provides stronger cues in detecting
small objects due to the context where those objects are present. Hence,
contextual information is described as “a natural way to improve detection”
[4, 7].

Contextual information in the field of object detection can help to understand
and explore object vicinity (i.e., scene-level context) as applied in [5, 38],
and also provides object-object relationships (i.e., object-level context) as
in [29, 10]. Moreover, Contextual information has been also studied in
different areas, such as object localisation [11], image segmentation [15],
image annotation [21], scene modeling [7] and cognitive robotics [40].

Context can be classified upon the sources of information extracted from
images. Biederman et al. [6] state that there are five categories of object-
environment dependencies, which are: “(i) interposition objects interrupt
their background, (ii) support: objects often rest on surfaces, (iii)
probability: objects tend to be found in some environments but not others,
(iv) position: given an object in a scene, it is often found in some positions
but not others, and (v) familiar size: objects have a limited set of sizes
relative to other objects”. Galleguillos et al. [14] grouped those
relationships into three main categories: (i) Semantic (Probability), (ii)
Spatial (interposition, support and position) and (iii) Scale (familiar size).

###  II-C Attention and the Transformer model

Vaswami et al. [35] proposed the Transformer architecture for natural language
processing, as a way to encode word context from documents corpora using dot
product attention between word vectors. The Transformer consists of a set of
encoders and decoders, which are composed of a stack of layers. In terms of
encoders: each has two major components, which are (1) self-attention layer
and (2) feed-forward neural network. On the other hand, the decoder has two
similar components and an additional one: (1) self-attention layer, (2)
encoder-decoder layer, and (3) feed-forward neural network. The Transformer
architecture is shown in Figure 1. We refer the reader to [35] for further
information. The Transformer architecture, due to its performance and speed,
has been used in a variety of approaches in NLP, such as [13, 37, 36, 30], and
has recently been applied to computer vision problems [9].

Figure 1: The Transformer Architecture, reproduced from [35]

##  III Proposed Method

A novel model is proposed in this paper, which obtains a better performance
compared to the Faster-RCNN detector whether perturbations are applied to the
images or not. The proposed model is built upon the success of the Transformer
model proposed by [35]. However, only the Transformer-Encoder is adapted, as
shown in Figure 2, where the proposed model, named Transformer-Encoder
Detector Module (TEDM) architecture is illustrated.

Figure 2: Transformer-Encoder Detector Module Architecture

First, an image is passed to the baseline detector (i.e., Faster-RCNN) for
feature extraction. Faster-RCNN, proposed by Shaoqing et al. [31], uses a two
stages for detection. In the first stage, it uses a CNN network to extract
regions in the image that are likely to contain an object. The second stage,
moreover, performs detection (classification & localisation) for each region
proposed by the first stage. Faster-RCNN has been implemented in a variety of
articles studying the importance of contextual information (e.g. [16, 17]),
and it is still one of the state-of-the-art detection methods, and due to some
of its advantages (e.g. speed, accuracy), it is also used as the baseline
detector in this paper.

Features representing image regions for the detected objects are extracted. As
the dimension of the features extracted is $4,096$, they are mean-pooled to
$2,048$ to suit further processing. The pooled features and the boundary boxes
obtained from the detector representing the detected regions are passed into
the Transformer-Encoder with a dimension of $2,048$. Boundary boxes are
included to encode the spatial features to extract the contextual information
among regions implicitly. Since there is no recurrence in the model, the
positions of the inputs are needed, thus positional encoding is applied, which
“injects some information about the relative or absolute position of the
tokens in the sequence”, using sine and cosine functions of different
frequencies. In other words, it is used to obtain the context of each feature
inputted [35].

The Transformer Model, moreover, is then applied, which is already pre-trained
on MS COCO 2014, adapted from [19, 35]. In details, the Transformer-Encoder
takes the passed features and processes them with the attention mechanism to
output features with a dimension of 512. A feed-forward NN classifier is then
applied. The classifier produces the new scores and predicted labels for each
region. We use a trainscg (scaled conjugate gradient back-propagation) Neural
Network approach, as implemented in MATLAB [22]. Scaled conjugate gradient
(SCG), a supervised learning algorithm, is a network training function used to
update weight and bias value according to the scaled conjugate gradient method
[26]. trainscg was implemented as explained in [22]. The standard network
consists of a two-layer feed-forward network, with a sigmoid activation
function in the hidden layer, and a softmax function in the output layer. The
number of hidden units defined is 200, as different numbers were tested, and
200 achieved the highest performance for this data.

This method, to the best of our knowledge, is the first to include the
Transformer-Encoder to benefit from the use of attention and the positional
encoding operation to apply for object detection performance in both natural
and perturbed images. The positional encoding, as said, helps to simply encode
the semantic and spatial contexts for each region inputted implicitly. TEDM is
examined, as below, on the MS COCO 2017 _val_ dataset in comparison with
Faster RCNN (i.e., baseline detector) on two types of images: (1) Natural
images, where no perturbations are added, and (2) perturbed images, as
presented in Section IV.

##  IV Experiments

This section presents the results obtained from the application of the new
proposed method (TEDM). Images before any attacks, called natural images, are
used to examine the impact of this model in comparison with Faster-RCNN, as in
Experiment one (Section IV-A). Experiment Two (Section IV-B) illustrates the
examination of the TEDM vs. Faster RCNN on images under adversarial attacks.

###  IV-A Experiment One: Natural Images

In this section, we are presenting how effective TEDM is in comparison with
Faster RCNN when applied on natural images.

Note that images used in these experiments are taken from MS COCO 2017 _val_
dataset. Only the images with more than one object detected by Faster RCNN are
used in order to compare the performance of this proposed model with the
Relabelling Model proposed by [1], which explicitly extracts contextual
features from images. This model improves the detection performance of Faster
RCNN detector as it rescores and relabels predictions. using some Refer to [1,
2] further reading about contextual information and how Relabelling Model
works.

First, two chosen images with only one object presented are used to examine
the performance of TEDM when a single object is presented. This is because
TEDM does not solely rely on contextual information as the Relabelling Model,
but also on the appearance features extracted by Faster RCNN. Therefore, it is
expected to work well even with one object presented as illustrated in Figure
3, where the predictions obtained from Faster RCNN and TEDM are shown on left
and right sides, respectively.

As we can see in the first row in Figure 3, a person is detected by Faster
RCNN with a confidence of 0.9985 and also predicted by TEDM, but with very
slightly lower confidence as 0.9883. Similarly, in the second row, a kite is
detected by Faster RCNN as the only object presented. Applying TEDM, in this
case, increases the confidence from 0.9647 to 0.9920. The two images are shown
as each presents one object that belongs to a different category. In all
cases, TEDM is believed to work very well when a single object is presented.
It can be said that TEDM is a compatible method producing comparable results
as Faster RCNN. Below, more visualised and statistical results are reported
where more than one object in the images used are presented.

Faster RCNN | TEDM
---|---
|
|
Figure 3: Results: Faster RCNN vs. TEDM outputs on images with a single
Object: Green boxes represent correct detection.

Images with more than one object are used to keep consistent and to report
comparable statistical results with the Relabelling Model. In Table I, the AUC
scores for some objects and all objects average for both TEDM and Faster RCNN
are presented. It can be noticed that TEDM outperforms the baseline detector
in all cases shown obtaining a higher average score of 0.8922. This is even
better than the Relabelling Model, whose mean of AUC scores is 0.78278.

Furthermore, Table II shows the mAP${}_{0}._{5}$ and mAP (IoU=[0.5:0.05:0.95])
for TEDM and Faster RCNN. As presented, TEDM outperforms the baseline.
Compared with the Relabelling Model, whose mAP and F1 scores are 65.50% and
58.95%, as reported with [1], TEDM still performs better.

TABLE I: A comparison between Faster RCNN and TEDM in terms of AUC scores of some MS COCO classes. Class Name | Faster RCNN | Relabelling Model [1] | TEDM
---|---|---|---
Person | 0.84345 | 0.84568 | 0.95174
Car | 0.81246 | 0.80474 | 0.93287
Cow | 0.82301 | 0.84035 | 0.93246
Snowboard | 0.74229 | 0.87412 | 0.88235
Sport ball | 0.84244 | 0.84203 | 0.95008
Mean | 0.76472 | 0.78278 | 0.89222
TABLE II: mAP and F1 scores in percentages [%] for Faster RCNN and Transformer-Encoder Detector Module (TEDM).  Model | mAP${}_{0}._{5}$ | mAP | F1
---|---|---|---
Faster RCNN | 62.82 | 33.48 | 57.34
Relabelling Model [1] | 65.50 | 34.07 | 58.95
Transformer-Encoder Detector Module | 69.07 | 38.19 | 63.27

In addition, as shown in Figure 4, two randomly chosen images taken from MS
COCO 2017 validation dataset are used to examine the performance of TEDM
compared with Faster RCNN. In the first row, seven objects are detected by
Faster RCNN. Four objects, which are a person, a TV, a keyboard and a mouse
are detected correctly. However, the other three, which are a person, a laptop
and a chair are incorrectly detected. TEDM is applied, which removes two of
the incorrectly detected objects, but still predicts the laptop incorrectly,
with very low confidence. This result is promising as it shows how TEDM
removes incorrect objects and reduces the confidence of the laptop. More
importantly, in the following image, TEDM outperforms Faster RCNN predictions.
It corrects the bed, which is incorrectly detected, to a couch as correct
detection. This clearly shows how the proposed model does not only contribute
to removing false detections but also how it rescores and relabels them.

Summary. Statistical and visual results suggest that TEDM achieves a better
performance than the baseline detector benefiting from the self-attention
mechanism. It also does a great job in detecting either single-object or
multiple objects, which are better in comparison with Faster RCNN and the
Relabelling Model [2].

Original Image | Faster RCNN | TEDM
---|---|---
|  |
|  |
Figure 4: Results: Faster RCNN vs. TEDM outputs: Green, red and white boxes
represent correct detection, incorrect detection, and objects removed and
relabelled as background, respectively

###  IV-B Experiment Two: Adversarial Images

Adversarial images are used to examine the impact of TEDM, i.e. the use of
contextual information, against adversarial attacks. Such images may have
different visual features due to the addition of Adversarial Perturbations
leading to an effect on contextual information especially when some objects
are misdetected.

Adversarial Perturbations are noises carefully computed such that, when added
to images, they are not visible to the naked human eye but they do fool the
Deep Neural Networks (DNNs) into mispredictions.

Due to the impact that both methods (i.e. UAP and FFF) cause to the CNN
models, they are used in this paper to examine their effect on TEDM and Faster
RCNN detector. UAP perturbation used in this experiment is trained on MS COCO
2017, as it is data-dependent. However, FFF is used as proposed (i.e. already
trained on ImageNet), but will be tested on MS COCO 2017. Figure 5 shows the
perturbations, which are added on images. It can be seen they are different,
even though they both are trained on the same model (i.e. VGG-16), but on
different training datasets.

FFF Perturbations | UAP Perturbations
---|---
|
Figure 5: FFF vs. UAP perturbations added to images

The two types of perturbations are applied and added to images in two
different approaches: (1) added to the entire image as experimented in Section
IV-B1, (2) added to each detected region as experimented in Section IV-B2.

####  IV-B1 Perturbation on the Entire Image

In this section, perturbations are added to the entire image, where
statistical and visual results are illustrated, below, to show the performance
of TEDM in comparison with Faster RCNN.

In terms of the statistical results, as shown in Table III. The average AUC
scores for TEDM is noticeably higher than Faster RCNN in both types of
attacks. Considerably, TEDM obtains higher scores for some objects such as the
train, stop sign and Pizza, we can clearly see a huge difference, as TEDM
benefits from the use of visual and contextual features in contrast to Faster
RCNN, which depends only on the visual features. In comparison with the
Relabelling Model, which encodes contextual information in an explicitly
manner, the average AUC scores are 0.4203, and 0.4333 for FFF and UAP attacks
respectively.

In addition, Table IV illustrates the mAP and F1 scores for TEDM and Faster
RCNN, where FFF and UAP perturbations are applied. Clearly, TEDM scores a
higher performance than Faster RCNN in both cases. However, in the case of UAP
attack, we can see that both models are less impacted compared with FFF. In
comparison with the Relabelling Model which obtains mAP and F1 of 49.39%,
41.91% and 50.72%, 43.12% for FFF and UAP respectively.

TABLE III: A comparison between some MSCOCO object classes AUC scores between Faster RCNN and TEDM on perturbed images | FFF | UAP
---|---|---
Class Label | Detector | TEDM | Detector | TEDM
Person | 0.62389 | 0.69576 | 0.62881 | 0.73342
Train | 0.42961 | 0.62051 | 0.41062 | 0.56773
Stop Sign | 0.76242 | 1 | 0.69155 | 0.78571
Surfboard | 0.39266 | 0.52464 | 0.44750 | 0.59365
Pizza | 0.67393 | 0.87767 | 0.63185 | 0.81783
Mean | 0.34714 | 0.47683 | 0.36050 | 0.48713
TABLE IV: AP and F1 scores in percentages [%] for Faster RCNN and TEDM on perturbed images Attacks | Models | mAP${}_{0._{5}}$ | F1 Score
---|---|---|---
FFF | Faster RCNN | 45.34% | 39.13%
TEDM | 50.59% | 43.16%
UAP | Faster RCNN | 46.40% | 40.05%
TEDM | 51.67% | 44.00%

Figure 6 presents two images illustrating the impact of FFF and UAP
perturbations. Firstly, in the top row results, FFF perturbation is added to
the entire image. Faster RCNN detects two objects correctly, which are two
persons, whereas incorrectly detects an umbrella, which is actually a wall.
The same perturbed image is passed into the TEDM predicting the presence of
only the correct objects, which are the two persons, and relabels the umbrella
as a background. However, in compare with Faster RCNN, TEDM scores the
correctly detected objects with lower confidences, but still higher than 0.81.

In terms of UAP perturbations, as illustrated in the second row. We can see
that both models perform very well. However, Faster RCNN fails to detect one
of the frisbees, which labels as a sports ball. TEDM correctly labels it as
frisbee with a confidence of 0.9089. Both models score all other objects with
considerably high confidences, even though perturbations are added.

Summary. We can clearly see that TEDM performs better scoring higher average
AUC scores in the majority of cases, and higher mAP and F1 scores compared
with Faster RCNN and the Relabelling Model. From the reported results, we can
say that TEDM is an excellent tool to overcome some of the errors that Faster
RCNN attempts. Below, both models are examined when perturbations are added on
regions rather than on the entire image.

Perturbation | Original Image | Faster RCNN | TEDM
---|---|---|---
FFF |  |  |
UAP |  |  |
Figure 6: Results: Faster RCNN and TEDM outputs for FFF and UAP perturbed
images: Green, red and white boxes represent correct detection, incorrect
detection, and objects removed and relabelled as background, respectively

####  IV-B2 Perturbation On Regions

In this section, perturbation is added on detected regions, because
perturbations are added to images, which are passed into single-object models,
as presented and developed in [23, 24]. Therefore, perturbations will be added
to each region of interest (RoI) that the detector detects during the
detection process.

Looking at Table V we can see that TEDM outperforms Faster RCNN in both types
of perturbation. FFF seems to impact both models lower than what UAP does, but
in general, both attacks significantly drop the performance of both models. We
believe TEDM can be offered, to some extent, yet as a solution to address
perturbation issue in the field of object detection. It also outperforms the
Relabelling Model, whose mAP and F1 scores for both FFF and UAP perturbations
are respectively 29.05%, 23.14% and 26.36%, 20.53%.

AUC scores are computed as presented in Table VI. On average, TEDM performs
better than Faster RCNN in the two cases of perturbation. As said, both models
perform better when FFF attack is applied, unlike when UAP perturbation added.
However, in some classes such as microwave Faster RCNN has higher AUC scores
(as per class) comparing with the proposed method. In comparison with the
Relabelling Model, which has an average AUC score for FFF and UAP as 0.19470
and 0.16994, where TEDM again achieves better performance.

TABLE V: AP and F1 scores in percentages [%] for Faster RCNN and TEDM on perturbed images Attacks | Models | mAP0.5 | F1 Score
---|---|---|---
FFF | Faster RCNN | 26.25% | 20.78%
TEDM | 35.28% | 26.25%
UAP | Faster RCNN | 23.18% | 18.17%
TEDM | 31.39% | 24.14%
TABLE VI: A comparison between some MSCOCO object classes AUC scores between detector and TEDM on perturbed Regions | FFF | UAP
---|---|---
Class Label | Detector | TEDM | Detector | TEDM
Person | 0.18573 | 0.31982 | 0.14653 | 0.28385
Train | 0.05501 | 0.08737 | 0.03883 | 0.02912
Cat | 0.06807 | 0.10563 | 0.03990 | 0.84507
Wine Glass | 0.27083 | 0.19791 | 0.24791 | 0.25625
Microwave | 0.17241 | 0 | 0.06896 | 0.09143
Mean | 0.14310 | 0.23058 | 0.12043 | 0.19991

Table 7 presents some results obtained from the application of both attacks on
Faster RCNN and TEDM. An image showing the detected regions before any
perturbation added, followed by the predictions of both models are
illustrated. As the aim, here, is not just to illustrate the differences
between models performances before and after the attack, but rather to show
the differences among both models after attacked per region is added.
Therefore, results after the attack are reported to provide ease when
comparing.

In the first image, where FFF perturbation is added to regions TEDM predicts
no objects. All objects detected by Faster RCNN after attacked are false
detection. TEDM helps to prevent false detections that Faster RCNN outputs.
Noticeably, as shown in the detected regions before the attack, the bed is
detected, but after the attack, it could not be predicted. This is a good
example of how negatively the perturbation impacts the model. It is found that
when the regions are large in size, they are likely to be impacted more by
perturbation resulting in not being detected.

In terms of UAP perturbation, ten regions are detected by Faster RCNN before
the attack, and only half of them are detected after. Faster RCNN detects four
objects correctly but fails in detects the cup. The TEDM fails to detect the
person that Faster RCNN already detects, which can be due to the perturbation
and lighting conditions. We can see that the person in the large region is not
detected, which can be in line with the findings stated earlier that larger
regions are more likely to be impacted.

Summary. TEDM is performing better than Faster RCNN to tackle adversarial
perturbations. This is because of the features encoding during the encoder
process, as it learns the spatial and visual features.

Perturbation | Regions Before Attack | Faster RCNN | TEDM
---|---|---|---
FFF |  |  |
UAP |  |  |
Figure 7: Results: Faster RCNN and TEDM outputs for FFF and UAP perturbed
regions: Light blue boxes represent regions detected before perturbation
added. Green, red and white boxes represent correct detection, incorrect
detection, and objects removed and relabelled as background, respectively.

##  V Conclusion

This paper presented a new context module, called Transformer-Encoder Detector
Module (TEDM), which when combined with an object detection architecture to
improve both performance and robustness to adversarial attacks. The proposed
model is based on the encoder part from the Transform model [35] to encode the
contextual features implicitly for scenes, and visual features using Faster
RCNN. TEDM was examined on natural images and perturbed images, where it
outperforms Faster RCNN and a contextual model that explicitly encodes
contextual features.

As experimented, the impact of adversarial attacks was reported to be higher
when applied on regions, which we believe is due to the size of the regions:
the larger the region is, the more it is impacted. Surprisingly, UAP
perturbation affects the performance of the examined models when added to the
entire image less than FFF does. However, when added to regions, it drops
performances considerably, which can be due to the data-dependency.

Future work will involve developing an end-to-end model, to refine not only
predictions but also boundary boxes from both contextual and visual features.

## References

  * [1] Faisal Alamri and Nicolas Pugeault.  Contextual relabelling of detected objects.  In 2019 Joint IEEE 9th International Conference on Development and Learning and Epigenetic Robotics (ICDL-EpiRob), pages 313–319, 2019.
  * [2] Faisal Alamri and Nicolas Pugeault.  Improving object detection performance using scene contextual constraints.  IEEE Transactions on Cognitive and Developmental Systems, July 2020\.
  * [3] Moshe Bar.  Visual objects in context.  Nature Reviews Neuroscience, 5(8):617–629, 2004.
  * [4] Ehud Barnea and Ohad Ben-Shahar.  Contextual object detection with a few relevant neighbors.  CoRR, abs/1711.05705, 2017.
  * [5] Sean Bell, C. Lawrence Zitnick, Kavita Bala, and Ross B. Girshick.  Inside-outside net: Detecting objects in context with skip pooling and recurrent neural networks.  CoRR, abs/1512.04143, 2015.
  * [6] Irving Biederman, Robert J. Mezzanotte, and Jan C. Rabinowitz.  Scene perception: Detecting and judging objects undergoing relational violations.  Cognitive Psychology, 14(2):143 – 177, 1982.
  * [7] Ilker Bozcan and Sinan Kalkan.  Cosmo: contextualized scene modeling with boltzmann machines.  Robotics and Autonomous Systems, 113:132–148, 2019.
  * [8] X. Cao, X. Wei, Y. Han, and X. Chen.  An object-level high-order contextual descriptor based on semantic, spatial, and scale cues.  IEEE Transactions on Cybernetics, 45(7):1327–1339, July 2015.
  * [9] Nicolas Carion, F. Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander M Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  ArXiv, abs/2005.12872, 2020.
  * [10] Xinlei Chen and Abhinav Gupta.  Spatial memory for context reasoning in object detection.  CoRR, abs/1704.04224, 2017.
  * [11] Myung Jin Choi, Antonio Torralba, and Alan S. Willsky.  A tree-based context model for object recognition.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(2):240–252, Feb 2012.
  * [12] Chaitanya Desai, Deva Ramanan, and Charless C. Fowlkes.  Discriminative models for multi-class object layout.  International Journal of Computer Vision, 95(1):1–12, Oct 2011\.
  * [13] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  CoRR, abs/1810.04805, 2018.
  * [14] Carolina Galleguillos and Serge Belongie.  Context based object categorization: A critical survey.  Comput. Vis. Image Underst., 114(6):712–722, June 2010.
  * [15] Stephen Gould, Jim Rodgers, David Cohen, Gal Elidan, and Daphne Koller.  Multi-class segmentation with relative location prior.  International Journal of Computer Vision, 80(3):300–316, Dec 2008\.
  * [16] Han Hu, Jiayuan Gu, Zheng Zhang, Jifeng Dai, and Yichen Wei.  Relation networks for object detection.  CoRR, abs/1711.11575, 2017.
  * [17] N. Inoue, R. Furuta, T. Yamasaki, and K. Aizawa.  Object detection refinement using markov random field based pruning and learning based rescoring.  In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1652–1656, March 2017.
  * [18] Yangqing Jia, Evan Shelhamer, Jeff Donahue, Sergey Karayev, Jonathan Long, Ross Girshick, Sergio Guadarrama, and Trevor Darrell.  Caffe: Convolutional architecture for fast feature embedding.  In Proceedings of the 22Nd ACM International Conference on Multimedia, MM ’14, pages 675–678, New York, NY, USA, 2014. ACM.
  * [19] Martin Krasser.  Image captioning transformer.  https://github.com/krasserm/fairseq-image-captioning#image-captioning-transformer, July 2020.  (Accessed on 07/15/2020).
  * [20] Li Liu, Wanli Ouyang, Xiaogang Wang, Paul W. Fieguth, Jie Chen, Xinwang Liu, and Matti Pietikäinen.  Deep learning for generic object detection: A survey.  CoRR, abs/1809.02165, 2018.
  * [21] Zhiwu Lu, Horace H. S. Ip, and Yuxin Peng.  Contextual kernel and spectral methods for learning the semantics of images.  IEEE Transactions on Image Processing, 20(6):1739–1750, June 2011\.
  * [22] MATLAB.  Deep Learning Toolbox R2017a.  The MathWorks Inc., Natick, Massachusetts, United States, 2017.
  * [23] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard.  Universal adversarial perturbations.  CoRR, abs/1610.08401, 2016.
  * [24] Konda Reddy Mopuri, Utsav Garg, and R. Venkatesh Babu.  Fast feature fool: A data independent approach to universal adversarial perturbations.  CoRR, abs/1707.05572, 2017.
  * [25] Roozbeh Mottaghi, Xianjie Chen, Xiaobai Liu, Nam-Gyu Cho, Seong-Whan Lee, Sanja Fidler, Raquel Urtasun, and Alan Yuille.  The role of context for object detection and semantic segmentation in the wild.  In 2014 IEEE Conference on Computer Vision and Pattern Recognition, pages 891–898, June 2014.
  * [26] Martin Fodslette Møller.  A scaled conjugate gradient algorithm for fast supervised learning.  Neural Networks, 6(4):525 – 533, 1993.
  * [27] Dennis Park, Deva Ramanan, and Charless Fowlkes.  Multiresolution models for object detection.  In Kostas Daniilidis, Petros Maragos, and Nikos Paragios, editors, Computer Vision – ECCV 2010, pages 241–254, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
  * [28] Andrew Rabinovich, Andrea Vedaldi, Carolina Galleguillos, Eric Wiewiora, and Serge Belongie.  Objects in context.  In 2007 IEEE 11th International Conference on Computer Vision, pages 1–8. IEEE, 2007.
  * [29] Andrew Rabinovich, Andrea Vedaldi, Carolina Galleguillos, Eric Wiewiora, and Serge J. Belongie.  Objects in context.  2007 IEEE 11th International Conference on Computer Vision, pages 1–8, 2007.
  * [30] Alec Radford.  Improving language understanding by generative pre-training.  In Technical report, OpenAI, 2018.
  * [31] Shaoqing Ren, Kaiming He, Ross B. Girshick, and Jian Sun.  Faster R-CNN: towards real-time object detection with region proposal networks.  CoRR, abs/1506.01497, 2015.
  * [32] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In International Conference on Learning Representations, 2015.
  * [33] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott E. Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich.  Going deeper with convolutions.  CoRR, abs/1409.4842, 2014.
  * [34] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  In International Conference on Learning Representations, 2014.
  * [35] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  CoRR, abs/1706.03762, 2017.
  * [36] Zhilin Yang, Zihang Dai, Yiming Yang, Jaime G. Carbonell, Ruslan Salakhutdinov, and Quoc V. Le.  Xlnet: Generalized autoregressive pretraining for language understanding.  CoRR, abs/1906.08237, 2019.
  * [37] T. Young, D. Hazarika, S. Poria, and E. Cambria.  Recent trends in deep learning based natural language processing [review article].  IEEE Computational Intelligence Magazine, 13(3):55–75, 2018.
  * [38] Xingyu Zeng, Wanli Ouyang, Bin Yang, Junjie Yan, and Xiaogang Wang.  Gated bi-directional cnn for object detection.  In ECCV, 2016.
  * [39] Zhengxia Zou, Zhenwei Shi, Yuhong Guo, and Jieping Ye.  Object detection in 20 years: A survey.  CoRR, abs/1905.05055, 2019.
  * [40] Hande Çelikkanat, Güner Orhan, Nicolas Pugeault, Frank Guerin, Erol Şahin, and Sinan Kalkan.  Learning context on a humanoid robot using incremental latent dirichlet allocation.  IEEE Transactions on Cognitive and Developmental Systems, 8(1):42–59, March 2016.


# Virus and Warning Spread in Dynamical Networks

Carlos Rodríguez-Lucatero<EMAIL_ADDRESS>&
<EMAIL_ADDRESS>Departamento de Tecnologías de la Información,
Universidad Autónoma Metropolitana-Cuajimalpa, Av. Constituyentes 1056,
Col.Lomas Altas, México, D. F., C.P. 11950, México  Roberto Bernal-Jaquez
Departamento de Matemáticas Aplicadas y Sistemas,
Universidad Autónoma Metropolitana-Cuajimalpa, Artificios 40, Col. Hidalgo,
Delegación Álvaro Obregón, México, D.F 01120, México

###### Abstract

Recent work on information survival in sensor and human P2P networks, try to
study the datum preservation or the virus spreading in a network under the
dynamical system approach. Some interesting solutions propose to use non-
linear dynamical systems and fixed point stability theorems, providing closed
form formulas that depend on the largest eigenvalue of the dynamic system
matrix. Given that in a the Web there can be messages from one place to
another, and that this messages can be, with some probability, new
unclassified virus warning messages as well as worms or other kind of virus,
the sites can be infected very fast. The question to answer is how and when a
network infection can become global and how it can be controlled or at least
how to stabilize his spreading in such a way that it becomes confined below a
fixed portion of the network. In this paper, we try to make a step ahead in
this direction and apply classic results of the dynamical systems theory to
model the behaviour of a network where warning messages and virus spread.

###### pacs:

89.75.Hc, 05.45.Df

##  I Introduction

Recently with the constant augmentation in the number of internet users as
well as the growth in the complexity of such networks, new security problems
have appeared in the scene and there is a lack of adequate security methods
for facing attacks under this new setting. These new environments are for
instance the P2P networks, sensor networks, social nets or wireless networks,
where information is to be stored, generated and retrieved. So under this new
environments it can be very important to study and model how the information
is spread or how to keep the spreading of a virus under control in such a way
that the information still being useful under these vulnerable circumstances.
In Deepa1  it is studied the problem of information survival threshold in
sensor and P2P networks, modeling the problem as a non-linear dynamical system
and using fixed point stability theorems, and obtain a closed form solution
that depends on an additional parameter, the largest eigenvalue of the
dynamical system matrix. In the sensor networks for instance, the nodes can
loss their communications links and the nodes can stop working because of
system failure produced by a virus infection and quarantine process or a
system maintenance procedure. Under such conditions they try to answer the
following question:

PROBLEM: _Under what conditions a datum can survive in a sensor network?_
Given that the nodes as well as the links can fail with some probability the
obvious model can be a Markov chain, but such a model can grow in complexity
very quickly because the number of possible states becomes $3^{N}$ where $N$
is the number of states. To avoid this mathematical problem, one alternative
is to model the system as a non-linear dynamical system. Recently they have
appeared in the conferences and journal articles some very interesting and
relevant research articles about the virus spread behaviour in a P2P network
or in scale free nets such as the Web. In Kempe1  the authors study the
communication mechanisms for gossip based protocols. Another very recent and
interesting work on how to distribute antidotes for controlling the epidemics
spread is presented in chayes1 . In this research the authors analyse the
problem under the approach of contact processes Durrett1  on a finite graph
and obtain very interesting and rigorous results. Concerning the properties
that arise in the random graphs, such as the existence of a _giant component_
, _percolation_ phenomena, node degree distribution and _small world_
phenomena, and that are the base of many recent works on virus spread on
networks, we can mention Barab0 ; Barab1 ; Barab2  as well as Alon1  Bollobas1
Falou1  and Radicchi1 . Concerning the subject on mathematical modeling of
epidemic spreading we should mention the outstanding work done by Romualdo
Pastor-Satorras and Alessandro Vespignani in Satorras1 ; Satorras2 ; Satorras3
. In the present work we will take as source of inspiration Deepa1 . In Deepa1
the authors implement some experiments on several real sensor and P2P networks
(from Intel, MIT, Gnutella, and others) to show the accuracy of their method.
In this work it is claimed that their method is not only applicable to sensor
nets but it is also applicable to many more settings where a piece of
information may be replicated across faulty links and faulty nodes. The
authors establish a survivability condition that produce a bound in the design
of distributed systems, allowing to:

  * •

Estimate the most economic retransmission rates for a datum to survive in a
sensor network.

  * •

Decide which nodes can be removed while still remaining above the
survivability threshold in a sensor network.

  * •

Drive a _virus_ as _datum_ to extinction for anti-virus protection, by
deciding how often to quarantine nodes and how long they should be kept down.

  * •

Propagate and maintain information (news, rumors, etc.)

So, this work is closely related with the areas of gossip based protocols,
epidemiology and computer security. Gossip-based protocols on networks, whose
related graphs have dynamic presence of nodes, that keep some level of state
consistency have been proposed in Kempe1 . The basic underlying idea of the
gossip protocols is that at each time step each node $i$ chose to communicate
with a node $j$ generally following a random rule, exchanging information
during a period of time, spreading it in the system in the same way as the
virus are spread. A fundamental issue in this kind of protocols is how the
underlying gossip low level mechanism affects the ability to design efficient
high level gossip protocol algorithms. In Kempe1  the authors show a
fundamental limitation on the power of the commonly used uniform gossip
mechanism for solving nearest-resource location problems. They show as well
that very efficient protocols for this problem can be designed using a non-
uniform spatial gossip mechanism. The gossip-based distributed protocol
algorithms obtained in Kempe1  for complex problems for a set of nodes in
Euclidean space are implemented by constructing an approximated minimum
spanning tree.

####  I.0.1 Previous proposed mathematical model of virus spread.

With the increasing importance and presence of sensor as well as P2P networks,
networks have a high level of congestion and because of that the theory
concerning information survivability becomes very important. One source of
inspiration for mathematical modeling problems of information survivability in
this kind of networks is the _epidemiology_.

The _epidemiology_ community has developed several stochastic models for
studying the spread and die-out of diseases in a population. The two most
relevant ones are the SIR and SIS models. Both are stochastic models of the
spread of disease through a population, where the _susceptible_ nodes can get
_infected_ on contact with _infected_ neighbors. The _infected_ hosts
eventually die (in the SIR model) or recover and become _susceptible_ again
(in the SIS model). The point of view adopted in Deepa1  was the SIS model.
Under this model a node is _susceptible_ to a data item when it is online and
under normal operation. When the nodes start to fail, they become _immune_
during their failure, and later they become _susceptible_ again when they are
back online. Some results obtained in Deepa1  are very useful to analyze the
survival of a infection in a population, based on the graph theory results
similar to the ones mentioned in Barab1 ; Barab2 ; Alon1 . In computer
security one of the important issues that have been studied under SIS and SIR
infection spreading mathematical models are the virus propagation as well as
worms on Internet, from where, the exponential spread of them and the
_epidemic thresholds_ can be estimated Satorras1 ,Satorras2 , Satorras3 . Let
us suppose that we have a sensor/P2P/social network of $N$ nodes (sensors or
computers or people) and $E$ directed links between them. Let us also assume
that we take very small discrete timesteps of size $\Delta t$ where $\Delta
t\rightarrow 0$. The survivability results in Deepa1  apply equally well to
continuous systems. Within a $\Delta t$ time interval, each node $i$ has
probabiity $r_{i}$ of trying to broadcast its information every time step, and
each link $i\rightarrow j$ has a probability $\beta_{i,j}$ of being _up_ , and
thus correctly propagating the information to node $j$. Each node $i$ also has
a node failure probability $\delta_{i}>0$ (e.g., due to battery failure in
sensors). Every dead node $j$ has a rate $\gamma_{j}$ of returning to the _up_
state, but without any information in its memory (e.g., due to the periodic
replacement of dead batteries). These and other symbols are listed in Table 1.

$\begin{array}[]{|l|l|}\hline\cr\mbox{Symbol}&\mbox{Description}\\\ \hline\cr
N&\mbox{Number of nodes in a network}\\\ \beta_{ij}&\mbox{Probability that the
link}\\\ {}{}{}{}{}&i\rightarrow j\mbox{is up}\\\ \delta_{i}&\mbox{Death rate:
Probability that node~{}}i\mbox{~{}dies}\\\ \gamma_{i}&\mbox{Resurrection
rate:}\\\ {}{}{}{}&\mbox{Probability that node~{}}i\mbox{~{}comes back up}\\\
r_{i}&\mbox{Retransmission rate:}\\\ {}{}{}{}{}&\mbox{Probability that
node}i\mbox{~{}broadcasts}\\\ \hline\cr p_{i}(t)&\mbox{Probability that
node}\\\ {}{}{}{}{}&i\mbox{~{} is alive at time}t\mbox{~{}and has info}\\\
q_{i}(t)&\mbox{Probability that node}\\\ {}{}{}{}&i\mbox{ ~{} is alive at
time}t\mbox{~{}but without info}\\\ 1-p_{i}(t)-q_{i}(t)&\mbox{Probability that
node}i\mbox{~{}is dead}\\\ \zeta_{i}&\mbox{Probability that
node}i\mbox{~{}does}\\\ {}{}{}{}&\mbox{not receive info from}\\\
{}{}{}{}&\mbox{any of its neighbors at time~{}}t\\\
\vec{p}(t),\vec{q}(t)&\mbox{Probability column vectors}\\\
f:\Re^{2N}\rightarrow\Re^{2N}&\mbox{Function representing a dynamical
system}\\\ \nabla(f)&\mbox{The Jacobian matrix of~{}}f(.)\\\
S&\mbox{The~{}}N\times N\mbox{~{}system matrix}\\\ \lambda_{S}&\mbox{An
eigenvalue of the~{}}S\mbox{matrix}\\\ \lambda_{1,S}&\mbox{The largest in
magnitude}\\\ {}{}{}{}&\mbox{eigenvalue of the}S\mbox{matrix}\\\
s=|\lambda_{1,S}|&\mbox{Survivability score = Magnitude of}\lambda_{1,S}\\\
\hline\cr\end{array}$

This system can be modeled as a Markov chain, where each node can be in one of
three states: _Has Info_ , _No Info_ or _Dead_ , with transitions between them
as shown in Diagram 1. The full state of the system at any instant consists of
$N$ such states, one for each node. Thus, there are $3^{N}$ system states.
Transitions out of the current system state depend only on the current state
and not on any previous states; thus it is a Markov chain.
The next graph represent the transition that take place in each node.
Resurrected$\gamma_{i}$Prob
$1-p_{i}-q_{i}$$1-\gamma_{i}$Dies$\delta_{i}$HasInfoProb
$p_{i}$$1-\delta_{i}$Dies$\delta_{i}$Receives
Info$1-\zeta_{i}(t)$NoInfo$\zeta_{i}(t)-\delta_{i}$Prob $q_{i}$DeadDiagram 1:
Transitions on each node

It can be pointed out that there is an absorbing set of states where no node
is in _Has Info_ state. Under such circumstances the information dies with
probability $1$ as $t\rightarrow\infty$. Some combination of parameters lend
the system quickly to this state and some other combination does not so in
practice the datum _survives_ for some parameter combination. The question is:
under what conditions does the information survive for a long time, and when
will the information die out quickly? Let $\overline{C}(t)$ denote the
expected number of _carriers_ (nodes in _Has Info_ state) at time $t$. In
general, $\overline{C}(t)$ decays exponentially, polynomially or
logarithmically (with expected extinction time comparable to or larger than
the age of the universe for large graphs), depending on the system being
below, at or above a threshold Durrett1 . Let us focus on the _fast
extinction_ case where $\overline{C}(t)$ decays exponentially.

######  Definition 1.

_Fast extinction_ is the setting where the number of carriers
$\overline{C}(t)$ decays exponentially over time ($\overline{C}(t)\propto
c^{-t},c>1$)

Now, the problem can be formally stated as follows: PROBLEM:

  * •

Given: the network topology (link _up_ probabilities) $\beta_{ij}$ the
retransmission rates $r_{i}$, the resurrection rates $\gamma_{i}$ and the
death rates ($\delta_{i}$ $i=1\ldots N,j=1\ldots N$)

  * •

Find the condition under which a datum will suffer _fast extinction_.

To simplify the problem and to avoid dependencies on starting conditions, we
consider the case where all nodes are initially in the _have info_ state.

####  I.0.2 Main Idea

Solving this problem for the full Markov chain requires $3^{N}$ variables and
is thus intractable, even for moderate-sized networks. Exact values for the
_fast extinction_ threshold are unavailable even for simpler versions of this
problem. The main contribution of Deepa1  is an accurate approximation, using
a non-linear dynamical system of only $N$ variables. The heart of their
approximation is to consider the states of the two different nodes to be
mutually independent. Let the probability of node $i$ being in the _Has Info_
and _No Info_ states at time $t$ be $p_{i}(t)$ and $q_{i}(t)$ respectively.
Thus, the probability of its being dead is $(1-p_{i}(t)-q_{i}(t))$. Starting
from state _No Info_ at time $t-1$, node $i$ can acquire this information (and
move to state _Has Info_) if it receives a communication from some other node
$j$. Let $\zeta_{i}(t)$ be the probability that node $i$ does not receive the
information from any of its neighbors. Then, assuming the neighbor’s states
are independent:

$\zeta_{i}(t)=\prod_{j=1}^{N}(1-r_{j}\beta_{ji}p_{j}(t-1))$ (1)

For each node $i$, we can use the transition matrix in Diagram 1 to write down
the probabilities of being in each state at time $t$, given the probabilities
at time $t-1$ (recall that we use very small time steps $\Delta t$, and so we
can neglect second-order terms). Thus:

$p_{i}(t)=p_{i}(t-1)(1-\delta_{i})+q_{i}(t-1)(1-\zeta_{i}(t))$ (2)

$q_{i}(t)=q_{i}(t-1)(\zeta_{i}(t)-\delta_{i})+(1-p_{i}(t-1)-q_{i}(t-1))\gamma_{i}$
(3)

####  I.0.3 Main previous Results

In Deepa1 , experimental results have been obtained under fast extinction
conditions that accurately correspond to what their model predicts. The
authors claim that the accuracy of their model predictions are due to the
_mixing properties_ of real networks. For the sake of completeness we will
state the main results in Deepa1  and to show how some of them are obtained
because our own results will be obtained by applying the same procedures.

######  Definition 2.

Define $S$ to be the $N\times N$ system matrix:

$S_{ij}=\left\\{\begin{array}[]{ll}1-\delta_{i}&~{}~{}~{}~{}\text{if~{}}i=j\\\
r_{j}\beta_{ji}\frac{\gamma_{i}}{\gamma_{i}+\delta_{i}}&~{}~{}~{}~{}\mbox{otherwise}\end{array}\right.$

Let $|\lambda_{1,S}|$ be the magnitude of the largest eigenvalue and
$\widehat{C}(t)=\sum_{i=1}^{N}p_{i}(t)$ the expected number of carriers at $t$
of the dynamical system.

######  Theorem 1.

(Condition for fast extinction). Define $s=|\lambda_{1,S}|$ to be the
survivability score for the system. If $s=|\lambda_{1,S}|<1$, then we have
fast extinction in the dynamical system, that is, $\widehat{C}(t)$ decays
exponentially quickly over time.

Where $|\lambda_{i,S}|$ is the magnitude of the largest eigenvalue of $S$,
being $S$ an $N\times N$ system matrix defined as $S_{ij}=1-\delta_{i}$ if
$i=j$ and $S_{ij}=r_{j}\beta_{ji}\frac{\gamma_{i}}{\gamma_{i}+\delta_{i}}$
otherwise, and being $\widehat{C}(t)=\sum_{i=1}^{N}p_{i}(t)$ the expected
number of carriers at time $t$ of the dynamical system. Two additional results
that appears in Deepa1  are the following

######  Lemma 1.

Fixed point. The values
$(p_{i}(t)=0,q_{i}(t)=\frac{\gamma_{i}}{\gamma_{i}+\delta_{i}})$ for all nodes
$i$, are a fixed point of the equations (2) and (3). Proved by a simple
application of the Equations.

######  Theorem 2.

(Stability of the fixed point). The fixed point point of Lemma 1 is
asymptotically if the system is bellow threshold, that is,
$s=|\lambda_{1,S}|<1$

######  Lemma 2.

(From reference [8] of Deepa1 ) Define $\nabla(f)$ (also called the Jacobian
matrix) to be a $2N\times 2N$ matrix such that

$[\nabla(f)]_{ij}=\frac{\partial
f_{i}(\vec{v}(t-1))}{\partial\vec{v}_{j}(t-1)}$ (4)

where $\vec{v}$ is the concatenation of $\vec{p}$ and $\vec{q}$. Then, if the
largest eigenvalue (in magnitude) of $\nabla(f)$ at $\vec{v}_{f}$ (vector
$\vec{v}$ valued at the fixed point) is less than $1$ in magnitude, the system
is asymptotically stable at $\vec{v}_{f}$. Also, if $f$ is linear and the
condition holds, then the dynamical system will exponentially tend to the
fixed point irrespective of initial state.

In Deepa1  the authors apply (2) and obtain the following block matrix

$\nabla(f)|_{\vec{v}_{f}}=\left[\begin{array}[]{lll}S&|&0\\\ \hline\cr
S_{1}&|&S_{2}\end{array}\right]$ (5)

The dimensions of each block matrix are $N\times N$ whose elements are

$S_{ij}=\left\\{\begin{array}[]{ll}1-\delta_{i}&~{}~{}~{}~{}\text{if~{}}i=j\\\
r_{j}\beta_{ji}\frac{\gamma_{i}}{\gamma_{i}+\delta_{i}}&~{}~{}~{}~{}\mbox{otherwise.}\end{array}\right.$
(6)

The others are

$S_{1ij}=\left\\{\begin{array}[]{ll}1-\delta_{i}&~{}~{}~{}~{}\text{if~{}}i=j\\\
-r_{j}\beta_{ji}\frac{\gamma_{i}}{\gamma_{i}+\delta_{i}}&~{}~{}~{}~{}\mbox{otherwise}\end{array}\right.$
(7)

and

$S_{2ij}=\left\\{\begin{array}[]{ll}1-\gamma_{i}-\delta_{i}&~{}~{}~{}~{}\text{if~{}}i=j\\\
0&~{}~{}~{}~{}\mbox{otherwise}\end{array}\right.$ (8)

So the question is _how can be obtained the fixed point of the system?_. In
the following paragraph we will sketch, in an alternative way of the used in
Deepa1 , how it can be done. In dynamical systems theory the _fixed point_ is
called _equilibrium point_ of the system. In this very point the state
probabilities become stable, then $p_{i}(t)=p_{i}(t-1)$ and
$q_{i}(t)=q_{i}(t-1)$. Then simplifying the notation by dropping the subindex
and the time parameter we can state the following equations system:

$\begin{array}[]{l}p=p\cdot(1-\delta)+q\cdot(1-\zeta)\\\
q=q\cdot(\zeta-\delta)+(1-p-q)\cdot\gamma\end{array}$ (9)

after algebraic simplification it can be obtained the following equations
system

$\begin{array}[]{l}-\delta\cdot p+(1-\zeta)\cdot q=0\\\ \gamma\cdot
p+(\zeta-1-\delta-\gamma)\cdot q=q\end{array}$ (10)

Expressing the equations system in matrix form we get

$\left[\begin{array}[]{ll}-\delta&1-\zeta\\\
-\gamma&\zeta-1-\delta-\gamma\end{array}\right]\left[\begin{array}[]{l}p\\\
q\end{array}\right]=\left[\begin{array}[]{l}0\\\ -\gamma\end{array}\right]$
(11)

Solving by Cramer’s method we obtain

$\begin{array}[]{l}p=\frac{\gamma\cdot(1-\zeta)}{\gamma\cdot(1-\zeta)-\delta\cdot(\zeta-1-\delta-\gamma)}\\\
q=\frac{\delta\cdot\gamma}{\gamma\cdot(1-\zeta)-\delta\cdot(\zeta-1-\delta-\gamma)}\end{array}$
(12)

The expressions (12) can be simplified by observing that the stable state _No
Info_ is related with the desired _fast extinction_ condition that is also
related with Markov chain probability condition $(1-\zeta)\rightarrow 0$, that
implies $p\rightarrow 0$. Taking into account this fact, we can rewrite (12)
as follows:

$\begin{array}[]{ll}p=&\frac{\gamma\cdot(1-\zeta)}{\gamma\cdot(1-\zeta)+\delta\cdot(1-\zeta+\delta+\gamma)}\\\
~{}~{}=&0\\\
q=&\frac{\delta\cdot\gamma}{\gamma\cdot(1-\zeta)-\delta\cdot(\zeta-1-\delta-\gamma)}\\\
~{}~{}=&\frac{\delta\cdot\gamma}{\gamma\cdot(1-\zeta)+\delta\cdot(1-\zeta+\delta+\gamma)}\\\
~{}~{}=&\frac{\delta\cdot\gamma}{\delta\cdot(\delta+\gamma)}\\\
~{}~{}=&\frac{\gamma}{\delta+\gamma}\end{array}$ (13)

###  I.1 Markovian Analysis

In Deepa1  the Markovian analysis was avoided because of the size of the
resulting configuration space ($3^{N}$ where $N$ correspond to the number of
nodes and $3$ to number of states in the Markov chain). However, it is
interesting to analyse the ergodicity behaviour of the Markov chains
associated inside each node. We have done this by the calculation of the
corresponding Z-transform of the associated matrix and performing the
following steps:

  * •

We obtain the transition matrix $P$

$P=\left(\begin{array}[]{ccc}(1-\delta)&0&\delta\\\
(\delta-\zeta)&(1-\zeta)&\delta\\\ (1-\gamma)&0&\gamma\end{array}\right)$ (14)

  * •

We calculate the Z-transform of the matrix $M=I-zP$, that is

$M=\left(\begin{array}[]{ccc}1-z(1-\delta)&0&-z\delta\\\
z(\delta-\zeta)&1-z(1-\zeta)&-z\delta\\\
z(-1+\gamma)&0&1-z\gamma\end{array}\right)$ (15)

  * •

The inverse matrix $M^{-1}$ of $M$ is obtained

  * •

The inverse Z-transform is applied to $M^{-1}$, obtaining

$H(n)={\cal{Z}}^{-1}\\{{M^{-1}}\\}$

This equation can be written as a sum of two matrices Howard , $S$ that
corresponds to the steady behavior and $T$ that represents the transient
behavior of the Markov Chain, that is

$H(n)=k_{1}S+k_{2}(C_{1})^{n}T$,

where $k_{1}$ and $k_{2}$ are constants. Based on this procedure we obtained
the ergodicity condition, that is, $C_{1}<1$ what assures the convergence to a
steady state no matter what the initial state was.

All the calculations were made using MATHEMATICA and the ergodicity condition
expression obtained is given by

$\noindent{C_{1}=\frac{2-\gamma-\delta+\sqrt{\gamma^{2}-6\gamma\delta+\delta^{2}}}{1-\gamma-\delta+2\gamma\delta}}.$
(16)

It’s worthy to notice that the ergodicity of the Markov chain depends on the
values of the transition probabilities involved. We should also mention that
the calculations of this analysis are an additional source of difficulty. The
more states the Markov chain have, the more complex become the algebraic
manipulation and Z-transforms. So, it is not a surprise that the Markovian
analysis was avoided in Deepa1  and the choice was the dynamical systems
approach.

##  II Our proposal

The model described in subsection I.0.1 and that constitutes the core of the
results obtained in Deepa1  has as main purpose to estimate the threshold
condition under which the propagation of a virus in a P2P network decays
exponentially. This last question implies that for keeping the network below
the threshold just mentioned, the protocols have to disconnect temporarily
some nodes, fix the problem and reboot them. This method is very efficient for
stopping the propagation of the virus. In this way the number of virus
carriers decays exponentially. Let us assume that at the same time we need to
propagate an alarm signal warning about the presence of a worm virus or an
antidote chayes1  in a P2P network. Then in these cases we need that the
network operates over the estimated threshold. So we are in a situation where
the threshold conditions are antagonist and that can happen in a real world
setting. Under such circumstances the question is _How to keep a datum and at
the same time avoid the virus spreading?_. Our hypothesis is that it will
depend on the proportion of virus messages versus warning messages. For this
reason we will propose a new model that will take into account this situation.
The previous and the new additional symbols are listed in Table 2.
${\scriptsize\begin{array}[]{|l|l|}\hline\cr\mbox{Symbol}&\mbox{Description}\\\
\hline\cr N&\mbox{Number of nodes in a network}\\\
\beta_{ij}&\mbox{Probability that the link}\\\ {}{}{}{}{}&i\rightarrow
j\mbox{is up}\\\ \delta_{i}&\mbox{Death rate: Probability that
node~{}}i\mbox{~{}dies}\\\ \gamma_{i}&\mbox{Resurrection rate:}\\\
{}{}{}{}&\mbox{Probability that node~{}}i\mbox{~{}comes back up}\\\
r_{i}&\mbox{Retransmission rate:}\\\ {}{}{}{}{}&\mbox{Probability that
node}i\mbox{~{}broadcasts}\\\ \hline\cr p_{i}(t)&\mbox{Probability that
node}\\\ {}{}{}{}{}&i\mbox{~{} is infected at time}t\mbox{~{}and has virus
info}\\\ q_{i}(t)&\mbox{Probability that node has no Info}\\\ {}{}{}{}&i\mbox{
~{} is healthy at time}t\mbox{~{}but susceptible}\\\
1-p_{i}(t)-q_{i}(t)-w_{i}(t)&\mbox{Probability that node}i\mbox{~{}is dead}\\\
w_{i}(t)&\mbox{Probability that node has warning Info}\\\ {}{}{}{}&i\mbox{ ~{}
is warned at time}t\\\ \zeta_{i}&\mbox{Probability that
node}i\mbox{~{}does}\\\ {}{}{}{}&\mbox{not receive info from}\\\
{}{}{}{}&\mbox{any of its neighbors at time~{}}t\\\ \nu_{i}&\mbox{Probability
that node}i\\\ {}{}{}{}&\mbox{receive virus}\\\ 1-\nu_{i}&\mbox{Probability
that node}i\\\ {}{}{}{}&\mbox{receive a warning}\\\ \chi_{i}&\mbox{Probability
that node}i\\\ {}{}{}{}&\mbox{applies vaccin}\\\
\vec{p}(t),\vec{q}(t)&\mbox{Probability column vectors}\\\
f:\Re^{2N}\rightarrow\Re^{2N}&\mbox{Function representing a dynamical
system}\\\ \nabla(f)&\mbox{The Jacobian matrix of~{}}f(.)\\\
S&\mbox{The~{}}N\times N\mbox{~{}system matrix}\\\ \lambda_{S}&\mbox{An
eigenvalue of the~{}}S\mbox{matrix}\\\ \lambda_{1,S}&\mbox{The largest in
magnitude}\\\ {}{}{}{}&\mbox{eigenvalue of the}S\mbox{matrix}\\\
s=|\lambda_{1,S}|&\mbox{Survivability score = Magnitude of}\lambda_{1,S}\\\
\hline\cr\end{array}}$

This system can be modeled as well as a Markov chain, where each node can be
in one of three states: _Infected_ ,_Warn Info_ , _No Info_ or _Dead_ , with
transitions between them as shown in Diagram 2. The full state of the system
at any instant consists of $N$ such states, one for each node. Therefore,
there are $4^{N}$ system states. Transitions out of the current system state
depend only on the current state and not on any previous states; then it is a
Markov chain without memory. The next graph represent the transitions that
take place in each node for our model.
Resurrected$\gamma_{i}$Prob
$1-p_{i}-q_{i}-w_{i}$$1-\gamma_{i}$Dies$\delta_{i}$InfecInfoProb
$p_{i}$$1-\delta_{i}$Dies$\delta_{i}$Receives
Virus$(1-\zeta_{i}(t))\nu_{i}$NoInfoWarnInfo

$\zeta_{i}(t)-\delta_{i}$Prob
$q_{i}$DeadWarn$(1-\zeta_{i}(t))$$\cdot(1-\nu_{i})$$\chi_{i}$$1-\chi_{i}-\delta_{i}$$\delta_{i}$Prob
$w_{i}$Diagram 2: Transitions on each node

Making the same node independence probability assumption that is stated in
equation (1) and taking into account the new states and transition
probabilities shown in the Diagram 2, the equations (2) and (3) as well as the
new equation corresponding to $w_{i}$ can be expressed as follows:

$\displaystyle p_{i}(t)$ $\displaystyle=$ $\displaystyle
p_{i}(t-1)(1-\delta_{i})+q_{i}(t-1)(1-\zeta_{i}(t))\nu_{i}$ (17)
$\displaystyle q_{i}(t)$ $\displaystyle=$ $\displaystyle
q_{i}(t-1)(\zeta_{i}(t)-\delta_{i})+$
$\displaystyle(1-p_{i}(t-1)-q_{i}(t-1)-w_{i}(t-1))\gamma_{i}$
$\displaystyle+\chi_{i}w_{i}(t-1)$ $\displaystyle w_{i}(t)$ $\displaystyle=$
$\displaystyle(1-\zeta_{i}(t))(1-\nu_{i})q_{i}(t-1)$
$\displaystyle+(1-\chi_{i}-\delta_{i})w_{i}(t-1)$

Also in our case of study, instead of solving the Markov Chain, that is rather
complicated, we will describe the behaviour of our system considering it as a
dynamical system described by the equations (17), (II) and (II). Following
Hirsch  we will calculate the fixed points of the system. As we have stated
before, in these very points the state probabilities become stable, then
$p_{i}(t)=p_{i}(t-1)$, $q_{i}(t)=q_{i}(t-1)$ and $w_{i}(t)=w_{i}(t-1)$. Using
(17), (II) and (II), we can state the following result

######  Lemma 3.

$p_{i}(t)+q_{i}(t)+w_{i}(t)\rightarrow\frac{\gamma_{i}}{\gamma_{i}+\delta_{i}}$
Proof: In the same way that has been done in Deepa1  we can do the subtraction
$1-p_{i}(t)-q_{i}(t)-w_{i}(t)$ and simplify by renaming
$x_{i}(t)=p_{i}(t)+q_{i}(t)+w_{i}(t)$ what give us the following linear system

$x_{i}(t)=(1-\delta_{i}-\gamma_{i})\cdot x_{i}(t-1)+\gamma_{i}$ (20)

In the fixed point $x_{i}(t)=x_{i}(t-1)$ so if we apply this to the last
equation we have that

$x_{i}(t)=\frac{\gamma_{i}}{\gamma_{i}+\delta_{i}}$ (21)

that is,
$p_{i}(t)+q_{i}(t)+w_{i}(t)=\frac{\gamma_{i}}{\gamma_{i}+\delta_{i}}$. Then by
Lemma 2 in Deepa1 , this convergence is exponential.

It is worthy to notice that the same results for the fixed points are obtained
considering the linear behaviour of the system on these points. Using (17),
(II) and (II) and for simplicity dropping the indexes and the the time
dependance, we obtain the equations

$\begin{array}[]{l}-\delta\cdot p+\nu(1-\zeta)\cdot q=0\\\
(-1+\zeta-\delta-\gamma)q+(-\gamma+\chi)w=-\gamma\\\
(1-\zeta-\nu+\zeta\nu)q+(1-\chi-\delta)w=0\\\ \end{array}$ (22)

Whose solutions can be obtained using Cramer’s method

$\begin{array}[]{l}p=-\frac{\gamma\cdot(-1+\zeta)\nu(\delta+\chi)}{(\gamma+\delta)\left(\delta+\delta^{2}-\delta\zeta+\delta\chi+\nu\chi-\zeta\nu\chi\right)}\\\
\\\
q=\frac{\gamma\delta(\delta+\chi)}{(\gamma+\delta)\left(\delta+\delta^{2}-\delta\zeta+\delta\chi+\nu\chi-\zeta\nu\chi\right)}\\\
\\\
w=\frac{\gamma\delta(1-\zeta-\nu+\zeta\nu)}{(\gamma+\delta)\left(\delta+\delta^{2}-\delta\zeta+\delta\chi+\nu\chi-\zeta\nu\chi\right)}\par\end{array}$
(23)

Once more, this expression can be simplified if we observe that the stable
state _No Info_ is related with the desired _fast extinction_ condition that
is also related with Markov chain probability condition $(1-\zeta)\rightarrow
0$, that implies $p\rightarrow 0$, this can be summarized as

$\begin{array}[]{l}p=0\\\ \\\ q=\frac{\gamma}{\gamma+\delta}\\\ \\\
w=0\par\end{array}$ (24)

Given that by hypothesis, the probability of events in each node are
independent, we can try to analyse the problem using the Markov approach. This
will be made in the next subsection.

###  II.1 Markovian Analysis

In this section we analyse again the ergodicity behaviour of the Markov chains
associated inside each node under our model.

The calculation steps performed were :

  * •

We obtain the transition matrix $P$

$P=\left(\begin{array}[]{ccccc}\zeta_{i}(t)-\delta_{i}&(1-\zeta_{i}(t))\nu_{i}&(1-\zeta_{i}(t))(1-\nu_{i})&\delta_{i}\\\
0&1-\delta_{i}&0&\delta_{i}\\\ \chi_{i}&0&1-\chi_{i}-\delta_{i}&\delta_{i}\\\
\gamma_{i}&0&0&1-\gamma_{i}\par\end{array}\right)$ (25)

  * •

we calculate the Z-transform of the matrix $M=I-zP$, that is

$M=\left(\begin{array}[]{cccc}1-z(-\delta+\zeta)&z(-1+\zeta)\nu&z(-1+\zeta)(1-\nu)&-z\delta\\\
0&1-z(1-\delta)&0&-z\delta\\\ -z\chi&0&1-z(1-\delta-\chi)&-z\delta\\\
-z\gamma&0&0&1-z(1-\gamma)\end{array}\right)$ (26)

  * •

The inverse matrix $M^{-1}$ of $M$ is obtained

  * •

The inverse Z-transform is applied to $M^{-1}$, obtaining

$H(n)={\cal{Z}}^{-1}\\{{M^{-1}}\\}$

This equation can be written as a sum of two matrices Howard , $S$ that
corresponds to the steady behavior and $T$ that represents the transient
behavior of the Markov Chain, that is

$H(n)=k_{1}S+k_{2}(C_{1})^{n}T$,

where $k_{1}$ and $k_{2}$ are constants. Based on this procedure we obtained
the ergodicity condition, that is, $C_{1}<1$ what assures the convergence to a
steady state no matter what the initial state was.

All the calculations were made using MATHEMATICA and the ergodicity condition
expression obtained is given by

$C_{1}=\frac{1-2\delta+\zeta-\chi+\sqrt{1-2\zeta+\zeta^{2}+2\chi-2\zeta\chi-4\nu\chi+4\zeta\nu\chi+\chi^{2}}}{\delta^{2}+\zeta+(-1+\nu)\chi-\zeta\nu\chi+\delta(-1-\zeta+\chi)}.$
(27)

Again, it can be noticed from the calculation above, that the ergodicity of
the associated Markov chain depend on the choice of the transition
probabilities involved. It should be also mentioned that the algebraic
manipulations become even more complex than in the case of the Markov chain of
Deepa1  given that our Markov chain have one state more.

###  II.2 Jacobian and fix point

In our case of study, we can proceed as Deepa1 . Firstly, let us define the
column vectors $\vec{\mathbf{p}}(t)=(p_{1}(t),p_{2}(t),\dots,p_{N}(t))$,
$\vec{\mathbf{q}}(t)=(q_{1}(t),q_{2}(t),\dots,q_{N}(t))$ and
$\vec{\mathbf{w}}(t)=(w_{1}(t),w_{2}(t),\dots,w_{N}(t))$. Let the vector
$\vec{\mathbf{v}}(t)=(\vec{\mathbf{p}}(t),\vec{\mathbf{q}}(t),\vec{\mathbf{w}}(t))$
be the concatenation of the previous vectors and let $\vec{\mathbf{v}}_{f}(t)$
be the vector $\vec{\mathbf{v}}(t)$ evaluated at the fixed point. Then, the
entire system can be described by

$\vec{\mathbf{v}}(t)=\mathbf{f}(\vec{\mathbf{v}}(t-1))$ (28)

where

$f_{i}(\vec{\mathbf{v}}(t-1))=\left\\{\begin{array}[]{lllll}p_{i}(t-1)(1-\delta_{i})&~{}~{}\text{if~{}}i\leq
N&\\\ +q_{i}(t-1)(1-\zeta_{i}(t))\nu_{i}\\\ &\\\
q_{i}(t-1)(\zeta_{i}(t)-\delta_{i})\\\
+(1-p_{i}(t-1)-q_{i}(t-1)&~{}~{}\text{if~{}}N<i\leq 2N&\\\
-w_{i}(t-1))\gamma_{i}+\chi_{i}w_{i}(t-1)\\\ &\\\
(1-\zeta_{i}(t))(1-\nu_{i})q_{i}(t-1)\\\
+(1-\chi_{i}-\delta_{i})w_{i}(t-1)&~{}~{}\text{if~{}}2N<i\leq
3N&\end{array}\right.$

Now, following Hirsch , let us define the the Jacobian matrix of the system,
$\nabla\mathbf{f}$ as

$[\nabla\mathbf{f}]_{ij}=\frac{\partial
f_{i}(\vec{\mathbf{v}}(t-1))}{\partial\vec{\mathbf{v}}(t-1)}.$

In order to explore the asymptotic stability of fixed points and according to
Hirsch  we will have to take into account the value of the function
$\nabla\mathbf{f}$ in these points In our case, we obtain the $3N\times 3N$
Jacobian matrix

$\nabla(\mathbf{f})|_{\vec{\mathbf{v}}_{f}}=\left[\begin{array}[]{lllll}S&|&0&|&0\\\
\hline\cr S_{1}&|&S_{2}&|&S_{3}\\\ \hline\cr
S_{4}&|&0&|&S_{6}\end{array}\right]$ (29)

where each block $S,S_{1},\dots$ is a $N\times N$ matrix whose elements are
given by

$S_{ij}=\left\\{\begin{array}[]{ll}1-\delta_{i}&~{}~{}~{}~{}\text{if~{}}i=j\\\
r_{j}\beta_{ji}\nu_{i}\frac{\gamma_{i}}{\gamma_{i}+\delta_{i}}&~{}~{}~{}~{}\mbox{otherwise}\end{array}\right.$
(30)

and the others are

$S_{1ij}=\left\\{\begin{array}[]{ll}-\gamma_{i}&~{}~{}~{}~{}\text{if~{}}i=j\\\
-r_{j}\beta_{ji}\frac{\gamma_{i}}{\gamma_{i}+\delta_{i}}&~{}~{}~{}~{}\mbox{otherwise}\end{array}\right.$
(31)

$S_{2ij}=\left\\{\begin{array}[]{ll}1-\gamma_{i}-\delta_{i}&~{}~{}~{}~{}\text{if~{}}i=j\\\
0&~{}~{}~{}~{}\mbox{otherwise}\end{array}\right.$ (32)

$S_{3ij}=\left\\{\begin{array}[]{ll}-\gamma_{i}+\chi_{i}&~{}~{}~{}~{}\text{if~{}}i=j\\\
0&~{}~{}~{}~{}\mbox{otherwise}\end{array}\right.$ (33)

$S_{4ij}=\left\\{\begin{array}[]{ll}0&~{}~{}~{}~{}\text{if~{}}i=j\\\
r_{j}\beta_{ji}\frac{(1-\nu_{i})\gamma_{i}}{\gamma_{i}+\delta_{i}}&~{}~{}~{}~{}\mbox{otherwise}\end{array}\right.$
(34)

$S_{6ij}=\left\\{\begin{array}[]{ll}1-\chi_{i}-\delta_{i}&~{}~{}~{}~{}\text{if~{}}i=j\\\
0&~{}~{}~{}~{}\mbox{otherwise.}\end{array}\right.$ (35)

Once we have calculated the Jacobian matrix of the system we can extend the
results of Lemma 2. That is, if the largest eigenvalue (in magnitude) is less
than one then it is assured that the system is asymptotically stable in the
fixed point $\vec{\mathbf{v}}$ and the dynamical system will exponentially
tend to the fixed point whatever was the initial state. Those interested in
the detailed proof of this Lemma 2 can consult the appendix of Deepa1 .

##  III Simulations.

Until now, we have theoretically described the behaviour of the net.

Figure 1: Number of carriers $C(t)$ vs time (simulation epochs) in Chakrabarti
model under the threshold. Values for $\delta=0.1$ and $\gamma=0.01$ Figure 2:
Number of carriers $C(t)$ vs time (simulation epochs) in our model under the
threshold. Values for $\delta=0.1$ and $\gamma=0.01$. Figure 3: Number of
carriers $C(t)$ vs time (simulation epochs) in Chakrabarti model on the
threshold. Values for $\delta=0.07$ and $\gamma=0.004$ Figure 4: Number of
carriers $C(t)$ vs time (simulation epochs) in our model on the threshold.
Values for $\delta=0.07$ and $\gamma=0.004$. Figure 5: Number of carriers
$C(t)$ vs time (simulation epochs) in Chakrabarti model above the threshold.
Values for $\delta=0.01$ and $\gamma=0.01$ Figure 6: Number of carriers $C(t)$
vs time (simulation epochs) in our model above the threshold. Values for
$\delta=0.01$ and $\gamma=0.01$

Using the Dynamical Systems approach we have been able to predict the
conditions (a threshold) under which fast extinction is reached by using a
limited set of parameters that assures the we will converge to a fixed point.

In order to complete the study of our model and compare its performance with
the Chakrabarti model, we have made different simulations corresponding to the
cases in which we are under, on and above the threshold values established in
the previous section.

For this end, we have randomly generated the adjacency matrix corresponding to
a thirty node graph. We have taken, for the sake of comparison, the same set
of parameters that appears in section 4 of Deepa1 , that is, $r=0.1$ and
$\beta_{i,j}=0.1$. Additionally, we used the different values of $\delta$ and
$\gamma$ proposed in Deepa1  corresponding to P2P GNUTELLA data sets. We have
fixed $\nu=0.8$ and $\chi=0.1$ and we have started with six infected nodes
that we choose randomly. The number of time steps have been fixed in our
simulation to one and three hundred.

In Figures 1 and 2 it is shown that if the settings of the parameters values
fulfil the fast extinction condition then the same result is obtained in both
models. We can have a diverse set of parameters values as long as we are under
the threshold condition for achieving fast extinction.

In Figures 3 and 4 we show that if the set of parameters are combined in such
a way that they give exactly the threshold value the fast extinction is
achieved again in both models but in this case the fast extinction is slower
than in the first case. When the parameters values are combined in such a way
that we are beyond the threshold value then fast extinction is no longer
accomplished and the number of carriers grow very fast and eventually the
whole set of nodes could become infected. This behaviour is shown in Figures 5
and 6. In this case it can be observed a slight difference between both models
behaviour due to the presence of the parameter $\nu_{i}$.

##  IV Conclusions and Future Work

As we have exposed in the sections corresponding to our proposal, if under our
model $1-\zeta_{i}(t)\rightarrow 0$, our _fix point and fast extinction
condition_ are consistent with those obtained in Deepa1 . In the other side,
if under our model $1-\zeta_{i}(t)>0$, then the _fix point and fast extinction
condition_ mentioned in the appendix section of Deepa1  are not longer valid.
In this last case the dynamical system becomes nonlinear, and the degree of
non-linearity will depend on the topology of the network. In this new setting
our $\nu_{i}$ parameter start to play a rôle in the virus as well as antidote
spreading on the network. In the future we will study this problem. If we take
as starting point this scenario it can be interesting to ask if the system
falls in a chaotic regime and if this is the case then how the stability of
the network can be re-established. If we want to achieve this state of the
system we can recall the synchronization and chaos tools developed in the
research field of automatic control. This is one of the subjects that we will
try to explore in the future.

## References

  * (1) R. Albert and A.L. Barabási.  Error and attack tolerance of complex networks.  Nature, 406, 2000.
  * (2) A.L. Barabási and R. Albert.  Emergence of scaling in random graphs.  Science, 286:509–512, 1999.
  * (3) Ayalvadi Ganesh Christian Borgs, Jennifer Chayes and Amin Saberi.  How to distribute antidote to control epidemics.  Random Structures and Algorithms John Wiley and Sons, Inc. New York, NY, USA, (Volume 37, Issue 2):204–222, 2010.
  * (4) R. Durrett and X.-F. Liu.  The contact process on a finite set.  The Annals of Probability, 16(3):1158–1173, 1988.
  * (5) Alain Barrat Filippo Radicchi, Jose J. Ramasco and Santo Fortunato.  Complex networks renormalization: Flows and fixed points.  Physical Review Letters, (Volume 65):1487011–1487014, 2008.
  * (6) M. W. Hirsch and S. Smale.  Differential Equations,Dynamical Systems, and Linear Algebra.  Academic Press, second edition, 1974.
  * (7) Ronald A. Howard.  Dynamic Programming and Markov Processes.  The MIT Press, fourth edition, 1966.
  * (8) C. Faloutsos S. Madden C. Guestrin J. Leskovec, D. Chakrabarti and M. Faloutsos.  Information survival threshold in sensor and p2p networks.  In IEEE INFOCOM 2007, 2007.
  * (9) D. Kempe and J. Kleinberg.  Protocols and impossibility results for gossip-based communication mechanisms.  In Proceedings of the Symposium on Foundations of Computer Science (FOCS 2002), 2002.
  * (10) P. Faloutsos M. Faloutsos and C. Faloutsos.  On power-law relationships of the internet topology.  In In Proceedings Sigcomm 1999, 1999.
  * (11) D. Ben-Avraham A.L. Barabási N. Schwartz, R. Cohen and S. Havlin.  Percolation in directed scale-free networks.  Physical Review E, 66(1):0151041–0151044, 2002.
  * (12) Itai Benjamini Noga Alon and Alan Stacey.  Percolation on finite graphs and isoperimetric inequalities.  The Annals of Probability, (Volume 32, No.3A):1727–1745, 2004.
  * (13) Romualdo Pastor-Satorras and Alessandro Vespignani.  Epidemic dynamics and endemic states in complex networks.  Physical Review E, (Volume 63, Issue 2):0661171–0661178, 2001.
  * (14) Romualdo Pastor-Satorras and Alessandro Vespignani.  Epidemic spreading in scale-free networks.  Physical Review Letters, (Volume 86, Number 14):3200–3203, 2001\.
  * (15) Romualdo Pastor-Satorras and Alessandro Vespignani.  Epidemic dynamics in finite size scale-free networks.  Physical Review E, (Volume 65):0351081–0351084, 2002.
  * (16) Béla Bollobási Paul Balister.  Bond percolation with attenuation in high dimensional voronoi tilings.  Random Structures and Algorithms, Wiley InterScience, pages 5–10, 2009.