Conference on Applications of Network Theory

Apr 7, 2011, 9:00 AM → Apr 9, 2011, 6:00 PM Europe/Stockholm

FD5

Petter Holme (Computational Biology), Petter Minnhagen (Umeå University)

Venue

AlbaNova University Center, hosted by Nordita, Stockholm, 7-9 April, 2011

Organizers

Peter Minnhagen and Petter Holme

List of invited speakers

• Lada Adamic, University of Michigan
• Albert-Laszlo Barabási, Northeastern University
• Jordi Bascompte, Consejo Superior de Investigaciones Cientificas
• Sebastian Bernhardsson, Niels Bohr Institute
• Vincent Blondel, University of Louvain
• Aaron Clauset, University of Colorado
• Sergey Dorogovtsev, University of Aveiro
• Birgitte Freiesleben de Blasio, University of Oslo
• Thilo Gross, MPI Dresden
• Kimmo Kaski, Aalto University
• Beom Jun Kim, Sungkyunkwan University
• Renaud Lambiotte, FUNDP
• Vito Latora, Catania University
• Sune Lehmann, Technical University of Denmark
• Fredrik Liljeros, Stockholm University
• Jukka-Pekka Onnela, Harvard University
• Juyong Park, Kyung-Hee University
• Veronica Ramenzoni, MPI Nijmegen
• Martin Rosvall, Umeå University
• Jari Saramäki, Aalto University
• Bo Söderberg, Lund University
• Brian Uzzi, Northwestern University
• Jevin West, University of Washington

This conference is part of the Nordita program Applications of network theory: from mechanisms to large-scale structure.

If you want to present a poster or give a talk you need to supply title and abstract upon registration.

Registration deadline: 15 March 2011 or when we have 70 participants registred.

Registration is over, the workshop is filled. We won't have a waiting list to replace cancellations. Interested local people are encouraged to interact with the surrounding Nordita program (see above). For other people we would like to advertise Netsci2013 with a partly the same organizers.

The program & abstracts can be downloaded here.

agenda conference_program_abstracts.pdf

Poster nwkconf2011.png

Thu, April 7

9:40 AM Registration / Coffee

10:10 AM Opening

Opening of the workshop + info.

1 Geography, Community and Privacy in Complex Networks

Many complex networks have their nodes distributed in space. In this talk, I will describe various recent results for spatially distributed networks. In particular, I will report results obtained from a community detection method on a large network constructed from communications between millions of mobile phone users at a country level. I will quantify in this network the decrease with distance of connection probability between mobile phone users and will describe a conjecture about a possible explanation for the observed decrease. If time permits, I will finally describe a surprising and unexplained connection between how people relocate in the US and the eigenvectors of a matrix constructed from the relocation network.

Speaker: Prof. Vincent Blondel (University of Louvain)

2 Path lengths, correlations, and spreading dynamics in temporal networks

In temporal networks, where nodes are connected through sequences of temporary events, information or resources can only flow through paths that follow their time-ordering. The properties of these temporal paths play a crucial role in dynamic processes: consider, e.g., simple SI spreading dynamics, whose speed is determined by the time it takes to complete such paths. I will discuss temporal path lengths and distances, their measurement, and their relationship to static graph distances. With the help of time-domain null models, one can also measure the effects of temporal correlations and heterogeneities, such as burstiness, on temporal distances and spreading processes. These effects may be very different: in human communication networks, temporal heterogeneities are seen to increase temporal distances and slow down spreading dynamics, whereas in an air transport network their effect is the opposite.

Speaker: Dr Jari Saramäki (Aalto University)

3 The Personality of Popular Facebook Users

Social science aims at understanding how large-scale behaviour emerges from the intrinsic properties of a large number of individuals and their pairwise interactions. Contrary to network connectivity, whose organization has been explored in email or mobile phone data, the psychological profile of large-scale populations has not been studied so far. In this work, we have analyzed data from a highly-popular Facebook application that is able to survey a very large number of Facebook users with peer-reviewed personality tests. Based on test results, we study the relationship between network importance (number of Facebook contacts) and personality traits, the first of its kind on a large number of subjects (400,000). We test to which extent two prevalent viewpoints hold. That is, sociometrically popular Facebook users (those with many social contacts) are the ones whose personality traits either predict many offline (real world) friends or predict propensity to maintain superficial relationships. We find that the strongest predictor for number of friends in the real world (Extraversion) is also the strongest predictor for number of Facebook contacts. We then verify a widely held conjecture that has been put forward by literary intellectuals and scientists alike but has not been tested: people who have many social contacts on Facebook are the ones who are able to adapt themselves to new forms of communication, present themselves in likable ways, and have propensity to maintain superficial relationships. We show that there is no statistical evidence to support such a conjecture.

