Applications of Network Theory: From Mechanisms to Large-Scale Structure

Mar 28, 2011, 8:00 AM → Apr 20, 2011, 6:00 PM Europe/Stockholm

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

The main idea is to convene key world-class researchers on complex networks and let them interact freely with the Nordic groups interested in the area. The program will be divided into four thematic areas: biological networks, general network theory, technological networks, and social networks. Many of the intended participants are interested in several of these points. Much progress in network theory has been made by analogies from different fields, and complex-network researchers value this, therefore we believe such a schedule will not seem unattractive to participants. In addition to the regular schedule during the Nordita program, of one or two talks per day, we will arrange a more intense, three day workshop April 7-9. One purpose of this workshop, is to attract researchers not able to stay the extended time required by the program.

Monday, March 28

1:20 PM Opening and orientation

1 Respondent-driven Sampling on Directed Networks

Respondent-driven sampling (RDS) circumvents the difficulties in sampling hard-to-reach population by using their social networks. It has been shown that the RDS is an effective method for generating handful sample. What’s more, under certain assumptions, unbiased estimates for population traits can be generated by weighting the sample with respondents’ personal network sizes. For these advantages the RDS has been widely used in HIV-related studies among high risk populations in recent years. However, despite the quite acknowledged evidences that most social networks are directed, all existing RDS estimators are based on assumption that the social relationships between respondents are reciprocal and consequently the RDS recruitment process happens on undirected networks. To investigate the potential bias brought by network directedness, and further generalize the RDS method, we propose several estimators that work both on directed networks and undirected networks. Performances of estimators are compared by RDS simulations on networks with different degrees of directedness, assortativity, indegree-outdegree correlation and homophily. Results reveal that the most robust estimator is the one which assumes the amount of individuals with trait A in the sample is proportional to the total indegree for individuals of group A in the population. A sensitivity test method is proposed when the sample indegree is not known. Given the widely existence of irreciprocal relationships among social society, we suggest the new estimator to be used in future RDS studies.

Speaker: Xin Lü (Karolinska Institute)

Tuesday, March 29

9:00 AM Breakfast at Nordita

2 Structural difference between public and private communication in an online community

We investigate an online community where there are two modes of communication. Either a user can reply to others in a public forum in such a way that we see who comments on whom; or they can send e-mail-like direct messages. In this data we investigate network structures (such as degree-distributions and assortativity), temporal structures such as response-, interevent times and activity levels. Furthermore, we measure combined structures from the different communication channels relating to structural-balance theory. Among other things, we find that in private communication, people keep feeling obliged to reply longer than in public discussions. We also observe a weak anti-correlation between activity levels in public and private communication respectively, suggesting that different personality types drive the large-scale structural evolution. We relate our findings to theories of social organization and human dynamics.

Speaker: Ms Fariba Karimi (IceLab, Umeå University)

3 Network aspects of chromosome interactomes

DNA is folded into increasingly complex yet highly mobile structures to organize the chromosomes. In this talk I will describe work with Rolf Ohlsson’s lab at KI where we have tried to quantify whether chromosome-chromosome interactions are random or not, and (if it is not) can we say something about the network structure of such interactions. The key experimental technique is high throughput sequencing of both read (short segements) known to interact with a known bait sequence, as well as chimeric reads containing pieces from different locations, in addition to the bait.

Speaker: Prof. Erik Aurell (KTH)

Wednesday, March 30

4 Metabolic networks, information, a null model and evolution

A simple general null-model, the Ikea network, is described and its properties are investigated. This network is argued to be the appropriate network for a random assembling of links, such that both which link is attached to which and the time-order are all distinct random possibilities. From this point of view it is the opposite of preferential attachment. This network is discussed in the context of metabolic networks, where the metabolism of an organism is reduced to a network of substances. The striking agreement between the Ikea network and the metabolic networks implies that the null model catches the overall features. Using the network structure measures clustering and assortativity, a small difference is nevertheless identified and is argued to imply a possible evolutionary pressure. This difference is manifested in a slight difference in the degree distribution.

Speaker: Prof. Petter Minnhagen (Umeå University)

5 Why do metabolic networks look like they do? The last decade and the next

