Following the series of book summaries, student notes to papers and analysis related to Network Science posted in this blog, all of them easy to reach using the
network science label, I focus this time on a classical survey paper titled
"
Complex networks: Structure and dynamics" by S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.-U. Hwang.
This is a paper with over 100 pages and 888 references. The summary approach I follow this time is different. After having read and highlighted the paper, I literally copy here those statements that could be considered a non-complete summary of the paper. Network science students could find it useful as an initial reference to later on dive deep into the
entire paper.
1. Intro
- Networks: systems composed by a large number of highly interconnected dynamical units.
- The first approach to capture the global properties of such systems is to model them as graphs whose nodes represent the dynamical units, and whose links stand for the interactions between them.
- A relevant property regards the degree of a node, that is the number of its direct connections to other nodes. In real networks, the degree distribution P (k), defined as the probability that a node chosen uniformly at random has degree k or, equivalently, as the fraction of nodes in the graph having degree k, significantly deviates from the Poisson distribution expected for a random graph and, in many cases, exhibits a power law (scale-free) tail with an exponent taking a value between 2 and 3.
- real networks are characterized by correlations in the node degrees, by having relatively short paths between any two nodes (small-world property), and by the presence of a large number of short cycles or specific motifs.
- coupling architecture has important consequences on the network functional
robustness and response to external perturbations, as random failures, or targeted attacks.
- how the network structure affects the properties of a networked dynamical
system
- some brain diseases are the result of an abnormal and, some times, abrupt synchronization of a large number of neural populations
- finding the communities within a network is a powerful tool for understanding the functioning of the network, as well as for identifying a hierarchy of connections within a complex architecture
2. Structure
- The walk of minimal length between two nodes is known as shortest path or
geodesic. A cycle is a closed walk, of at least three nodes, in which no edge is repeated.
- A component of the graph is a maximally connected induced subgraph. A giant
component is a component whose size is of the same order as N.
- The degree (or connectivity) k i of a node i is the number of edges incident with the node.
- in assortative networks the nodes tend to connect to their connectivity peers, while in disassortative networks nodes with low degree are more likely connected with highly connected ones
- The concept of betweenness can be extended also to the edges. The edge betweenness is defined as the number of shortest paths between pairs of nodes that run through that edge
- transitivity means the presence of a high number of triangles
- An alternative possibility is to use the graph clustering coefficient C
- A motif M is a pattern of interconnections
- a community (or cluster, or cohesive subgroup) is a subgraph G (N , L ), whose nodes are tightly connected, i.e. cohesive
- The spectrum of a graph is the set of eigenvalues of its adjacency matrix
- The eigenvalues and eigenvectors of A, and N have been used to characterize either models and real networks, and also for discovering the presence of cohesive subgroups
- despite the inherent differences, most of the real networks are characterized by the same topological properties, as for instance relatively small characteristic path lengths, high clustering coefficients, fat tailed shapes in the degree distributions, degree correlations, and the presence of motifs and community structures
- in most of the real networks, despite of their often large size, there is a relatively short path between any two nodes. This feature is known as the small-world property
- when
the scientists approached the study of real networks from the available databases, it was considered reasonable to find degree distributions localized around an average value, with a well-defined average of quadratic fluctuations. In contrast with all the expectancies, it was found that most of the real networks display power law shaped degree distribution
- Such networks have been named scale-free networks [2,93], because power-laws have the property of having the same functional form at all scales
- ER random graphs are the best studied among graph models, although they do not reproduce most of the properties of real networks
- the degree distribution is well approximated by a Poisson distribution
- The Watts and Strogatz (WS) model is a method to construct graphshaving both the small-world property and a high clustering coefficient
- Graphs with a power-law degree distribution can be simply obtained as a special case of the random graphs with a given degree distribution. We denote such graphs as static scale-free to distinguish them from models of evolving graphs
- Static scale-free graphs are good models for all cases in which growth or aging processes do not play a dominant role in determining the structural properties of the network
- The Barabási–Albert (BA) model is a model of network growth inspired to the formation of the World Wide Web and is based on two basic ingredients: growth and preferential attachment
- The BA model does not allow for changes after the network is formed. However, in real networks like the WWW or a social network, connections can be lost and added. Albert and Barabási (AB) have proposed a generalization of
their original model
- Here we present some of the most striking examples of real systems which have been studied as weighted networks. It has been found that the weights characterizing the various connections exhibit complex statistical features with highly varying distributions and power-law behaviors. Correlations between weights and topology provide a complementary perspective on the structural organization of such systems. Biological, social and technological networks.
- The easiest way to construct a weighted network is by considering a random graph with a given probability distribution P (k), and by assuming that the weights of the edges are random independent variables, distributed according to a weight distribution Q(w)
- Spatial networks: A particular class of networks are those embedded in the real space, i.e. networks whose nodes occupy a precise position in two or three-dimensional Euclidean space, and whose edges are real physical connections. The typical example are neural networks
- networks with strong geographical constraints are not small worlds
- example that power law degree distributions do not necessarily imply the small-world behavior
- random immunization in presence of geographical clustering might be more successful in controlling human epidemics than previously believed
- the structure of the world-wide airport network, finding empirical evidences
that both degree and betweenness distributions decay as truncated power laws
3. Static and dynamic robustness
- Robustness refers to the ability of a network to avoid malfunctioning when a fraction of its constituents is damaged. This is a topic of obvious practical reasons
- static robustness, is meant as the act of deleting nodes without the need of redistributing any quantity
- dynamical robustness refers to the case in which the dynamics of redistribution of flows should be taken into account
- The two types of robustness are similar in spirit, but while the first can be analytically treated, e.g. by using the tools of statistical physics such as percolation theory, the analytical treatment of the second case is harder and in almost all cases one has to rely on numerical simulations.
- The study of random failures in complex networks can be exactly mapped into a standard percolation problem
- the response to attacks of the scale-free network is similar to the response to attacks and failures of the random graph network
- The numerical results indicate that both the global and the local efficiency of scale-free networks are unaffected by the removal of some (up to 2%) of the nodes chosen at random. On the other hand, at variance with random graphs, global and local efficiencies rapidly decrease when the nodes removed are those with the higher connectivity
- The conclusion that follows immediately is that any graph with a finite amount of random mixing of edges for which the second moment diverges does not have a percolation threshold
- targeted deletion of nodes in uncorrelated scale-free networks are highly effective if compared to random breakdown, as previously anticipated by the numerical simulations by Albert et al. [275]. This is due to the critical high degree of just a few vertices whose removal disrupts the whole network. On the other hand, tolerance to attacks in correlated networks is still a problem entirely to be explored. This is due in part to the lack of generic models that produce networks with arbitrary degree-degree correlations
- in order to prevent the breakdown of scale-free networks, one has to find an optimal criterion that takes into account two factors: the robustness of the system itself under repeated failures, and the possibility of knowing in advance that the collapse of the system is approaching
- cascading failures occur much easier in small-world and scale-free networks than in global coupling networks
- an appropriate randomness in path selection can shift the onset of traffic congestion, allowing to accommodate more packets in the network
4. Spreading processes
- Epidemic spreading vs rumour spreading
- epidemiological processes can be regarded as percolation like processes
- the long term maintenance of the infection in a closed population is impossible in the SIR model, due to the depletion of susceptibles, as the epidemic spread through the population
- in both models the spread of infections is tremendously strengthened on scale-free networks. For such a reason, here we shall mainly concentrate on the SIR model
- Heterogeneous graphs with highly skewed degree distributions are particularly important to describe real transmission networks. For example, in the case of sexual contacts, which are responsible for the diffusion of sexually transmitted
diseases, the degree distribution has been found to follow a power-law
- a targeted immunization based on the node connectivity can restore a finite
epidemic threshold and potentially eradicate a virus. This result gives also important indications on the best public health strategies to adopt in order to control and eradicate sexually transmitted diseases (as the HIV). The real
problem here is that sexual promiscuous individuals are not always easy to identify
- vaccination of random acquaintances of random chosen individuals. This strategy is based on the fact that the probability of reaching a particular node by following a randomly chosen edge is proportional to the nodes degree
- structured scale-free networks do not possess the small-world property
- the diseases are longest lived in assortative networks
- desirable to spread the “epidemic” (the rumour) as fast and as efficiently as possible
- The standard rumor model is the so-called DK model
- denoted by ignorant (I), spreader (S) and stifler (R) nodes
- there is no “rumor threshold”, contrarily to the case of epidemic spreading.
The difference does not come from any difference in the growth mechanism of s(t)—the two are actually the same—,but from the disparate rules for the decay of the spreading process
- contrary to epidemic modelling, rumor processes can be tailored depending on the specific application. In this respect, there are still many issues to be addressed such as the influence of correlations, and dynamical rewiring. But we already know that even for a very poorly designed rumor, the final fraction of stiflers is finite at variance with epidemiological models
5. Synchronisation and collective dynamics
- Synchronization is a process wherein many systems (either equivalent or non-equivalent) adjust a given property of their motion due to a suitable coupling configuration, or to an external forcing
- We start with discussing the so called Master Stability Function approach
- Master stability function arguments are currently used as a challenging framework for the study of synchronized behaviors in complex networks, especially for understanding the interplay between complexity in the overall topology and local dynamical properties of the coupled units
- where a weighting in the connections has relevant consequences in
determining the network’s dynamics
- asymmetry in the coupling was shown to play a fundamental role in connection with synchronization of coupled spatially extended fields
- conveying the global complex structure of shortest paths into a weighting procedure gives in that range a better criterion for synchronization than solely relying on the local information around a node
- asymmetry here deteriorates the network propensity for synchronization
- which are the essential topological ingredients enhancing synchronization in weighted networks? The answer is that only the simultaneous action of many ingredients provide the best conditions for synchronization
- The first ingredient is that the weighting must induce a dominant interaction from hub to non-hub nodes
- A second fundamental ingredient is that the network contains a structure of connected hubs influencing the other nodes
- the need of a dominant interaction from hubs to non-hubs for improving synchronization, also for highly homogeneous networks
- weighted networks is the most promising framework for the study of how the architectural properties of the connection wiring influence the efficiency and robustness of the networked system in giving rise to a synchronized behavior
- the coupling strength at which the transition occurs is determined by
the largest eigenvalue of the adjacency matrix
- the ability of a given network to synchronize is strongly ruled by the structure of connections
- some studies suggested that small-world wirings always lead to enhance synchronization as compared with regular topologies
6. Applications
- the larger is the clustering coefficient, the easier the development of the consensus takes place
- the role of complex topologies in opinion dynamics is still to be better investigated
- network structure can be as important as the game rules in order to maintain
cooperative regimes
- the Internet has a relatively high clustering coefficient, about 100 times larger than that of a ER random graph with the same size. Interestingly, the clustering properties increase with time. Moreover, the clustering coefficient is a power-law decaying function of the degree
- Finally, the betweenness distributions follow a power-law
- For the data mining in WWW, it is necessary to estimate the accuracy and
valueness of such information. Interestingly, in the commercial search engine Google such estimation is performed by the so called “page rank” measurements
- it is expected that the large-scale network approach may lead to new insights on various longstanding questions on life, such as robustness to external perturbations, adaptation to external circumstances, and even hidden underlying design principles of evolution
- Similarly to metabolic networks, scale-free properties, high-clustering and small-world properties with hierarchical modularity and robustness against random attacks were observed in protein–protein interaction networks
- argued that the
biological functional organization and the spatial cellular organization are correlated significantly with the topology of the network, by comparing the connectivity structure with that of randomized networks
- Protein crystallography reveals that the fundamental unit of the protein structure is the domain
- Up to now, we have presented evidences supporting that scale-free distributions, small-world, and high clustering seem to be universal properties of cellular networks
- One of the basic properties of scale-free networks is the existence of hub nodes
- The scale-freeness property of a network might indicate growing and
preferential attachment as evolutionary principles that led to the formation of the network as we know it nowadays
- Suppressing a link between highly connected proteins and favoring links between highly connected and low-connected pairs of proteins decreases the likelihood of cross talks between different functional modules of the cell, and increases the overall robustness of the network against localized effects of deleterious perturbations. This feature (combined with scale-free and small-world property) is considered nowadays a key property to explain biological robustness
- Each network motif appears to carry out a specific dynamical function in the network, as it has been experimentally and theoretically demonstrated
- the brain organization is ruled by optimizing principles of resource allocation and constraint minimization
- This plasticity renders neurons able to continuously change connections, or establish new ones according to the computational and communication needs
- The literature usually refers to three different types of connectivity: neuroanatomical, functional and effective
- the description of neural system may be improved by using weighted networks
- Within the framework of learning of artificial neural networks, it has recently been shown that a small-world connectivity may yield a learning error and learning time lower than those obtained with random or regular connectivity patterns
- Some brain diseases, as epilepsy, are the result of an abnormal and, some times, abrupt synchronization of a large number of neural populations
- Many open questions e.g. the presence of motifs is a relevant feature in the structure of cortical networks. However, the role of motifs in brain dynamics remain unclear
- learning could induce changes in the wiring scheme
- Synchronization has been found to be enhanced by a small-world wiring structure. This finding has suggested a plausible paradigm to explain the emergence of some neural phenomena as epileptic seizures, characterized by
a sudden and strong synchronization. Unfortunately, there is presently no conceptual or computational works to understand the role of connectivity in the control of these synchronized states
7. Other topics
- finding the communities within a network is a powerful tool for understanding the structure and the functioning of the network, and its growth mechanisms
- spectral graph partitioning
- A class of algorithms that work much better when there is no prior knowledge on the number of communities is the hierarchical clustering analysis used in social networks analysis
- a series of algorithms based on the idea of iteratively removing edges with high
centrality score have been proposed. Such methods use different measures of edge centrality, as the random-walk betweenness, the current-flow betweenness
- fast method based on modularity
- The study of the eigenvector associated with the second smallest eigenvalue is of practical use only when a clear partition into two parts exists, which is rarely the case
- other algorithms use voltage drops, the graph is considered an electric circuit
- The ability to navigate and search for shortest paths in a network without knowledge on its whole topological structure is a relevant issue, not only in
social systems, but also in optimization of information finding from the World Wide Web, traffic way-finding in a city, transport of information packets on the Internet, or diffusion of signaling molecules in a biological cell
- Analytical and numerical results show that the information does not distribute
uniformly in heterogeneous networks
- Since in a highly heterogeneous network, as the Internet, the highest-degree nodes are connected to a significant fraction of all nodes in the network,
the agent need only a few steps to find a node that is a neighbor of the target q
- This means that in the small world regime, the average search time increases very slowly with the network size, in comparison with regular and random networks, and also with respect to a strategy based on random walk
- For a single search problem the optimal network is clearly a highly polarized starlike structure. This structure is indeed very simple and efficient in terms of searchability, since the average number of steps to find a given node is always bounded, independently of the size of the system. However, the polarized starlike structure becomes inefficient when many search processes coexist in the network, due to the limited capacity of the central node
- This means that only two classes of networks can be considered as optimal: starlike configurations when the number of parallel searches is small, or homogeneous configurations when the number of parallel searches is large.
- agents making use of local information of the net topology are more efficient in such dynamical environment than agents making use of the global information, thus suggesting that this can explain what occurs in multi-agent systems for the processes of allocation of distributed resources
- Finally, for high densities and small noises, the motion of walkers becomes ordered on the same scale of the system size, and all walkers move in the same spontaneously chosen direction
 |
| Networking |