Speaker: Dr Renaud Lambiotte (FUNDP)

12:20 PM Lunch & poster session

4 FunCoup: global protein networks by Bayesian integration

Interactomes computationally predicted via data integration are becoming an increasingly popular tool and context for biological research. However merging disparate data sources and presenting relevant parts of a global network is not trivial. FunCoup, an optimised Bayesian framework and a web resource, was developed to resolve these issues. FunCoup provides a number of uniqe features. (1) It annotates network edges with confidence scores in support of different kinds of interactions – physical interaction, protein complex member, metabolic or signalling link. (2) It supports selective usage of eight different types of evidence. (3) It provides on-line 'comparative interactomics' where a subnetwork in one species is aligned to an orthologous subnetwork in another species. FunCoup predictions were validated on independent cancer mutation data. The networks, which are the largest interactome reconstructions to date for nine eukaryotes, are freely available for download and query at http://FunCoup.sbc.su.se. In a recently published study, FunCoup was used to analyse cancer gene networks and to search for genes that are linked to known cancer genes in the network. This resulted in 1891 new candidates for cancer genes in total, 185 of which are linked to more than 10 known cancer genes. These genes are thus predicted to be central in processes associated with cancer, and an example of how network analysis can generate hypotheses relevant to medicine.

Speaker: Prof. Erik Sonnhammer (Stockholm University)

5 Structural correlations in bacterial metabolic networks

The metabolism of an organism makes up a very well defined network of reactions catalyzed by enzymes. These highly complex networks has presumably evolved from a simple primordial metabolism, from where they have diversified and specialized under the constraints of an underlying biochemistry. But how diverse are these networks? How much do they have in common, what can an ensemble of metabolic networks tell us about there common past, to what extent does a common core exist, and how does the underlying biochemical constraints influence the network evolution? We here address these questions by studying the overlap of the metabolic-reaction networks of 134 bacterial species. We introduce the concept of organism degree (OD), the number of organism in which the reaction is present. Network analysis shows that common reactions are found in the center of the network, and that the average OD decreases as we move to the periphery. Also, nodes of the same OD are more likely to be connected to each other compared to a random OD relabeling. Our results lend additional support to the importance of horizontal gene transfer during metabolic evolution, and suggest that the biochemical constraints can help both to diversify and narrow down metabolic evolution.

Speaker: Dr Sebastian Bernhardsson (Niels Bohr Institute)

6 Flavor network and the principles of food pairing

Animals, especially omnivores, feed selectively to fulfill energy needs and nutrient requirements, guided by chemical cues perceived as flavors. Among animals, humans exhibit the most diverse array of culinary practice. The diversity raises the question whether there are any general patterns of ingredient combination that transcend individual tastes and cuisines. We introduce a flavor network that captures the chemical similarity between culinary ingredients. Together with recipe datasets of various cuisines, the flavor network shows that Western cuisines have a tendency to use ingredient pairs that share many flavor compounds, supporting the food pairing hypothesis used in molecular gastronomy. By contrast, East Asian cuisines tend to avoid compound sharing ingredients.

Speaker: Dr Yong-Yeol Ahn (Northeastern University)

7 Blocs, multiplexity, and global economic crises

Persistent recurrence of global economic crises throughout economic history calls for understanding of their generic features. Given the ever highly interconnected nature of the global economic system, a network dynamics approach may provide some key insights toward this goal. In this talk, we discuss how the connectivity patterns of the global economic system would affect the spreading of crises from the perspective of collective network dynamics. Using a cascading-failure-type toy model, we show how the dynamics of crisis spreading is shaped by local and global connectivity profiles of the global economic network. We also discuss the perspective of multiplex network modeling and its implications to the assessment of systemic risk.

Speaker: Dr Kwang-Il Goh (Korea University)

3:50 PM Coffee break

8 Joint Coordinative Structures: Nested Processes of Intrapersonal and Interpersonal Coordination

