Simplifying complex networks | EPFL Graph Search

The framework of complex networks has been shown to describe adequately a wide class of complex systems made up of a large number of interacting units. In this framework, a node is associated to each unit and two nodes are connected by an edge if the two units interact with each other. Examples of such systems can be found in living organisms—the map of interactions between proteins or the network of neurons in the brain. Moreover, artificial systems such as the WWW, electrical grids or airplane connections have been studied using the tools of complex networks. Finally networks have found many applications in social sciences to characterize for instance human interactions of different kinds underlying the spreading of an epidemic. For most of these systems, the complexity arises because of the large number of units and their intricate connection patterns. A natural approach is therefore to simplify the systems by decreasing their size. Different schemes can indeed be designed for each particular system, leading to effective but case-dependent methods. From a more global and statistical perspective, a promising alternative is to reduce the complexity of the corresponding networks. In order to simplify complex networks, two strategies are presented in this Thesis. The first approach refers to the well-known clustering paradigm. It aims at identifying groups of nodes densely connected between each other and much less to the rest of the network. Those groups are referred to as clusters or communities. For most real systems, nodes within a community share some similarity or common feature. For instance, in a synonymy network where nodes are words and edges connect synonymous words, we have shown that finding communities allowed us to identify words corresponding to a single concept. We have also studied a network describing the dynamics of a peptide by associating a node to a microscopic configuration and an edge to a transition. The community structure of the network was shown to provide a new methodology to explore the main characteristics of the peptide dynamics and to unravel the large-scale features of the underlying free-energy landscape. Finally we have designed a new technique to probe the robustness of the community structure against external perturbations of the network topology. This method allows us, among else, to assess whether communities correspond to a real structure of the network, or are simple artifacts of the clustering algorithms. Community detection techniques have found a large number of practical applications as a method to simplify networks since the number of clusters is often much smaller than the number of nodes. However, a crucial issue has often been disregarded: is the network of clusters truly representative of the initial one? In this Thesis, we show that this is indeed not verified for most networks. For example we have considered the evolution of random walks on the network of clusters and found that it behaves quite differently than in the initial network. This observation led us to develop a new strategy to simplify complex networks, ensuring that the reduced network is representative of the initial one. It is based on the idea of grouping nodes, akin to community detection. However, the aim is no longer to identify the "correct" clusters, but to find a smaller network which preserves the relevant features of the initial one, and especially the spectral properties. We therefore refer to our method as Spectral Coarse Graining, by analogy with the coarse graining framework used in Statistical Physics. Applying this method to various kinds of networks, we have shown that the coarse-grained network provides an excellent approximation of the initial one, while the size could be easily reduced by a factor of ten. Therefore, the Spectral Coarse Graining provides a well-defined way of studying large networks and their dynamics considering a much smaller coarse-grained version. Overall, we first discuss the use and the limits of the usual clustering approach to reduce the complexity of networks, and apply it to several real-world systems. In a second part, we develop a new coarse graining strategy to approximate large networks by smaller ones and provide several examples to illustrate the power and the novelty of the method.

Realtime Face Tracking and Animation

Sofien Bouaziz

Capturing and processing human geometry, appearance, and motion is at the core of computer graphics, computer vision, and human-computer interaction. The high complexity of human geometry and motion dynamics, and the high sensitivity of the human visual system to variations and subtleties in faces and bodies make the 3D acquisition and reconstruction of humans in motion a challenging task. Digital humans are often created through a combination of 3D scanning, appearance acquisition, and motion capture, leading to stunning results in recent feature films. However, these methods typically require complex acquisition systems and substantial manual post-processing. As a result, creating and animating high-quality digital avatars entails long turn-around times and substantial production costs. Recent technological advances in RGB-D devices, such as Microsoft Kinect, brought new hopes for realtime, portable, and affordable systems allowing to capture facial expressions as well as hand and body motions. RGB-D devices typically capture an image and a depth map. This permits to formulate the motion tracking problem as a 2D/3D non-rigid registration of a deformable model to the input data. We introduce a novel face tracking algorithm that combines geometry and texture registration with pre-recorded animation priors in a single optimization. This led to unprecedented face tracking quality on a low cost consumer level device. The main drawback of this approach in the context of consumer applications is the need for an offline user-specific training. Robust and efficient tracking is achieved by building an accurate 3D expression model of the user's face who is scanned in a predefined set of facial expressions. We extended this approach removing the need of a user-specific training or calibration, or any other form of manual assistance, by modeling online a 3D user-specific dynamic face model. In complement of a realtime face tracking and modeling algorithm, we developed a novel system for animation retargeting that allows learning a high-quality mapping between motion capture data and arbitrary target characters. We addressed one of the main challenges of existing example-based retargeting methods, the need for a large number of accurate training examples to define the correspondence between source and target expression spaces. We showed that this number can be significantly reduced by leveraging the information contained in unlabeled data, i.e. facial expressions in the source or target space without corresponding poses. Finally, we present a novel realtime physics-based animation technique allowing to simulate a large range of deformable materials such as fat, flesh, hair, or muscles. This approach could be used to produce more lifelike animations by enhancing the animated avatars with secondary effects. We believe that the realtime face tracking and animation pipeline presented in this thesis has the potential to inspire numerous future research in the area of computer-generated animation. Already, several ideas presented in thesis have been successfully used in industry and this work gave birth to the startup company faceshift AG.

EPFL2015

Cities, from Information to Interaction

João Vitor Meirelles de Miranda

From physics to the social sciences, information is now seen as a fundamental component of reality. However, a form of information seems still underestimated, perhaps precisely because it is so pervasive that we take it for granted: the information encoded in the very environment we live in. We still do not fully understand how information takes the form of cities, and how our minds deal with it in order to learn about the world, make daily decisions, and take part in the complex system of interactions we create as we live together. This paper addresses three related problems that need to be solved if we are to understand the role of environmental information: (1) the physical problem: how can we preserve information in the built environment? (2) The semantic problem: how do we make environmental information meaningful? and (3) the pragmatic problem: how do we use environmental information in our daily lives? Attempting to devise a solution to these problems, we introduce a three-layered model of information in cities, namely environmental information in physical space, environmental information in semantic space, and the information enacted by interacting agents. We propose forms of estimating entropy in these different layers, and apply these measures to emblematic urban cases and simulated scenarios. Our results suggest that ordered spatial structures and diverse land use patterns encode information, and that aspects of physical and semantic information affect coordination in interaction systems.

2018

Comparing Dynamics: Deep Neural Networks versus Glassy Systems

Mario Geiger, Levent Dogus Sagun, Stefano Spigler, Rainer Wesche

We analyze numerically the training dynamics of deep neural networks (DNN) by using methods developed in statistical physics of glassy systems. The two main issues we address are the complexity of the loss-landscape and of the dynamics within it, and to what extent DNNs share similarities with glassy systems. Our findings, obtained for different architectures and data-sets, suggest that during the training process the dynamics slows down because of an increasingly large number of flat directions. At large times, when the loss is approaching zero, the system diffuses at the bottom of the landscape. Despite some similarities with the dynamics of mean-field glassy systems, in particular, the absence of barrier crossing, we find distinctive dynamical behaviors in the two cases, thus showing that the statistical properties of the corresponding loss and energy landscapes are different. In contrast, when the network is under-parametrized we observe a typical glassy behavior, thus suggesting the existence of different phases depending on whether the network is under-parametrized or over-parametrized.

2018

Realtime Face Tracking and Animation

Sofien Bouaziz

EPFL2015