This year is the 10th anniversary of the discovery that metabolic networks are scale-free. I will make a brief review of this decade of research relating network topology and function in metabolic reaction systems with a focus on our contributions. I discuss the hypothesis that network clusters correspond to functional modules. Metabolic network, however represented, are not as distinctly modular as the cartoon picture of intricately wired subsystems with few I/O-terminals. Does this reflect a trade-off between functionality and robustness, or is it an inevitable consequence of non-enzymatic reaction kinetics, or something else? I also discuss optimal levels of representations—if one uses a multiplex, directed, and perhaps bipartite, representation one can encode more information, but standard methods are harder to apply. If one goes for a simple-graph representation with vertices connected by undirected edges, then how can one encode as much functional information as possible? I will also mention how one can use other types of reaction systems, like reactions in planetary atmospheres, as null-models of metabolic networks. Finally I look forward and discuss open questions within reach with current and future data sets.

Speaker: Dr Petter Holme (Coputational Biology)

Thursday, March 31

6 Detecting community structures in uncertain networks using ensemble clustering

During recent years many different methods to detect community structures in complex networks have been developed. Despite significant efforts from many different scientists from different fields, no completely satisfactory method to detect communities has been developed. In this talk, we present a method to merge the results from several different community detections run into a single final estimated community structure. Each run can either use a different method or else an ensemble of results from the same algorithm an be merged. We propose three different methods for the merge. Two of these are related to ensemble clustering methods used in standard data clustering problems. We apply these three methods on some different problems to demonstrate their usefulness. Some existing methods are stochastic in nature and generate different results for each run. Using the merging methods, one can use the collective information from the entire ensemble of possible community structures to find the most likely structure. This is shown to improve the performance of some stochastic algorithms. Another problem is related to the problem of uncertain Social Networks. In these networks, edges are not known with certainty to exist. Instead, a probability (or probability interval) is given for their existence. Using methods from statistical simulation, one can create an ensemble of networks that are consistent with the uncertain network. Applying existing methods for detecting community structures on each network from the ensemble creates a large number of different candidate community structures (one for each realization of the uncertain network). Applying the merging methods presented in this talk, one can merge (fuse) these different candidate structures into one, thus finding the community structure of the uncertain network.

Speaker: Mr Johan Dahlin (Swedish Defense Research Agency)

Friday, April 1

7 Some results on hierarchical structures

Hierarchical structures have been considered as a way to study networks in a regular fashion. Our interest is especially in those obtained by tiling a hyperbolic plane, and we introduce numerical and analytical results about critical phenomena on these structures. We also show that the results can be extended to study phase transitions on the two-dimensional plane as well, including the percolation phenomena and the critical Potts model.

Speaker: Dr Seung Ki Baek

8 Exploring spatial networks with greedy navigators

During the last decade, network research has focused on the global structural properties. Fewer studies take the local perspective of agents traveling the network. In this talk I will present a method that uses such a local perspective to integrate topological and spatial properties. This approach, we argue, will be even more important in this era of GPS-equipped smartphones, which give users ability to access local geometric information and navigate efficiently. We use a simple greedy spatial navigation strategy as a probe to explore spatial networks. These greedy navigators use geometric information to guide their moves and have a memory of their route in the network. We apply our method to several real-world networks of roads and railways. The results suggest that centrality measures have to be modified to incorporate the navigators’ behavior. We also see that removing some edges may actually enhance the routing efficiency, which is reminiscent of Braess’s paradox (caused by the conflict between user- and global optima). Furthermore, we present the reverse problem of optimizing the spatial layout of networks themselves to enhance the performance of the greedy spatial navigation. We relate these results, to the positioning of facilities and even architectural design to facilitate the behavior of humans.

Speaker: Dr Sang Hoon Lee (IceLab, Umeå University)

Monday, April 4

9 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 timeordering. 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: Jari Saramäki (Aalto University)

Tuesday, April 5

9:00 AM Breakfast at Nordita

10 Null and true models in weighted and time-dependent networks

Anomalous structures in networks are crucial for understanding the function and the organization of complex systems. The problem is related to computing the probability of finding such structures on a proper null model. Although it is quite natural to choose as a candidate the configuration model in the case of unweighted networks, it is less trivial how to define good null models for weighted and time-dependent networks. We discuss the problem, its connections with studies on backbones of weighted networks, and some implications on how to make null models more similar to true models of real systems.

Speaker: Andrea Lancichinetti (ISI)

11 Zipf's law unzipped

