Printable version of the programme (Last updated: June 14)
Monday, June 4, 2012
14:30Bus departs from airport
16:00Coffee & welcome
The general theory about the spreading on complex networks will be presented. In particular, we will cover
a) Percolation theory in complex networks
b) The friendship paradox
c) General spreading dynamical models SI, SIS, SIR
d) Mapping dynamical spreading models into static percolation problems
e) Applications of spreading models to the dynamics of rumors, information, disease, etc.
Tuesday, June 5, 2012
Dynamic phenomena on networks can be of many kind. When links are active only temporarily the network shows specific properties; there are, e.g., important constrains for spreading. The study of such phenomena require a new formalism, that of temporal networks, where links can be switched on and off. Examples include communication or social interaction networks. Important characteristics and measures of temporal networks will be reviewed. The recently introduced concept of temporal motifs will also be presented.
We will review some of the recent developments about how time-varying and temporal networks impact the spreading con complex networks. In particular, we will cover:
a) Characterization of dynamical contact networks: heterogeneous activity,edge creation/destruction, bursty patterns of contact, etc.
b) Spreading on dynamical networks.
b1) Influence of the heterogeneity of activity (application to viral marketing).
b2) Impact of burstiness in SIR models (the dynamical strength of social ties).
b3) Effect of edge creation/destruction in spreading.
14:0015:30Spectral properties and synchronization in complex networks Albert Díaz-Guilera (University of Barcelona, Spain) / Slides
I will introduce the Kuramoto model of synchronization of phase oscillators. Starting from very simple settings I will show which are the conditions for the system to synchronize. If oscillators are identical, after a transient, the system approaches the synchronized state in such a way that the equations of motion can be linearized. This can be solved in terms of normal modes and establish the relation between topology (by means of eigenvalues of the static Laplacian matrix of the network) and dynamics (in terms of the time needed to synchronize). Furthermore, I will show that intermediate time scales are related to subsets of eigenvalues and communities.
Special guest talk (Chairman: Santo Fortunato)
17:0018:00The next level of modeling social interaction: How to detect, quantify and utilize emotional influence Frank Schweitzer (ETH Swiss Federal Institute of Technology, Zurich, Switzerland) / Slides
Models of (bounded) rational agents failed to predict, or even capture, recent collective phenomena in social and economic systems. Ranging from the current financial crisis to the Arab spring, social "ingredients" such as herding, (dis)trust, empathy, agression, or other forms of positive or negative emotions seem to play the major role in amplifying critical situations. Do we have tools to detect and to quantify such emotions? Online datasets (written text from fora, microblogs, or reviews) can be used to apply sentiment analysis algorithms and to map the writer's emotions along the dimensions of valence and arousal. But what do we learn from that analysis, beyond the nation's mood in the morning? How do expressed emotions affect the response of other users in the cyberspace? Can we develop an interaction model of emotional agents to reproduce the stylized facts observed? Could we even manipulate cyberemotions? (and can I answer all these questions in less than one hour? - I'll try at least)
Wednesday, June 6, 2012
9:0010:30Dynamical networks: empirics, modeling, and dynamical processes Alain Barrat (CPT Marseille, France) / Slides
In recent years, the study of the dynamics of complex networks has been largely stimulated by the novel availability of data sets with temporal resolution. I will describe several aspects of the study of dynamical networks, building on examples of infrastructure and social network data. I will discuss various tools used to describe empirical dynamical networks, and describe various representations of the data sets. I will present some modeling approaches and studies of dynamical processes on dynamical networks, ranging from toy to realistic data-driven models.
The statistics of activities on a network shows interesting features. Very often the processes are not Poissonians but characterized by a very broad, power law inter-event time distribution. Examples include communication activities, neuron firing or earthquake signals. Another quantity characterizing the activity's temporal behavior is the autocorrelation function, which has also a power law decay. It will be shown that for renewal processes there is a scaling law connecting the exponents of the two quantities. An indication of the departure from the renewal processes is If the scaling law is violated. The distribution or the number of events is a good indicator for the dependence of the events. This quantity is closely related to the memory of the process.
I will show how to generalize spectral properties and dynamical approach to a synchronized state in the case of moving oscillators. When oscillators move and they can interact with nearby oscillators they form a time dependent contact network. In terms of the time scales for motion and synchronization we describe the different regimes of the system.
16:0016:30Will they like my game? A social game industry perspective Tuomas Rinta (Applifier) / Slides
Applifier is a cross-promotion network of games on Facebook, and has been recommending new games to Facebook users for the last two years. During those two years, Applifier has managed to build profiles of over 300 millions users on what they play and when. What then can be extracted from this information to better predict a match between a game and a player?
Thursday, June 7, 2012
First session (Chairman: Alain Barrat)
9:009:30Localization and Spreading of Diseases in Complex Networks José Fernando Mendes (University of Aveiro, Portugal) / Slides
Using the SIS model on unweighted and weighted networks, we consider the disease localization phenomenon by using a spectral approach. We show that the contradiction between the mean-field approximation and the exact result can be resolved if we take into account localization of diseases. In contrast to the well-recognized point of view that diseases infect a finite fraction of vertices right above the epidemic threshold, we show that diseases can be localized on a finite number of vertices, where hubs and edges with large weights are centers of localization. Our results follow from the analysis of standard models of networks and empirical data for real-world networks.
9:309:50Exploiting temporal structures of human interaction for efficient vaccination Luis Rocha (Catholic University of Louvain, Belgium) / Slides
Interactions between individuals are not necessarily regular but follows heterogeneous contact patterns. These patterns can be used to identify individuals that contribute more to the spread of infections than the average. In this talk, I will discuss two vaccination protocols where partners of random vertices are selected according to their temporal distance. One method is based on selecting and vaccinating the most recent contact, and the other on selecting the most active partner of a random individual. These protocols are applied to empirical and benchmark networks and their efficiency is quantified by measuring the epidemic outbreak of a SIS model in comparison to similar simulations using the random neighbor vaccination protocol. Our results indicate that vaccinating the partner of the most recent contact is more effective to reduce the prevalence in case of networks where contacts are more concentrated temporally. On the other hand, in networks where contacts are more evenly distributed, selecting the most active partner has increased ability to reduce the simulated epidemics both in comparison to recent and to random neighbor protocols.
9:5010:10Correlated dynamics in egocentric communication networks Marton Karsai (Aalto University, Espoo, Finland) / Slides
We investigate the communication sequences of millions of people through two different channels and analyse the fine grained temporal structure of correlated event trains induced by single individuals. By focusing on correlations between the heterogeneous dynamics and the topology of egocentric networks we find that the bursty trains usually evolve for pairs of individuals rather than for the ego and his/her several neighbours thus burstiness is a property of the links rather than of the nodes. We compare the directional balance of calls and short messages within bursty trains to the average on the actual link and show that for the trains of voice calls the imbalance is significantly enhanced, while for short messages the balance within the trains increases. These effects can be partly traced back to the technological constrains (for short messages) and partly to the human behavioural features (voice calls). We define a model that is able to reproduce the empirical results and may help us to understand better the mechanisms driving technology mediated human communication dynamics.
Second session (Chairman: Albert Díaz-Guilera)
Change is a fundamental ingredient of interaction patterns in biology, technology, the economy, and science itself: Interactions within and between organisms change; transportation patterns by air, land, and sea all change; the global financial flow changes; and the frontiers of scientific research change. Networks and clustering methods have become important tools to comprehend instances of these large-scale structures, but without methods to distinguish between real trends and noisy data, these approaches are not useful for studying how networks change. Only if we can assign significance to the partition of single networks can we distinguish meaningful structural changes from random fluctuations. In my presentation, I will show that bootstrap resampling accompanied by significance clustering provides a solution to this problem.
11:1011:30The 1/k assumption for sandpiles on networks: origin, failure and alternative Pierre-André Noël (UC Davis, California, USA) / Slides
Sandpile models were originally introduced on a lattice as an example
of self-organized criticality. Analytical descriptions of this process
on a network usually assume that the probability for a node of degree
k to topple upon reception of a single grain of sand is equal to 1/k.
Originally demonstrated in the annealed network case, the use of this
assumption in quenched settings is typically justified through
numerical simulations: a node of degree k approximately topples a
fraction 1/k of the times it receives a grain of sand, and the
critical exponents obtained as a result of this assumption agree with
Nonetheless, we show that the 1/k assumption is false in quenched systems. Of prime importance is that nodes toppled by receiving sand from a "parent" node are much less likely to cause this parent to topple than their other neighbours. This affects both the small cascades distribution and on the total amount of sand in the equilibrium state. Returning to the basic assumptions of self-organized criticality, we obtain an analytical formalism accounting for this effect, as well as of other correlations, through a multi-type branching process. Finally, we study how the original single-type branching process with the 1/k approximation turns out to provide the correct critical exponents.
11:3011:50Optimized reduction of uncertainty in bursty human dynamics Hang-Hyun Jo (Aalto University, Espoo, Finland) / Slides
Human dynamics is known to be inhomogeneous and bursty but the detailed understanding of the role of human factors in bursty dynamics is still lacking. In order to investigate their role we devise an agent-based model, where an agent in an uncertain situation tries to reduce the uncertainty by communicating with information providers while having to wait time for responses. Here the waiting time can be considered as cost. We show that the optimal choice of the waiting time under uncertainty gives rise to the bursty dynamics, characterized by the heavy tailed distribution of optimal waiting time. We find that in all cases the efficiency for communication is relevant to the scaling behavior of the optimal waiting time distribution. On the other hand, the cost turns out in some cases to be irrelevant depending on the degree of uncertainty and efficiency.
Third session (Chairman: Janos Kertész)
13:3014:00Complex networks and hidden metric spaces. An application of the S1 model to metabolism Mariangeles Serrano (University of Barcelona, Spain) / Slides
Hidden geometries underlying real networks appear to provide a simple and natural explanation for their structure. Beyond the ability of these models to simulate the observed topologies, they enable an inverse method to map real networks to congruent metric spaces. In particular, we prove that metabolism, the set of coupled biochemical reactions in the cell that secure life, can be successfully mapped using the Euclidean one-dimensional S1 model. The S1 model turns out to be a paradigmatic geometric model for critical topological properties, like small-world topological distances, scale-free connectivity, clustering, and self-similarity. In the case of metabolic networks, it opens a new geometric perspective which challenges the classical definition of biochemical pathway and, at the same time, allows us a powerful method to detect missing reactions with high accuracy. Interestingly, the S1 model has become the precursor of a family of equilibrium and growing network models, in which similarity between nodes has a geometric interpretation that shapes network structure, dynamics and evolution.
Many natural and artificial networks evolve in time. Nodes and connections appear and disappear at various timescales, and their dynamics has profound consequences for any processes in which they are involved. Until recently however, a large majority of studies about complex networks have focused on a static or aggregated representation, in which all the links that appeared at least once coexist. In recent years, the interest towards the temporal dimension of the network description has blossomed, and at the same time, researchers have started to study how the temporal evolution of the network substrate impacts the behavior of dynamical processes.
Here, we study how random walks, as paradigm of dynamical processes, unfold on temporally evolving networks. To this aim, we use empirical dynamical networks of contacts between individuals in various social contexts, as recorded by the SocioPatterns project. These dynamical networks exhibit heterogeneous and bursty behavior, indicated by the long tailed distributions for the lengths and strength of conversations, as well as for the gaps separating successive interactions.
Furthermore, we show how introducing different randomizing strategies allows us to identify the role of the different properties of the empirical networks. We perform numerical analysis both for the coverage and the mean first passage time properties of the random walk. In both cases we have found that the empirical sequences deviate systematically from the mean field prediction, inducing a slowing down of the network exploration and of the mean first passage time. Remarkably, the analysis of the randomized sequences has allowed us to point out that this is due uniquely to the temporal correlations between consecutive conversations present in the data, and not to the heterogeneity of their lengths.
Finally, we address the consequences of the intrinsically limited duration of many real world dynamical networks. Considering the fundamental prototypical role of the random walk process, we believe that these results could help to shed light on the behavior of more complex dynamics on temporally evolving networks.
14:2014:40A thermodynamic counterpart of the Axelrod model of social influence Yerali Gandica (University of Coimbra, Portugal) / Slides
We propose a thermodynamic version of the Axelrod model of social influence. In one-dimensional lattices, the thermodynamic model becomes a Potts model of several coupled lines with a site (agent) interaction that increases with the site matching traits. We analytically calculate thermodynamic and critical properties for a one-dimensional system and show that an order-disorder phase transition only occurs at T = 0, independently of the number of cultural traits q and features F of the agents. We find that in the thermodynamic model the parameter q does not induce any transition or anomaly in the system, as it does in the social model that violates detailed balance. The one-dimensional thermodynamic Axelrod model belongs to the same universality class of the Ising and Potts models notwithstanding the increase of the internal dimension of the local degree of freedom.
Fourth session (Chairman: Renaud Lambiotte)
In this paper we present a network solution to a central problem in the study of crime specialization, that is, which crimes should be considered of a similar type and which crimes should be considered distinct from the perspective of criminal's behavior. By studying a large set of Swedish suspects we empirically investigate the generalist and specialist behavior of suspects. We show that there is a large group of criminals who can be described as generalists. At the same time, we observe a non-trivial pattern of specialization across age and gender of suspects. Women are less prone to commit crimes of certain types, and in particular are more prone to specialize in crimes related to fraud. We also find evidence of temporal specialization of suspects. Older persons are more specialized than younger ones, and some crime types are preferentially committed by suspects of different ages.
15:4016:00Communication dynamics in finite capacity social networks Jan Haerter (Niels Bohr Institute, Copenhagen, Denmark) / Slides
In communication networks structure and dynamics are tightly coupled. The structure controls the flow of information and is itself shaped by the dynamical process of information exchanged between nodes. In order to reconcile these effects, a generic model, based on the local interaction between nodes, is considered for the communication in large social networks. In agreement with data from a large human organization, we show that the flow is non-Markovian and controlled by the temporal limitations of individuals. We confirm the versatility of our model by predicting simultaneously the degree-dependent node activity, the balance between information input and output of nodes and the degree distribution. Finally, we quantify the limitations to network analysis when it is based on data sampled over a finite period of time.
16:0016:20Modelling conflict in social cooperation: the Wikipedia edit wars Gerardo Iñiguez (Aalto University, Espoo, Finland) / Slides
We model the rise, persistence and resolution of severe conflicts in Wikipedia by coupling opinion formation with article edition in a bounded confidence dynamics. The complex social behavior surrounding article edition is implemented in a minimal model as being two fold: individuals interact directly to share information, and edit articles to establish their own opinions. The model shows interesting properties such as scaling in the relaxation time of the dynamics and oscillatory transient states in the edit history of an article. A dynamical phase transition due to agent renewal characterizes different kinds of edit warring, which qualitatively reflect the dynamics of conflict in real Wikipedia data.
16:2016:40Revert Network of Wikipedia Editors in Editorial Wars Taha Yasseri (Budapest University of Technology, Hungary) / Slides
Despite the large number of present scholarly studies, a comprehensive image of the underlying mechanisms, leading to collaborative production of the largest online encyclopedia ever, Wikipedia, is still missing. Among different aspects, editorial wars and controversial topics are of great interest, as the process of consensus reaching and equilibration among large number of unsupervised cyber-agents, eager to represent their opinions in Wikipedia articles, is far from trivial. In this work, we try to locate, quantify, and understand the features of editorial wars. To this end, we focus on the network of editors of certain articles, who are connected by anti-collaboration links, i.e. revert edits. Then we introduce a measure of controversy based on the parameters of the revert network, which ranks the articles according to the "amount of conflict" in them, we further analyze the temporal characteristics of editorial wars by comparing samples of controversial/peaceful articles. We also observe different scenarios of edit wars with various characteristics and ways to approach to consensus.
17:00Trip to Porvoo
Friday, June 8, 2012
First session (Chairman: Luis Rocha)
9:009:30On the identification of social communities in mobile phone communication networks Vincent Blondel (Catholic University of Louvain, Belgium) / Slides
We describe a simple and efficient method, the "Louvain method", for the detection of communities in networks. The method has sub-quadratic computational complexity and can be routinely used for networks with billions of nodes or links; the method was chosen a couple of months ago by LinkedIn for its network visualization tool. As an illustration of the method, we describe the communities obtained on a social network constructed from billions of mobile phone communications at country scale. The low complexity of the method allows the analysis of large time-evolving networks and we illustrate this with a visualization of how a country-wide social network evolved over a six months period.
There is a growing interest in comparing the standards and quality of different countries and regions according to their research performance. To do this we categorize each research article to a location based on its author's affiliation. We then study the geographical patterns and biases in the corresponding citation and collaboration network. Finally, we show how does citation and collaboration in different countries (or cities) are correlated with each other.
We have been analyzing data from the application that produces more
Internet traffic in Europe, Bittorrent. Bittorrent is a file sharing application
used worldwide. Our data is the most precise ever extracted for this
application: we have what more than 1 million users shared, when and
with whom during 1 month.
In this analysis we have found a clear correlation between how the people use this applications and their economic level. In particular we find that people are specialists on what they share. That is, individuals typically share only one or two types of contents. Countries are also heterogeneous in their composition of sharing specialists. Finally, we see that the sharing behaviors of the countries are highly correlated with their level of economic development. Surprisingly, individuals in countries with more advanced economies tend to share smaller files, rather than larger. These results could lead to optimize or even personalize the actual Internet protocols as well as to stimulate further studies to link the use of technology and economy.
Second session (Chairman: José Fernando Mendes)
For many years, the behavior of the susceptible-infected-susceptible (SIS) model for epidemic spreading on networks was believed to be described very accurately by the heterogeneous mean-field (HMF) theory. HMF predicts vanishing threshold for scale-free networks and finite threshold for scale-rich networks. In the last few years, this picture has been challenged and the behavior of the SIS model has been shown to be surprisingly richer. In this talk I will show that the threshold vanishes for any network, different physical mechanisms may trigger the transition and I will discuss other very recent developments.
Identifying and understanding modular organizations is centrally important in the study of biological systems. We are interested in a general formalization of modularity applicable to multivariate dynamical systems. Such a formalization can be used not only for the analysis of system dynamics but also to compare notions of modularity found in disparate domains. Our treatment starts from the point of view of statistical modeling and prediction of dynamical systems. It is known that for finite amounts of training data, simpler models can have greater predictive power than more complex ones. The trade-off between model simplicity and predictive accuracy generates optimal multiscale decompositions of dynamical networks into weakly-coupled, simple modules.
11:3011:50Markov dynamics zooming for the detection of non clique-like communities in complex multiscale networks Michael Schaub (Imperial College London, UK) / Slides
In recent years there has been a surge of interest in community detection in complex networks. Popular community detection algorithms and random graph benchmarks normally assume an implicit notion of community based on clique-like subgraphs, yet many real networks do not conform to this notion. Specifically, networks that emerge from an underlying concept of distance can have a well-defined multiscale structure based on non clique-like subgraphs, which can be interpreted as long-range communities. Here we show how by adopting a dynamical perspective towards community detection, in which the evolution of a Markov process on the graph is used as a zooming lens over the structure of the network at all scales, one can detect both clique- and non clique-like communities without imposing an upper scale to the detection. The tendency to over-partitioning exhibited by popular methods, such as modularity and the Map equation, when applied to non-clique like communities is due to these methods being "one-step" and thus blinded by a restricted "field-of-view", an intrinsic upper scale on the communities they can detect. By introducing an explicit time-dependent flow via Markov sweeping "an approach that can also be applied to enhance the multiscale capabilities of the Map equation" one can detect relevant communities over particular timescales and extricate the multiscale community structure, if present. We illustrate our work with examples drawn from diverse application areas, such as image segmentation, structural analysis of proteins and power grid networks, where a multiscale structure of non clique-like communities is revealed.
Third session (Chairman: Martin Rosvall)
13:3014:00Ranking and clustering of nodes in networks with smart teleportation Renaud Lambiotte (University of Namur, Belgium) / Slides
Random teleportation is a necessary evil for ranking and clustering directed networks based on random walks. Teleportation enables ergodic solutions, but the solutions must necessarily depend on the exact implementation and parametrization of the teleportation. For example, in the commonly used PageRank algorithm, the teleportation rate must trade off a heavily biased solution with a uniform solution. Here we show that teleportation to links rather than nodes enables a much smoother trade-off and effectively more robust results. We also show that, by not recording the teleportation steps of the random walker, we can further reduce the effect of teleportation with dramatic effects on clustering.
14:0014:20Effective resampling of citation networks for significance analysis of ranking and clustering Atieh Mirshahvalad (University of Umeå, Sweden) / Slides
Community detection helps us to simplify the complex configuration of networks. But communities are reliable only if they are statistically significant. To detect statistically significant communities, one approach is to repeatedly perturb the original network and analyze the communities. But the perturbation approach is reliable only if we understand how the results depend on the underlying assumptions of the perturbation method.
Here we explore how maintaining link correlations in resampling schemes affect the significance of communities in citation networks. We compare maintained link correlations in non-parametric article resampling with parametric resampling of citations that reduces link correlations in multinomial and Poisson resampling. While multinomial resampling maintains the variance of individual link weights and eliminates correlations between connected links, Poisson resampling eliminates any link correlations. For significance analysis of ranking and clustering, we find that it is more important to capture the variance of individual link weights than the correlations between link weights. We also find that Poisson resampling underestimates the variance of link weights. Therefore, when only link weights are available and neither article resampling nor multinomial resampling is possible, we suggest a simple parametric resampling scheme that generates link variances close to link variances of non-parametric article resampling.
Nevertheless, when we highlight and summarize important structural changes in science, we find that the more link correlations we maintain in the resampling scheme, the earlier we can predict structural change.
In our recent paper we introduced the concept of temporal motifs for studying mesoscale temporal structure of time-dependent networks. We show how these temporal motifs can be used to study temporal network data where nodes have different types. We present tools for identifying motifs that are statistically more or less common than expected were all nodes similar regardless of their type. The obtained results are purely temporal in the sense that they are independent of the structure of the aggregate network. By applying this method to a large mobile phone data set we find systematic differences between node types, and some examples of temporal homophily.
Fourth session (Chairman: Claudio Castellano)
15:1015:40Semi-metric topology and collective computation in complex networks Luis Rocha (Indiana University, Bloomington, USA) / Slides
We outline the nonlinear isomorphism between weighted graphs used to characterize proximity/similarity among items, and those used to characterize distance. This allows us to compare transitive closure in Fuzzy graphs with the All Pairs Shortest Paths (APSP) Dijkstra algorithm (or metric closure), which is but one form of distance closure. This isomorphism allows us to derive various concepts useful for a characterization of complex networks as weighted graphs: semi-metric behavior, distance closure, distance backbone, and semi-metric threshold. We discuss the application of these concepts to the study of the small-world phenomenon in weighted graphs, and apply them to various networks built from empirical data.
There have been many advances in understanding the topological or structural properties of complex networks. There has also been much interest in the modularity of networks, which is closely tied to their robustness to structural perturbations. However, to fully understand biochemical regulation, we need to look at complexity from the dynamics perspective. We outline our schema redescription methodology, used to extract the canalizing core of automata network dynamics, thus simplifying the characterization of the dynamics of large models of natural networks. The canalizing core of a network provides a natural link from micro-level interactions to macro-level dynamics; it also allows us to identify essential control modules in the dynamics of biochemical networks. Our methodology is naturally applicable to the analysis of collective computation in other complex networks, though we focus on biochemical networks.
15:4016:00The priority-diffusion model: protocols to enhance the motion of low priority information Michael Maragakis (University of Thessaloniki, Greece) / Slides
Communication-like networks in real systems often have limited bandwidth between nodes. This enforces a maximum rate for the data to be transmitted over the links. An example can be a peer to peer network, like Skype, were video and audio data are transmitted along with text. In a limited bandwidth situation (network overload or broken main connection) we may be required to at least have the ability to write, while video is a luxury we can't afford. It is not uncommon though to desire image stills to be sent every few seconds.
We use the previously defined  priority diffusion model for the motion of two types of particles, A and B, which can represent any type of information. The diffusion of particles is based on either a random choice of site (node), or that of a randomly chosen particle out of both species. We define them respectively as "site" and "particle" protocols. In all cases, when both species coexist in the same space, the movement of A takes precedence over that of B. The model's main result , the miring of B particles in hubs, can be undesirable in certain cases. We present several variations of the model that allow for the low priority population to diffuse at a controllable, yet lower than that of A, rate. We suggest a protocol (moveA) where once a B particle is chosen to move, the movement is given to any coexisting A particle, if one exists. This results in the expulsion of A from hubs and provides the B with the opportunity to leave the hub. We achieve similar results by applying even the smallest probability for the B to move, even when an A is coexisting. This makes the average waiting time of B in hubs finite and inversely dependent on the probability applied (soft priorities). Finally, we suggest two additional variations where i) particles avoid to move through hubs and ii) we apply a limit in the particle capacity of each node.
 M. Maragakis, S. Carmi, D. ben Avraham, S. Havlin, and P. Argyrakis, Phys. Rev. E Rapid Communication, 77, 020103 (2008).
16:0016:20Maximal entropy random walk in community search methods Jeremi Kazimierz Ochab (Jagellonian University, Krakow, Poland) / Slides
A number of community search methods related to random walks (RW) will be reviewed with the attention paid to the comparison between two particular types of RW that may be utilised: generic random walk (GRW) and maximal-entropy random walk (MERW).
The commonest choice is the well-known GRW, defined by equal probabilities of going from a node to any of its nearest neighbours. In comparison, MERW ensures equiprobability of all paths of given length and endpoints.
Although for many problems GRW and biased RWs are often more suitable, MERW deserves particular interest: while GRW maximizes entropy locally (entropy of nearest neighbor selection), MERW lies on the other end of the spectrum of possibilities maximizing entropy globally (entropy of path selection). As a random walk can be thought of as an ensemble of possible paths, it is MERW that yields the largest entropy for that ensemble. In a sense, it is the most random of random walks.
While MERW exhibits localization of its stationary distribution [1,2,6], it seems to relax very fast within connected regions (proven for Cayley trees [3,7]), and it takes long time to relax between two identical connected regions , our intuition is that it might become trapped in communities and hence be able to find them more easily.
I will refer to methods that use: spectral decompositions of adjacency matrix and counting (weighted) paths, which belong rather to graph theoretical approaches, and calculating powers of the transitions matrix of a RW and its mean first-passage times, which belongs to the theory of Markov chains. It can be observed that MERW can formally unify those approaches. However, as it is a novelty in such applications, I assess its suitability for the known community search algorithms, and compare it on benchmark graphs  to the methods using other random walks.
 Z. Burda, J. Duda, J.M. Luck, and B. Waclaw, Phys. Rev. Lett. 102, 160602 (2009).
 Z. Burda, J. Duda, J.M. Luck, and B. Waclaw, Acta Phys. Pol. B 41, 949 (2010).
 J.K. Ochab, and Z. Burda, Phys. Rev. E 85, 021145 (2012).
 J.K.Ochab, arxiv: 1202.1160 (2012).
 A. Lancichinetti, S. Fortunato, F. Radicchi, Benchmark graphs for testing community detection algorithms, Phys. Rev. E 78, 046110 (2008).
 B. Waclaw, Generic Random Walk and Maximal Entropy Random Walk, Wolfram Demonstration Project.
 J.K. Ochab, Dynamics of Maximal Entropy Random Walk and Generic Random Walk on Cayley trees, Wolfram Demonstration Project.
16:2016:40Detection of dynamic communities in strongly evolving networks Rémy Cazabet (University of Toulouse, France) / Slides
Community detection is a well known problem in network analysis. Many solutions have been proposed to solve it in the last few years, handling problems such as hierarchical communities, overlap of nodes and scalability to very large networks. But very few work has been done on the detection of dynamic communities on evolving/temporal networks. I proposed a method which takes a sequence of modifications of a network (interval graph) as an input, and gives as a result a list of communities with their beginning date, ending date, and inclusion/removal of nodes during their lifetime. I applied this method on real world datasets (3 years of data on a Web 2.0 social network, 12 years' animal interaction network) with interesting results.
Saturday, June 9, 2012
9:00Bus departs to airport