Complex network

Summary

In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in networks representing real systems. The study of complex networks is a young and active area of scientific research (since 2000) inspired largely by empirical findings of real-world networks such as computer networks, biological networks, technological networks, brain networks, climate networks and social networks. Definition Most social, biological, and technological networks display substantial non-trivial topological features, with patterns of connection between their elements that are neither purely regular nor purely random. Such features include a heavy tail in the degree distribution, a high clustering coefficient, assortativity or disassortativity among vertices, community structure, and hierarchical structure. In the case of directed networks these featu

Official source

https://en.wikipedia.org/wiki/Complex_network

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (86)

Related publications

Related people (11)

, , , , , , , , ,

Related people

Related units (8)

Related units

Related concepts (26)

Related concepts

Related courses (9)

Related courses

Related lectures (12)

Related lectures

A complex networks approach to traffic flow theory: measures and models

Leonardo Bellocchi

In this thesis, we developed a research direction that combines the theoretical concepts of complex networks with practical needs and applications in the field of transportation engineering. As a first objective we analyzed the phenomenon of congestion propagation in a city trying to synthesize - hence reproduce - dynamical systems of complex nature in a well-established and elegant mathematical-physical structure. With this perspective, we identified in the reaction-diffusion-like system the most natural way to describe how congestion spreads in the road networks according to elementary diffusion mechanics (linear) and self-enhancement of traffic jam (non-linear). This analysis showed that models with a small number of parameters can reproduce dynamic network patterns without the need for very detailed and accurate input data. Another topic we dealt with was to indicate centrality measures expressively defined for congested road networks. Inspired by classical complex networks theory, we defined more suitable and exploitable indices in the field of transport and urban mobility that consider in a dynamic framework both the network topology and the spatial distribution and magnitude of congestion. For this scope, we proposed the definition of dynamical efficiency for single and multi-layer networks. Dynamical efficiency responds adequately to the need for classification of urban areas based on their accessibility and on the influence that traffic has, region-par-region, on the average travel time of passengers. This measure combines and exploits local information (average road speeds, functional type) with the complex structure of the road network and the opportunity for convenient alternative routes. Furthermore, by generalizing the dynamical efficiency definition in a multimodal environment, we are able to identify the most attractive intermodal exchange stations (for example, bus-metro, private car-public transport) and estimate their optimal capacity service. This opens up the workspace for innumerable engineering applications and accurate evaluations of the impact of high traffic demand in each transport system. Among the same lines, another chapter of this thesis concerns a measure of simplicity for paths and allows us to study an extended database of real trajectories and classify the drivers according to their priority path choice factors. Finally, we studied the congestion propagation under a topological perspective as an aggregation of connected components of congested links. By analyzing the distribution of their sizes and the average merging rate we are be able to (i) point out important premonitory signals that anticipate imminent traffic jam (namely morning and evening peak-hours), (ii) to visualize the most critical bottlenecks and (iii) to better understand the causal inference between components of congestion and the average network speed.

EPFL2020

Coupled dynamical systems are omnipresent in everyday life. In general, interactions between individual elements composing the system are captured by complex networks. The latter greatly impact the way coupled systems are functioning and evolving in time. An important task in such a context, is to identify the most fragile components of a system in a fast and efficient manner. It is also highly desirable to have bounds on the amplitude and duration of perturbations that could potentially drive the system through a transition from one equi- librium to another. A paradigmatic model of coupled dynamical system is that of oscillatory networks. In these systems, a phenomenon known as synchronization where the individual elements start to behave coherently may occur if couplings are strong enough. We propose frameworks to assess vulnerabilities of such synchronous states to external perturbations. We consider transient excursions for both small-signal response and larger perturbations that can potentially drive the system out of its initial basin of attraction. In the first part of this thesis, we investigate the robustness of complex network-coupled oscillators. We consider transient excursions following external perturbations. For ensemble averaged perturbations, quite remarkably we find that robustness of a network is given by a family of network descriptors that we called generalized Kirchhoff indices and which are defined from extensions of the resistance distance to arbitrary powers of the Laplacian matrix of the system. These indices allow an efficient and accurate assessment of the overall vulnera- bility of an oscillatory network and can be used to compare robustness of different networks. Moreover, a network can be made more robust by minimizing its Kirchhoff indices. Then for specific local perturbations, we show that local vulnerabilities are captured by generalized resistance centralities also defined from extensions of the resistance distance. Most fragile nodes are therefore identified as the least central according to resistance centralities. Based on the latter, rankings of the nodes from most to least vulnerable can be established. In summary, we find that both local vulnerabilities and global robustness are accurately evaluated with resistance centralities and Kirchhoff indices. Moreover, the framework that we define is rather general and may be useful to analyze other coupled dynamical systems. In the second part, we focus on the effect of larger perturbations that eventually lead the sys- tem to an escape from its initial basin of attraction. We consider coupled oscillators subjected to noise with various amplitudes and correlation in time. To predict desynchronization and transitions between synchronous states, we propose a simple heuristic criterion based on the distance between the initial stable fixed point and the closest saddle point. Surprisingly, we find numerically that our criterion leads to rather accurate estimates for the survival probability and first escape time. Our criterion is general and may be applied to other dynamical systems.

EPFL2020

Robustness of Synchrony in Complex Networks and Generalized Kirchhoff Indices

2018

A complex networks approach to traffic flow theory: measures and models

Leonardo Bellocchi

EPFL2020