The outcome of a random process is often well described by a bell-shaped curve, the normal distribution. Some hundred years ago, it was noticed that things like the richness among people, town sizes, surnames, and the frequency of words have different broader distributions. Many, more or less system-specific, proposals for the deviation from normal have been suggested under names like "rich gets richer", "principle of least effort", "preferential attachment", and "independent proportional growth". Here, it is argued that the phenomenon is connected to a more ubiquitous random group formation. A group is like a soccer team with positions to fill. You want the right player in the right position. Thus, unlike for the normal distribution where you pick a player for the team, you now try to pick a player for a position in the team. Information theory is used to find the most likely distribution of group sizes given the number of objects, groups and the number of objects in the largest group. The agreement between data and predictions speaks for itself. We suggest that this gives a new starting point for the understanding of Zipf-type phenomena and fat-tailed distributions in general.

Speaker: Prof. Petter Minnhagen (Umeå University)

Wednesday, April 6

12 Synchronization on fully connected graph with periodically switching edges

We investigate synchronization of the Kuramoto oscillators with dynamic interaction patterns. The oscillators are fully connected and each edge is periodically switched with different phase. Through this model, we try to understand how dynamic interaction patterns change synchronization phenomena. Measuring phase order parameter, we found the model shows interesting temporal response to dynamic interaction patterns. In particular, the temporal structure of phase order parameter has asymmetric sync-desync behavior for strong coupling and fast switching.

Speaker: Dr Sungmin Lee (IceLab, Umeå University)

13 Overlapping communities in networks from the flow perspective of the map equation

Infomap clusters networks using the correspondence between compression, regularity detection and learning expressed in the minimum description length principle. Here we extend that approach to find partitions with overlaps, considering flow on the nodes near the boundary of modules. Specifically, we analyze how affects the modular structure the return proportion of flow on those nodes, versus the proportion going to different modules. We show that the return proportion characteristic can be better captured -- in terms of average bit-length per step -- by allowing nodes to belong to several modules, effectively making the modules to overlap. This work introduces both the updated framework and a fast greedy algorithm that finds the module overlappings. Also, we present the outcomes of our new method when processing several real world networks and in the context of a benchmark procedure. For the later one, we devised a way of calculating the mutual information between two partitions that deals with overlaps consistently.

Speaker: Alcides Viamontes Esquivel (IceLab, Umeå University)

14 Significant communities in large sparse networks

Researchers use community-detection algorithms to reveal large-scale organization in biological and social systems modeled by networks. But this community detection approach is useful only if the communities are significant and not a result of noisy data. To assess the statistical significance of the detected structure, the robustness of the network communities, one approach is to perturb the network structure and measure how much the communities change. However, perturbing sparse networks is challenging because they are inherently sensitive; the networks easily shatter if we perturb the networks by removing links. Here we propose a method to perturb sparse networks and assess the significance of their communities. In our approach, we first resample the network by adding extra links based on local information and then we aggregate the information from multiple re-sampled networks to find a coarse-grained description of significant clusters. We test our method both on benchmark and real-world networks, and find good performance on inherently sensitive sparse networks.

Speaker: Atieh Mirshahvalad (IceLab, Umeå University)

Thursday, April 7

9:45 AM Applications of Network Theory – The Conference (Day 1)

Friday, April 8

9:00 AM Applications of Network Theory – The Conference (Day 2)

Saturday, April 9

9:00 AM Applications of Network Theory – The Conference (Day 3)

Monday, April 11

15 Beyond Space For Spatial Networks

Many complex systems are organized in the form of a network embedded in space. Important examples include the physical Internet infrastucture, road networks, flight connections, brain functional networks and social networks. The effect of space on network topology has recently come under the spotlight because of the emergence of pervasive technologies based on geo-localization, which constantly fill databases with people's movements and thus reveal their trajectories and spatial behaviour. Extracting patterns andregularities from the resulting massive amount of human mobility data requires the development of appropriate tools for uncovering information in spatially-embedded networks. In contrast with most works that tend to apply standard network metrics to any type of network, we argue in this paper for a careful treatment of the constraints imposed by space on network topology. In particular, we focus on the problem of community detection and propose a modularity function adapted to spatial networks. We show that it is possible to factor out the effect of space in order to reveal more clearly hidden structural similarities between the nodes. Methods are tested on a large mobile phone network and computer-generated benchmarks where the effect of space has been incorporated.

