DYNAMICS ON AND OF COMPLEX NETWORKS VII

A Satellite Workshop of European Conference on Complex Systems, 2014

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.

 

Matthieu Latapy

 Link streams

 

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.

 

Yamir Moreno

Forecasting large scale social phenomena


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.

 

Soumajit Pramanik

Controlling Information Flow in Social Networks

 

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)."



Peter Fennell

A general and exible framework for studying dynamics on complex networks

 

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:

http://twitter-app.mpi-sws.org/who-likes-what/