In recent years, research in the field of social interactions has focused on the exploration of the coordinative structures that substantiate joint task performance. Coordinative structures or synergies refer to online the soft-assembly of neuromuscular elements that function as a collective unit. Synergies exploit neuromotor redundancies to provide multiple, equivalent motor solutions while also providing stability via reciprocal compensations for unwanted perturbations and fluctuations. It has been proposed that synergies can exist at the interpersonal scale as well as at the scale of an individual actor’ s neuromotor system. This project proposes a novel methodological approach for quantifying how synergies at the interpersonal and intrapersonal scales respond to changes in task constraints in the context of a joint performance. Principal component analysis (PCA) is used to identify relevant interpersonal and intrapersonal coordinative modes for the single and joint performance, and cross-recurrence quantification analysis (CRQA) was combined with PCA in order to quantify the degree and stability of interpersonal coordination across intrapersonal coordinative modes. The composition and number of coordinative modes varied for joint compared to single performance, and that interpersonal coordination across the first coordinative mode increased in degree and stability for joint compared to single performance. Overall, these findings indicate that joint coordinative structures are affected by the nature of the task performed and the constraints it places on joint and individual performance.

Speaker: Dr Verónica Ramenzoni (Max-Planck-Institute for the Psycholinguistics)

9 Network Formation among Future Business Elites

We use a dataset of email communication to document the formation of social relationships between students in a prestigious MBA program. First, we analyze how new relationships form day by day during students' time in the program. Our dataset starts before students' arrival on campus and it offers an unique opportunity to understand the inception of a social network. Second, we examine how students' social connections affect their financial donations to the school at the time of graduation. Especially, we highlight how clustering and network turnover influence students' integration in the MBA community and subsequently their donations.

Speaker: Dr Helena Buhr (Northwestern University)

10 Human sexual networks

Sexually transmitted infections continue to be a severe health problem. In this talk I will present and discuss a variety of explanations that have been advanced on why this type of disease is so hard to eradicate, despite the fact that the contact by which it is spread is far less frequent than is the case with most other infectious diseases. We conclude that several processes and mechanisms facilitate the spread of sexually infected diseases, and that both broad and targeted intervention is therefore needed to eradicate such diseases.

Speaker: Prof. Fredrik Liljeros (Stockholm University)

6:10 PM Conference dinner

Fri, April 8

11 The Trouble with Community Detection

Modular structures in complex networks can be extremely important for understanding the functional, dynamical, evolutionary and robustness properties of networks, and are widely believed to be ubiquitous in complex social, biological and technological networks. Most of the empirical evidence in support of the modular hypothesis, however, is indirect and derived from "community" or module detection algorithms. In general, however, these techniques do not yield unambiguous results and their objective performance in scientific contexts is not well understood. In this talk, I'll discuss some of the problems with the existing popular community detection frameworks and show that even in simple contexts they can produce highly counter-intuitive results. A consequence is that probably none of the existing claims of modular structure in, for example, biological networks should be trusted and there remains a great deal of work to be done to test the modular-organization hypothesis in such contexts. I'll conclude with some forward-looking thoughts about the general problem of identifying network modules from connectivity data alone, and the likelihood of circumventing these problems using, for instance, notions of functionality and robustness.

Speaker: Prof. Aaron Clauset (University of Colorado)

12 Hierarchical organization of large integrated systems

Ever since Aristotle, organization and classification have been cornerstones of science. In network science, categorization of nodes into modules with community-detection algorithms has proven indispensable to comprehending the structure of large integrated systems. But in real-world networks, the organization rarely is limited to two levels, and modular descriptions can only provide cross sections of much richer structures. For example, both biological and social systems are often characterized by hierarchical organization with submodules in modules over multiple scales. In many real-world networks, directed and weighted links represent the constraints that the structure of a network places on dynamical processes taking place on this network. Networks thus often represent literal or metaphorical flows: people surfing the web, passengers traveling between airports, ideas spreading between scientists, funds passing between banks, and so on. This flow through a system makes its components interdependent to varying extents. In my talk, I will present our information-theoretic approach to reveal the multiple levels of interdependences between the nodes of a network.

Speaker: Dr Martin Rosvall (Umeå University)

10:20 AM Coffee break

13 Community structure in densely connected networks

