A Satellite Workshop of European
Conference on Complex Systems, 2013
Barcelona, Spain, September 18, 2013.
Marc Barthélemy
“Evolution of road networks”
The road network is a crucial component of urban systems: its
growth and evolution reflect how a city changes in time. This
network is both embedded in space and evolves in time, and we thus
have to face the difficulty of measuring and characterizing its
evolution, and to extract useful information. I will illustrate in
this talk these various problems and present some recent results
on empirical case studies. If time allows, I will also mention
various directions for modeling these systems.
Vincent Blondel “The privacy bounds of human mobility”
We study fifteen months of human mobility data for one and a half
million individuals and find that human mobility traces are highly
unique. In fact, in a dataset where the location of an individual
is specified hourly, and with a spatial resolution equal to that
given by the carrier's antennas, four spatio-temporal points are
enough to uniquely identify 95% of the individuals. We coarsen the
data spatially and temporally to find a formula for the uniqueness
of human mobility traces given their resolution and the available
outside information. This formula shows that the uniqueness of
mobility traces decays approximately as the 1/10 power of their
resolution. Hence, even coarse datasets provide little anonymity.
These findings represent fundamental constraints to an
individual's privacy and have important implications for the
design of frameworks and institutions dedicated to protect the
privacy of individuals.
Renaud Lambiotte
“Decentralized Routing on Spatial Networks with Stochastic Edge
Weights”
We investigate algorithms to find short paths in spatial networks
with stochastic edge weights. Our formulation of the problem of
finding short paths differs from traditional formulations because
we specifically do not make two of the usual simplifying
assumptions: (1) we allow edge weights to be stochastic rather
than deterministic; and (2) we do not assume that global knowledge
of a network is available. We develop a decentralized routing
algorithm that provides en route guidance for travelers on a
spatial network with stochastic edge weights without the need to
rely on global knowledge about the network. To guide a traveler,
our algorithm uses an estimation function that evaluates
cumulative arrival probability distributions based on distances
between pairs of nodes. The estimation function carries a notion
of proximity between nodes and thereby enables routing without
global knowledge. In testing our decentralized algorithm, we
define a criterion that allows one to discriminate among arrival
probability distributions, and we test our algorithm and this
criterion using both synthetic and real networks.
Camille Roth
“Reputation and activity dynamics within topical communities”
We analyze the structure and processes of link creation and
reputation building in a sample of Internet communities. Our
approach uses a corpus of around 9,000 'active' French websites
and blogs which have been manually labeled as belonging to a
specific topical territory, such as "cooking", "crafts", or
"politics". Building upon dynamic data spanning over a
period of several months, we are then able to exhibit
characteristic trajectories of engagement into each territory and,
more broadly, reputation building on the web. Beyond the
description of peculiar determinants of link creation, we propose
a typology and map of the various structural positions that these
websites may hold within their territory.
Monojit Choudhury
“Semiotic Dynamics of the Web Search Queries: A window to the
emergence of linguistic structure”
The structure of Web search queries is evolving through a
self-organizing process; millions of Web users query the search
engines for their information needs and modify the queries based
on search engine feedback, and on the other hand, the search
engines exploit the querying behavior of the users to serve better
results. This bidirectional adaptive process has led to increase
in length and complexity of the Web search queries. In this talk,
I will discuss some recent results, where we show that the
increase in length of the queries is indeed due to emergence of a
unique syntactic structure; queries are not merely a bag-of-words
anymore. I will also present a comparative study of complex
network modeling of queries and Natural language text, which shows
that queries have many non-trivial structural properties that are
hard to replicate through simple stochastic query generation
models. These properties are akin to those of Natural languages,
but also differ from natural languages in certain important ways.
These and many other such studies point to the fact that a unique
syntactic structure is evolving for Web search queries, which is
perhaps similar to the structure of the how human protolanguage –
a conjectured linguistic state that predates the current natural
languages during the history of human evolution.
Luis E. C. Rocha
"Flow Motifs Reveal Limitations of the Static Framework to
Represent Human Interactions"
Networks are many times used as underlying structures to represent
interactions where infections, information, or other quantities
may spread. The standard approach is to aggregate all links into a
static structure. However, several studies have shown that the
time order in which the links are established may alter the
dynamics of spreading. In this talk, I will introduce a method to
study the variations in the flow between adjacent vertices when
the temporal information is included. The flow between vertices is
estimated by using a simulated random walk dynamics. Links are
split into high- and low-flow such that the original undirected
network is converted into a directed flow network. By quantifying
the flow motifs of this new network, it is possible to identify
that in some categories of networks, the local flow changes
significantly when the time information is included. In
particular, if the identity of the active vertices changes over
time (e.g. communication in dating sites), the representativity of
flow motifs is different in the static and temporal frameworks. On
the other hand, in networks with regular contacts and persistent
vertices (e.g. email communication), the representativity of flow
motifs is similar in both frameworks. Moreover, the method reveals
that 3- and 4-vertex cliques, containing all low-flow links, are
more representative than those cliques containing all high-flow
links. These results suggest that the local topology and temporal
activity are insufficient to fully understand the flow between
adjacent vertices. The structure of the clique alone does not
completely characterize the potential of flow between the
vertices.
Fabien Tarissan
“Real-world spreading phenomena: experiments on a large-scale P2P
system”
Understanding the spread of information on complex networks is a
key issue from a theoretical and applied perspective. Despite the
effort in developing theoretical models for this phenomenon,
gaging them with large-scale real-world data remains an important
challenge due to the scarcity of open, extensive and detailed
data. In this talk, we explain how traces of peer-to-peer file
sharing may be used to this goal. We reconstruct the underlying
social network of peers sharing content and perform simulations on
it in order to assess the relevance of the standard SIR model to
mimic key properties of real spreading cascades. The results show
that it is insufficient to mimic real spreading cascades, thus
raising an alert against the careless, widespread use of this
model. However, we also show that using the available temporal
data in the trace and integrating it into an heterogeneous version
for the spreading model enables to improve its relevance in this
context.
János Kertész
“Temporal motifs in mobile communication networks”
with Lauri Kovanen, Kimmo Kaski, Jari Saramäki (Aalto)
Electronic communication records provide detailed
information about temporal aspects of human interaction. Previous
studies have shown that individuals' communication patterns have
complex temporal structure, and that this structure has
system-wide effects. In this paper we use mobile phone records to
show that interaction patterns involving multiple individuals have
non-trivial temporal structure that cannot be deduced from a
network presentation where only interaction frequencies are taken
into account. We apply a recently introduced method, temporal
motifs, to identify interaction patterns in a temporal network
where nodes have additional attributes such as gender and age. We
then develop a null model that allows identifying differences
between various types of nodes so that these differences are
independent of the network based on interaction frequencies. We
find gender-related differences in communication patters, and show
the existence of temporal homophily, the tendency of similar
individuals to participate in interaction patterns beyond what
would be expected on the basis of the network structure alone. We
also show that temporal patterns differ between dense and sparse
parts of the network. Because this result is independent of edge
weights, it can be considered as an extension of Granovetter's
hypothesis to temporal networks.
Janette Lehmann
“User Engagement: The Network Effect Matters!”
with Mounia Lalmas, Ricardo Baeza-Yates, Elad Yom-Tov
In the online industry, user engagement is the quality of the
user experience associated with the phenomena of users wanting to
use a web ap- plication on a regular basis. Many online providers,
such as MSN, Google, and Yahoo!, offer a variety of sites enabling
users to, for instance, communicate via email or chat tool, share
information via social networks, and read daily as well as
entertainment news. The aim of these online providers is not only
to keep users interacting with each of the site they offer, but
across all their sites, that is their whole network of sites. To
achieve this, online providers direct users to their various sites
by using, for instance, hyperlinks. This leads to a virtuous cycle
be- tween site engagement and the traffic between sites: each
reinforces the other. We call user engagement with a network of
sites networked user engagement.
How can we measure networked user engagement? When assessing
engage- ment with a provider network, we must also take into
account the traffic between sites. Current engagement metrics,
such as click-through rate, page views, and return rates, were
developed to measure engagement for each site separately. They
cannot be used in any straightforward way to measure engagement
within a network of sites. We therefore develop a new approach
that models sites (the nodes) and the traffic between them (the
edges) as a network. Then, we ap- ply complex network metrics in
conjunction with engagement metrics to study user engagement
within a provider network. We use complex network metrics at the
network level (such as modularity, density) to describe the
engagement with respect to the whole network. We use metrics at
node level (such as degree, betweenness, centrality) to learn
about the engagement and traffic for specific sites. We evaluate
our approach using browsing data of 2M users and a total of 25M
online sessions across 728 Yahoo! sites from 80 different
countries.
Eduardo Altmann
“Endogenous and exogenous factors in the dynamics of linguistic
innovations”
The electronic availability of historical texts allows us to
quantify the temporal evolution of linguistic innovations with an
unprecedented accuracy. By connecting these observations to simple
models we obtain information about the microscopic rules
underlying the process of innovation spreading. We are
particularly interested in quantifying the importance of
endogenous (e.g., word-of-mouth, direct connections in a social
network) and exogenous (e.g., broadcasting, external fields)
processes in the observed change. Applying our methodology to the
case of orthographic reforms and regularization of verbs we obtain
that linguistic changes follow the expected "S-curve" only if the
exogenous effects dominate, otherwise an exponential curve is
observed. Our methodology is not restricted to the case of
linguistic innovations and should be of interest whenever data
with good resolution of the temporal evolution of the innovation
is available.
Sudipta Saha
“Understanding Evolution of Inter-Group Relationships Using
Bipartite Networks”
In online social systems, users with common affiliations or
interests form social groups for discussing various topical
issues. We study the relationships among these social groups,
which manifest through users who are common members of multiple
groups, and the evolution of these relationships as new users join
the groups. Focusing on a certain number of the most popular
groups, we model the group memberships of users as a subclass of
bipartite networks, known as Alphabetic Bipartite Networks
(α-BiNs), where one of the partitions contains a fixed number of
nodes (the popular groups) while the other grows unboundedly with
time (new users joining the groups). Specifically, we consider the
evolution of the thresholded projection of the user-group
bipartite network onto the set of groups, which accurately
represents the inter-group relationships. We propose and solve a
preferential attachment based growth model for evolution of α-
BiNs, and analytically compute the degree distribution of the
thresholded projection. Next, we investigate whether the
predictions of this model can explain the projection degree
distributions of user-group networks derived from several real
social systems (Livejournal, Youtube and Flickr). This study shows
that the inter-group network is tightly knit, and there is an
implicit semantic hierarchy within its structure, that is clearly
identified by the method of thresholding. Our analysis also
reveals that the robustness in the structure of the real-world
inter-groups networks comes significantly from the existing huge
heterogeneity in the number of common members among different
groups. Joydeep Chandra
“How users gain connectivity in Online Social Networks --- An
Analytical Perspective”
In online social networks, the growth of connectivity of the users
is guided by certain network specific factors like the scope and
the purpose the network serves, the extent of information made
available about the other users in the network and also on the
maximum number of social contacts, in terms of friends or
followers, that an user is allowed to have. We model the
connectivity properties of the users in steady state based on
these above stated factors and derive closed form equations that
represent the relation between each of these parameters and the
connectivity. This information can be used by the application
developers to set these parameters so as to tune the various
topological properties of the connectivity network. We
validate our models using extensive simulations. Finally, we apply
our model on real traces of social networks like Twitter and
Facebook and show that our model can successfully represent the
connectivity properties of the users in the respective networks.
Laetitia Gauvin
“Beyond Counting Tweets: Mining Time-resolved Topical Activity in
Social Media”
Streams of user-generated content in social media exhibit
patterns of collective attention across diverse topics, with
temporal structures determined both by exogenous factors and
endogenous factors. Teasing apart different topics and resolving
their individual, concurrent, activity timelines is a key
challenge in extracting knowledge from microblog streams. Facing
this challenge requires the use of methods that expose latent
signals by using term correlations across posts and over time.
Here we focus on content posted to Twitter during the London 2012
Olympics, for which a detailed schedule of events is independently
available and can be used for reference. We mine the temporal
structure of topical activity by using two methods based on
non-negative matrix factorization. We show that for events in the
Olympics schedule that can be semantically matched to topics we
obtain from Twitter, the extracted activity timeline closely
matches the known timeline from the schedule. Our results show
that, given appropriate techniques to detect latent signals,
Twitter can be used as a social sensor to extract
high-resolution topical-temporal information on real-world events.
Luca Maria Aiello
“Reading the Source Code of Social Ties”
Though social network research using online data has exploded
during the past few years, not much thought has been given to the
translation of online records to social datasets. Records of
online interactions have been interpreted as indicative of one
social process or another (e.g., status exchange or trust), often
with little systematic justification regarding the relation
between observed data and theoretical concept. Our research aims
to breach this gap in computational social science research, by
illustrating how online interactions can be automatically
classified into different domains of interaction. We conceptualize
social ties as sequences of exchange interactions and develop an
algorithm to cluster them according to the type of resource
exchanged. In particular, we use data from a book-review website
(aNobii) to distinguish between user-to-user interactions that
represent exchanges of status, knowledge and social support. A
clear structure mapping onto these three domains of interaction
emerges spontaneously when conversational transitions are
considered. The use of such methods allows us to examine the
relationship between the three modes of exchange in the same dyad,
setting the stage for more nuanced analysis of dynamic social
streams that may one day incorporate the normative grammar of
social interaction.
Marc Timme
“Dynamics of Interdependent Networks: Co-action of Stability
and Communication in Power Grids"
with Dirk Witthaut
Ensuring reliable electric energy supply constitutes one of the
major challenges of modern societies and is thus of current
topical interest across science and engineering. Dynamic
consequences of the interdependence of functionally different
networks (power grids and computer networks in the example
published most prominently, Buldyrev et al., Nature, 2010, Gao et
al., Nature Physics, 2012) have been studied since recently. Yet,
it remains unclear how exactly the stability of power grids
depends on the communication structure among the nodes. Here we
study the dynamics of modern power grids with respect to
decentralization and uncover which topologies in the power
transmission and the communication networks favor (and which
prevent) stability [1-3].
"Temporal network as a modeling framework for disease
spreading"
We will discuss the past future and present in the modeling
infectious disease spreading with temporal networks—i.e. data
where one explicitly model (or record) information about both when
and between whom that contacts have happened. We will discuss
which temporal network structures that are most important for
disease spreading; how these can be exploited to mitigate
epidemics and which diseases that actually can be studied with a
temporal network framework. Among other things we will argue that
the turnover of relationships is an important factor for
spreading. We will also discuss how to bridge temporal network
epidemiology and the study of opinion and information spreading in
social networks.