Thanks for the introduction. So I hope everybody can
hear me please do safe? Not. And uh
I hope this is visible. It is great.
Thanks. So, uh as I said, I'm
on today, I'll be talking about dynamical processes on
large networks today. And uh uh first I hope
I don't want to have to convince you that networks
are really everywhere. For example, uh the social
network for example, where people are friends are uh
of each other. And you can see the facebook
network here in 2010 is a very interesting network.
It's a human disease network where notes diseases and edges
are between diseases share genes. So the nice thing
about networks is that they give you the local structure
as well as the global information. Right? Like
you can quickly see how the social network is distributed
throughout the world. You can see how diseases interact
and how the clusters and how similar diseases share similar
genes. So, uh, understanding that what I
wish to convey in this talk is that dynamical processes
over networks are also everywhere. And what it means
by dynamical process will be made clear soon. But
essentially some kind of propagation of spreading kind process on
the network. So why do we care? So
why do we care about this dynamical processes? We
care Because it occurs in lots of different domains and
lots of feels for example, online information refusing is
kind of like a dynamical process viral marketing where people
recommend products to each other on amazon, on twitter
and sales propagate are also a dynamical process. Then
they are also in cybersecurity where virus processes propagate the
epidemiology and public health. It's a big application area
for those kinds of processes and so on. So
I try to give you a sense of two main
application areas in my talk, one is the epidemiology
and one social media. So in epidemiology, the
dynamical process essentially disease spreading over contact networks, right
? Like for example in this contact network, you
have this uh infected with some disease flew his ill
probably spread to one of his neighbors. And what
I mean by contact networks, especially people who come
in contact with each other. Right. Who can
actually spread the disease to one hour. So yeah
, happens. This is a very interesting network actually
. It was the american general Health. It was
uh this is CDC data series is the Center for
Disease Control in Atlanta. And this is the visual
visualization of the 1st 35 tuberculosis patients. So what
it does is it shows you how the patient zero
was there and how he actually he or she spread
the uh disease to other parts of the uh,
in the population. And by the way, the
gray ones do not. People uh cases it's fatal
and the big ones do not which are not.
So you can quickly realized that which the nose you
should have immunized which uh help to control the disease
for example. So just to give you an example
of the type of questions we try to answer using
such uh terminology and abstraction is like this is one
of my work which I did with uh people like
michigan, like it's like each circle is the hospital
and this is like 303 3000 hospitals across the U
. S. And the U. S. Medicare
uh network. And this is like more than 30,000
patients transport. So the question here really was that
we had some k. Units of some infection control
resource. And we wanted to just decide how to
spread them out across the hospitals to immunize to minimize
the patients infected, right? So like we could
, so we developed an algorithm which was like this
the current practice, you can see like the red
ones do not, the hospitals are infected and you
can see the current our method is like almost six
times for your hospital infected. So that's the nice
thing, right? So uh these kinds of abstraction
help you solve such real problems. Uh so the
second application area, which I want to convey his
online diffusion which is like information diffusion in the social
sphere. For example, this is just a snapshot
of the startups and companies which are in the social
sphere in like 2007. So uh like facebook twitter
and linkedin are already really big companies with a lot
of revenue and also projected earnings. So it's a
big, it has a huge economic impact as well
. Uh So for example, in social viral marketing
, what would be the scenario? So you can
think of this as the mega celebrity who has thousands
of followers, all these little birds and suppose the
celebrity says bye to say either the U. S
. Has paid him or her or he tells of
his own volition but the resultant that follows go ahead
and buy something in and everyone makes money. So
uh this is essentially the demise of social media marketing
. Uh And of course given the events of the
past year or so like uh you might imagine the
social networks and uh this dynamical processes can be used
for collaborative action of some sort of changing the world
, right? So uh what I also want to
country is that you have different settings, multiple really
high impact settings but also similar questions are similar code
questions arising in different areas. For example, in
the uh social media setting, you can be like
squashing rumors right? Like somebody spread some bad rumor
about untrue things on twitter. How do you squash
them? How do you see the two information on
different people in the network? How do your opinion
spread? So how do rumors spread might change into
an epidemic spreading epidemiological setting? And how to opinion
spread in a facebook or in a group can be
a similar question can be asked. And how to
products are viruses spread or say a contact network or
influence network and how to market better in the twitter
said it can be also how to transmit software patches
. For example, Windows is working on ways to
transmit software patches in the best efficiently as possible to
prevent attacks. So uh again, hiding back with
multiple settings. So what's the research team? So
my research has really been consulted on these three main
areas, like essentially you have to, there's the
data which is the data about the large real world
applications and processes for and you build models out of
it and then you analyze the models which is the
analysis and understanding part. And once you do the
analysis, the next part is actually using their understanding
from the data to actually develop policy in action on
these processes. So for example, how this look
in epidemiological setting, for example, in the public
health setting, this would be modeling number of patient
transports, right? How how diseases spread among patients
in hospitals. Then the analysis part would be like
a new allies in the epidemic models to say well
an epidemic happened. And the policy and action part
would be essentially how to control outbreaks. I mean
, so once you have understood how the epidemics happened
, you can use that information to actually control the
outbreaks right by uh item distributing, disinfected and similarly
in the social media setting, you can think of
the data is modeling tweets, uh tweets spreading,
the people are retweeting uh information or topics or some
interesting news means item and the analysis would be what
would be the number of cascades and future can predicted
? Can you build a model for it and essentially
then using it for settings like how to market better
? Because once you have that are right. So
in this stock, I'll try to give you three
concrete questions which are trying to answer one of them
would be in the analysis part, which is like
given provocation models. Can you actually predict with an
epidemic happened? So these are really well understood,
well established propagation models and disease spreading. For example
, the second question would be in the policy action
part that once you have understood how these epidemics happened
, can unionize and control these outbreaks better. So
that's that that's a bit more algorithmic, right?
Because it's like you're developing algorithms to control the uh
epidemics. And the final thing I try to spend
some time is how to hashtag spread. For example
, that that give you a flavor of different application
domains here, the data is from twitter with tweets
are spreading among the people active on twitter and you
want to understand how do different topic hashtag just like
topics attached to the tweets and you want to understand
how different topic spread. Right? So as I
said this, the outline of the talk first,
I'll go over the theoretical part which is epidemics,
what happens then the action which is how to immunize
then some learning models from the total data. And
if time permits, I'll try to cover some other
uh other work which have been interested in can do
so uh in epidemic spreading. The fundamental question is
like uh when an epidemic happens. So imagine like
you have a strong virus on this contact network and
uh this probably this guy gets infected and it spread
the infection to his neighbors and then so slowly because
the virus is so virulent and strong, it spreads
to everyone in the network and you have a giant
dick epidemic. So almost everybody in the network is
infected, right? Uh suppose now you have a
weak virus. Uh you would imagine that the infection
would spread just to probably a couple of people and
it dies out, right? And so the footprint
is small, the number of infected people at the
end of small. So really you have these two
regimes of the epidemic and you want to understand what
separates them. So more concretely suppose you have this
number of infected was sustained. This is just the
number of infections per unit time and this is the
about but it's about regime which is the epidemic regime
that a lot of people got infected. And you
also have a bill a regime which is extinction.
And essentially the question is can you find a condition
which separates these two regimes? So right. So
again, just to reiterate you are given the epidemic
model. So of course you need to assume a
model here which is I have learned from the data
analysis analyzed and then you have the virus and under
graph which is essentially the contact network on which the
virus is spreading. And you want to find a
condition for virus extinction. So and I call this
the static version right now because the graph we assume
is static, it doesn't change. So essentially it's
the same given graphics you have. So, uh
, of course there's a fundamental question. You might
think that is interesting in itself, but why is
it important? Right? So it's important for uh
, many reasons. So one of them is that
it can accelerate simulations because these simulations are really expensive
and either done a lot of different machines and using
really huge contact networks and uh, so on.
So it would be really nice to actually be able
to predict analytically, but certainty that what happens,
right? If so if, if a simulation will
lead to a condition where the epidemic doesn't happen,
you don't really need to simulate right? It probably
is not that useful. And also forecasting what if
scenarios, what if the virus was two stripes are
stronger uh half times a week. So what will
happen? What will change how with the distribution of
the epidemic change? And so, uh, and
finally as I'll show later in the dark as well
, it's a great handle to manipulate the spreading which
is controlling outbreaks or maximum argument spreading it. Like
for example, maximum collaboration. So in this part
, the outline is essentially I'll try to give you
quickly a bit of background of the epidemic models.
And so and then the result of the inclusion on
static graph. Some uh, some ideas of the
proof. How Of course I won't be able to
give you the full proof, but I'll try to
give you a sense of what we did. And
as a bonus using similar methodology, you can even
get powerful results and other different areas like what if
the grass for changing over time, for example,
which is the more realistic scenario. Right? And
also in the domain of competing viruses. So let's
go. So this background. So S. I
. R. Is essentially a very simple one of
the most common basic epidemic models which is like it's
got a susceptible infected recovered model which is uh models
like immunity which you gain in mom's once you get
months you'll never get it again in your life.
So uh so the assumption here is that each node
in the network is essentially in three states, one
of them is susceptible, which just means healthy.
One of them is infected, you are infected with
the virus and the third one is removed their unfortunate
where you can get infected again or unfortunately you passed
away. So uh this this is represented by the
state diagram here. So you can think of this
as a susceptible estate I. And art. So
one of these parameters. So you assume that the
graph the virus spreads in this way, for example
, here you have shown three snapshots of the network
. So in the first snapshot this guy has been
infected and it spreads the virus for each of his
neighbors independently with probably DaVita. So that's an assumption
we make that the virus is essentially spreading independently on
the edges from an infected person. So sometime in
the future it is going to this guy spreads the
virus to one of his neighbors. At the same
time there is a competing process and the competing process
, the curing rate that the probability that infected person
cures themselves. Right? And that's delta. So
safe for time is typically three. This guy's cure
himself and he uh this person is infected. So
not that the epidemic has died out, right?
There's no way the epidemic can spread. There are
only two people who who have been affected by the
virus and that's it because there's no other neighbors for
this person. So so essentially we want to identify
when this happens in a general way. Uh as
you can imagine there are a lot of different epidemic
models. Uh we called I called virus propagation models
and uh the stock and uh so one variant of
the science model. It's also very popular model is
the flu like model in this you don't recover,
you don't get any immunity, you become susceptibility.
So uh there's the CRS model that you have temporary
immunity like purposes which is whooping cough and the ci
our moms like like virus incubation and all those things
. And the underlying contact network is essentially home.
Okay, so again, so this is a very
old problem as you can think of because it's very
easy to state and uh it's a lot of work
has been done on the right, so some of
the papers you can see is like from 69 91
so on. But really the key things to take
over here is that all our about structured apologies where
apologies has given its all resume. So it can
be like fully connected clicks which is everybody is connected
to everybody else or blocked Agnes or hierarchy. Uh
population is distributed hierarchical, there are random graphs or
they give the specific virus propagation models, like they
assume the virus propagation model to be some specific structure
and or static graphs where the graphs don't change.
So in the stock, I try to generalize all
these three directions. Right? So how would so
yeah, how would the answer look like? Right
. What should answer depend on. So because the
inputs the problem are essentially the graph and the virus
propagation model. It's reasonable to assume that it should
depend on both of them. Right? That if
you change the graph, the answer change. If
you change the model of the answer should change again
. But how like uh it's clear that because it's
a spreading process, there should be some connectivity metric
of the graph. Right? Uh So how should
the graph player should be average degree or uh expected
degree of max degree of the diameter. All these
are connectivity metrics. And for the virus propagation model
, which farm it is important. For example,
in the CR models, you saw beta and delta
two parameters which ones should be important? Like beta
and delta. Both important or are. And finally
the question is of course, how to combine them
? I mean, it should be linear quadratic explanation
in some format. So the nice thing is that
uh what we found in our uh work was that
it's easily suitable resident. So informally for any arbitrary
topology, which is be represented the topology by an
adjacency matrix. A. It's a matrix. Uh
and by a number of notes, uh and any
virus propagation model in the treasure standard literature. And
if you represent the adjacency matrix, it's only one
parameter lambda, which is the largest organ value of
the C matrix. I'll try to give you an
intuition about what it exactly means. And also a
constant cBP in which we talk to C B p
M. And it's a constant depending on the virus
propagation model and it's an explicit constant. We give
the constant in the proof. And given these two
things, there's no epidemic. If lambda times CPM
is less than one, that's it. So the
graph interacts with the threshold question. Uh The threshold
question uh only with only one parameter and its linear
in combination. Right? So it's lambda times C
B P. M. And C B P.
M is essentially a constant which is depending on the
virus propagation model. So if you multiply that and
it's less than one you're done. So how does
this uh threshold actually substantiate in particular models? So
some of these models, so just the standard is
a discussion. I'll try to use this term which
is effective strength. I do not it by S
. And so this is essentially this product. So
if this product is less than one year below threshold
, otherwise you're about threshold. So for the for
a whole bunch of models S. I. R
. S. I. S. This the flu
like this, the moms like and all the alphabet
soup, you can think that it's just lambda,
beta delta. So the important thing to note here
is that uh all these models actually have much more
parameters. For example, S. I. R
. S. Has a forgetting factory. It's temporary
immunity. So you gain immunity, then you lose
it. So there are a lot of different factors
which actually are in the model, but they don't
play a role in the threshold. And this gives
you a sense of the power of the result,
right? Because you can see these interactions play out
in the uh result. And for all these cases
lambda is essentially uh the graph the interacts only the
uh by the parameter lambda. Uh And they are
much more complicated models have said. But for example
, this model has two infected states. So it's
it's a bit more complex model for all of them
. The threshold is S is equal to one.
That's it. So what's the intention for lambda?
Right. So the official linear algebra definition is essentially
it's the root of the of the largest magnitude of
the characteristic polynomial. So sure, it doesn't give
too much attention. So uh what's the unofficial intuition
? This is essentially the number of parts of the
graph. So what we so imagine this adjacency matrix
, right? And if you take it to the
chaos power, then the I I. J.
Element in this matrix. This a square matrix and
digest element is essentially the number of parts from I
to change the network. So of course this parts
of repeated and their loops. But the rough intuition
is that it's captures the conduct of the graph in
that sense. And if you take the spectral decomposition
, so you don't need to know much about the
decomposition, apart from the fact that it involves tagging
value uh and the Eigen vectors. So we took
it just to the first I can vector and Eigen
value, you can see that lander to the parquet
. We don't care about these things. The lander
to the arcade government essentially. What's the magnitude of
this matrix in some sense? So how does it
look for some paragraphs? Right, So for example
, look at this uh there's a change star and
click uh all of have the same number of notes
, but uh different number of edges in particular.
These two are actually same number of edges. But
intuitively you can imagine that star is better for the
virus, right? Because once you infect the center
it will quickly spread. So how does it look
turned up in the wagon value so well, so
the differences are not too large here. But uh
, if you make it end notes, for example
, that how would it look like the value of
the star is essentially the uh, sorry, the
chain is essentially constant. So it's uh, the
corresponds to intuition, right? So to 10 no
change is probably as bad as 100. No change
. But the 10 note star is much better than
100 note stuff. And in particular grows as lieutenant
here and it grows as landmines from click is the
worst. Right? Because once you infect anyone of
them, you can quickly infect the rest of the
world. So uh, yeah, I've given also
values for them and see and it's called 1000.
Right? So what I wish to claim is that
for this problem, better connectivity is highlander. So
like and uh, I'll give you some examples of
uh, this result. So for maybe use a
really huge graphics was actually developed by the folks at
any ssl here in Virginia Tech and this is a
really huge graph like 31 million links and six million
notes. And uh it's been used lots of outbreak
stories like smallpox and all those things. And so
you can see two graphs here, we simulated the
sierra Madre here. So the two graphs are infection
profile and the takeoff plot. The infection profile,
essentially the number of people infected number of nodes infected
per unit time. So you can clearly see the
two different regimes. What it doesn't show is exactly
where the regime separate and this is this is what
this blood shows. So that the takeoff plot,
you can see that the X axis, the effective
strength, if you remember the effective strength was s
the product and biases the footprint essentially how many people
were in effect at the end of the infection.
So how bad the infection was. So you can
see that this is the predicted threshold at 10 0
which is one. And then the effective strength is
one. Suddenly the footprint takes off so you can
see that we can market these two regimes. Uh
And just to give you a further example, there's
another plot with the I. R. S.
Model which is the temporary immunity model purposes and you
can see similar behaviors. They're like uh So not
that effective strength incidentally means the same thing here.
Right? It's still land a bit of a delta
. It doesn't matter uh even though the series as
an extra parameter. So yeah. Right now that
I've given you a sense of the result and what
it means in different models uh I will try to
go a bit over the proof. Right. So
what's the proof sketch? So there are two main
ingredients in our model, in our proof which gives
rise to this nice operability between these two parameters,
which is one of the model, one on one
of the model, one on the graph. So
what are these two ingredients? One is the generalized
virus propagation model structure. That we have tried to
generalize all these cascade style models into some coherent structure
which is uh which captures every one of them and
get distracted. And at the same time we used
ideas from stability theory equivalents and stability points to actually
get some handle on the uh on the land or
how to involve the graph in the computation. So
these are the two ingredients which give rise to these
two parameters of the proof. So, for the
first part of our March, so they're all these
models. Right? And what we were able to
do, well we were able to convert all of
them into one big generalized model which you call S
. S. Stars for restart. So this uh
essentially represents these uh there are three different types conceptual
types of states in these kinds of models, one
of them susceptible, one of them is infected and
one of them is vigilant. And in our model
and I generalized model there can be any number of
states and any on any of these classes, right
? Because there's a family journalist state diagram respectively.
So and so the interesting part here is that there
is a big red arrow. So these are what
we term has graft, this transition. So intuitively
it just means that you can get infected only by
your neighbor. You can't just get infected by your
own. If you can get infected by your own
then it's it's not really a cascade style model.
Right? So this is this is one of the
only assumptions that you use and we were able to
generalize the whole, you know, big set of
models. So I won't go over this. Essentially
what I want to say here is that the huge
big boulders uh hire all these complexities, right?
There can be any number of transitions from any number
of states. You can have transition between states across
classes and so on. So uh yeah. So
what's the special case? So if you have just
one susceptible uh known one uh infected no one vigilant
state then it's just you're playing or less. I
our model right? That you have already seen before
. So another example is this which you are two
different uh infected states. So here essentially this means
non terminal and this is a terminal case for HIV
and what it shows is multiple, vigilant and multiple
infectious states. Uh The second ingredient in the proof
. Once you have generalized the model is essentially and
uh nonlinear dynamical system and stability theory. So the
key idea here is that view the whole system,
the view the whole evolution of the epidemic system as
a energies which is an only in a dynamical system
. And here essentially you have a big huge vector
B. D. Plus one which is a function
of the previous state which is P. T.
And what's the what's the relation between these two states
? Especially given by the function G. Which is
a huge but not only in your function. So
it's discrete time as you can see. So the
key idea here is that the P. T.
Can be probably directorate. It just states the what
specifies the state of the system at time, t
what's the probability of each note in the graph,
being in each state of the system and so on
. And jesus, as I said, a huge
big anonymous function. So it's a huge messy function
for the generalized model, which I won't try to
right here. But the idea is that it gives
explicitly gives the evolution of the system. So once
you're given gene, what you're given B you can
explicitly of all the system. Now the now that
you have an only in a dynamical system which is
given by PNG what what you do with it.
The next idea is that you transform the threshold question
, which is when an epidemic will happen. We're
tipping point question of stability question of this system and
uh we should analyze the stability. But at which
point, so the fixed point there which you analyze
the stability is essentially given by then nobody is infected
, right? Because that's when you and you infect
a few people initially. That's when you want to
uh understand that the system will take off or die
out. And what does it mean by stable and
unstable uh equilibrium points? So imagine this to be
uh contour as given by G by the system.
And you can see imagine the whole epidemic to be
this box. So you can see that a small
push to the system will effectively roll it down,
right, It will quickly go down and the epidemic
will take off essentially. And whereas a stable it's
below threshold, the epidemic will try to actually come
back. So the system will try to come back
to the state where there was no one infected.
And at threshold which is the neutral equilibrium. You
can say that there's no no inclination to go either
way. So what we have done is they cast
it as an energy is and then use it as
a stability and equilibrium point question rather than a threshold
question initially. So I won't try to go here
. But for N. S. I. R
. For example PT will be just three blocks right
? Which is probably of each note in the graph
being in each of the three states. That's it
. And you can have this G than the standard
ideas, the fixed point again, when no note
is infected, the question we're asking is that stable
? And in special case of S. I.
R. You can think of two notes in the
graph say I one I two and you are essentially
this is P. I. One and this P
. I to the probably no one is infected problem
nor too is infected so on under the stable regime
, which is below threshold regime. You can see
that if you part of the system, if you
make few notes infected in the system, it will
try to come back because it's below threshold. And
on the other hand, if you do the same
thing to an unstable system, it will just take
off and go. So what we've done is we
were able to separate out these two regimes based on
this condition. So again, please see the pain
over the whole proof. But these are the two
essential ingredients in the proof, which gives rise to
this nice linear severability. So right coming back to
the outline as I said, I promise you that
this kind of analysis and proof technique can actually be
uh extended to give you even more powerful results in
other cases, for example in dynamic graphs while dynamic
graphs. So this essentially the idea is to you
want to capture alternative behavior right? And human uh
mobility, uh, people go to work in the
morning. So essentially you come in contact with the
co workers and then you go back to your home
and Children probably go to school and playground and come
in contact with each other and and they come back
at night. So the adjacency matrix has changed.
So the notes are the same, the same people
is just that their behavior changes in the day and
night. So you have two different adjacency matrices and
as you can ask the same question here, right
? That if you have so for concreteness, I've
used just the science model here. Uh, if
you have the C. S Mott and set of
the arbitrary class. So the nice thing here is
that we assume the grass can be arbitrary. They
are just given, we have given just a set
of the class and which represent bay nine. It
can be weekend. You can get any granularity.
You're just given this tea set of grass and you
want to ask the same question with an epidemic takeoff
amount. So again, uh, we were able
to prove that the informally, there is no epidemic
. If the value of uh, of a matrix
, which is a huge risk matrix is less than
one. And again, it's just a single number
, right? It's just the value of a matrix
. And this matrix is just a product of some
matrices. Uh and the the important thing to note
here is that this sub matrices involved comes from the
virus propagation model as well as the ai their distance
matrices, which is a very reasonable intuitive right?
Because it should depend on the uh actually just changing
the distance matrices as well as the virus propagation model
. So, right and again, this gives you
the time plot this. Uh so on the left
side, I've shown you a synthetic uh network and
this is the mighty reality, which is a which
was a famous project by uh Sandy Pentland at M
I T. Which try to uh follow like track
undergraduates at M I T campus. And you can
see dips and then there's weekends because there's no connectivity
between people between their mobile phones in blue and so
on. So you can see the three again,
three different regimes, right? In all these three
cases and more concretely, if you look at the
takeoff plots, you can clearly see the difference.
Uh So the uh the X axis is again affected
strength here. The effective strength is the value of
that huge big nasty product of matrices, right?
And y axes. Again, the footprint, you
can see the predicted threshold is here and these are
the two separate regions. So so yeah, the
second bonus I wanted to tell you about this computing
viruses. So so the the law, right,
Only argue about a single viruses that there's one virus
and one. Uh and a bunch of contact networks
probably. So what if they're to viruses? And
these are really common scenarios. For example, you
can think of iphone versus android or blackberry. This
is the really or even more biological situations like common
flu is living through a pneumococcal infections and so on
. Uh And the question we the simple model that
we use here. So it's an extension of the
S. I. S. Model which you have
all seen. The important thing to note here is
that because you feel mutual immunity. So what it
means is that if you have an iphone you won't
buy an android unless you ditch type of. Right
? So that's what this model tries to capture.
The once you're infected one of the viruses you won't
be infected with another virus. So given such a
very simple extension of the classic S. I.
S. Model, uh what do we want to
ask the question? So you can clearly our previous
work answers the question with the one of the viruses
will survive or not. Right? I mean if
there's about threshold that will survive otherwise not. Uh
But what we really want to answer is that if
both of them are about threshold, what happens?
What's the end state? Right. And what happens
in the end? That's and this can be thought
of the footprint of the steady state development footprint at
the steady state of the, of the second wives
. So just for sake of clarity, just assume
that one of the virus is stronger than the other
. And uh, you're given just the first few
uh, time takes a revolution, Right? It's
the same infection profile. So what happens in the
end you think, uh, it will go like
this? Uh, I'll go like this. And
the ratio of the uh, end states will be
some factor of the strength. Like if you,
it's reasonable to assume that if the virus is two
times as strong, the end steady state will be
two times as worse. Right? The market share
would split probably in in that basis are square or
some other thing. So that really interesting thing which
reform that all of this is not true. And
essentially when it takes off. So even if one
of the viruses even a bit stronger than the second
one, it will just wipe it off. So
the weaker virus always dies off. So what's the
result? The result is given our model and any
graph again the graph is totally arbitrary. So uh
compared with previous stuff the weaker virus always dies or
uh and of course the cabinet is the stronger virus
survives if it itself is about threshold. And what's
the threshold? The threshold which were already computed from
a previous work just affected strength. Right? It's
the same as before. Right? So we try
to do some data and real examples. So this
shows you google translate to which is like a proxy
for the interests of the market share of product.
And you can see that the search if you plot
the search percentage of it was this time. This
is real data, right? For these two pairs
of products. So you can see some around these
like like boston it's like christmas is for example you
can see when the sales just pick up there.
But if you see the broad uh broad qualities,
qualitative behavior is still there. For example that it
was just a you can see that the strong viruses
coming down. Right. Right. So the law
have concentrated on essentially the theoretical part right? Which
is analyzing these models and seeing what happens, predicting
and answering some metrics of things. But how do
you actually go ahead and use like to do some
tasks. So the action part which we I'll go
where is who to immunize algorithms? So what's uh
what's the problem the so completely the problem is that
you're given a virus propagation model and you've given a
budget, right budget is you can think of the
number of nodes you want to remove and you want
to find the best care notes for removing, for
example its case to in this network and you remove
these two notes, is this two nights better or
these two notes? Uh intuitively you might imagine this
note this removal is better because it makes the graphic
chain and as we have seen before chain is bad
for the virus because the country is spread. So
if you can guess what's coming up that uh so
I'll talk about static graphs and then I try to
give you a flavor of an application. But what
are the challenges in such a question? Right,
so the challenge is, is the metric, how
do you measure the goodness value of a set of
notes? Which you have to measure that? Which
to set of notes are better. Uh an algorithm
. How do you actually go and quickly find these
best case set of notes with the highest goodness value
. So uh and given my previous work, the
proposed one liberty measure is actually lambda. And why
is it provided? It's true. It's because land
is epidemic threshold. So clearly what you want to
really do is to drop in value as fast as
possible. Because if it's about the threshold, you
know, there is an epidemic which below the threshold
that is not. So if you want to remove
notes, remove notes in a way that drops in
value as fast as possible. And so what I
mean by again, I can drop which is the
change in the value. Right? So you have
these two graphs which is original draft and you have
removed notes two and six. You can see diagonal
is probably this and adding value for here is this
dragon values. Again, the largest trading value of
the adjacency matrix. And what you want to find
is those set of notes which maximize the screen bar
within the budget. So uh as you can guess
the director algorithm is really expensive. You can prove
that it's NPR uh just to give you an example
if you're just 1000 notes and if you run the
good force method, you can see that it takes
like almost 2600 years. Just find five best notes
. So what what's our answer? So our our
method involves two parts again uh Part one is for
the shield value which was the goodness value of a
network. What for a set of notes? What
we did was we carefully approximately Dragon drop, which
is the drop in the value using matrix perturbation theory
. So once you get this formula for the I
can drop you can actually use. And it turns
out that this uh this uh this function which you
get from the matrix perturbation theory is essentially some model
. What it really means. Uh is that because
it's someone that you can do just a really approximation
quickly find the best game modes. And this gives
you a near optimal solution which is in the running
uh like linear and running time in both nodes and
edges. So this was nice because uh as you
can see, the direct algorithm is really expensive,
but we were able to get a really near optimal
linear time solution. And this is just an experiment
. So this is sort of contact graph again.
So this gives you the again the time profile,
this is the log of fraction of infected nodes poses
time. And these are the different uh immunization metrics
and algorithms currently in use. So you can see
that next year is the lower of all of them
, so it quickly drops to zero and the restriction
dies off. But the interesting thing to note here
is that if you know to look at the Qantas
immunization, this is a really popular uh method where
you choose a random person out of phone book.
You don't even is a random person, you immunized
random neighbor of that person. What it does is
that it gives you a handle on the degree,
the spreading the degree of the ground. So you
tend to immunize hubs hiding how you connected notes,
but you can see that our method is clearly much
better than that. Uh This is because we optimize
the real idea she'll value right, Which is uh
again value which we got from a previous present.
So as a promise, you just uh this is
uh variants like variant of the uh removal problem which
I actually had the good fortune of working with real
doctors at michigan. In fact uh it was interesting
working with the person who was a real doctor because
sometimes he had to come out or surgery and for
a meeting and used to tell us uh things happening
there. So uh the problem here is that you
have a network of hospitals like and hospitals transfer patients
and these patients have critical drug raises critical these patients
critically ill. Right? There are drug resistant bacteria
like this extensively drug resistant tragic losses. And what's
happening is that you have a set of fixed budget
of resources, can be money, it can be
disinfected, it can be a specialized medication which centralized
agencies trying to distribute among these hospitals and how do
you do that? So I suppose you have this
bunch of disinfectants and you give it to one of
the hospitals and what really happens to study the hospital
becomes more robust, Right? So the strength of
this infection decreases. And how does the strength decreases
given by a function? So of course there are
some specialized functions used in literature, but the key
idea everywhere is that it's diminishing returns because the more
you give, the more infection control associate, you
don't get a proportionately higher impact right? Which is
very reasonable. And under such a setting, you
really want to find out how you distribute these and
it can be any grand laboratory uh right to maximize
these hospitals so that these hospital starting a huge technical
picture, have already seen introduction. Right? So
these are the medical network, as I think you
have already seen the draft. So this is the
current practice. The current practices essentially giving every hospital
equal amount because they don't want to discriminate among hospitals
. So you can see that smart aleck bizarre method
and uh you can see that it has substantially fewer
infections and uh, this is the running time.
So before we came, before we started this collaboration
with the doctors, they were actually running simulation monte
Carlo simulations and they used to take more than three
weeks to actually figure out any kind of distribution.
So this is in contrast to the current practice on
the ground in the hospital, which is just uniform
. So you can see that this is greater than
one week, just like 14 seconds more than 30,000
XP. So yeah, I mean, it's a
totally different way of doing these things here. Uh
just to give you a further example of this problem
, uh coming back to the theme of that similar
problems in many different areas. This problem also occurs
in uh social graphs. So this is an online
virtual gain second life and their people administrators have some
resources time, which can, you can think of
time and you want to do this, you want
to see which users misbehaving and this user you should
give time to. And this is a pen network
. This is just the hospital network of pennsylvania and
it's an all pairs. So it's kinda was all
kinds of things. Uh again you can see more
than five x or 2.5 X difference between the current
practice and uh so uh lower is better work.
Uh Right, so the final uh part which I
would like to talk about the standard processes, learning
models from twitter, which is kind of uh study
on a huge data. So this was work done
with Yeah. What's the problem? We are given
an action log of people tweeting hashtag right. So
uh these are people who are tweeting and hashtag and
you just recording what they tweeted uh and you have
an underlying network of users so this network can be
defined in many different ways as and I come to
what we actually use in our work and what we
want to find is how external influence varies with the
number of hashtag. What is this concrete you mean
? So so you have a network which is this
person falling this and so on and she tweets something
about some topic. It can be done in Egypt
or Justin Bieber uh he picks it up and he
also tweets about it and you see even this person
tweeting about it. So the question we really wanted
to ask is that what really happened and what part
statistically can you figure out what part of it would
be due to this? Because he actually saw her
tweeting it or she just saw something in tv and
went ahead and tweeted about it. So why is
this important is that if you are a market and
a bunch of dollars very should give the dollar,
should give the money to this person because she cost
the whole cascade or you should just run an advertisement
on because that will give you much more mileage for
your money. Uh And we wanted to see how
these values with the hashtag right? Because as you
can imagine this might depend on the actual content of
the time. So the data we used was like
uh as I said this was the yahoo and this
was like almost more than almost 15 terabytes of data
. This was uh yeah who had twitter firehose where
they just used to get this whole big jump of
the day to more than 7 50 million tweets and
uh we ran our algorithms on the hard work and
pick system. It's like more than it's a huge
, they have a really excellent infrastructure, more than
6000 machines. Uh what we did was we took
find hashtags and we just saw how they value their
behavior on network of users and the network person connected
to another person if he or she can influence other
person. Right? So what does influence means is
essentially we are assuming that either your follower, what
you have at least actually directed messages to her.
So yeah there are many different ways of defining this
network, this is just one of the more acceptable
ways in the literature right now. So the model
here is this again details like the market here is
that we developed a model. The propagation is a
part of influence and external. So the influence part
is essentially how you get influence from the neighbors.
And the external part is what percentage of it is
through externalities rather than the network itself. So what
we did was we developed a model which takes the
previous observations take on. And there are some parameters
which explicitly represent the influence. So I want to
go into the detail of the model itself. But
the key thing to note here is that there are
parameters which actually represent external influence directly. And then
we are also developed E. M. Alternative minimization
algorithm to learn these models. But once you have
learned the models, when you have this set of
parameters on different hashtags, what we did was we
went ahead and group these tax according to the parameter
. And that's where we got interesting results on the
different behavior of hashtags to give you a flavor of
the results so you can see that. Uh So
if you think about these being external effects, so
more the external effect is essentially more externalities in the
hashtag and this is what sustained and not that these
are parameters which I learned from the model, not
given the data itself. So these are parameters as
implemented by the model. So these bunch of different
behaviors uh just go over two of them. So
these these are hashtags which represent the long running tax
. So you can see that there are really high
external component. So these are tax, which I
mean on twitter for almost two years. So there
is no really local component there there is no network
affects their. People know about the tags that you
eat it whenever they want. For example, this
just says not watching, this is what are they
watching now? It doesn't really depend on your friend
. Right? And so these these are taxes really
high. External component. On the other hand,
these are really word of more processes. These are
hashtags which actually grow organically in local networks and then
take off and then they are mentioning the twitter trending
topics pecked and these trending topics are essentially capture the
slash doc effect because suddenly there on the trending list
everybody knows about it and then there is no local
component again because now everybody knows about it and they
talk about it. So what we were able to
do is very, very able to capture these kinds
of different behaviors, right? And if you have
money, so these are just pastilles, external events
and trending. So if you have a bunch of
money where you would you give to hashtag behave like
this, right? Because essentially you are just seeing
the community with these hashtag, they're talking about it
and then they suddenly take off and a lot of
people know about it. So this gives you the
greatest bang for your buck. And the nice thing
here is that you can use this for forecasting anomaly
detection because if you have a hashtag which are expected
to behave in a certain way, they behave so
differently than you can do something there. Right?
So this concludes the uh dynamical process part of my
talk. So I try to quickly go over uh
for finance also about uh some of the other interesting
work I have done. So as I said,
I won't get too much time to discuss the details
, but I will be happy to talk about it
offline. So the first thing is like uh community
detection. This was what I did with Sprint research
. So the nice thing is that they had really
huge amounts of data on mobile polygraph users, right
? So essentially like we had, we collected data
from a switch in a large US city should remain
anonymous and you have 200,000 users and millions of calls
. So what we wanted to do is essentially understand
how how do these graphs look like, like So
I got to the long story short, we did
some extra data analysis, but the key thing is
that we were able to, if the graphs look
like this, which is essentially a core with a
lot of different small communities connected to the core,
then you can quickly identify these small communities and then
a really interesting thing is that these communities can be
clicks or by part of course. So even finding
planted clicks is a really hard problems, right?
But uh, finding bipartisan causes even harder and by
part I of course are not really community in the
traditional sense because there's no real connection between them,
there's a connection across them to the other side.
So, and and what we found that this kind
of pattern, the pattern which we developed according a
lot of different data sets, a lot of different
uh, switches and users and months on the sprint
dataset as well. So using this we were able
to find really interesting communities. For example, this
is a patent graph. This is just who cited
home in a patent citation network. You can see
that you can find, we could quickly find these
two kinds of communities which are like patent from the
same in rentals. And this shows the curtain based
geographic, essentially all patents were on the same thing
and you just go ahead and pick the reference from
the previous payment and just copied it. So you're
citing all these previous parents with the other day said
. And so uh, for the Sprint for example
, this kind of communities which are near clicks and
nearby part of course were representative of much more business
. Uh, many phenomena which are important to business
right? For example, to all these people who
are talking to each other. They leave too together
. Right? One of them leaves the company,
one of them such as service providers, you the
others, which also, so that was one thing
interesting. We were able to actually go ahead and
talk to the marketing department of Sprint and validate that
. So down this book. And so yeah,
the other thing is time series analysis. Uh,
so here the, one of the data sets which
I used was like PGP daughter updates, Yeah,
Pgp daughters that you can imagine just some networking rotors
which propagate path information across the network. And the
network be used was in Italy network. It's a
famous research network all throughout the United States. So
we had like almost 80 million updates over two years
. And so what we have is that you have
time see, is that each of these rotors essentially
the number of uh traffic per unit time. That's
it. And you want to find patterns and nominees
. So very open ended question here. So what
we did was we were able to find to concentrate
on two patterns which are important even for a networking
point of view. And uh, so one of
them is for example, this is just the uh
same time series after doing the logarithm market over time
. You can find that there's something really steady and
constant happened here. Right. And why is this
important? This just means that there is a constant
studies traffic for a long period of time. And
what it means is that it means it relates to
a real networking human called wrong flapping. Which is
uh like people advertising I. P. And then
take it back and they do this for a long
period of time. And this is really points to
inefficiencies in the network. So we were actually using
a method we were actually able to find uh well
appointed Alabama supercomputing network which which confirmed that one of
the Rockies was actually flapping. And uh this when
detected and resolved almost 30 days. Like there's a
professionally managed network. And so this shows that it's
really important to do these kinds of pattern analysis on
the historical data as well. Right? And the
other thing is also if you just if I just
give you this mostly sequence, it's really hard to
find anything useful there. Right? And it turns
out that if you just magnify this part of the
portion there is a really huge short burst of traffic
which and it's a short bus ride just in eight
hours by compared to the month long steady activity of
uh the other event. And what we were able
to show like this was uh it was because they
were spammers in some middle schools in china which was
uh what was happening is that they used to span
quickly for eight hours and then go and take a
second I. D. Block and do the same
thing again. So and we were able to do
this using a multi scale uh analysis which uses wave
. Let's I won't go into details but there's an
algorithm which we developed an algorithm which we quickly identified
the spikes from the data. So right. The
last time series analysis question which we try to answer
is uh answering similarity varies. So this was motivated
again by the GDP data which we had and also
different many different kinds of data like data center monitoring
data where you have time series from different sensors on
the uh data center uh physio physiotherapy data, healthcare
data for example heartbeats or some sensors on your body
. Or even motion capture data where you can have
markers which attracted movement in time. And what you
really want to answer is that if you have a
database of such types of time series can you quickly
find other similar ones? Given a very. So
what are the challenges? I just try to give
you a challenge in the BdB setting. So if
you have a say the time series from Washington after
and you have a time series from uh Salt Lake
city of water, then how do you say whether
these are similar? So people are used the traditional
classical methods of Euclidean distance or dynamic time warping,
which captures like. But the problem with all these
methods, like for example, for the ingredients,
if the spice align then clearly there's nothing else you
need to do. Most of the series will be
classified as similar. So because these sequences so busty
, you need something else. And there are uh
specific problems with other distance functions as well. So
what we did was we developed a complex, extended
the classic real value Kalman filters which are like graphical
models, uh like hidden Markov models which try to
capture the statistical revolution of the data. So what
we were able to do that we extended this uh
real value common filters with complex domain. So we
have no complex and variable and complex distributions. And
we were able to develop a E. M.
Style algorithm again here, which quickly learns these features
. And once you've given these features you can quickly
classifying cluster or do anything with them. And the
nice thing about these features that learns dynamics, it
learns the underlying uh evolution system. Like for example
in the motion capture data, it learns how you
walk there to walking motions. Most of them will
remain the same, right? If you're walking a
little bit faster, the dynamics are similar. Just
the parameters are slightly different, but you want them
to be clustered together. So. So yeah,
so it captures all the nice things. And the
really nice thing also is that includes all these workhorses
, right? Like the CIA or the regression B
f D. S special cases of the model.
Uh Right. And if you apply it on GDP
data, you can quickly see these clusters like which
are, which makes sense because the geographical clusters and
because the GPS routing protocol you would expect geographically closer
, it is to be essentially similar in traffic.
So right, right. Finally, future plans.
So what my research team has essentially touched upon all
these three things which have already seen like the data
analysis and the policy action part. So my research
future plans also are more line with these three right
now. So the first challenge in the data part
is of course capability given the unprecedented amount of data
. Like you really need algorithms and techniques for massive
graphs and we and the nice the interesting thing here
is that you have high dimensionality which is you have
much richer data as well as a large sample size
. So a lot of data. So you need
to get level algorithms for both learning models on the
data if you remember the model learning part and also
developing policies because if you develop a policy for actually
manipulating the process, you need to make it act
on really last data. So it's interactive both of
these cases. So as part of my at least
like what the law I use like mattresses, clusters
and like how to for the data and it's a
part and also compute uh if you have a computer
in terms of simulations use like paralyzed systems like so
so the second trust is on understanding analysis. Like
it's using models forecast which is essentially you building predictive
models. So this is one thing for example and
actually forecasting and back casting the processes. For example
this is a nice example you have all these people
infected right? Can you actually reverse engineer epidemic and
figure out who started it? So that's one way
of using the model to actually back cast and prevent
who are the culprits. And the other thing is
like emerging models. So you if you have suppose
you have this google trends data right? This essentially
gives you the number of flu that is for your
time and you have also CDC data which gives you
the population density and the distribution of population United States
. Can and if you have a model of learning
this time series for example, you can say that
the slope is a 1.5. So can you actually
predict which part of the network it actually originated from
? Can you actually identify which part of the network
actually gave you that uh post and figure out of
the epidemic is actually spreading. So essentially combining different
kinds of models. And the third challenge is active
policy which is on more online and timely intervention.
So right now I show you immunization algorithms where he
wants to the decision, you didn't really change it
. Right? So how do you update these decisions
on time? So for example if you have a
lot of money and should be about money, one
going a marketing campaign, say on twitter or you
should try to spread the money or a month given
how it goes. Or you should just uh have
a constant uh supply. What to do with the
vaccination campaign is not going well. Uh how do
you change the parameters which how do you target and
change the organization algorithms? So, uh final thing
is like you want to tighten this, I want
to tighten really try to describe the analysis and policy
and action. So for example, right now the
object IDs are probably not being transparent in the design
and analysis of these actions. Right? So for
example, when you want to do immunization, do
you want to minimize the expected number of people in
uh effective or want to minimize economic damage? How
do you actually bring them into analysis part and actually
do an analysis and given optimal or near optimal algorithms
for this? Uh Also collaborating with the miners group
that Minister of Pittsburgh, which is like, which
is also an agent based simulations group, which where
we're trying to study can be actually uh w optimal
algorithms for such on the fly campaigns. So,
uh hopefully, finally, I've given you a sense
of that. The dynamical process on networks is a
really rich area. The comments, problems, incompatible
settings and not only see us uh areas are really
heavily involved like machine and statistics. Uh Computer systems
for data analysis uh like hello big data analysis and
theory and algorithms but also they have really outreach and
applications in many different areas like biology, like ecologies
, you're always in epidemiology, Public health physics like
money in the systems, uh social sciences, understanding
human behavior, mobility and economic like money marketing and
a lot of different things. So just a bit
of shameless self promotion is the list of publications I
have and uh the stars represent the publications I talked
about in the talk that double stars represent. I
meant it a bit more detail. Uh a couple
of patents in summit advance. Uh I wish to
thank my collaborators from the different universities and research labs
and also graduate students and uh also the funding agencies
. Thank you. Uh Mhm. Okay. Mhm 1227 00:54:34.150 --> A:middle L:90% . Yeah.