We know that communities in networks often overlap such that nodes simultaneously belong to several groups. Additionally, many networks are known to possess hierarchical organization, where communities are recursively grouped into a hierarchical structure. However, when each and every node belongs to more than one group, a single global hierarchy of nodes cannot capture the relationships between overlapping groups. Here we define communities as groups of links rather than nodes and show that this approach reconciles the ideas underlying overlapping communities and hierarchical organization. Link communities naturally incorporate overlap while revealing hierarchical organization. We discuss the proper validation of detected communities and show examples of relevant link communities in a number of networks, including major biological networks such as protein–protein interaction and metabolic networks, and show that a large social network contains hierarchically organized community structures spanning inner-city to regional scales while maintaining pervasive overlap.

Speaker: Dr Sune Lehmann (Technical University of Denmark)

14 From document delivery to document discovery: automated mapping of the network ecology of science at the article level

As Derek de Solla Price famously noted in 1965, the scientific literature forms a vast network. The nodes of this network are the millions of published articles, and they are linked to one another by citations and footnotes. This network grows dynamically and organically, doubling in size every ten to twenty years. It is within this growing network ecosystem that scholars conduct their research. But how does one find his or her way around a vast edifice in which new rooms, corridors, vestibules, and wings are continually added on an ever-expanding foundation? We propose that the revolution in digital scholarship provides the raw material, that when combined with intelligent algorithms, can resolve this problem. Our general approach is to infer a hierarchical map of science from citation data, and then label the structures on this map using an information-theoretic analysis of the full text of papers we are studying. We are currently scaling this technique to the full universe of scholarly publication, so that researchers may always be navigating with maps that are current not to years but to days.

Speaker: Dr Jevin West (University of Washington)

12:00 PM Lunch & poster session

15 Plant-Animal Mutualistic networks: the Architecture of Biodiversity

The mutualistic interactions between plants and the animals that pollinate them or disperse their seeds can form complex networks involving hundreds of species. These coevolutionary networks are highly heterogeneous, nested, and built upon weak and asymmetric links among species. Such general architectural patterns increase network robustness to random extinctions and maximize the number of coexisting species. Therefore, mutualistic networks can be viewed as the architecture of biodiversity. However, because pylogenetically similar species tend to play similar roles in the network, extinction events trigger non-random coextinction cascades. This implies that taxonomic diversity is lost faster than expected if there was no relationship between phylogeny and network structure. I will conclude by exploring the trade-offs between a species’ relative contribution to the above patterns of network architecture, and its own survival probability.

Speaker: Prof. Jordi Bascompte (Estación Biológica de Doñana, CSIC)

16 Archetypical micro-configurations of social-ecological systems: a bottom-up network approach in studying complex social-ecological systems

Abstract: When conceptualizing integrated social-ecological systems (SES), the modeling approaches commonly applied are often (a) based in ecology with social aspects added afterwards, or (b) based in social science with aspects of the natural environment added afterwards. So far there are few integrated conceptual modeling approaches that, from start, fully embrace the complex linkages that exists between societies and nature. We argue that this is needed to advance the understanding of SES. Also, given the complexity of SES, there is a need for conceptual modeling approaches that can simplify while still retaining the essential characteristics of a complex SES. As a response to this challenge, the generic systems perspective of network analysis has been suggested as a way to better capture, and make explicit, the inevitable and complex interrelation that exist between the natural and social subsystems. In such a model, all different social and ecological entities making up a SES are modeled as a set of interdependent nodes in a social-ecological network. Since neither the social nor the ecological parts are given any precedence in such model, new and novel transdisciplinary approaches seems feasible. Although an interesting and promising overall suggestion, it is however not entirely clear how such approach could, in detail, be applied in researching SES. In this work we contribute to such development by conceptualizing SES as a set of different network-based archetypical SES configurations each retains some important and irreducible characteristics of a complex SES. These micro-configurations (motifs) are constructed following the general assumption that any non-trivial SES must consist of multiple actors and multiple natural resources that all are interconnected in different ways. From a bottom-up perspective, a minimal set of social and ecological entities representing any non-trivial SES would consist of two social actors and two ecological resources; i.e. a four-node representation of a social-ecological network. Such a set of two plus two social and ecological nodes can be interconnected in a finite number of ways, and each specific pattern of interconnecting links among the four nodes correspond to a specific SES motif. We further characterize each motif, based on its pattern of links, using four key variables: social connectivity, ecological connectivity, substitutability, and competition/exclusion. Based on these variables and their interaction, and by drawing from insights from SES research, we then describe each motif in terms of its main challenges and opportunities for natural resource governance. Using this approach, it is possible to decompose any larger SES represented as a social-ecological network into these basic building blocks. A statistical analysis can then be applied to investigate if and to what extent the different motifs appear in the larger SES. This exercise can potentially inform on the main challenges and opportunities that prevail in the larger SES, and in using a multi-case study approach possible interaction effects among the different motifs can be investigated. We illustrate this using a case study from Madagascar. We finally show one way to further elaborate into the characterization of the motifs using controlled experiments in lab.

