Lucca, Italy, Wednesday, September 24,
2014.
Sala dell’Affresco (San Micheletto)
Luis M. Rocha
Redundancy,
control and collective computation in network dynamics
The structure of networks has provided many
insights into the organization of complex systems. The success
of this approach is its ability to capture the organization of
multivariate interactions, and how it changes in time (network
evolution) without explicit dynamical rules for node variables.
As the field matures, however, there is a need to move from
understanding to controlling complex systems. This is
particularly true in systems biology and medicine, where
increasingly accurate models of biochemical regulation have been
produced. More than understanding the organization of
biochemical regulation, we need to derive control strategies
that allow us, for instance, to move a mutant cell to a
wild-type state, or revert a mature cell to a pluripotent state.
In this talk I will highlight ongoing work in our group aimed at
supporting this goal: 1) identification of redundant edges in
network evolution via the computation of the metric backbone of
weighted graphs; 2) a study of the relationship between network
structure and controllability through the analysis of dynamical
ensembles of BN; 3) an outline of our schema redescription
methodology, used to extract the canalizing core of automata
network dynamics, thus simplifying the characterization of
control in large models of natural networks, such as models
biochemical regulation; 4) a study demonstrating that
canalization (measured as effective connectivity) is an order
parameter of Boolean network dynamics.
Many real-world data are naturally modeled as link
streams, i.e. series of triplets (t,a,b) indicating that an
interaction between a and b occurred at time t. Typical examples
include phone calls, email exchanges, file or money transfers,
citations, and many others. Modeling such data as networks
captures their structural features, while modeling them as time
series captures their dynamics. In order to capture both
aspects, network science has recently developed several
approaches like temporal networks, time-varying graphs, or
dynamic graphs. Although they already provide much insight,
these approaches still poorly capture the both structural and
temporal nature of link streams. We propose instead to consider
link streams as a new family of objects, and to define concepts
for studying them directly, without resorting to graphs. This
language would play for link streams a role similar to the one
played by graph theory for networks. I present in this talk our
first steps towards such a language, and the reasons why this
approach seems promising.
Ginestra Bianconi
The network controllability is determined by
low in-degree and out-degree nodes
The controllability of the dynamical state of a
network is central in network theory and has wide applications
ranging from network medicine to financial markets. The driver
nodes of the network are the nodes that can bring the network to
the desired dynamical state if an external signal is applied to
them. Using the framework of structural controllability, here it
will be shown that the density of nodes with in-degree and
out-degree equal to 0,1 and 2 determines the number of driver
nodes in the network. Moreover, networks with minimum in-degree
and out-degree greater than 2, are shown to be always fully
controllable by an infinitesimal fraction of driver nodes,
regardless on the other properties of the degree distribution.
Finally, based on these results, an algorithm to improve the
controllability of networks is proposed.
Online social
networks have changed the way in which we communicate. These
networks are characterized by a competitive information flow
and a dynamic topology, where most of the mechanisms leading
to structural and dynamical changes are yet to be discovered.
In this talk, we analyze data from a microblogging service to
address the question of whether consensus and collective
attention can be anticipated. To this end, we first propose a
new methodology based on the analysis of temporal series to
unravel who are the drivers of a social movement and when a
transition from a fragmented phase to a global scale movement
can take place. Finally, we also discuss a new methodology
that allow studying online social systems as an ecosystem.
Alexandru Babeanu
Using opinion dynamics for probing cultural spaces
Authors: Alexandru-Ionut Babeanu, Leandros Talman,
Diego Garlaschelli
An interesting challenge arising when studying
social systems is understanding how these provide favorable
conditions for both collective behavior on the short term and
cultural diversity on the long term. At a formal level, this
problem has recently been solved, by showing that both aspects
are present if the non-trivial properties of the underlying
``cultural space'' are taken into account. A ``cultural space''
is the set of pairwise "cultural distances" for a given sample
of individuals, which are in turn directly related to the
pairwise overlaps in their measured opinions with respect to a
given set of issues. An empirical cultural space can be
constructed from large-scale survey data. It has been shown
that, when used as input for two types of models of opinion
dynamics, one providing a measure of short term collective
behavior and one a measure of long term cultural diversity,
the empirical space behaves very differently than a randomly
generated space, signaling that the former has interesting
structural properties. However, this has been explicitly shown
only for one source of data. By repeating the same analysis for
cultural spaces obtained from multiple empirical sources, we
provide extensive evidence for the ubiquity of these structural
properties. Building on previous work, we also develop and
study models for artificially generating cultural spaces that
would reproduce these results.
Social information flow is basically the spread
of any information among socially connected (friends, family,
colleagues etc.) people. In real-life, this type of
information flow is very hard to capture but in case of
digital world this phenomenon can be investigated with the
help of Online Social Networks (OSNs) like Facebook, Twitter,
Foursquare etc. In OSNs, whenever a user shares any
information, her direct neighbors (friends/followers) can
automatically get exposed to that and may decide to propagate
it or not. This type of information propagation can be logged
and used as a proxy of real-world social information
diffusion. In case of information propagation in OSNs, there
is a specific role of mediators/information-brokers who help
to spread the information beyond the immediate reach of social
neighbors. For instance, in Twitter, “Mention” is such a
mediator utility. “Mention” is enabled in a tweet by adding
“@username”. All the users mentioned in a tweet will receive a
mention notification and are able to retrieve the tweet from
their personal “Mention” tabs. So, by using “Mention”, one can
draw attention from a specific user (may not belong to his set
of followers), or highlight a place or organization anytime. So, the main research
question we are trying to address is- "how this mediators
(e.g. “Mention”) facilitates any information flow in an OSN
(e.g. Twitter)."
Authors: Peter Fennell, Davide Cellai and James
P. Gleeson
MACSI, Department of Mathematics and Statistics,
University of Limerick
Dynamics on networks, where nodes can be in
either of a finite set of states, are a rich area of research
and application. In this talk, we will discuss a general
modeling framework for such dynamics called the Approximate
Master Equations (AME) approach. The AME been successfully
implemented as a framework for a variety of well known binary
state-dynamics including the SIS, Ising and voter models [1].
Furthermore, the approach has recently been generalised to the
case of multi-state dynamics; in [2] it was successfully found
to capture a model of the glass transition and so gave novel
insights into the transient behaviour of glass-forming
dynamics. This exibility of the AME is rare in analytical
approaches and its accuracy in modelling dynamics makes it a
highly useful tool. Next, we will discuss how the AME can be
used alongside Big Data to give an insight into real world
processes. We will illustrate this with an example of
diffusion dynamics taking place on the Twitter social network,
showing how these dynamics differ to those previously studied
with the AME in the transition rates are non-Markovian. We
show how the AME can be extended to account for this and the
resulting insights that the approach gives.
References
[1] James P. Gleeson. Binary-State dynamics on
complex networks: Pair approxi-
mation and beyond. Physical Review X, 3(2), April
2013.
[2] Peter G Fennell, James P Gleeson, and Davide
Cellai. Analytical approach to
the dynamics of facilitated spin models on random
networks. arXiv preprint
arXiv:1405.0195, 2014.
Renaud Lambiotte
Non-Markovian
Models of Networked Systems
In this talk, I will present recent work where we
extend the network formalism in order to incorporate memory,
in time and in pathways, into the modelling of complex
systems.
Refs:
Memory in network flows and its effects on
spreading dynamics and community detection, Martin
Rosvall, Alcides V. Esquivel, Andrea
Lancichinetti, Jevin D. West and Renaud Lambiotte, Nature
Communications 5, 4630 (2014)
Generalized master equations for non-Poisson
dynamics on networks, Till Hoffmann, Mason Porter and Renaud
Lambiotte, Physical Review E 86, 046102
(2012)
Martin Gueuning
Is spamming an efficient
strategy in temporal networks?
In this work, we are looking at a diffusion
process on a network of agents where the probability of
success depends on the allocated time for the attempt. We
consider different time-allocation strategies for the agents
consisting in a trade-off between many unlikely attempts
versus few likely ones. Our model incorporates a bursty
behaviour as observed in human-related networks such as
Twitter or mailbox checking. Our results show that, for the
same mean time between two successful transmissions, the
former strategy is more efficient in terms of diffusion.
Saptarshi Ghosh
Inferring
topical attributes of users in the Twitter Online Social
Network
Online Social Networks (OSNs) such as Twitter and
Facebook are among the most popular sites on the Web, and are
used by hundreds of millions of users. Today, OSNs are used
not only to communicate with one's friends, but also to
discover content / information on various topics of one's
interest. Especially, Twitter is increasingly being used to
gather real-time information on various topics and events.
Given this scenario, we are developing methodologies to
improve topical information retrieval (search, recommendation)
in Twitter. Since users are the primary producers as well as
consumers of information in an OSN, a primary challenge for
topical information retrieval is to accurately determine the
topics of expertise and interest of individual users. We have
proposed novel crowdsourcing-based methodologies to infer the
topics of expertise and interest of users, utilizing the
Twitter Lists feature. Our methodologies give accurate and
comprehensive topical attributes for millions of popular
Twitter users. We are presently utilizing the knowledge of
topical attributes of users to develop topical search and
personalized recommendation systems on the Twitter platform.
Some of the systems developed by us are:
(i) Who is Who, a system to infer topical
expertise of popular Twitter users:
http://twitter-app.mpi-sws.org/who-is-who/
(ii) Cognos, a search system for topical experts
in Twitter:
http://twitter-app.mpi-sws.org/whom-to-follow/
(iii) Who likes What, a system to infer topics of
interest of Twitter users: