Speech Transcript - DIFFUSIONS OF INNOVATIONS ON DETERMINISTIC TOPOLOGIES

0:00:15	i think it's safer to use these microphone
0:00:17	so my my talk is entitled fusion of innovations it's
0:00:21	uh the the the to is very brief and the talk is very brief size
0:00:24	i i and i will let you go pretty one
0:00:27	um yeah i M P sending this work which is actually
0:00:32	uh a you the bench i number uh banning tried of uh john use D
0:00:36	who was my for student and then a post can to make T and no
0:00:41	uh starting a new job
0:00:43	uh and the to go authors uh dot on a all blue and uh a us so that that are
0:00:49	and them at
0:00:51	um
0:00:52	so this some agency my gaze or of the the the biological agents are are humans so though a lot
0:00:59	of the the behavior of bill i i'm trying to model in this talk
0:01:04	uh could be applied a tree two forms of biological agents uh in fact the more of interaction is the
0:01:09	fairly simple
0:01:11	uh and what i'm discussing these uh uh you bought mechanism to oh feet to what we observe a when
0:01:18	a in new innovations uh uh the many innovations and introduced in society and how this spread
0:01:24	so
0:01:25	um even been officially innovations but not spread um simply yeah on contact
0:01:32	uh so i a lot of the a them weak more this so that that based on the idea that
0:01:35	i i uh i get in contact with some agent which she's has an infectious D
0:01:41	and automatically the through that contact that i you contract a disease
0:01:45	uh they wouldn't hold
0:01:47	um and the balloon capture the dynamics there are observed in these more that
0:01:51	um
0:01:51	so at typically actually innovation moves uh very slowly
0:01:56	and that
0:01:56	not reading these diffusion on a um and needs uh is slightly more complicated model but by was you we
0:02:02	see my mother is very simple
0:02:04	um so i the the idea ease uh the motivation is obviously of for engineers is mostly the standing how
0:02:11	they would
0:02:12	uh explore white all the data that we have now one social networks uh in a link that connections
0:02:18	two and you know diffuse new product
0:02:21	or actually to interpret what out uh would would be good
0:02:24	uh ways of a a um and spreading ideas or new body
0:02:29	okay so what was the what is the state of the art
0:02:32	um
0:02:33	as you can imagine this problem has been studied in sociology and economics
0:02:38	and the first person to produce the model that that seem to credibly present what was going on in
0:02:44	in the observations
0:02:46	uh was gonna vector
0:02:48	you on a that in the nineteen seventy eight uh wrote in uh a
0:02:53	they basically a the they're spay better on this problem
0:02:56	and introduce ways
0:02:58	it more which is called a actual model for collective behavior
0:03:02	i actually
0:03:03	if you high but that arised that uh innovation and uh is not adopted
0:03:07	uh simply by absurd being your neighbours but by absurd being a sufficient number of your neighbours so if you
0:03:13	cross
0:03:15	that that actual or of um adoption that in uh uh uh in a local class that all of
0:03:21	or um
0:03:22	um you uh friends or neighbours
0:03:26	uh then you have proper to adopt the innovation otherwise you will continue to two
0:03:32	stay with the uh all the invention
0:03:34	and easily the ants to adopt a new ideas he's in fact up in society
0:03:39	um
0:03:40	so um
0:03:42	the the group of nodes that introduces the innovation here to called the seed set
0:03:47	in the T D L pay but it was a single a agent but uh it seems more realistic to
0:03:51	assume that you have an initial set
0:03:54	and they i D also is that each individual has but a different threshold do you want have to have
0:03:59	the same for actual the cross the network
0:04:02	um
0:04:02	so so the model of that actually simply if a fraction of agents
0:04:07	um which is a few you large or adopted the innovation and you will adopt a
0:04:12	so or um
0:04:13	um do not but that also said that these probably ease of but that more that on or of to
0:04:18	to to capture at their if X how decisions are made or or uh a more steps but had
0:04:25	even for these these is actually the the the contagion own contact is not necessary the best model
0:04:31	uh and uh you know what i get behaviour in not there uh uh if X make iteration could be
0:04:36	model like the
0:04:38	so i i these i mean up a better that was it a bit over a well we sign of
0:04:42	the but then uh uh the in that is in these big top
0:04:46	um and the ninety seeks uh about and the D a number of interesting experiment that expect that the i-th
0:04:53	actually uh at to to validate these small the that was a purely to read you got more that
0:04:59	um
0:05:00	so a the application was um the diffusion on all prescription there i
0:05:06	uh the a sinus it to set the patient the diffuse of the the the the the data are option
0:05:11	by a the doctors patient
0:05:14	in a has system
0:05:16	um
0:05:17	and a but it actually a the sort of court operated these hypotheses uh are usually may my go not
0:05:24	the gonna a there that that an actual behavior as explain what is going on
0:05:30	um any is also explains
0:05:32	he i of are they of a uh uh the other uh
0:05:37	diffusion of innovations each D would flash on or new technologies
0:05:41	um a because a similar trends were found in in in those a fee
0:05:46	um
0:05:47	like at on camp in into doesn't in two D and two doesn't of five um a uh to call
0:05:52	their uh uh a a not this study uh um of these uh a problem and try to uh to
0:05:59	look at instead of having it at that we six actual more will happen if you had that on to
0:06:02	actual so you
0:06:04	or sports possibly change of mood and therefore
0:06:07	um some you what let less six test subset steve
0:06:10	two or or your neighbours and some days you what are more step that so active to your neighbour
0:06:16	um or or you were simply you know a little bit jet legs like M or your be an L
0:06:21	O or or more uh a sharp and so you would make decisions
0:06:25	depending on having more or less people around you
0:06:29	that uh uh adopt the innovation
0:06:31	um and can also started to do some serious and i E D got work
0:06:35	on these problem
0:06:37	a in this think figure a like to D than the we uh exam i mean whether that was convergence
0:06:41	and or
0:06:42	what was the issue of that there meaning meeting um know
0:06:47	the the the the the
0:06:48	the configurations for the optimal seed set
0:06:51	the was it's but i to these you know if an across society
0:06:54	and these was a problem a camp it looked into and he proved of for sure like the problem is
0:06:59	np-hard at which is not very good
0:07:02	um however uh that's subsequently to cover the problem again
0:07:07	a in looked at uh the if fact of connect T V
0:07:11	uh well leave
0:07:13	the model underlying the connect D V Ds that on them graph in particular watts sees uh uh famous for
0:07:19	the
0:07:19	small world more they'll
0:07:21	uh that
0:07:22	is uh embrace by mania as a as a reasonable more for social of networks
0:07:26	so what's this cast
0:07:28	the value elements or of um
0:07:31	a a a a a a diffuse on of information
0:07:34	uh with respect to be to these small that's all the data elements of having a good model for
0:07:39	for this source and that V D and how would that affect fact the diffusion of innovation
0:07:45	uh in practice
0:07:48	um
0:07:48	so also what's not these that um
0:07:51	all these graph connectivity be he always found that
0:07:55	he had to had this in me to get significant mass
0:07:58	oh any other up there if uh somehow they was like nation
0:08:03	uh in the process then uh you would probably stop you would not have to type society all
0:08:10	i like that
0:08:11	um about okay but that prove that these uh that to the optimize optimization of the C D's np-hard hard
0:08:17	they don't no either significant to results
0:08:20	uh in fact to conduct that i the fixed point so or here this paper or does if you
0:08:25	a a has i if you want sort a sort of
0:08:28	um interesting results some that
0:08:31	so then i talk more that he's a graph the agents out of the bad texas
0:08:35	and the the edges
0:08:37	capture or they're connect D V D
0:08:39	and for me to the static the half door you could imagine that it would be interesting to extend these
0:08:44	results to a stochastic have
0:08:46	um a the neighbour her they neighbourhood be represented by these uh uh
0:08:54	uh and i of G
0:08:56	um um and just these are the neighbours that can in a gender i
0:09:02	so each agent does i said has its an actual which i indicate
0:09:06	as feel by which is a number between zero and one
0:09:09	not i K zero i have a subset of in T V so the has that
0:09:13	these innovation and these is the seed set
0:09:16	and i D not these by this can be that fee zero
0:09:19	which is obviously a subset of the to six
0:09:22	so the global been of a doors oh oh have already been exposed
0:09:26	uh to the innovation is a represented by this set
0:09:30	uh and they good be also was simply the be the promoters you with a P
0:09:35	all all mathematically the interaction model is simple
0:09:39	um
0:09:40	is a if uh a the a a the name in it's that if the intersection between the seats set
0:09:46	and the initial group um is a um did F X
0:09:51	uh the the node i
0:09:53	is such that the fraction of nodes
0:09:55	uh the this containing in the neighborhood be sufficiently high
0:09:59	uh then that the i will adopt deterministic tell thickly um the innovation either otherwise Z will uh uh is
0:10:05	training set
0:10:07	so be do not by feel value uh uh the adopt there's at at at each iteration of these are
0:10:13	going so we imagine that every time
0:10:15	uh we we compute
0:10:17	um what use the fraction all of the nodes in the neighbourhood the are part of these um i is
0:10:24	a set of a top there
0:10:26	and the new the group is called by if yeah
0:10:30	and they all that all group um of adopt there's at the at iteration of these are go me simply
0:10:36	the union
0:10:37	a cross this set
0:10:39	and so obviously agent i
0:10:42	we adopt the innovation at step and a E for these you on all a adopt there's
0:10:47	intersex sexed neighbour with a sufficient number of agent
0:10:51	so the question is we a you know actual of i don't
0:10:54	and if not what at the fixed point
0:10:56	and which one of the peak peaks point will be selected to given an initial set
0:11:01	so these is simply the mathematical
0:11:03	so the of these i take a question you have to define an object which is called the coherence that
0:11:09	and the coherence set
0:11:11	i um is defined uh a um
0:11:15	a relative uh uh um
0:11:18	to these a particular for soul we group in a and
0:11:22	uh and number of agents
0:11:23	uh each agent as the fee i
0:11:26	and we say that a a non empty subset of the where to C is a coherent set
0:11:31	is the intersection between these site
0:11:33	and the neighbour or bad every agent in this set is such that these inequalities matt
0:11:40	uh in in these what you mean is that
0:11:43	for each member of this that the the fractional neighbours the V sides in the set
0:11:48	is the bob
0:11:49	the agents specific
0:11:51	so actual
0:11:52	and so
0:11:53	these coherence measure this coherent set essentially measure of how um how well connected are
0:11:59	um the these these group of not so if the these is a coherent set uh
0:12:04	you know
0:12:05	this is what
0:12:07	so
0:12:08	the important point is that because of these the finish shown
0:12:11	well how it is that the members of these uh coherent set can not adopting innovation a less
0:12:17	for somebody's on somebody inside the set adopts the innovation so they need
0:12:21	somebody inside
0:12:23	to convince them they want to otherwise
0:12:26	and this is an example
0:12:28	so you have an i took these is the simple topology
0:12:31	um and here i set up that that actual
0:12:34	um in a particular way i say that
0:12:36	for not wanting one and to that actual these point five minus a a small you C don't
0:12:42	important porn the three four five and six
0:12:44	if instead that point five plus
0:12:46	some at C
0:12:48	so here you good
0:12:50	uh easily compute uh the coherence set
0:12:53	uh the that in these network
0:12:55	oh well easy he computes list take you a while because he's it can be a other a problem and
0:13:00	there are menu coherent sets but is not a to identify them uh once you the i'd when made it
0:13:05	possible
0:13:06	that's of these side
0:13:08	and for example is not need if you difficult to see they want to city
0:13:11	for one here and set because
0:13:13	uh you see that they all have chronic T V D uh the smaller than two
0:13:19	um
0:13:20	a a and is for has an L connect T V D uh a city so the you can actually
0:13:26	uh break you P the coherence so
0:13:29	or this is just to point out that that are menu coherent sets there not how to identify but that
0:13:33	are many of them in the E D the be yet target problem in these it ice on aids
0:13:37	we the fact um there was pointed out to to finding the best C is an np-hard problem so you
0:13:43	have he relates with these aspect
0:13:46	oh why better why the important to define coherence that because then you can define us a mean a clear
0:13:53	way what of the fixed points
0:13:55	for the diffusion of innovation according to that to actual model that
0:13:58	and so given a graph
0:14:00	thank even then these uh a actual it's
0:14:03	um
0:14:04	is they up not set is if you have not up this that at feast a of then you can
0:14:09	uh be sure
0:14:11	uh that these are top their set is a fixed point
0:14:14	if the complement of these are their set
0:14:16	uh is actually coherence set
0:14:18	so that would be a fixed point
0:14:21	okay
0:14:22	and the pro of is very simple or uh or you just a apply the definition of coherence set
0:14:27	to the uh uh to the complement all these set of a there's send you figured out that it it
0:14:33	by you late
0:14:34	it is below bill actual right
0:14:36	uh and body uh element in fees below of actual
0:14:40	and that is uh what motivates definition of coherence
0:14:44	so do is the main out of this talk
0:14:47	um and uh thank you for being so patient to a it to these
0:14:51	uh as for a given to not graph these is what you can say about this speaks points
0:14:55	if there is no uh feast a
0:14:58	is a which is included in in
0:15:01	such that the seed
0:15:03	uh
0:15:03	includes a dot
0:15:06	and the complement of P studies coherent
0:15:09	then the innovation will D fuse while out
0:15:11	the network
0:15:13	he instead
0:15:15	there exist a unique feast that the contains the C the C D the initial the up there's
0:15:20	and
0:15:21	the complement is coherent
0:15:22	then obviously that is the fixed point
0:15:25	and that can also be extended uh in uh the case where this seat
0:15:30	is actually contained
0:15:32	in it but you'll are uh a a set feast are
0:15:36	such that
0:15:37	um
0:15:38	um so what you know there was there is not a unique
0:15:41	feast on there are many piece data
0:15:43	and they are all uh uh a index by these substitute stick subscript I S
0:15:47	assuming that that are K of them
0:15:50	and the C D in one of these
0:15:52	uh then um what happens is that the adoption of be innovation will be meted to the intersection of all
0:15:59	these
0:16:00	um
0:16:01	uh
0:16:01	these sets P start of it
0:16:05	and these is an example so you and all this search able the here set is uh uh read that
0:16:10	um and uh extensive is not too hard once you place the C to few your out if there is
0:16:16	a coherent set the will be a fixed point
0:16:19	so for the example that i uh provided before
0:16:22	um i you have it is these uh these uh the actual does we said
0:16:26	um which is point five minus that in for not one and two and point five plus types you on
0:16:32	for the remaining no
0:16:34	and if the seed node in this case not one
0:16:37	and final adopter set a remains one and to so if uh the evolutionary is not one
0:16:43	you're are out of luck you evolution with no i
0:16:46	um so you will only convenes beans your next door keyboard and that would be
0:16:52	um so these these
0:16:54	uh this is also uniquely defined so you also know in this case uh that you want to have at
0:17:00	all
0:17:00	uh uh the possibly
0:17:03	or all in discussed bidding up in a uh even more recent paper and by a at all a or
0:17:10	simple all
0:17:11	how we want to pronounce it uh is my in pronunciation
0:17:15	it and two doesn't and and he published uh an article uh in the science magazine
0:17:20	a and and i think with beautiful experiment that a is was a like experiment and i think uh again
0:17:26	it has a network of patients
0:17:28	uh and how they
0:17:30	no prescription of new
0:17:32	i practise is well if using across the to work
0:17:36	the be you'll the experiment this the he somehow on be this fifteen and it
0:17:40	agents to communicate with a fixed topology that he had P D their mean and he use to topologies
0:17:47	one is a perfect a regular lattice this topology and the other one is that on number graph so yes
0:17:51	actually D Y are
0:17:53	uh the the the topology a that uh more war
0:17:57	um
0:17:58	and to all experiments he not east
0:18:01	that's somehow how the lack teeth
0:18:03	topology was more class that was
0:18:06	seemingly be more effective to spread innovation
0:18:09	then the is more words type of network was
0:18:13	which is somewhat counterintuitive as there is out to because we have told that small what net had in fact
0:18:19	diffusion fusion of ideas in
0:18:21	uh and uh the six degree of separation
0:18:24	among a a a members of society or diffusion all of information seems to
0:18:29	to be a a by they data on them midi whiting
0:18:33	um
0:18:34	uh i i is suggest that that these are actually not uh um
0:18:39	completely counting to E D
0:18:41	uh but a standing in some cases gonna actually we can a week and the option because a may eight
0:18:47	these school queen and set and uh was that an next then
0:18:51	these each but apps an extreme
0:18:53	case of that
0:18:54	so i depends on the size of the class that that's basically the bottom line and how that size of
0:18:59	the class the
0:19:00	you lace the threshold
0:19:01	which are obviously starting that chant tall up what did not
0:19:05	really control
0:19:06	because he was a using a real agents so the had they on
0:19:09	actual so the only thing that he decoding control was
0:19:13	the flash
0:19:14	so he couldn't necessarily relate what keyed at billy how the threshold and the class size
0:19:20	interacted that each other
0:19:22	so the fact of class is actually
0:19:25	uh we think not uh not to the other
0:19:28	uh and so the the the they've
0:19:31	finding the fact if if you'll a a complicated problem
0:19:35	but essentially a good guideline would be
0:19:38	to search for positions that was not a lead to have a large coherent sets as complement
0:19:47	and that concludes my talk thank
0:24:36	um

DIFFUSIONS OF INNOVATIONS ON DETERMINISTIC TOPOLOGIES

Bio-inspired Information Processing and Networks

Presented by: Anna Scaglione, Author(s): Ercan Yildiz, Massachusetts Institute of Technology, United States; Daron Acemoglu, MIT ECON, United States; Asuman Ozdaglar, Massachusetts Institute of Technology, United States; Anna Scaglione, University of California Davis, United States