Speaker: Dr Örjan Bodin (Stockholm University)

17 Identifying diseases of unknown origin using network theory

Community structure is a ubiquitous feature of complex networks, and methods for its detection has gained much attention in recent years. Beyond the study social networks with well defined links, these methods can be generalised to operate on any dataset in which different entities are similar in one or more traits, and be used to identify meaningful groupings. Here, we describe the application of network theory and methods for finding community structure to identify undiagnosed disease outbreaks reported in online surveillance systems. The efficacy of these programs is often inhibited by the anecdotal nature of informal or rumour-based reporting, and uncertainty of pathogen identity. We create associations between disease outbreaks and and their symptoms, case fatality ratio, and seasonality, and represent them in an abstract network. We train the model with a set of outbreaks reports of 10 known infectious diseases causing encephalitis and combine methods for community detection with an optimisation procedure for symptom weights to generate networks of maximal modularity. We then use these to determine a most probable identification for 97 outbreaks of encephalitis reported in an online surveillance system as undiagnosed or ‘mystery illness’, by determining the best association with communities in the reference networks. This illustrates the general use of methods from network analysis for the study of datasets even where links are not obvious physical entities but mere measures of similarity.

Speaker: Dr Sebastian Funk (Institute of Zoology)

18 Linear and Optimization Hamiltonians in Random Graph Modeling

Exponential random graph theory is the complex network analog of the canonical ensemble theory from statistical physics. While it has been particularly successful in modeling networks with specified degree distributions, a naïve model of a clustered network using a graph Hamiltonian linear in the number of triangles has been shown to undergo an abrupt transition into an unrealistic phase of extreme clustering via triangle condensation. Here we study a non-linear graph Hamiltonian that explicitly forbids such a condensation and show numerically that it generates an equilibrium phase with specified intermediate clustering. We also discuss some applications based on Hamiltonian-based graph theory.

Speaker: Dr Juyong Park (Kyung Hee University)

3:50 PM Coffee break

19 Co-evolution of network structure and content

Network time series can be used to track and predict the co-evolution of structure across different networks, and between a network's structure and its communicated content. We formulate a measure, temporal conductance, that captures how unexpected a particular network is given its past evolution. We find that structure in one network can not only correlate with the concurrent structure in another network over the same nodes, but can also help predict how the second network will evolve. We also find that the entropy of what is being communicated is captured and can be predicted by the shape of the communication network. Smaller, denser networks, with less reciprocity and clustering correspond to more uniform information content, while diminished temporal conductance is indicative of greater change in communicated content.

Speaker: Prof. Lada Adamic (University of Michigan)

20 Simulation of opinion formation driven communities in coevolving social networks

Here we model the dynamics of opinion formation in human societies by a co-evolution process involving two distinct time scales of fast transaction and slower network evolution dynamics. In the transaction dynamics we take into account short-range interactions as discussions between individuals and long-range interactions to describe the attitude to the overall mood of society. The latter is handled by a uniformly distributed parameter, assigned randomly to each individual, as quenched personal bias. The network evolution dynamics is realized by rewiring the societal network due to state variable changes as a result of transaction dynamics. The main consequence of this complex dynamics is that communities emerge in the social network for a range of values in the ratio between time scales. In this paper we focus our attention on the attitude parameter $\alpha$ and its influence on the conformation of opinion and the size of the resulting communities. We present numerical studies and extract interesting features of the model that can be interpreted in terms of social behaviour.

Speaker: Prof. Kimmo Kaski (Aalto University)

21 Controllability of Complex Networks