Speaker: Dr Renaud Lambiotte (FUNDP)

16 Time irreversibility of quantum diffusion in complex networks

We study time-reversal dynamics of quantum diffusion in the Watts-Strogatz small-world networks at the rewiring probability $p$. We start from the localized wave packet, and integrate the time-dependent Schr\"odinger equation. At time $T$ a perturbation to the wave packet is made and then the system evolves backward in time until $t=2T$ is reached. We calculate the mean square displacement $\sigma(t; \eta)$ of the wave packet as a function of time $t$ at different perturbation strength $\eta$. The time irreversibility is quantitatively measured by $\sigma(2T; \eta) - \sigma(2T; 0)$, which reveals that the irreversibility linearly increases with $\eta$ in the weakly perturbed regime. The results from the WS networks and the regular network are compared.

Speaker: Prof. Beom Jun Kim (Sungkyunkwan University)

Tuesday, April 12

17 Social Coordinative Structures; scope and limitations of current methodological approaches in the study of coordinative processes

During joint tasks, when two or more people interact to accomplish a shared goal, actors coordinate their cognitive processes along with their motor outputs online in order to achieve a shared goal. Spatial-temporal coordination of behavior (e.g., eye movements, postural sway, or limb movements) depends to a large extent on the perceptual-motor systems ability to adapt to changing constraints while supporting joint actions. Soft-assembly of synergies across individuals (interpersonal) and within each individual (intrapersonal) is a common strategy for coping with changes in constraints that can span scales. Synergies at the intrapersonal and interpersonal scales are not independent from one another, but establish rather a system of nested relations in which adjustments in the synergies at the intrapersonal level help support and maintain coordination at the interpersonal level. In spite of the plethora of studies on the emergence and soft assembly of coordinative structures, evidence so far has mainly pointed at how changes in external and internal constraints impact them globally (i.e., changes in overall stability). This talk will introduce the problems of how to better identify and characterize coordinative structures, the changes local relations within structures undergo in response to constraints, and how they impact the efficiency of coordinative relations globally. The advantages and limitations of well-established and newer methodologies for confronting the problem will be discussed. The goal of the talk is to promote discussion on the potential contribution of computational network theory to the study of social coordination.

Speaker: Dr Veronica Ramenzoni (Max Planck Institute for Psycholinguistics)

Wednesday, April 13

18 Markov Chains as models of human mobility, and possible applications

How far into the past do we need to know of a person's whereabouts to describe where they go next?

Speaker: Dr Juyong Park (Kyung Hee University)

Thursday, April 14

19 SAME OR DIFFERENT? Relations between apparently different graph models

Apparently different (sparse) graph models can lead to identical behaviour. An example is given by the Poissonian mix subclass of the Configuration Model and the rank one subclass of Inhomogeneous Random Graphs. Similar relations can be found between unrestricted versions of these models and a sparse model superclass, which can be viewed as a configuration model with hidden variables.

Speaker: Bo Söderberg (Lund University)

20 The physical embedding of ideas in science

Which came first, the disciplines or the departments? Science is a dynamic, organized, and massively parallel human endeavor to discover, explain, and predict the nature of the physical world. In science, researchers build new ideas upon old ideas as ideas flow from researcher to researcher. Since the pattern of interactions between scientists affects this flow, networks affect the constant change scientific research undergoes as fields grow and shrink, merge and split, and ultimately change the architecture of universities. Or is it the other way around?

Speaker: Dr Martin Rosvall (IceLab, Umeå University)

Friday, April 15

21 The role of interacting network structure

Recently, we've seen increased interest in studying systems of interacting networks. We are now beginning to see many networks not as isolated objects, but as one component in a much larger system. For instance, modern critical infrastructure spans assorted electric grids, telecom and computer networks, and transportation networks. Likewise, in biological systems, genes do not trigger one-another directly; instead, activated genes make proteins, which may return to the genetic level and activate or inhibit other genes. Individual networks are increasingly interdependent and previously neglected or "hidden" inter-network connections can significantly impact our understanding of network structure. In this talk I will present both an overview of the current studies of interacting networks and my own recent work concerning the emergence of connectivity in systems of interacting networks.

Speaker: Dr Elizabeth Leicht (Oxford University)

22 Costs and constraints from time-delayed feedback in small gene regulatory motifs

Speaker: Dr Andreas Grönlund (Uppsala University)