The ultimate proof of our understanding of natural or technological systems is reflected in our ability to control them. While control theory offers mathematical tools to steer engineered and natural systems towards a desired state, we lack a framework to control complex self-organized systems. Here we develop analytical tools to study the controllability of an arbitrary complex directed network, identifying the set of driver nodes whose time-dependent control can guide the system’s entire dynamics. We apply these tools to several real networks, finding that the number of driver nodes is determined mainly by the network’s degree distribution. We show that sparse inhomogeneous networks, which emerge in many real complex systems, are the most difficult to control, but dense and homogeneous networks can be controlled via a few driver nodes. Counterintuitively, we find that in both model and real systems the driver nodes tend to avoid the hubs.

Speaker: Prof. Albert-László Barabási (Northeastern University)

Sat, April 9

22 Fairness and coordination in self-organized collaboration networks

We study the self-assembly of a complex network of collaborations among self-interested agents. The agents can maintain different levels of cooperation with different partners. Further, they continuously, selectively, and independently adapt the amount of resources allocated to each of their collaborations in order to maximize the obtained payoff. We show analytically that the system approaches a state in which the agents make identical investments, and links produce identical benefits. Despite this high degree of social coordination some agents manage to secure privileged topological positions in the network enabling them to extract high payoffs. Our analytical investigations provide a rationale for the emergence of unidirectional nonreciprocal collaborations and different responses to the withdrawal of a partner from an interaction that have been reported in the psychological literature.

Speaker: Dr Thilo Gross (Max-Planck-Institute for the Physics of complex systems)

23 Solution of the explosive percolation quest

Until recently, the percolation phase transitions were believed to be continuous, however, in 2009, a remarkably different, discontinuous phase transition was reported in a new so-called "explosive percolation" problem. Each new link in this problem is established by a specific optimization process. We develop the exact theory of this phenomenon and explain its nature. Applying strict analytical arguments to a wide representative class of models for the infinite system size limit, we show that the "explosive percolation" transition is actually continuous though with an uniquely small critical exponent of the percolation cluster size. These transitions provide a new class of critical phenomena in irreversible systems and processes. We obtain a complete description of the scaling properties of these second order transitions. For all these models, we find the scaling functions and the full set of critical exponents, and, also, the upper critical dimensions which turn out to be remarkably low, close to 2.

Speaker: Prof. Sergey Dorogovtsev (University of Aveiro)

10:20 AM Coffee break

24 Networks of motifs from sequences of symbols

There are many examples in biology, in linguistics and in the theory of dynamical systems, where information resides and has to be extracted from corpora of raw data consisting in sequences of symbols. For instance, a written text in English or in another language is a collection of sentences, each sentence being a sequence of the letters from a given alphabet. Not all sequences of letters are possible, since the sentences are organized on a lexicon of a certain number of words. In addition to this, different words are used together in a structured and conventional way. Similarly, in biology, DNA nucleotides or aminoacidic sequence data can be seen as corpora of strings. Many results have shown proteins are far from being a random assembly of peptides and DNA sequences show non-trivial statistical properties. All this gives meaning to the metaphor of DNA and protein sequences regarded as texts written in a still unknown language. Sequences of symbols can also be found in time series generated by dynamical systems. In fact, a trajectory in the phase space can be transformed into sequence of symbols, by the so-called “symbolic dynamic” approach. In all the examples mentioned above, the main challenge is to decipher the message contained in the corpora of data sequences, and to infer the underlying rules that govern their production. We propose a general method to construct networks out of any symbolic sequential data. The method is based on two different steps: first it extracts in a “natural” way motifs, i.e. those recurrent short strings which play the same role words do in language; then it represents correlations of motifs within sequences as a network. Important information from the original data are embedded in such a network and can be easily retrieved as we will show through diverse applications to social dialogs, biological examples and dynamical systems. With the respect to previous linguistic methods, our approach does not need the a priori knowledge of a given dictionary. All this, makes the method very general and opens up a wide range of applications from the study of written text, to the analysis of different trajectories in dynamical systems.

Speaker: Roberta Sinatra (University of Catania)

25 Controlling centrality in weighted complex networks