Monday, April 18

23 Locally self-organized quasi-critical percolation in multiple disease model

Diseases emerge, persist and vanish in an ongoing battle for available hosts. Hosts, on the other hand, defend themselves through development of immunity that limits the ability of the pathogens to reinfect old hosts. I will here explore a multi disease system with emphasis on mutual exclusion. I demonstrate that such a system develops towards a steady state, where spreading of individual diseases self-organizes to a state close to that of critical percolation, without any separation of time scale or global control mechanism. For a broad range of introduction rates of new diseases, the likelihood of transmitting diseases remains nearly constant.

Speaker: Jeppe Søgaard Juul (CMOL, Niels Bohr Institute)

24 Laplacian-based centrality in directed networks

The PageRank is a dominant centrality measure for directed networks. I would like to discuss the utility of an alternative centrality measure based on the graph Laplacian. The Laplacian-based centrality value for a node is in fact equal to the probability that a new type introduced at the node takes over the entire population in the voter dynamics. In addition, the Laplacian-based centrality captures importance of nodes in various other dynamics on networks including random walk and synchronization. I also explain its behavior in networks with community structure, its algebraic characterization, and the relationship to the Pagerank. Any applications?

Speaker: Prof. Naoki Masuda (University of Tokyo)

Tuesday, April 19

25 Social media reveal complex human communication patterns

Social media have become essential channels for the exchange of ideas on a global scale. Using real-time data from Twitter, we identify fundamental human communication patterns. We use methods based on networks to gauge the spread of ideas and analyze the collective behavior in massive social organizations. We show that correlations in the content of user communication follow a universal scale free distribution. The correlations indicate a self-organizing dynamics in large social organizations where the exchange of information between individuals is highly volatile. Further perspectives are presented in the form of communication data from a university environment.

Speaker: Dr Mathiesen Joachim (Niels Bohr Institute)

26 Design robust network: how and why?

In a recent PNAS paper (PNAS.108.3838: Mitigation of malicious attach on network), Schneider et.al. introduced a new measure for robustness of network to malicious attacks, $R=1/N\sum_{q=1}^N s(q)$, where $N$ is the number of nodes in the network and s(q) is the fraction of nodes in the largest connected cluster after removing q nodes with highest degree. In terms of the measurement R, the authors proposed a way to improve the robustness of a network: continuously swap the connections of two randomly chosen edges to increase R until no further improvement is achieved. It has been found that such manipulations are efficient in improving the performance of the European electricity system and the Internet as well as complex networks models against malicious attacks. Particularly, in the case of scale-free networks, a unique onion-like topology characterizing robust networks is revealed. However, we note that only connectivity links are considered when disintegrating the network (a node fails only when it, or the cluster it is in, becomes completely disconnected from the network). Nonetheless, dependency links are more relevant for real transmission systems, such as the power grids and Internet traffic. That is, the nodes in the networks are interdependent, and the failure of one node may cause his direct neighbors to become also failure (with some probability). Here we make comparative studies by investigating cascading process on scale-free networks generated by uncorrelated configuration model and the optimal surrogates in terms of Schneider et.al. Our preliminary simulations suggest that in the context of cascading dynamics the onion-like topology may be rather fragile to both random failures and intentional attacks as compared to the original networks. As such, caution should be taken into account in designing real infrastructures by using the method presented in the PNAS paper, and an open question therefore arises: how to design a robust network in which the nodes are interdependent?

Speaker: Prof. Zhi-Xi Wu (Lanzhou University)

Wednesday, April 20

27 Simulation of disease dynamics co-evolving with network structure

The structural patterns of sexual contacts are believed to shape the spreading dynamics of Sexually Transmitted Infections (STI). More importantly, the order the contacts are made creates heterogeneity in the contacts sequence and restricts the possible paths for an infection to propagate in the population. This temporal constrain has not been much explored but has several consequences for dynamics on the network, for example, it results in larger outbreaks and increases the diversity of outbreak sizes. In this talk, I will first introduce a large empirical dynamic network of sexual contacts, obtained from a web community related to sexual encounters between sex-buyers and -sellers in Brazil. Afterwards, I present some results about the simulation of general STIs on this evolving network and discuss how the infection patterns change due to not only the temporal constrain but also to other network properties, as the cluster structures.

Speaker: Luis Enrique Correa da Rocha (IceLab, Umeå University)