Many centrality measures have been proposed in the last decade to assess the relative importance of vertices in a complex network and to identify the role played by each node in the network. Finding important nodes is useful to estimate the potential damage that can be inflicted to the structure of a network by removing particular nodes. In this letter we show that it is always possible to set a given eigenvector centrality for all the nodes in a weighted network by tuning the weights of a very small subset of nodes, called controlling set. We introduce a measure of controllability for weighted networks based on the size of the minimal controlling set, and propose two greedy algorithms which are able to find sufficiently small controlling sets. Experimental results reveal that even large real networks have very small controlling sets, and are therefore vulnerable to focused changes of edge weights which can modify the eigenvector centrality of any node.

Speaker: Dr Vincenzo Nicosia

26 Kuramoto model on interdependent networks

We explore the synchronization behavior in the interdependent system, where the 1D network is ferromagnetically intercoupled to the Watts-Strogatz (WS) small-world network. In the absence of the internetwork coupling, the former network is well known not to exhibit the synchronized phase at any finite coupling strength, whereas the latter displays the mean-field transition. Through an analytic approach based on the mean-field approximation, it is found that for the weakly coupled and thus nonsynchronized 1D network becomes a heavier burden for the synchronization process of the WS network. As the intracoupling in the 1D network becomes stronger, the more enhanced partial synchronization in the 1D network makes the burden lighter. Extensive numerical simulations confirm these expected behaviors, while exhibiting a reentrant behavior in the intermediate range of coupling strength. The nonmonotonic change of the critical value of JII is also compared with the result from the numerical renormalization group calculation.

Speaker: Prof. Beom Jun Kim (Sungkyunkwan University)

12:20 PM Lunch & poster session

27 Information Sharing for Mobile Phone Users in Sensing Field

With the popularity and advancements of smart phones, mobile users can interact with the sensing facilities and exchange information with other wireless devices in the environment by short range communications. Opportunistic exchange has recently been suggested in similar contexts; yet we show strong evidence that, in our application, opportunistic exchange would lead to insufficient data availability and extremely high communication overheads due to inadequate or excessive human contacts in the environment. In this paper, we present "OppSense", a novel design to provide efficient opportunistic information exchange for mobile phone users in sensing field with data repositories that tackles the fundamental availability and overhead issues. Our design differs from conventional opportunistic information exchange in that it can provide mobile phone users guaranteed opportunities for information exchange regardless the number of users and contacts in different environments. Through both analysis and simulations, we show that the deployment of data repositories plays a key role in the overall system optimization. We demonstrate that the placement of data repositories is equivalent to a connected K-coverage problem, and an elegant heuristic solution considering the mobility of users exists. We evaluate our proposed framework and algorithm with real mobile traces. Extensive simulations demonstrate that data repositories can effectively enhance the data availability up to 41% in low contact environment and significantly reduce the communication overheads to only 28% compared to opportunistic information exchange in high contact environment.

Speaker: Dr Edith Ngai (Uppsala University)

28 Random Feynman graphs

Certain classes of random graphs can be derived as the Feynman graphs for simple quantum theories, with a statistical weight for each graph being given by the value of the corresponding Feynman graph. Such models of random graphs are closely related to a previously considered random graph model, known as CDRG, or Colored Degree-driven Random Graphs, where vertices are randomly equipped with a number of colored stubs, to be randomly paired with color-dependent preferences.

Speaker: Dr Bo Söderberg (Lund University)

29 Plain, biased and interacting random walkers on complex nets

Random walks are the simplest way to explore a graph. In this talk we will discuss some of the properties of random walks (such as equilibrium distributions, entropy rates, and mean first-passage times) which might have relevant applications to study traffic fluctuations in the Internet, to design optimal diffusion processes on correlated or uncorrelated networks, or to achieve the best synchronization in a system of Kuramoto oscillators moving on a graph. In particular, we will consider degree-biased random walks with a jumping probability depending on some power of the degree of the target node. Based on whether the exponent is positive or negative, this can give rise to walks that favor or disfavor high-degree vertices. Finally, we will discuss a model of interacting random walkers which compete for the nodes of a complex network. The complementary roles of competition and motion produce a variety of fixed points, whose stability depends mostly on the structure of the underlying network. The model can be useful to simulate processes which usually take place on complex topologies and are characterized by strong competition among orthogonal species, such as diffusion of consumer products, competition of biotypes, and selections of languages.

Speaker: Prof. Vito Latora (University of Catania)

3:30 PM Closing